Інтервали
Число називається хорошим, якщо воно складається з хороших цифр.
Дано 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.