Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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.

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

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

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

$\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$.

提交代码