DCEPC13D - The Ultimate Riddle

no tags 

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.

Input

First line contains T number of testcases.

Each line contains 3 integers N, R, M.

Output

Output the required answer

Constraints

1 <= T <= 104

1 <= <= 109

1 <= R <= N <= 109

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

Example

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

Output:
10
4
120
13

hide comments
taejin_101: 2024-08-15 04:03:30

Nice Question. Learn Luca's + CRT + fermat

codephilic: 2020-10-04 07:53:56

using CRT!!

nimphy: 2018-05-19 17:23:54

lucas!

RIVU DAS: 2015-05-08 07:07:22

Time limit is too strict for python!!

dce coders: 2015-05-02 12:33:06

@Min_25 You are right, there was a problem in an input file.
It has been fixed now.

Min_25: 2015-05-02 11:50:10

@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
asgerix: 2015-03-30 10:46:29

A hint to others: Check for empty lines in the input file, and output 0 as answer for these.

Min_25: 2015-03-20 04:08:29

@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
asgerix: 2015-03-19 15:51:04

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]).


Added by:dce coders
Date:2015-03-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:dce_coders