Mrs Tang's Task
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 3 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
There are N members in the school dance team, and they are numbered 1, 2, 3... N.
One day, they have to rehearse a new dance. At first, they are arranged in a circle order by their numbers. As for a circle, N has to be next to N-1 and 1.
But some dancers want to stand in some specified positions. They tell their requests to their teacher, Mrs Tang. However, Mrs Tang thinks that a big change will affect their dancing performance. Mrs Tang only thinks it's acceptable that every dancer can stand at her original position or its adjacent ones after the change.
For example, there are 4 dancers in the dancing team. Their original order is 1-2-3-4(team member i stands on position i and 4 is adjacent to 1). After the change, if the order become 1-3-2-4, Mrs Tang will accept the rearrangement. However, if the order changes to 3-4-1-2, Mrs Tang will think that's a mess and reject that.
At that moment, Cindy is passing Mrs Tang's office, so Mrs Tang passes this task to Cindy by no reason.
After receiving this glorious task, Cindy confirms that only K dancers want to stand at specified positions, while the others have no opinions. When Cindy prepares to calculate the number of acceptable arrangements, Cindy gets astonished, because that result is very very big!
Cindy is asking for help. As a enthusiastic ACMer, will you help him to solve Mrs Tang's problem?
One day, they have to rehearse a new dance. At first, they are arranged in a circle order by their numbers. As for a circle, N has to be next to N-1 and 1.
But some dancers want to stand in some specified positions. They tell their requests to their teacher, Mrs Tang. However, Mrs Tang thinks that a big change will affect their dancing performance. Mrs Tang only thinks it's acceptable that every dancer can stand at her original position or its adjacent ones after the change.
For example, there are 4 dancers in the dancing team. Their original order is 1-2-3-4(team member i stands on position i and 4 is adjacent to 1). After the change, if the order become 1-3-2-4, Mrs Tang will accept the rearrangement. However, if the order changes to 3-4-1-2, Mrs Tang will think that's a mess and reject that.
At that moment, Cindy is passing Mrs Tang's office, so Mrs Tang passes this task to Cindy by no reason.
After receiving this glorious task, Cindy confirms that only K dancers want to stand at specified positions, while the others have no opinions. When Cindy prepares to calculate the number of acceptable arrangements, Cindy gets astonished, because that result is very very big!
Cindy is asking for help. As a enthusiastic ACMer, will you help him to solve Mrs Tang's problem?
Input
There are multiple test cases. The first line contains an integer T (T<=1000), indicating the number of test cases.
Then, in the first line of each case, two integers N (3<=N<=1000000) and K (0<=K<=100) are shown, indicating that there are N dancer members, and K of them wants specified positions.
The next K lines, two integers A and B are in each line, indicating that dancer with index A wants to stand at position B. (Position B is the position which the dancer with index B stand at originally.)
Then, in the first line of each case, two integers N (3<=N<=1000000) and K (0<=K<=100) are shown, indicating that there are N dancer members, and K of them wants specified positions.
The next K lines, two integers A and B are in each line, indicating that dancer with index A wants to stand at position B. (Position B is the position which the dancer with index B stand at originally.)
Output
For each test case, output "Case #D: E". The integer D is the test case number, and the integer E is the total number of acceptable arrangements.
Because the answer would be very very big, print out the remainder of the answer divided by 10^9+7.
Because the answer would be very very big, print out the remainder of the answer divided by 10^9+7.
Sample Input
2 3 1 1 1 4 2 1 2 3 4
Sample Output
Case #1: 2 Case #2: 2
Source
华南师范大学·2012年ACM程序设计竞赛·决赛