5576：Expection of String

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 $\times$ as the operator. If the $\times$ 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 $\binom{n}{2} ^ K$ ways(Same as $\left(C_{n}^{2}\right)^K$) for the whole swap operations, so if the expected result is x, you need to output $x \times \binom{n}{2} ^ K$ as an integer.

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 '$*$'.

$\cdot$ $1 \leq T \leq 100$.

$\cdot$ the string's length is $L$.

$\cdot$ for 70% data, $1 \leq L \leq 10$ and $0 \leq K \leq 5$.

$\cdot$ for 95% data, $1 \leq L \leq 20$ and $0 \leq K \leq 20$.

$\cdot$ for 100% data, $1 \leq L \leq 50$ and $0 \leq K \leq 50$.

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 $10^9 + 7$.