有一条很长的数轴，一开始你在$0$的位置。接下来你要走$n$步，第$i$步你可以往右走$a_i$或者$b_i$。

问$n$步之后，到$m$位置，有多少种不同的走法。输出答案对$1000000007$取模的结果。

输入格式

第一行，两个整数$n, m$。

接下来$n$行，每行两个整数$a_i, b_i$。

输出格式

一行，一个数，表示答案。

输入样例

3 7
1 2
2 6
3 4

输出样例

2

数据规模

对于所有数据，保证$1\leq n\leq 100, 1\leq m\leq 10^5, 1\leq a_i,b_i\leq 1000, a_i\neq b_i$。