Byteland 有 n 种硬币。方便地,硬币类型k的面额除以硬币类型k的面额+1,硬币类型1的面额等于1图格里克。硬币类型k+1和k的面额之比等于ak。已知对于每个x,最多有20种面额x的硬币。
Byteasar 身上有 bk 个类型为 k 的币,他需要支付正好 m 个图格里克。据了解,Byteasar 身上从来没有超过 3·105 个币。 Byteasar 想知道有多少种方式可以准确支付 m 个图格里克。如果存在整数k,使得这两种方式中类型k的硬币数量不同,则两种方式是不同的。作为所有 Byteland 公民,Byteasar 想知道模 109 + 7 的路数。
输入
第一行包含单个整数 n (1 ≤ n ≤ 3·105) — 硬币类型的数量。
第二行包含 n - 1 个整数 a1, a2, ..., an - 1 (1 ≤ ak ≤ 109) - 硬币类型面额之间的比率。保证对于每个 x 最多有 20 种面额 x 的硬币。
第三行包含 n 个非负整数 b1, b2, ..., bn — Byteasar 每种类型的代币数量。保证这些整数之和不超过3·105。
第四行包含单个整数 m (0 ≤ m < 1010000) — Byteasar 需要支付的 tugricks 金额。
输出
打印单个整数 — 支付 m tugricks 模 109 + 7 的方式数量。
示例
输入 #1
1 4 2
输出 #1
1
输入 #2
2 1 4 4 2
输出 #2
3
输入 #3
3 3 3 10 10 10 17
输出 #3
6
注意
在第一个例子中,Byteasar 有 4 个面额为 1 的硬币,他必须支付 2 个图格里克。只有一种方法。
在第二个示例中,Byteasar 有 4 个不同类型面额的硬币 1,他必须支付 2 个 tugricks。有3种方式:支付一个第一种硬币和一个另一种硬币,支付两个第一种硬币,支付两个第二种硬币。
在第三个示例中,面额等于 1、3、9。