{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eZS the Coder and Chris the Baboon has explored Udayland for quite some time. They realize that it consists of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e towns numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. \u003c/p\u003e\u003cp\u003eThere are \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e directed roads in the Udayland. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th of them goes from town \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e to some other town \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ \u003ci\u003ei\u003c/i\u003e\u003c/span\u003e). ZS the Coder can flip the direction of any road in Udayland, i.e. if it goes from town \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e to town \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e before the flip, it will go from town \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e to town \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e after.\u003c/p\u003e\u003cp\u003eZS the Coder considers the roads in the Udayland \u003cspan class\u003d\"tex-font-style-it\"\u003econfusing\u003c/span\u003e, if there is a sequence of distinct towns \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e \u0026gt; 1\u003c/span\u003e) such that for every \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ei\u003c/i\u003e \u0026lt; \u003ci\u003ek\u003c/i\u003e\u003c/span\u003e there is a road from town \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e to town \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e + 1\u003c/sub\u003e\u003c/span\u003e and another road from town \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e to town \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e. In other words, the roads are confusing if \u003cspan class\u003d\"tex-font-style-bf\"\u003esome of them\u003c/span\u003e form a directed cycle of some towns.\u003c/p\u003e\u003cp\u003eNow ZS the Coder wonders how many sets of roads (there are \u003cspan class\u003d\"tex-span\"\u003e2\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e variants) in initial configuration can he choose to flip such that after flipping each road in the set exactly once, the resulting network will \u003cspan class\u003d\"tex-font-style-bf\"\u003enot\u003c/span\u003e be confusing.\u003c/p\u003e\u003cp\u003eNote that it is allowed that after the flipping there are more than one directed road from some town and possibly some towns with no roads leading out of it, or multiple roads between any pair of cities.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— the number of towns in Udayland.\u003c/p\u003e\u003cp\u003eThe next line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ \u003ci\u003ei\u003c/i\u003e)\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e denotes a road going from town \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e to town \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single integer\u0026nbsp;— the number of ways to flip some set of the roads so that the resulting whole set of all roads is not confusing. Since this number may be too large, print the answer modulo \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Examples","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\u003e3\n2 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e4\n2 1 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e5\n2 4 2 5 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e28\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eConsider the first sample case. There are \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e towns and \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e roads. The towns are numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e and the roads are \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/9107c41dfe8eab8095f89d22242ef68b?v\u003d1715569900\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/199718e195dff5fa9a9d95ed6e00dac3?v\u003d1715569900\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/0d3a730dbadc558e8a825cb697402b5f?v\u003d1715569900\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e initially. Number the roads \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e in this order. \u003c/p\u003e\u003cp\u003eThe sets of roads that ZS the Coder can flip (to make them not confusing) are \u003cspan class\u003d\"tex-span\"\u003e{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}\u003c/span\u003e. Note that the empty set is invalid because if no roads are flipped, then towns \u003cspan class\u003d\"tex-span\"\u003e1, 2, 3\u003c/span\u003e is form a directed cycle, so it is confusing. Similarly, flipping all roads is confusing too. Thus, there are a total of \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e possible sets ZS the Coder can flip.\u003c/p\u003e\u003cp\u003eThe sample image shows all possible ways of orienting the roads from the first sample such that the network is \u003cspan class\u003d\"tex-font-style-bf\"\u003enot confusing\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/d59d3d4e01871420e37d8ce08b7327e4?v\u003d1715569900\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e"}}]}