eolymp
bolt
Try our new interface for solving problems
Məsələlər

Интервалы

Интервалы

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
1 1 1 1 1 1 1 1 1 1
2
4 6
15 19
Çıxış verilənləri #1
15
Giriş verilənləri #2
1 0 1 0 1 0 1 0 0 0
2
4 6
15 19
Çıxış verilənləri #2
7
Giriş verilənləri #3
1 0 0 1 1 1 1 1 1 1
2
4 6
15 19
Çıxış verilənləri #3
0
Mənbə 2013 Петрозаводск, Moscow SU ST + NNSU Contest, День 2, Август 24, Задача H