Description

路边共有$n$种不同的毒瘤，第$i$种毒瘤有$k_i$个，每个需要占据$d_i$的空间。Salamander的袋子能装下的最大体积为$m$。

Salamander是一个很贪心的人，不过他也不要求带尽可能多或是总体积尽可能大的毒瘤回家，他只要求袋子里再也装不下剩余的任何一种毒瘤。

Salamander想知道有多少种不同的装毒瘤的方案。两种方案不同当且仅当取的毒瘤种类不同或者至少有一种毒瘤取的数量不同。由于方案数可能太多，请输出答案对$19260817$取模后的结果。

Input Format

第一行包括两个正整数$n$、$m$，表示毒瘤的种类数和袋子的大小。

接下来的$n$行，每行两个正整数$k_i$、$d_i$，表示一种毒瘤。

Output Format

一行，表示不同的方案数对$19260817$取模后的结果。

2 5
2 3
3 1

2

Hint

###样例解释：

两种方案如下：

1.取1个第一种毒瘤和2个第二种毒瘤。

2.取3个第二种毒瘤。

$~$ $~$

对于10%的数据，$1\leq n,k_i,d_i\leq 10$，$1\leq m\leq 100$；

对于30%的数据，$1\leq n,k_i,d_i\leq 50$，$1\leq m\leq 5000$；

对于另外20%的数据，$k_i=1$；

对于100%的数据，$1\leq n,k_i,d_i\leq 500$，$1\leq m\leq 10^5$。