G. МАТЕМАТNКА
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Если вы дошли до этой задачи, вы всё равно вряд ли станете читать легенду...

Вам дана бинарная строка и целое число . Найдите количество целых k, 0 ≤ k < N, таких что для всех i = 0, 1, ..., m - 1

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

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

В первой строке входного файла содержится строка s, состоящая из символов 0 и 1 (1 ≤ |s| ≤ 40).

В следующей строке содержится целое число n (1 ≤ n ≤ 5·105).

В каждой из следующих n строк содержатся два разделённых пробелом целых числа pi, αi (1 ≤ pi, αi ≤ 109, pi простое). Все pi различны.

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

Едиственное число — ответ на задачу.

Примеры
Входные данные
1
2
2 1
3 1
Выходные данные
2
Входные данные
01
2
3 2
5 1
Выходные данные
15
Входные данные
1011
1
3 1000000000
Выходные данные
411979884