SPOJ.com - Problem COLORSEG

COLORSEG - Coloring Segments

Making a fun is a not a bad thing, but while making a fun if you disrespect someone then it will not be acceptable. Some of the North South University's students has done this type of wrong thing. So as a punishment they have to solve this problem. And you are a friend of them, so you should help them.

You will have N segments. Each one is connected in contiguous way. And we can number them from 1 to N. See the following figure:

Now you need to paint them, you have some colors, which are numbered from 1 to M. Now you need to count number of ways to paint the segments with the colors, such that this property preserves-

    U = color(i) + color(j)
    V = color(j) + color(k)
    U, V is Coprime.
    Here 1 <= i < j < k <= N and j = i + 1, k = j + 1
    And i, j, k indicates the index of segments and color(i) means the color you have painted on i th segment.

Input

Input starts with an integer T (≤ 2500), denoting the number of test cases.

Each case starts with a line containing two integers N, M.

1 <= N <= 50

1 <= M <= 50

Output

For each case, print the case number and the number of ways to paint the segments following above conditions. Since the result can be very large, you have to print the result modulo 1000003

Sample

Input
3
3 1
3 2
3 3

Output
Case 1: 0
Case 2: 4
Case 3: 14

Submit solution!

hide comments



	smso: 2020-06-06 09:21:29 Deal with nasty TLE by precomputing.
	karthik1997: 2017-12-23 10:24:20 Really Good Question . I wonder , how much was the complexity of those , who solved it , in less than 10ms (0.00 s)
	hodobox: 2017-04-26 02:23:49 Pretty cool, haven't seen anything quite like this before :)
	mdaamir151: 2017-03-08 18:43:19 @Faiyaz I am getting sigsev ( runtime error ) on submission . It runs just fine on my machine! I am unable to spot where I am getting seg fault. Can you tell me why/where I am getting this? My submission id: 18922906 Thanks in Advance Last edit: 2017-03-08 18:44:35
	naruto09: 2016-07-11 02:02:50 great question..!!
	Rishi Vikram: 2016-03-12 21:37:31 For those getting WA, answer for n<=2 is NOT zero.
	parijat bhatt: 2015-06-05 21:20:53 Francky pls help.
	parijat bhatt: 2015-06-05 21:20:19 could any one tell me the complexity per test case. thanks
	Francky: 2014-11-14 23:43:57 @Mitch : In the submission list, when I'm logged (or not!), I only see 11832574, 11832563, 11832471 submissions from you, those 3 are WA. I don't see your others ones. If it can help... You can burn this message after reading. ;-) (reply from Mitch) Thanks for that info, I suspected as much. I think it's only visible to psetter, solver, and admins. It is similar to how psetter's submissions to his own problem are hidden by default. On Polish SPOJ those are shown by default. I also experimented with submitting to BFBINADD on SHORTEN -- it is visible by default, but I made that submission "Private" so that it would not count, and now the other option "Set visible" does not undo that action (although the name implies it would). The system seems a little buggy although not generally an issue. I would guess that it is the same flag that was activated in this case for the disqualified submissions. Last edit: 2014-11-15 00:24:47
	Mitch Schwartz: 2014-11-14 22:48:21 @Ahmad Faiyaz: It is very rude to change the source limit after publication and then disqualify correct longer codes. You should have thought about those things before publishing. I don't know how many users were affected by this, but I know I'm not the only one -- probably there were quite a few. You did not even leave a comment to notify and apologise. The problem is hidden and moved to tutorial for now. Please return the problem to its original state and rejudge all disqualified submissions. (You can just rejudge all submissions, if it would be too inconvenient to target the disqualified ones individually.) After that, the problem could be moved back to classical and made visible again, or you could keep this original version in tutorial and create a duplicate with the lower source limit for classical if you want. There could be other options too (depending on how many approaches there are to this, and what types of constraints those approaches can handle), but the rude option you chose is not acceptable. @Mitch Schwartz, I am sorry for changing the source limit. I used source limit at main contest where this problem was used. But when I uploaded the problem on SPOJ, I forgot to change that. As it is on online judge I thought it would not be a bad idea if I change the source limit like changing the time limits. Though it affected maybe 5-6 solvers and I added a note in the problem statement which says to check the source limit. Anyway I reverted to the initial version. Hope its OK now. (reply from Mitch) Thanks for that. What about rejudge? In my experience, rejudging a disqualified submission "undisqualifies" it. Did you try? Edit: I can see that my submission is now judged as AC even though it does not appear in the main rank table. It is curious. Maybe a cache issue that will be updated in a bit. (Or maybe a SPOJ bug.) Problem is now visible. Thank you. Edit 2: Now I notice that my rejudged submission is not visible if I'm not signed in! Looks like a SPOJ bug. Anyway, if it doesn't update then we can just resubmit, not a big deal. Last edit: 2014-11-14 23:34:08

Submit solution!

Added by:	Faiyaz
Date:	2014-06-26
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own Problem