Problem Description
Frog has just learned how to multiply two numbers. Now he wants to do some exercise.
He wrote a string on the paper, which only contains digits and a single × as the operator. If the × appears at the front or the end of the string, he regards the result as zero, otherwise he does the calculation as a normal multiplication.
After some play, he wonders a new problem: for a initial string, each time he randomly choose two characters and swap their positions. He will do this again and again, say for K times, he wants to know the expected calculation result for the newest string that he gets.
It can be shown that their can be (n2)K ways(Same as (C2n)K) for the whole swap operations, so if the expected result is x, you need to output x×(n2)K as an integer.
Input
First line contains an integer T, which indicates the number of test cases.
Every test case begins with an integers K, which is the numbers of times the Frog can swap characters.
The second line of each test case contains the string Frog plays with, which only contains digits and exactly one multiplication operator, written as '∗'.
⋅ 1≤T≤100.
⋅ the string's length is L.
⋅ for 70% data, 1≤L≤10 and 0≤K≤5.
⋅ for 95% data, 1≤L≤20 and 0≤K≤20.
⋅ for 100% data, 1≤L≤50 and 0≤K≤50.
Output
For every test case, you should output "Case #x: y", where x indicates the case number and counts from 1 and y is the result.
Because y could be very large, just mod it with 109+7.
Sample Input
2
1
1*2
2
1*2
Sample Output
Case #1: 2
Case #2: 6
