Bagel World
Tag(s):

## Hard, Math, Modulus Arithmetic, Number Theory

Problem
Editorial
Analytics

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.
SAMPLE INPUT
4 5
2 3
2 4
2 6
3 6

SAMPLE OUTPUT
4
0
3
4

Explanation

For the $1^{st}$ restaurant, there are $2$  kinds of bagels and the order consists of $3$  bagels. All the possible ways to make the order are: $(0, 3), (1, 2), (2, 1) \text{ and } (3, 0)$. So the answer is $4$  mod $5$  $i.e.$$4$

Note: $(x, y)$ here represents that you order $x$  bagels of first kind and $y$  bagels of second kind.

For the $2^{nd}$ restaurant $5$ the  possible ways are: $(0, 4), (1, 3), (2, 2), (3, 1) \text{ and } (4, 0)$. So the answer is $5$  mod $5$  $i.e.$ $0$

For the $3^{rd}$ restaurant the $3$  possible ways are: $(2, 4), (3, 3), (4, 2)$. So the answer is $3$  mod $5$  $i.e.$ $3$

Note: $(0, 6), (1, 5), (5, 1) \text{ and } (6, 0)$ are NOT valid orders as count of any kind of bagel is always less than $P$ .

For the $4^{th}$ restaurant there are $19$ possible ways to order. So the answer is $19$ mod $5$  $i.e.$ $4$

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

March Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Basic Programming > Implementation
• Data Structures > Advanced Data Structures
• Algorithms > Dynamic Programming
• Math > Geometry
• Algorithms > Dynamic Programming