P18702 [HackerEarth] The link to the Russian translation.
普及
题目描述

The link to the Russian translation.

Alex has opened the evil vault and is looking for her sister. The vault is evil and has an unstable shape. All Alex knows about it is this:

There are n spots in the vault and there are tunnels between some pairs of spots. The graph of these spots is simple, undirected and connected.

In an undirected graph, the distance between v and u (d(v,u)) is the length (number of edges) of the shortest path from v to u. Diameter of a graph is the value of max(d(v, u) for v, u in V (set of vertices)).

Alex also knows that if she adds any edge that doesn't exist in the current graph (edge between to distinct vertices) its diameter will change.

Alex wants to know the number of graphs with this property. She also notes that the order (label) of vertices doesn't matter (so she wants the number of isomorphism classes of such graphs).

Alex has a great position in the armory, so, don't make her force you...!

Input
The first line of input contains a single integer T, the number of scenarios (1 ≤ T ≤ 500). The next T lines contain the description of these scenarios, each with one integer n (1 ≤ n ≤ 10^6).

Output
For each scenario prints its answer modulo 1000 000 007 (10^9+7) in one line.

SAMPLE INPUT
3
3
6
8

SAMPLE OUTPUT
2
7
21

输入格式

见题面

输出格式

见题面

样例输入
500 3 1 3 8 7 4 1 7 8 5 4 2 2 6 2 3 2 9 3 2 1 2 6 3 1 8 8 2 5 1 1 6 5 1 1 6 7 3 1 1 6 3 1 2 5 1 2 3 3 2 2 2 10 8 10 2 10 3 1 2 3 6 4 3 2 10 5 4 5 1 9 10 5 5 2 3 1 2 2 6 1 9 9 3 5 2 7 6 2 3 8 3 1 5 1 3 8 3 5 9 7 9 8 8 2 9 6 3 4 7 4 6 8 4 10 1 2 10 1 10 6 8 8 6 1 10 4 4 7 8 5 2 2 4 9 5 7 1 4 6 1 8 4 1 8 4 4 6 4 5 1 1 7 10 6 7 1 6 8 10 8 6 2 5 5 8 2 7 1 8 7 5 5 6 7 7 4 7 4 3 6 3 9 6 1 7 9 2 9 10 3 7 9 6 5 8 10 3 3 6 7 7 1 10 10 6 1 10 5 3 2 6 6 4 5 4 6 8 7 5 2 6 5 6 9 2 5 9 3 5 9 7 3 4 4 6 10 8 7 3 7 8 2 2 8 10 2 8 6 9 3 7 7 6 9 7 8 10 4 9 10 10 5 6 3 10 3 8 4 9 8 7 6 4 3 10 7 5 5 5 9 9 3 9 8 6 4 8 2 9 2 9 10 8 7 10 4 7 4 8 3 1 6 4 1 1 6 2 6 7 10 7 3 7 7 9 4 7 5 2 3 8 2 5 10 9 9 4 10 7 2 6 3 2 3 10 5 10 7 6 7 5 9 1 1 5 2 5 1 10 8 4 1 9 10 8 7 2 5 2 5 5 6 3 8 1 8 2 2 7 3 7 5 7 9 5 1 7 3 4 1 8 7 4 6 2 9 4 5 8 2 6 1 6 2 9 7 1 4 10 4 5 4 8 4 8 1 5 7 2 2 3 7 9 6 5 1 8 7 3 8 9 1 6 6 6 10 7 6 7 1 1 10 10 8 5 4 2 9 6 6 2 2 10 4 9 10 5 8 4 6 9 5 7 9 1 2 5 1 4 6 3 9 6 3 2 10 10 8 9 4 9 9 5 5 2 1 9 6 6 4 10 6 8 6 9 4 6 6 7 6 3 8 3 8 5 7 10 5 10
样例输出
831477088 37 512668660 992738510 492890146 248686566 359869203 590000073 326052224 877311277 65793 932366349 992738510 95057789 326052224 831477088 899770637 670970039 227875486 759212534 831477088 512668660 932366349 670970039 2081 134225921 73 258799464 438655639 32897 335485020 2081 16513 759212534 95057789 65793 439985166 524801 805069165 932515764 966257886 756334334 258799464 24288736 326052224 932515764 848263543 258799464 536887297 147516403 131329 996369259 11 492890146 629754384 504902357 517598927 455750971 158945093 459655278 2081 517598927 938996694 919310555 663026116 756334334 134225921 805069165 2081 879606271 79472547 629754384 2081 459655278 359869203 8390657 759212534 879606271 146534819 73 326052224 831477088 33558529 848263543 590000073 180000138 248686566 1057 495758778 326052224 517598927 439985166 134225921 335485020 438655639 158945093 801960242 293069637 497373131 180000138 524801 985780291 536887297 335485020 73 900980125 759212534 801960242 335485020 663026116 492890146 1057 1049601 293069637 137 4161 831477088 831477088 2098177 4130609 8261217 376036849 48577471 134225921 459655278 9804706 938996694 73774586 2 227875486 919310555 899770637 662954168 439985166 273 21 919310555 326052224 79472547 992738510 9804706 326052224 919310555 258799464 1057 24288736 932366349 831477088 8390657 610138322 466183175 756334334 32897 16513 799541266 2098177 273 663026116 879606271 831477088 663026116 877311277 7 295032805 359869203 48577471 497373131 814877196 32897 877311277 459655278 992738510 492890146 985780291 492890146 662954168 4161 79472547 16513 629754384 4161 879606271 670970039 16513 8390657 439214658 1 2081 610138322 359869203 805069165 137 146534819 4 495758778 610138322 919310555 466183175 67117057 670970039 1057 8390657 662954168 134225921 932515764 992738510 2098177 466183175 801960242 719738405 985780291 424131772 919310555 3 719738405 590000073 662954168 1049601 752073697 134225921 67117057 495758778 4 670970039 4130609 180000138 439214658 248686566 524801 536887297 590000073 2081 180000138 24288736 37 879606271 879970331 2 16781313 759212534 932366349 799541266 878429315 65793 536887297 756334334 158945093 2 11 517598927 996369259 134225921 466183175 466183175 258799464 938996694 831477088 932515764 65793 180000138 8257 95057789 4 759212534 79472547 899770637 48577471 879970331 273 439214658 799541266 899770637 877311277 4161 48577471 512668660 67117057 2098177 610138322 65793 805069165 273 227875486 759212534 966257886 899770637 752073697 2081 497373131 33558529 590000073 4161 512668660 258799464 932515764 131329 1057 326052224 37 424131772 670970039 137 879970331 1057 992738510 629754384 801960242 16781313 848263543 293069637 293069637 3 1049601 131329 536887297 268451841 262657 610138322 610138322 4161 831477088 16781313 4130609 439214658 8257 262657 8257 492890146 48577471 966257886 146534819 756334334 629754384 11 439985166 37 1 966257886 293069637 147516403 79472547 95057789 335485020 295032805 48577471 268451841 48577471 932366349 65793 158945093 663026116 33558529 495758778 439214658 517598927 459655278 4130609 48577471 512668660 991517555 805069165 985780291 11 517598927 273 438655639 814877196 424131772 147516403 4196353 932515764 504902357 326052224 495758778 877993380 11 293069637 65793 4161 899770637 158945093 848263543 190115577 21 424131772 919310555 180000138 879606271 1057 131329 439214658 1049601 966257886 492890146 504902357 512668660 517598927 147516403 878429315 158945093 134225921 831477088 899770637 48577471 37 878429315 756334334 1 899770637 932366349 424131772 32897 536887297 756334334 1057 137 1057 95057789 985780291 16781313 1 512668660 3 801960242 21 966257886 466183175 293069637 293069637 966257886 529 146534819 3 293069637 879606271 670970039 662954168 992738510 180000138 4196353 1 512668660 16781313 73774586 11 536887297 536887297 439214658 8257 919310555 805069165 879970331 4161 517598927 996369259 95057789 258799464 455750971 831477088 134225921 759212534 805069165 877311277 439214658 293069637 1 966257886 293069637 190115577 938996694 752073697 2081 16781313 8257 4196353 512668660 11 877993380 759212534 524801 16513 459655278 134225921 11 4130609 492890146 4161 4 831477088 32897 879606271 900980125 227875486 158945093 878429315 273 8257 16781313 4 848263543