The Relationship in Club

There are many student clubs in the campus, among which the Always Creatively Moha (ACM) club gained the most popularity. The ACM club consists of $N$ members. Not all of them know each other, so we may describe the relationship between two members with an integer ranging from 0 to $M$ inclusively. For example, 0 means that the two persons do not know each other. 1 may indicate that they know each other but are not familiar. 520 indicates that they have fallen into love.
The members are partitioned into two non-empty groups to participate a team-building activity. To get them know each other, it is required that the value of relationship between every pair of members in the same groups is always 0, while the relationship between persons from different groups can be any value between 0 and $M$.
It should be noted that such a partition is not always possible. For example, if there are 3 members in the club and the value of relationship between them is greater than 0, it is impossible to partition them as required.
The organizer comes up with an interesting question. Assuming we may assign any integer between 0 and $M$ to the relationship between any two members. Among all the ways of assignment, how many of them can make the partitioning possible?

The first line of input contains a number $T$ indicating the number of test cases ($T≤100$).
Each test case consists of two integers $N$ and $M$ indicating the number of members and the maximum value of relationship ($1≤N,M≤1000$).

For each test case, output a single line consisting of “Case #X: Y”. $X$ is the test case number starting from 1. $Y$ is the number of ways assigning value to relationships that makes the partitioning possible. As the answer could be huge, you only need to output $Y$ module 105225319.

3
2 1
3 2
1 3

Case #1: 2
Case #2: 19
Case #3: 0

2015 ACM/ICPC Asia Regional Hefei Online