Интервалы
Число называется хорошим, если оно состоит из хороших цифр.
Дано n интервалов [l[i], r[i]] и множество цифр, которые считаются хорошими. Сколько существует способов выбрать по одному числу из каждого интервала таким образом, чтобы их сумма была хорошим числом. Можно выбрать одно и то же число из нескольких интервалов. Два варианта выбора считаются различными, если существует такое число i (1 ≤ i ≤ n), что из интервала i выбраны различные числа. Ответ может быть большим, поэтому ответ следует вывести по модулю 10^9 + 7.
Входные данные
Первая строка содержит десять целых чисел: i-ое число равно 1, если цифра i хорошая и 0 иначе. Эти числа пронумерованы с 0 до 9. Следующая строка содержит количество интервалов n (1 ≤ n ≤ 7). Каждая из следующих n строк содержит два целых числа без ведущих нулей: l[i] и r[i] (0 ≤ l[i] ≤ r[i] < 10^10).
Выходные данные
Вывести количество способов по модулю 10^9 + 7.