本题来源于：2014 年 ICPC 亚洲（陕西）西安区域赛 Problem F
朵花，按顺序排成一排。从 种颜色中选出 种颜色，给这 朵花染色，要求相邻的花颜色不同。问共有多少种染色方案？答案对 取模。
Recently, Mr. Big recieved flowers from his fans. He wants to recolor those flowers with colors. The flowers are put in a line. It is not allowed to color any adjacent flowers with the same color. Flowers and are said to be adjacent for every , . Mr. Big also wants the total number of different colors of the flowers being exactly .
Two ways are considered different if and only if there is at least one flower being colored with different colors.
The first line of the input gives the number of test cases, . test cases follow. is about and in most cases is relatively small.
For each test case, there will be one line, which contains three integers (, , ).
For each test case, output one line containing
Case , where is the test case number (starting from ) and is the number of ways of different coloring methods modulo .
2 3 2 2 3 2 1
Case #1: 2 Case #2: 0