该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【超长篇！一篇文章讲懂生成函数！】【那些你可能忘记了的算法5】生成函数&例题&卷积-CSDN博客看不懂来找hansang

【题意】做完本题，对比2025

有 $n$ 种水果，每种水果选购个数在 $[a_i,b_i]$ 之间，问买 $m$ 个水果有多少种方案？

【输入格式】

本题目包含多组测试，请处理到文件结束(EOF)。

每组测试第一行包括两个正整数 $n$ 和 $m$ ($1 \le n \le 1000$，$1 \le m \le 2000$)

接下来有n行水果的信息，每行两个整数 $a_i,b_i(0 \le a_i \le b_i \le 100)$，表示至少要买该水果 $a_i$ 个，至多只能买该水果 $b_i$ 个。

【输出格式】

对于每组测试，在一行里输出总共能够卖的方案数。

答案对 $2^{64}$ 取模。（可以使用 unsigned long long 自然溢出实现）

2 3
1 2
1 2
3 5
0 3
0 3
0 3

2
12