P18674 [HackerEarth] We all are aware of Gaurav and his love for "weird" recurrences.
普及
题目描述

We all are aware of Gaurav and his love for "weird" recurrences.
Recently, he came up with another of his wierd recurrence namely the "12321" recurrence.
F(n)= 1 * F(n-1) + 2 * F(n-2) + 3 * F(n-3) + 2 * F(n-4) + 1 * F(n-5)
He intends to make the use of his new "weird" recurrence for his latest encryption technique.
Rajat, an ethical hacker and a friend of Gaurav claimed that his encryption technique has loopholes and can be broken in no time.
To prove his claim, Rajat needs to find the Nth number of the sequence formed using the recursion as fast as possible.

Using his knowledge of hacking, he was able to get some seed values of the recurrence that Gaurav intends to use in his encryption.
F(1)=1
F(2)=2
F(3)=3
F(4)=2
F(5)=1

Help Rajat hack Gaurav's recurrence by your programming skills. Your hack will decide the future of "Cryptography".
Input Format:
First line will contain T, the number of test cases.
Following T lines contain a single integer n.

Output Format:
Output a single line for each test case, denoting the value of F(n)%(10000007).

Scoring Criteria:
20 Points: T ≤ 10 and 1 ≤ N ≤ 25
50 Points: T ≤ 1000 and 2 ≤ N ≤ 100000
90 Points: T ≤ 10000 and 2 ≤ N ≤ 10^(18)

SAMPLE INPUT
2
10
29

SAMPLE OUTPUT
524
8647330

输入格式

见题面

输出格式

见题面

