E. Байтландские монеты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Байтландии в ходу монеты n разных видов. Для удобства расчётов, достоинство монеты вида k обязательно делит достоинство монеты k + 1, а достоинство монеты вида 1 равно 1 тугрик. Отношение достоинств монет вида k + 1 и k равно ak. Также известно, что для любого x есть не более 20 видов монет, имеющих достоинство x.

У Байтазара с собой есть ровно bk монет вида k, и сейчас ему нужно заплатить ровно m тугриков. Также известно, что Байтазар не носит с собой более 3·105 монет. Байтазар хочет узнать, сколько у него есть способов заплатить m тугриков. Способы считаются различными, если для некоторого k в способах различается количество монет вида k. Как и всех в Байтландии, Байтазара количество способов интересует исключительно по модулю 109 + 7.

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

В первой строке записано одно целое число n (1 ≤ n ≤ 3·105) — число видов монет.

Во второй строке записано n - 1 целых чисел a1, a2, ..., an - 1 (1 ≤ ak ≤ 109) — отношения между достоинствами монет. Гарантируется, что для любого x есть не более 20 видов монет, имеющих достоинство x.

В третьей строке записано n неотрицательных целых чисел b1, b2, ..., bn — количество монет каждого вида, имеющихся у Байтазара. Гарантируется, что их сумма не превосходит 3·105.

В четвёртой строке записано одно целое число m (0 ≤ m < 1010000) — сумма в тугриках, которую Байтазар должен заплатить.

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

В единственной строке выведите одно число — количество способов заплатить ровно m тугриков по модулю 109 + 7.

Примеры
Входные данные
1

4
2
Выходные данные
1
Входные данные
2
1
4 4
2
Выходные данные
3
Входные данные
3
3 3
10 10 10
17
Выходные данные
6
Примечание

В первом примере у Байтазара есть 4 монеты достоинства 1, и нужно заплатить 2 тугрика. Способ единственен.

Во втором примере у Байтазара есть по 4 монеты двух различных видов достоинства 1, и нужно заплатить 2 тугрика. Теперь способов 3: заплатить одну монету первого вида, одну — второго, заплатить две монеты первого вида, или заплатить две монеты второго вида.

В третьем примере достоинства монет равны 1, 3, 9.