Saturated Tumor Packing

You are given a bag with a maximum volume (m) and (n) different types of tumors. For each tumor type (i) ((1 \le i \le n)), there are (k_i) tumors available and each tumor of type (i) occupies (d_i) volume. You need to select some tumors (possibly none) so that the total volume does not exceed (m) and the bag is "saturated" in the following sense: for every type (i) for which you did not take all (k_i) tumors, the remaining bag capacity cannot accommodate a single extra tumor of that type. In other words, if you choose (x_i) tumors of type (i) (with (0 \le x_i \le k_i)) and let (S=\sum_{i=1}^{n} d_i,x_i) be the total volume used, then (S) must satisfy (S\le m) and for every (i) with (x_i<k_i) it holds that [ m - S < d_i. ]

Two selections are considered different if there exists at least one type (i) for which the number of tumors chosen differs. Calculate the number of different ways to choose tumors under these conditions. Since the answer might be very large, output it modulo (19260817).

inputFormat

The first line contains two integers \(n\) and \(m\) --- the number of tumor types and the maximum bag capacity, respectively.

Then \(n\) lines follow. The \(i\)-th line contains two integers \(k_i\) and \(d_i\) --- the number of tumors of type \(i\) and the volume occupied by each tumor of type \(i\), respectively.

outputFormat

Output a single integer, the number of valid tumor selection schemes modulo \(19260817\).

sample

2 10
3 3
2 5

1