{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nMarjar University has decided to upgrade the infrastructure of school intranet by using fiber-optic technology. There are \u003cvar\u003eN\u003c/var\u003e buildings in the school. Each building will be installed with one router. These routers are connected by optical cables in such a way that there is exactly one path between any two routers.\n\u003c/p\u003e\n\n\u003cp\u003e\nEach router should be initialized with an operating frequency \u003cvar\u003eF\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e before it starts to work. Due to the limitations of hardware and environment, the operating frequency should be an integer number within [\u003cvar\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e, \u003cvar\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e]. In order to reduce the signal noise, the operating frequency of any two adjacent routers should be co-prime.\n\u003c/p\u003e\n\n\u003cp\u003e\nEdward is the headmaster of Marjar University. He is very interested in the number of different ways to initialize the operating frequency. Please write a program to help him! To make the report simple and neat, you only need to calculate the sum of \u003cvar\u003eF\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e (modulo 1000000007) in all solutions for each router.\n\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\n\u003cp\u003eThere are multiple test cases. The first line of input contains an integer \u003cvar\u003eT\u003c/var\u003e indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003e\nThe first line contains one integer \u003cvar\u003eN\u003c/var\u003e (1 \u0026lt;\u003d \u003cvar\u003eN\u003c/var\u003e \u0026lt;\u003d 50). The next line contains \u003cvar\u003eN\u003c/var\u003e integers \u003cvar\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e (1 \u0026lt;\u003d \u003cvar\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u0026lt;\u003d 50000). Then, the following line contains \u003cvar\u003eN\u003c/var\u003e integers \u003cvar\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e (\u003cvar\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u0026lt;\u003d \u003cvar\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u0026lt;\u003d 50000).\n\u003c/p\u003e\n\n\u003cp\u003e\nFor the next \u003cvar\u003eN\u003c/var\u003e - 1 lines, each line contains two integers \u003cvar\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e and \u003cvar\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e. That means there is an optical cable connecting router \u003cvar\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e and router \u003cvar\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e (indexes are 1-based).\n\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\n\u003cp\u003e\nFor each test case, output a line with \u003cvar\u003eN\u003c/var\u003e integers representing the sum of \u003cvar\u003eF\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e (modulo 1000000007) in all solutions.\n\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\n4\n1 2 3 4\n2 3 4 5\n1 2\n2 3\n3 4\n4\n1 2 3 4\n2 3 4 5\n1 2\n1 3\n1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5 10 14 19\n10 23 31 41\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\n\u003cp\u003e\nIn the first sample test case, there are 4 ways to initialize the operating frequency:\n\u003c/p\u003e\n\n\u003cp\u003e\u003c/p\u003e\u003cul\u003e\n\u003cli\u003e1 2 3 4\u003c/li\u003e\n\u003cli\u003e1 2 3 5\u003c/li\u003e\n\u003cli\u003e1 3 4 5\u003c/li\u003e\n\u003cli\u003e2 3 4 5\u003c/li\u003e\n\u003c/ul\u003e\u003cp\u003e\u003c/p\u003e\n"}}]}