Число называется хорошим, если оно состоит из хороших цифр.

Дано n интервалов [li, ri] и множество цифр, которые считаются хорошими. Сколько существует способов выбрать по одному числу из каждого интервала таким образом, чтобы их сумма была хорошим числом. Можно выбрать одно и то же число из нескольких интервалов. Два варианта выбора считаются различными, если существует такое число i (1 ≤ i ≤ n), что из интервала i выбраны различные числа. Ответ может быть большим, поэтому ответ следует вывести по модулю 109 + 7.

Входные данные

Первая строка содержит десять целых чисел: i-ое число равно 1, если цифра i хорошая и 0 иначе. Эти числа пронумерованы с 0 до 9. Следующая строка содержит количество интервалов n (1 ≤ n ≤ 7). Каждая из следующих n строк содержит два целых числа без ведущих нулей: li и ri (0 ≤ li ≤ ri < 1010).

Выходные данные

Вывести количество способов по модулю 109 + 7.