样例输入
10 11 6 25 11 23 21 23 8 2 4
样例输出
4405860 6099346 6881865 3899797 9532312 8722553 3103483 9737148 6407874 6984212 5491563 3249576 5680187 6947267 4179033 9331464 2862581 1249720 7432123 1239693 6779029 4603051 494372 1159016 6427788 7890583 4922140 1791218 4791106 86934 6293576 7579315 2125288 6761052 1661597 2921746 4158529 2150129 9643906 9558055 3615884 7208821 1690432 6100080 4323531 5449590 5871136 6537520 3694201 8808183 9036618 9996449 6529733 2056799 6858350 77571 2345058 9387808 8813462 145130 3343389 8140264 7579942 7347589 8828351 5998580 550654 3657320 7582377 375100 9602106 2754798 8056021 1599988 5476799 8517738 2259549 7689145 4692382 4415776 8632573 4933148 2265828 7083228 6662568 5709289 8640144 6716647 3844121 2927561 4518489 7652149 3664390 2279309 9059063 2435581 8205596 4445532 5172587 7509264 4187433 5122222 783328 43453 1084199 9597587 3221672 4509806 726428 8767597 7896478 3463059 1436913 4473021 1121837 7425437 6144912 7714678 8542819 9713477 1838887 8231667 2201020 6691717 2476466 6948361 4111299 1612495 7796002 7698174 9173465 9344936 7784370 3623450 9409628 4114963 1993215 6787961 7842935 7509534 5788034 329227 6354422 8938962 2748691 8517248 7905330 3556232 2897444 2633335 3415420 464784 585414 6593268 8926538 6483121 5841499 7035951 9738332 7145986 1432396 6872540 4433272 6535103 528375 5123450 7058554 9787441 4981191 293483 5176465 6400417 2715457 4186094 8675197 7200722 4912717 6572104 6204644 7803597 561392 2979112 7002239 4941267 7802808 9753010 3453598 3924885 557682 2342840 9137398 9043519 3594913 8606191 8055486 5443145 3056917 6650468 4655232 30537 970790 2573616 2234499 1482172 3708573 5146460 6069377 4865350 6430774 3528222 4679684 444031 6926900 8511898 703555 6772190 661735 9554389 4013577 2572279 1862709 1898550 2762185 2669914 2221490 3411809 8839447 103495 2039591 8638348 4959434 6467797 1274187 6722136 5078102 771912 8946062 5159533 7380162 1284524 9701411 9521313 1336916 5285155 4795936 1719989 876813 991049 9080330 9487068 7657855 491040 6400386 4267187 528488 6346245 4748632 6567764 5042530 7764151 2811908 735929 8705855 6645374 3000043 839204 8605812 9411950 8086621 2790947 2494007 571929 9657537 5586498 4163621 9474071 8172663 5224775 8585271 6982143 6980578 7466823 7765117 1562164 5406858 8193353 2986571 4243822 9559191 4588285 3160020 2995258 992399 2751246 6638701 3292932 456900 398556 1898789 2603201 6320652 7428051 5445933 194512 1021283 4621789 1277909 6873071 1651450 5667318 3642397 5004872 6471976 5798642 6333300 5017872 1996937 9529645 2790603 1180989 175590 1334896 970151 1949612 4368726 7606091 6096069 5458708 835618 2460470 490994 5941922 6877085 2846060 4820302 7681170 8881775 5871173 8967326 2604558 9856288 7112017 4045486 2361045 3601585 5712794 5340119 5401183 6174598 2386350 101322 2816943 457687 4985875 7689885 5210988 7482168 8447822 4345012 9909782 8505680 9104107 4158274 193412 6049922 789449 1681289 5143252 4862667 1242935 3628548 1661548 8796390 8892276 1240088 4771902 3201849 7868217 8248182 4013577 7313817 3104836 4647991 3264615 8086621 7897302 7598415 5006846 6114389 7829721 2693763 9733277 545693 476017 4818331 1302295 9204377 2206113 1076594 415019 9054604 4111299 1470112 6069689 3002826 4630382 3898968 7557852 7903811 9000975 2591943 10410 596367 9006287 1692077 4092976 6751808 9178799 1598867 7847778 1890755 597473 4253866 2768319 668794 7231316 472493 9615575 1164912 8509647 9825789 9421183 7907176 7852934 166904 4439750 6864720 5527887 4857972 1463213 7575448 7451340 1493264 6887780 3053524 1448290 2122563 9001427 3303992 6665198 7245942 1970319 7144773 3422251 1613873 1853937 7144531 1925471 8110923 2219449 4757090 7698553 5759696 2678313 2821063 7702360 5119871 8269599 8172536 813832 9588367 7968827 8629600 2890732 5043958 6909033 2410176 9889916 8139312 2970232 9097964 8402153 1306368 6511714 8927930 5654124 8404271 2799061 1591856 377440 9999645 4680240 5962827 3353741 8427852 1213847 7039589 4154682 9685305 1084022 1062724 5913085 7597653 1797130 4502447 8551932 3340983 2656056 3570294 504955 3669472 4809122 4421357 2909515 2196985 8575914 5652762 9419554 8408322 1629112 3929811 3750957 8545184 4660747 8906888 3455559 7604167 4433134 5149266 3912137 875623 9650701 5266831 7003052 4724127 5824188 8673224 9612720 2319848 982205 1724333 2562834 8395951 206173 2200673 2442607 8419559 1168913 8630140 3350414 1838314 6084647 1875327 4913322 8779420 9751786 7838130 9675677 2009019 8000880 8484798 4217604 7742595 9849481 1359131 5842 8842088 7291287 1612983 6410035 7490183 1212140 1692347 6917360 7975832 3360120 1427588 7969083 3358585 6615280 3104719 9790793 5095614 1032819 1195461 7431481 3702653 4539033 151475 1957219 2916683 1582743 1274888 1033617 5957671 5330673 8982564 956534 8881185 3047833 6117185 2421857 8003952 69005 3734619 1635235 2980 5812696 4714949 6618675 6791887 6390600 3523028 1687000 5488018 8182206 6412627 7372778 7016158 9732102 6077000 7403756 4387203 430780 4175375 1016770 1756216 5376199 4891861 9406056 4597720 7614856 4487935 1820978 1979876 8815921 269031 6434633 4652289 2226070 3977041 6354267 9644629 2415940 7273023 8606166 9218030 520875 4441342 2534078 649829 3658763 4350513 5930042 7460400 3835102 7840186 4404163 1406601 5072782 538684 6317281 6485075 6797914 4749535 4748335 2976728 9330841 3992387 6907305 8847134 3349131 4487935 9480786 10600 7749775 2438350 7239431 545693 6633703 3515638 1275085 8457778 3437332 3918179 1806289 4015814 7389229 1066586 9985569 6149345 3467067 9453234 7249531 5203160 3476359 3158035 8501431 8160122 9664687 9311369 5798012 2535140 7510172 6653339 2658979 876813 1825323 545122 6132047 4112712 2375030 2001189 4947802 1551398 3596555 8591929 1149289 2817737 1690432 1741417 5017617 8934459 6265462 3568522 7014152 9256910 7008826 9062033 1790000 8945777 4582945 9805123 6026290 5589624 457946 58057 9005237 968126 855633 2652952 2362209 9451048 3640067 5814397 2460706 3753193 493654 561630 67124 9949074 309184 3911380 9792886 9616096 5564852 7385744 7065643 1599988 5124335 877828 8717441 6069754 3357523 9745101 6621937 4939781 6809637 2363234 7306080 6214139 4758967 8379380 2153297 9093618 1894703 8658563 3082411 5512335 7142698 1157821 8027869 7799000 7410333 9548890 2670157 2581186 9860631 5454124 984943 2098673 8215436 5275547 5999282 8113425 7019628 8759787 1443578 3184120 8740602 4581025 148217 9515077 4845192 7350762 731129 1082605 8819338 8238188 3685578 3193066 1785358 5044001 2209969 3857511 6639522 6844340 2386421 4536991 813832 5431677 8263621 5940163 9897039 5296750 2708911 3338661 8375234 7223812 4188580 8285692 6566019 5689278 8101340 4119755 3409921 7562045 638697 8630140 1090769 4960356 5781326 6281692 6301718 7137733 540484 4019419 7620848 7967876 1598652 7521530 7543014 6505730 6577479 9318159 9092901 4958039 9161453 5405857 8572321 7040906 1154963 3409834 4492849 8377458 1748766 9371289 5454769 9419847 7720767 1797665 6898458 8627806 6395092 7478038 9730874 1930921 4900003 7440930 8082034 427827 3409834 8940561 9419847 3735897 1047030 6409505 4479330 5552554 5491481 4313898 7245626 9201342 5835066 311343 5328218 8271027 711416 780387 2474586 5014264 7749691 9757242 3322422 1613895 3999093 2782209 227714 9141900 5411555 3420495 4855226 6274129 7097646 4067547 645758 8841334 4046114 2041968 1661597 5956617 9912623 9166250 324927 1957039 3842765 1914172 529909 5760164 2374284 4076366 4339136 3360582 6579565 8771963 9170523 974013 7771366 2735591 7905492 7401941 1671647 6468618 3511496 6837167 9068263 1447532 2842951 8312940 2927529 7195197 6656826 1522022 3064822 5775588 2067398 7761448 2337803 2811907 5323112 1697709 8269331 3988218 1410791 5224921 9603725 3002804 1332274 6125866 2320254 1345504 2930170 4984148 2092524 9775137 525675 5055541 6397573 3840899 6374700 1914280 5875721 5422965 1894411 1356652 9103407 9123565 3324607 868007 2201802 1906076 9014176 3125319 1207438 3372623 1687773 3973620 4064945 2629576 6621113