Bagel World

Practice

5 (2 votes)

Mathematics

Hard

Modular arithmetic

Number theory

Problem

84% Success 218 Attempts 50 Points 2s Time Limit 256MB Memory 1024 KB Max Code

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

Sample Output

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\)

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor

Constraints