Migrated from Lutece 2393 耀西藏蛋

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

耀西下了很多的恐龙蛋，但是它很担心闸种桀哥把它的蛋给偷走了，他决定把蛋给分散地藏在蘑菇王国的各地。

我们把蘑菇王国划分为 $n$ 行 $m$ 列的区域，耀西藏蛋决定遵循以下几条规则：

1. 对于每一列来说，这一列区域中藏有的恐龙蛋最多不超过一个
2. 对于第 $i$ 行，从左往右的前 $a_i$ 个区域里恰好一共藏了一个蛋。
3. 对于第 $i$ 行，从右往左的前 $b_i$ 个区域里恰好一共藏了一个蛋。

这里保证 $a_i + b_i \leq m$，即两个区间不会相交。

问在满足上述条件的情况下耀西总共有几种不同的藏法。输出藏法的个数对 $10^9 + 7$ 取模的结果。

Input

第一行输入两个数，$n$ 和 $m$ ( $1 \leq n \leq 100,~ 1 \leq m \leq 300$)

接下来有 $n$ 行，每行两个数字，分别代表 $a_i$ 和 $b_i$ 。( $1 \leq a_i,~b_i \leq m$ 且 $1 \leq a_i + b_i \leq m$ ）

Output

一个整数，代表对 $10^9+7$ 取模的结果。

Samples

2 4
1 2
2 1

1

3 7
1 3
2 2
3 1

4

Resources

2020 UESTC ICPC Training for Dynamic Programming