E. Byteland coins

在比特兰，有 #cf_span[n] 种硬币。方便起见，第 #cf_span[k] 种硬币的面值整除第 #cf_span[k + 1] 种硬币的面值，第 #cf_span[1] 种硬币的面值等于 #cf_span[1] 图格里克。第 #cf_span[k + 1] 种硬币与第 #cf_span[k] 种硬币的面值之比为 #cf_span[ak]。已知对于每个 #cf_span[x]，面值为 #cf_span[x] 的硬币种类至多有 *20* 种。 Byteasar 手中有 #cf_span[bk] 枚第 #cf_span[k] 种硬币，他需要恰好支付 #cf_span[m] 图格里克。已知 Byteasar 手中的硬币总数不超过 #cf_span[3·105] 枚。Byteasar 想知道有多少种方式可以恰好支付 #cf_span[m] 图格里克。两种方式不同，当且仅当存在某个整数 #cf_span[k]，使得在这两种方式中第 #cf_span[k] 种硬币的数量不同。作为所有比特兰公民，Byteasar 想知道结果对 #cf_span[109 + 7] 取模的值。 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3·105]) —— 硬币种类数。 第二行包含 #cf_span[n - 1] 个整数 #cf_span[a1], #cf_span[a2], #cf_span[...], #cf_span[an - 1] (#cf_span[1 ≤ ak ≤ 109]) —— 硬币面值的比率。保证对于每个 #cf_span[x]，面值为 #cf_span[x] 的硬币种类至多有 *20* 种。 第三行包含 #cf_span[n] 个非负整数 #cf_span[b1], #cf_span[b2], #cf_span[...], #cf_span[bn] —— Byteasar 拥有的每种硬币的数量。保证这些整数的和不超过 #cf_span[3·105]。 第四行包含一个整数 #cf_span[m] (#cf_span[0 ≤ m < 1010000]) —— Byteasar 需要支付的图格里克金额。 请输出一个整数 —— 恰好支付 #cf_span[m] 图格里克的方式数，对 #cf_span[109 + 7] 取模。 在第一个例子中，Byteasar 有 #cf_span[4] 枚面值为 #cf_span[1] 的硬币，需要支付 #cf_span[2] 图格里克。只有一种方式。 在第二个例子中，Byteasar 有 #cf_span[4] 枚两种不同类型的面值为 #cf_span[1] 的硬币，需要支付 #cf_span[2] 图格里克。有 #cf_span[3] 种方式：支付一枚第一种硬币和一枚第二种硬币，支付两枚第一种硬币，或支付两枚第二种硬币。 在第三个例子中，面值分别为 #cf_span[1], #cf_span[3], #cf_span[9]。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3·105]) —— 硬币种类数。第二行包含 #cf_span[n - 1] 个整数 #cf_span[a1], #cf_span[a2], #cf_span[...], #cf_span[an - 1] (#cf_span[1 ≤ ak ≤ 109]) —— 硬币面值的比率。保证对于每个 #cf_span[x]，面值为 #cf_span[x] 的硬币种类至多有 *20* 种。第三行包含 #cf_span[n] 个非负整数 #cf_span[b1], #cf_span[b2], #cf_span[...], #cf_span[bn] —— Byteasar 拥有的每种硬币的数量。保证这些整数的和不超过 #cf_span[3·105]。第四行包含一个整数 #cf_span[m] (#cf_span[0 ≤ m < 1010000]) —— Byteasar 需要支付的图格里克金额。 ## Output 请输出一个整数 —— 恰好支付 #cf_span[m] 图格里克的方式数，对 #cf_span[109 + 7] 取模。 [samples] ## Note 在第一个例子中，Byteasar 有 #cf_span[4] 枚面值为 #cf_span[1] 的硬币，需要支付 #cf_span[2] 图格里克。只有一种方式。在第二个例子中，Byteasar 有 #cf_span[4] 枚两种不同类型的面值为 #cf_span[1] 的硬币，需要支付 #cf_span[2] 图格里克。有 #cf_span[3] 种方式：支付一枚第一种硬币和一枚第二种硬币，支付两枚第一种硬币，或支付两枚第二种硬币。在第三个例子中，面值分别为 #cf_span[1], #cf_span[3], #cf_span[9]。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of coin types. Let $ a_1, a_2, \dots, a_{n-1} \in \mathbb{Z}^+ $ be the denomination ratios, with $ a_k = \frac{d_{k+1}}{d_k} $, where $ d_k $ is the denomination of coin type $ k $. Let $ d_1 = 1 $, and $ d_k = \prod_{i=1}^{k-1} a_i $ for $ k \geq 2 $. Let $ b_k \in \mathbb{Z}_{\geq 0} $ be the number of coins of type $ k $ available, with $ \sum_{k=1}^n b_k \leq 3 \cdot 10^5 $. Let $ m \in \mathbb{Z}_{\geq 0} $ be the target amount in tugricks, with $ m < 10^{10000} $. **Constraints** 1. $ 1 \leq n \leq 3 \cdot 10^5 $ 2. $ 1 \leq a_k \leq 10^9 $ for all $ k \in \{1, \dots, n-1\} $ 3. $ b_k \geq 0 $ for all $ k \in \{1, \dots, n\} $, and $ \sum_{k=1}^n b_k \leq 3 \cdot 10^5 $ 4. For each distinct denomination $ x $, there are at most 20 coin types with $ d_k = x $. 5. $ m $ is given as a decimal string of up to $ 10000 $ digits. **Objective** Compute the number of integer solutions $ (x_1, x_2, \dots, x_n) $ such that: $$ \sum_{k=1}^n x_k d_k = m, \quad \text{with } 0 \leq x_k \leq b_k \text{ for all } k, $$ modulo $ 10^9 + 7 $.