{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"正在上一年级的LYD今天刚学会了乘法,开心的他迫不及待地想做一些练习题。他在纸上写了一些只包含数字和1个乘号\"*\"的字符串即乘法表达式,如果乘号位于整个字符串的首端或者末端,则整个表达式的值为0,否则为乘法运算的结果。\n几次尝试之后,好学的他提出了一个船新问题:对一个初始的乘法表达式字符串,每次他都随机选择其中两个字符并交换他们的位置,重复k次这样的操作。他想知道最终得到的表达式的期望值。\n显然地,他一共有C(2,n)^k种选法。因此为了避免浮点运算,请将表达式的期望值乘上C(2,n)^k作为最终的答案。"}},{"title":"Input","value":{"format":"MD","content":"第一行一个整数表示数据组数,每组数据包含一个整数k和一个字符串s,k表示LYD交换字符的次数,字符串为上述乘法表达式且包含恰好一个\"*\"。其中,T\u003c\u003d100,0\u003c\u003dk\u003c\u003d50,1\u003c\u003d|s|\u003c\u003d50。\n"}},{"title":"Output","value":{"format":"MD","content":"对每一组数据输出\"Case #x: y\",x为数据组号,y为答案。由于y可能非常大,输出对1e9+7取模的结果。"}},{"title":"Sample Input","value":{"format":"MD","content":"\u003cpre\u003e\n1\n2\n2*3\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"MD","content":"\u003cpre\u003eCase #1: 18\n\u003c/pre\u003e"}}]}