有一条很长的数轴,一开始你在$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$。