背景

Salamander 见到路边有如此多的毒瘤，于是见猎心喜，从家里拿来了一个大袋子，准备将一些毒瘤带回家。

题目描述

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

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

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

输入格式

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

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

输出格式

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

2 5
2 3
3 1

2

提示

样例解释：

两种方案如下：

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$。