{"trustable":true,"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":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e Matt, a famous adventurer who once defeated a pack of dire wolves alone, found a lost court. Matt finds that there are N fluorescent lights which seem to be the stars from the firmament. What’s more, there are M switches that control these fluorescent lights. Each switch is connected to a group of lights. When Matt touches a switch, all the lights connected to it will change their states (turning the dark on, turning the bright off).\u003cbr\u003e\u003cbr\u003e Initially, all the fluorescent lights are dark. For each switch, Matt will touch it with probability 1 .\u003cbr\u003e\u003cbr\u003e As a curious gentleman, Matt wants to calculate E[X3], where X represents the number of bright lights at the end, E[X3] represents the expectation of cube of X.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" The first line contains only one integer T , which indicates the number of test cases.\u003cbr\u003e\u003cbr\u003e For each test case, the first line contains N, M (1 ≤ N, M ≤ 50), denoting the number of fluorescent lights (numbered from 1 to N ) and the number of switches (numbered from 1 to M ).\u003cbr\u003e\u003cbr\u003e M lines follow. The i-th line begins with an integer Ki (1 ≤ K\u003csub\u003ei\u003c/sub\u003e ≤ N ). K\u003csub\u003ei\u003c/sub\u003e distinct integers l\u003csub\u003eij\u003c/sub\u003e(1 ≤ l\u003csub\u003eij\u003c/sub\u003e ≤ N ) follow, denoting the fluorescent lights that the i-th switch controls."}},{"title":"Output","value":{"format":"HTML","content":" For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1) and y is the answer. To avoid rounding error, the answer you should output is:\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cb\u003eE[X\u003csup\u003e3\u003c/sup\u003e] × 2\u003csup\u003eM\u003c/sup\u003e mod (10\u003csup\u003e9\u003c/sup\u003e + 7)\u003c/b\u003e\u003c/center\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n2 2\r\n1 1\r\n2 1 2\r\n3 1\r\n3 1 2 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 10\r\nCase #2: 27\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"For the first sample, there’re 4 possible situations:\u003cbr\u003eAll the switches is off, no light is bright, X^3 \u003d 0.\u003cbr\u003eOnly the first switch is on, the first light is bright, X^3 \u003d 1.\u003cbr\u003eOnly the second switch is on, all the lights are bright, X^3 \u003d 8.\u003cbr\u003eAll the switches is on, the second lights are bright, X^3 \u003d 1.\u003cbr\u003eTherefore, the answer is E[X^3] × 2^2 mod (10^9 + 7) \u003d 10.\u003cbr\u003e\u003cbr\u003eFor the second sample, there’re 2 possible situations:\u003cbr\u003eThe switches is off, no light is bright, X^3 \u003d 0.\u003cbr\u003eThe switches is on, all the lights are bright, X^3 \u003d 27.\u003cbr\u003eTherefore, the answer is E[X^3] × 2^1 mod (10^9 + 7) \u003d 27.\u003cbr\u003e"}}]}