Dhaka Regional ACM ICPC 2016 Preleminary Contest Solution I - Gadgets of Tomishu

I. Gadgets of Tomishu

Score: 1

CPU: 1s
Memory: 1200MB

Little Tomishu likes numbers. But he likes electronic gadgets (mobile, tablet, phablet, laptop and so on) more than numbers. His parents are trying to keep him engaged with numbers. So, they asked him to write down all the numbers of n length, consisting of only 0 and 1, and without any neighboring 1s. For example, if n = 3, he is supposed to write: 000, 001, 010, 100 and 101. Of course, Tomishu will write the numbers in increasing order. For each of the numbers, his parent will reward him with one of the k types of gadgets. Find out the number of ways he can get the gadgets. Two ways will be different if he received different gadget for the ith number for some i. For example, for n = 3, if there are k = 2 types of gadgets (say mobile and laptop), he can get the gadgets in 2 * 2 * 2 * 2 * 2 = 25 = 32 ways.
Since the answer can be quite big for the given n and k, you will also be given M. You need to provide the answer modulo M.
However, you should know that recently Tomishu’s interest shifted from electronic gadget to bookfacing.

Input

First line of the input is T (≤ 20), the number of test cases. Hence T lines will follow. Each of these lines will contain 3 positive integersn, k and M (1 ≤ n, k ≤ 100,000 and 1 ≤ M ≤ 1,000,000,000).

Output

For each of the cases print case number, followed by the answer. For details, please check the sample output.

Sample

InputOutput
2 3 2 100 4 3 1000 Case 1: 32 Case 2: 561













Comments

Post a Comment

Popular posts from this blog

Solution - Timus Problem 1293. Eniya

1293. Eniya Time limit: 1.0 second Memory limit: 64 MB It’s restless now on the slips of the intergalactic port’s sixth dock of planet of Torn. No longer then in a month the reconstruction of the small ironclad corvette “Eniya” will be finished. And again this battle ship and its brave team would have to struggle for the control over plutonium mines of Sibelius. The work cannot be stopped even for a second, self-powered laser welders work round the clock. Joints of robots-repairers fuse because of this permanent work. Nevertheless, they can’t stop not for a single moment. Now in all this turmoil it is discovered that corvette’s thermopanels again need an urgent processing with thorium sulphide. It is known that the processing of the one square meter of the panel needs 1 nanogramm of sulphide. In general, it is needed to process  N  rectangular panels, which dimensions are  A  by  B  meters. It is necessary to calculate as fast as possible, how m...
Read more...

Solution - Codeforces Problem 327B - Hungry Sequence

B. Hungry Sequence Iahub and Iahubina went to a date at a luxury restaurant. Everything went fine until paying for the food. Instead of money, the waiter wants Iahub to write a Hungry sequence consisting of  n  integers. A sequence  a 1 ,  a 2 , ...,  a n , consisting of  n  integers, is  Hungry  if and only if: Its elements are in increasing order. That is an inequality  a i  <  a j  holds for any two indices  i ,  j   ( i  <  j ) . For any two indices  i  and  j   ( i  <  j ) ,  a j  must  not  be divisible by  a i . Iahub is in trouble, so he asks you for help. Find a Hungry sequence with  n  elements. Input The input contains a single integer:  n  ( 1 ≤  n  ≤ 10 5 ). Output Output a line that contains  n  space-separated integers  a 1   a 2 , ...,  a n   (1 ≤  a i  ≤ 10 7 ) , representing a ...
Read more...

Solution - Timus Problem 1409. Two Gangsters

1409. Two Gangsters Time limit: 1.0 second Memory limit: 64 MB Two gangsters Harry and Larry had a rest at countryside. They decided to spend some time shooting, so they put several beer cans (no more than 10) on a log. Harry started to shoot cans one after another from the leftmost to the right and Larry – from the rightmost to the left. At some moment it happened so that they shot one and the same can. Harry got indignant and claimed that Larry owed him a considerable sum of money because Larry deprived him of shooting some more cans. Larry became furious and told Harry that he owed even greater sum of money to Larry because of the same reason. They started to argufy but nobody remembered how many cans there were at the very beginning. And no one of them was going to search cans which was shot. Anyway, each of them remembered exactly how many cans he shot. Determine how many cans were not shot by Harry and how many cans were not shot by Larry. Input The only inp...
Read more...