F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

The Relationship in Club

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 206    Accepted Submission(s): 78


Problem Description
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?
 

Input
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$).
 

Output
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.
 

Sample Input
3 2 1 3 2 1 3
 

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

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-02 09:09:46, Gzip enabled