Background

小A是一个屑勇者，他很喜欢收集钞票。

Description

小A某天在商店看到了伊雷娜手办，他很想买下来。
已知手办价格为\(M\)元
小A有\(N\)种面值不同的钞票，第i种钞票面值为\(a_i\)元，数量为\(c_i\)张
现在小A想知道他有多少种不同支付的方法？
由于答案可能太大，所以只需要输出\( \bf 方案数 mod 100000007的结果 \rm \)
注意：面值相同的钞票之间没有任何差异

Format

Input

第一行两个整数\(N\)，\(M\)
第二行N个整数，\(a_1,a_2,...,a_N\)
第三行N个整数，\(c_1,c_2,...,c_N\)

Output

输出一个整数，表示支付的\( \bf 方案数 mod 100000007 \rm \)的结果

Sample 1

Input

3 5
1 2 5
3 2 1

Output

3

Limitation

4s, 512MB for each test case.
对于30%的数据，\( 1 \leq N \leq 100 \)，\( 1 \leq M \leq 1000 \)
对于100%的数据，\( 1 \leq N \leq 5000 \)，\( 1 \leq M \leq 10000 \)，\( 1 \leq a_i \leq 100 \)，\( 1 \leq c_i \leq 100 \)

Hint

样例的三种支付方法如下：
(1, 1, 1, 2)
(1, 2, 2)
(5)