There are $T$ restaurants in bagel-world. The $i^{th}$ restaurant serves $n_i$ distinct kind of bagels. Being a foodie you visit all the restaurants and in $i^{th}$ restaurant you order $k_i$ bagels. You have to tell the number of ways the order can be placed in the $i^{th}$ restaurant given that the count of any kind of bagel should always be less than $P$. Two orders are considered different if there is atleast one kind of bagel whose count in the order is different. Since the answer can be large you have to output answer modulo $P$ .

Note: $P$ is a prime.

Constraints

• $1 \le T \le 10^5$
• $2 \le P \le 7654321$
• $P$  is a prime number
• $1 \le n_i \le 10^{12}$
• $1 \le k_i \le n_i \times (P - 1)$

Input Format

• First line contains two space separated integers $T$  and $P$  respectively. $T$  lines follow.
• $i^{th}$ line contains two space separated integer $n_i$ and $k_i$ respectively denoting the number of distinct kind of bagels available in $i^{th}$ restaurant and the number of bagels that you order.

Output Format

• For each testcase output a single integer, the value of answer modulo $P$ .
• $i^{th}$ line should be the answer for the $i^{th}$ restaurant.