由于评测机波动，将此题目评测时间限制由1000ms增加至1600ms

二色蓮花蝶　～ Red and White
早上，在池水上起舞的红白二色巫女映入眼帘。

Background

起得最早的我，长时间沉醉在那冷酷无情而又过激的舞姿中。不久后下起了雨，当我回过神 来时，巫女的身影已经无处寻觅了

Description

给定 $n,k,p$ 求

$$\sum \limits_{i=0}^n \sum \limits_{j=0}^i \dbinom{i}{k} \times (i+k) \times (j+k)$$

对于给定模数$p$取模，含有多组数据。

Format

Input

第一行给出数据组数$T$和指定模数$p$
接下来$T$行，每行两个整数$n,k$。

Output

对于每一个询问，输出一个整数代表答案。

Samples

7 998244353
10 10
114 514
1919 810
11410110097110100 119104105116101
11910511699 104111102
108111118101112 111116105111110
80101110 1037697105

566199
282252966
613255781
19223957
845343004
667277942
75267614

Limitation

TestCase	$n,k$	$T$	$p$
1	$\le 100$	$1$	$998244353$
2,3	$\le 1000$
4,5,6	$\le 10^6$
7,8,9	$\le 10^{18}$
10		$5 \times 10^5$	$\in [2,10^9]$