{"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马特是一位著名的冒险家,曾经独自击败了一群凶狼,他发现了一个迷失的宫廷。马特发现那里有N盏荧光灯,看起来就像天空中的星星。更重要的是,有M个开关可以控制这些荧光灯。每个开关都连接到一组灯。当马特触摸一个开关时,所有与之连接的灯都会改变状态(暗的变亮,亮的变暗)。\u003cbr\u003e\u003cbr\u003e最初,所有的荧光灯都是暗的。对于每个开关,马特将以概率1触摸它。\u003cbr\u003e\u003cbr\u003e作为一个好奇的绅士,马特想要计算E[X3],其中X代表最终亮着的灯的数量,E[X3]代表X的立方的期望值。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行只包含一个整数T,表示测试用例的数量。\u003cbr\u003e\u003cbr\u003e对于每个测试用例,第一行包含N、M(1 ≤ N,M ≤ 50),表示荧光灯的数量(从1到N编号)和开关的数量(从1到M编号)。\u003cbr\u003e\u003cbr\u003e接下来是M行。第i行以一个整数Ki(1 ≤ Ki ≤ N)开头。接下来是Ki个不同的整数lij(1 ≤ lij ≤ N),表示第i个开关控制的荧光灯。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行“Case #x: y”,其中x是案例编号(从1开始),y是答案。为避免四舍五入误差,你应该输出的答案是:\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cb\u003eE[X3] × 2M mod (109 + 7)\u003c/b\u003e\u003c/center\u003e"}},{"title":"示例","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"}},{"title":"提示","value":{"format":"HTML","content":"对于第一个示例,有4种可能的情况:\u003cbr\u003e所有开关都关闭,没有灯亮,X^3 \u003d 0。\u003cbr\u003e只有第一个开关打开,第一个灯亮,X^3 \u003d 1。\u003cbr\u003e只有第二个开关打开,所有灯都亮,X^3 \u003d 8。\u003cbr\u003e所有开关都打开,第二个灯亮,X^3 \u003d 1。\u003cbr\u003e因此,答案是E[X^3] × 2^2 mod (109 + 7) \u003d 10。\u003cbr\u003e\u003cbr\u003e对于第二个示例,有2种可能的情况:\u003cbr\u003e开关关闭,没有灯亮,X^3 \u003d 0。\u003cbr\u003e开关打开,所有灯都亮,X^3 \u003d 27。\u003cbr\u003e因此,答案是E[X^3] × 2^1 mod (109 + 7) \u003d 27。\u003cbr\u003e"}}]}