题目描述

有个 $n \times m$ 的棋盘，要往里面放棋子。

每行有两个参数 $left_i$ 和 $right_i$。任何一行的前 $left_i$ 个格子和后 $right_i$ 个格子必须恰好有 $1$ 个棋子且任何一列最多有 $1$ 个棋子。

求放置的总方案数模 $10^9+7$。

输入格式

第一行两个正整数 $n,m$。$(1\le n\le 50,1\le m\le 200)$

接下来 $n$ 行每行两个正整数 $left,right$。$(1\le left,right\le left+right\le m)$

输出格式

一行一个数表示答案。

样例

样例输入

4 12
3 5
2 8
6 3
4 4

样例输出

118332