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 >
	(Tjandra Satria Gunawan)(曾毅昆): 2015-01-02 23:42:05 Wow! Thats great news. Scoring system has been updated. If you get perfect score on test type3 you'll get bonus score: floor{(25.0-[your time on test 3])*8056.0}. If you wonder why 8056, the constant 8056 came from (2014=year this problem published) × (100=score each case on input type3) / (25=time limit). No bonus score if you get perfect score on test type1 and type2. New scoring system is designed so I just need to rejudge last submission. All old issue (minor bug) has been fixed. I'll update problem description shortly.
	Min_25: 2015-01-02 23:40:47 @Francky Thank you ! It was quite hard !
	Francky: 2015-01-02 23:15:04 Big congrats to Min_25 !!!!!!!
	(Tjandra Satria Gunawan)(曾毅昆): 2015-01-02 23:15:04 @Flago: Yes, I agree, by looking your code, I see how hard your work to beat Mitch for now :p btw, Min_25's points is about 80% of perfect score. There's high probability that someday it become perfect so I should start thinking about new scoring formula. @Anubhav Balodhi: Thank you ^^ Btw, I notice two minor bug in my master_judge 1) If you get "TLE" with zero sum of points, it will be judged as "Wrong Answer". 2) If your code judged as "Time Limit Exceeded" the judge not print details on each test data because there are some typo/unwanted '\n' in my master_judge code. Of course it just "minor" bug and not fatal. I'll fix this when I change scoring system (If Min_25 or someone has perfect score).
	Flago: 2015-01-02 23:15:04 Trying to get some points to beat Mitch is depressive when you see Min_25 having 100*more points ! (Min_25 too strong ! Should get malus !! :D)
	Anubhav Balodhi : 2015-01-26 19:59:28 I must say, very nice problem and good explanation ^_^
	Flago: 2015-01-02 23:15:04 Good one, no quite sure tho where i'm missing something... Type 2, d is 2 10³ as max, so n is 4 10⁶... I should be able to n² without having problems with php max int... edit : nvm m=10⁹ and n=10⁶ overflows... those 10¹⁸ are so bad for php users... Last edit: 2014-12-31 15:54:24
	(Tjandra Satria Gunawan)(曾毅昆): 2015-01-02 23:15:04 @californiagurl: I'll explain the image, the blue color on specific cell means the toy is absorbed to magical box, and white color means it left in the factory, if all the color is blue then all toys is absorbed into magical box, |12|3| (all blue) and |1|23| (all blue) in the image is different, |12|3| means toy 1 and toy 2 are absorbed into same magical box while toy 3 is absorbed into other magical box, and |1|23| means toy 2 and 3 is absorbed into same magical box while toy 1 is absorbed into other magical box. If you read problem description carefully, I think it will become clear (I've wrote problem description to be as clear as possible).
	(Tjandra Satria Gunawan)(曾毅昆): 2015-01-02 23:15:04 @Min_25: Congratulations! Your code is very amazing, you even optimize your code in low level :-O and also many attack on math side and computation side, many thumbs up for you ;-)
	californiagurl: 2015-01-02 23:15:04 i dont understand the explanation for example 7.