D. 组合数乘积
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

小文是一个数学苦手，对于一些组合数求和他一窍不通。

现在他有一个由 $$$n$$$ 个组合表达式 $$$C_{a_1}^{b_1} \cdot C_{a_2}^{b_2} \cdots C_{a_n}^{b_n}$$$，其中 $$$C_{x}^{y}=\frac{x!}{y!(x-y)!}$$$，你需要帮小文计算他们的乘积，这个结果可能很大，你需要输出对 $$$m$$$ 取模后的结果即可。

Input

第一行输入两个正整数 $$$n,m\ (1\le n\le 10^6,2\le m\le 10^9)$$$，表示需要求和的项数和模数。

接下来 $$$n$$$ 行，每行输入两个非负整数 $$$a_i,b_i\ (0\le b_i\le a_i\le 10^6)$$$，表示第 $$$i$$$ 项组合数。

Output

输出一个非负整数，表示答案。

Examples
Input
3 114514
19 1
9 8
1 0
Output
171
Input
8 998244353
24 11
28 19
34 2
92 30
289 12
200 39
76 73
325 25
Output
535371832
Input
3 999999999
1000000 500000
1000000 114514
1000000 1000000
Output
72955971