English

Indonesian

One day, at the north pole there is a huge factory that produce many awesome toys. Santa Claus, who own this factory want to deliver this toys as a gift to many children who want some gift on christmas day using flying reindeer, because for each year number of toy increase and his flying reindeer get older, he want his load to be as light as possible.

Fortunately this christmas (December 2014) he invent a new technology that can store infinite amount of toys using 4th space dimension, he call it "magical box", so every item/toys in magical box will weightless, very impressive! He invent that magical box on 23 December 2014, there still 2 days remaining before christmas, so he want to speed up the loading process.

There are many toys to load in short time and his magical box can't absorb many obcect to 4th space dimension in short time, so he decided to split the work in parallel because he has many magical box available. For example if the toys numbered from 1 to n first magical box absorb toy 2 to toy 5, ... , last magical box absorb toy n-7 to n-1. Note that it's possible that Santa's magical box can't absorb all toys in his factory on time even if he use parallel technique, so some toy maybe left in the factory for next christmas.

Because his magical box still in "beta version" it still has a bug, it can only absorb consecutive toys only, so if toys 3 and toys 5 absorbed to same magical box, toy 4 will be accidentally absorbed to that magical box too. Since the problem become too complex, Santa want to rest and he left the factory to feed and tell his flying reindeer a good news that he invent the magical box so his flying reindeer will not carrying heavy load again like previous year. He also planning how he pack the toys to magical box. Because Santa is perfection, he want each box if used contains at least d toys.

Now he wonder how many ways he can load the toys into his magical box if number of his magical box and number of toys in his factory is same. It's not necessary to use all his magical box, he want to use at least one of his magical box. Can you help him count how many ways he can do it?

Input

On the first line there is one integer c, denoting case type. For details about case type, see "Constraints".

Each next line untill EOF there are three integers d, n, and m

• d = Minimal number of toys Santa want to put on each magical box
• n = Number of toys available at the Santa's factory
• m = Modulo, since the answer is very large, Santa will understand, he just need the answer modulo m.

Output

For each answer you get, output two numbers, d and the answer modulo m in one line separated by a space.

Constraints

2014 cases.

1 ≤ c ≤ 3

1 ≤ d ≤ 2014 (d will be unique on each input file, no two cases with same d)

1 ≤ m ≤ 109

Type1: 0 ≤ n < 2×d; Score = 1 for each correct answer.

Type2: 0 ≤ n ≤ max(d2,2×d); Score = 10 for each correct answer.

Type3: 0 ≤ n < 264; Score = 100 for each correct answer.

Scoring

Your final score will be sum of score from test type1 to test type3.

If you print all correct answers on test case type3 you'll get bonus score.

Bonus score will be = floor{(25.0-[your time on test 3])*8056.0}

Example 1

Input:

1

1 1 1000

2 3 1000

3 5 1000

4 7 1000

Output:

1 1

2 3

3 6

4 10

Score:

Because this is input type 1, so each correct case worth 1 point.

For this example score=4*1=4.

Example 2

Input:

2

1 2 1000

2 4 1000

3 6 1000

4 8 1000

Output:

1 4

4 16

2 7

Score:

Note that you can put your answer in any order,

because there are 3 correct answers and this is input type 2 (each test case worth 10 points),

for this example score=3*10=30.

Example 3

Input:

2

1 2 1000

2 4 1000

3 6 1000

4 8 1000

Output:

1 4

3 10

4 16

2 7

Score:

For this example you'll get "Wrong Answer".

That's because for d=3 and n=6 and m=1000 answer should be 11, but output is 10.

Better not output "3 10" like in example 2, than output wrong answer.

For this example score = N/A.

Example 4

Input:

3

1 11 1000

2 11 1000

Output:

Score:

Because user don't output anything score=0.

Be careful, you'll get WA if sum of your score on test type1 to type3=0

Example 5

Input:

3

1 12345678987654321 1000

2 11 1000

Output:

2 23

Score:

Because this is input type 3, so each correct case worth 100 points.

For this example score=1*100=100

Example 6

Input:

3

1 3 5

2 4 6

Output:

1 2

2 1

1 2

Score:

All answer are correct, but no duplicate d allowed,

so for this example it will be judged as WA.

Score for this example = N/A

Example 7

Input:

3

1 3 1000000000

2 4 1000000000

Output:

1 12

2 7

Score:

200

Explanation for "Example 7"

Here is 12 ways to pack 3 toys using 1 or more magical box and each magical box must contain minimal 1 toy.

Here is 7 ways to pack 4 toys using 1 or more magical box and each magical box must contain minimal 2 toys.

Additional Information

All input (n and m) are generated with random uniform distribution in the range.

My score at the time publication of this problem is 66554, Will it be hard to beat this(?)

Update: [2014-12-24 13:42:56] Congratulations to Min_25, first user who break my record in this problem.

If some user has perfect score (223554) I'll not increase constraints or change test data, I'll change the scoring system (taking running time into account), but... will it happen?

Update: It happen! [2015-01-02 22:38:52] Congratulations to Min_25!

---

See also: Another problem added by Tjandra Satria Gunawan

---

hide comments

< Previous 1 2 Next >
	Min_25: 2015-01-02 23:15:04 I enjoyed it very much. :) (Thanks for 30-bit mod !) Last edit: 2014-12-25 16:46:57
	(Tjandra Satria Gunawan)(曾毅昆): 2015-01-02 23:15:04 @Mitch Schwartz: Thanks for your appreciation ;-)
	Mitch Schwartz: 2015-01-02 23:15:04 I'm very glad to see a good problem in challenge section that won't have to be moved out or hidden. :D :D :D