CF756E.Byteland coins

There are n types of coins in Byteland. Conveniently, the denomination of the coin type k divides the denomination of the coin type k + 1, the denomination of the coin type 1 equals 1 tugrick. The ratio of the denominations of coin types k + 1 and k equals a__k. It is known that for each x there are at most 20 coin types of denomination x.

Byteasar has b__k coins of type k with him, and he needs to pay exactly m tugricks. It is known that Byteasar never has more than 3·105 coins with him. Byteasar want to know how many ways there are to pay exactly m tugricks. Two ways are different if there is an integer k such that the amount of coins of type k differs in these two ways. As all Byteland citizens, Byteasar wants to know the number of ways modulo 109 + 7.

Byteland 有 $n$ 种硬币。方便起见，第 $k$ 种硬币的面值整除第 $k+1$ 种硬币的面值，且第 $1$ 种硬币的面值为 $1$ 图格里克（tugrick）。第 $k+1$ 种与第 $k$ 种硬币的面值之比为 $a_k$。已知：对任意面值 $x$，面值恰为 $x$ 的硬币种类数至多为 $20$ 种。

Byteasar 身上携带了 $b_k$ 枚第 $k$ 种硬币，他需要恰好支付 $m$ 图格里克。已知 Byteasar 身上的硬币总数不超过 $3 \cdot 10^5$ 枚。Byteasar 想知道：恰好支付 $m$ 图格里克的方案数有多少种。若存在某个整数 $k$，使得两种方案中第 $k$ 种硬币的数量不同，则认为这两种方案不同。和所有 Byteland 公民一样，Byteasar 希望得到该方案数对 $10^9 + 7$ 取模的结果。

The first line contains single integer n (1 ≤ n ≤ 3·105) — the number of coin types.

The second line contains n - 1 integers _a_1, _a_2, ..., a__n - 1 (1 ≤ a__k ≤ 109) — the ratios between the coin types denominations. It is guaranteed that for each x there are at most 20 coin types of denomination x.

The third line contains n non-negative integers _b_1, _b_2, ..., b__n — the number of coins of each type Byteasar has. It is guaranteed that the sum of these integers doesn't exceed 3·105.

The fourth line contains single integer m (0 ≤ m < 1010000) — the amount in tugricks Byteasar needs to pay.

第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）—— 表示硬币种类的数量。

第二行包含 $n-1$ 个整数 $a_1, a_2, \dots, a_{n-1}$（$1 \leq a_k \leq 10^9$）—— 表示各硬币面额之间的比率。保证对任意 $x$，面额为 $x$ 的硬币种类至多有 $20$ 种。

第三行包含 $n$ 个非负整数 $b_1, b_2, \dots, b_n$ —— 表示 Byteasar 每种硬币的数量。保证这些整数之和不超过 $3 \cdot 10^5$。

第四行包含一个整数 $m$（$0 \leq m < 10^{10000}$）—— 表示 Byteasar 需要支付的金额（单位：图格里克）。

Print single integer — the number of ways to pay exactly m tugricks modulo 109 + 7.

输出一个整数——恰好支付 m 图格里克的方案数，对 $10^9 + 7$ 取模。

In the first example Byteasar has 4 coins of denomination 1, and he has to pay 2 tugricks. There is only one way.

In the second example Byteasar has 4 coins of each of two different types of denomination 1, he has to pay 2 tugricks. There are 3 ways: pay one coin of the first type and one coin of the other, pay two coins of the first type, and pay two coins of the second type.

In the third example the denominations are equal to 1, 3, 9.

在第一个例子中，Byteasar 有 4 枚面值为 1 的硬币，需要支付 2 图格里克（tugricks）。仅有一种支付方式。

在第二个例子中，Byteasar 每种面值为 1 的硬币各有 4 枚，共两种不同类型的硬币，需要支付 2 图格里克。共有 3 种支付方式：使用第一种类型硬币 1 枚和第二种类型硬币 1 枚；使用第一种类型硬币 2 枚；使用第二种类型硬币 2 枚。

在第三个例子中，硬币面值分别为 $1$、$3$、$9$。