SPOJ.com - Problem DCEPC13D

DCEPC13D - The Ultimate Riddle

The Joker has played his cards again. This time he has chosen to attack DCE Coders. Gitanshu, and other coders have been abducted.

Mishra has solved the first part of the riddle and estimated N locations. Now, it's up to you to choose R locations among these N.

Calculate the number of ways you can chose the R locations. Since the answer can be large calculate the answer modulo M.

First line contains T number of testcases.

Each line contains 3 integers N, R, M.

Output the required answer

1 <= T <= 10⁴

1 <= M <= 10⁹

1 <= R <= N <= 10⁹

M is a square-free number having prime factors less than 50.

Input:
4
5 2 1001
5 2 6
20 6 210
13 4 39

Output:
10
4
120
13



2024-08-15 04:03:30 Nice Question. Learn Luca's + CRT + fermat
2020-10-04 07:53:56 using CRT!!
2018-05-19 17:23:54 lucas！
2015-05-08 07:07:22 RIVU DAS Time limit is too strict for python!!
2015-05-02 12:33:06 dce coders @Min_25 You are right, there was a problem in an input file. It has been fixed now.
2015-05-02 11:50:10 Min_25 @dce coders Assertion Failed: - assert(scanf("%u", &T) == 1); or assert(scanf("%u %u %u", &N, &R, &M) == 3); This means that some input file is broken. EDIT: Thanks ! Last edit: 2015-05-02 12:47:49
2015-03-30 10:46:29 asgerix A hint to others: Check for empty lines in the input file, and output 0 as answer for these.
2015-03-20 04:08:29 Min_25 @dce coders Some input file is broken. (T is larger than the number of test cases or some test case doesn't contain 3 numbers.) Please fix it. Last edit: 2015-03-20 04:11:11
2015-03-19 15:51:04 asgerix Could there be a problem with the input data? I get an exception (NZEC) when I parse the numbers, but if I exclude empty (or only whitespace) lines, I just get a Wrong Answer. I'm using C#, reading the lines with line = Console.ReadLine(), fields = line.Split(' ') and parsing the numbers with long.Parse(fields[i]).