P18704 [HackerEarth] You are given the following recurrences,
普及
题目描述

You are given the following recurrences,

F(n) = a * F(n - 1) + b * G(n - 2) for n ≥ 2

G(n) = c * G(n - 1) + d * F(n - 2) for n ≥2

H(n) = e * F(n) + f * G(n) for n ≥ 0

Input

First line contains the following 10 numbers in order : a, b, c, d, e, f, F[0], F[1], G[0], G[1].

Next line contains a single integer Q, the number of queries. The following Q lines contain a single query integer each: n

Output

For each query parameter n, output the sum *H[0] + H[1] +......+ H[n] modulo 1,000,000,007 * in a separate line.

Constraints

1 ≤ Q ≤ 1,000,000

All other input parameters lie in the range [0, 1,000,000,000]

SAMPLE INPUT
1 2 3 4 5 6 1 2 3 4
2
2
3

SAMPLE OUTPUT
193
609

输入格式

见题面

输出格式

见题面

样例输入
639426799 25010755 275029318 223210738 736471214 676699488 892179568 86938832 421921820 29797219 1000 0 1 218637975 505355288 26535969 198837650 649884438 544941481 220440622 589265684 809430457 6498759 805819252 698139395 340250516 155479499 957213073 336594545 92745843 96716376 847494367 603726031 807128274 729731787 536228091 973115764 378534377 552040631 829404665 618519752 861706901 577352145 704571836 45824383 227898275 289387963 79791977 232790886 101001429 277973603 635684444 364832179 370180967 209507030 266977822 936654588 648035385 609131006 171138648 729126798 163402493 379455442 989523351 639999760 556949744 684614251 842851921 775999912 229048072 32100243 315453048 267740876 210982843 942909715 876367627 314677881 655438665 395631901 914547590 458851853 264880166 246627507 561368134 262741608 584585990 897822884 399400505 219320759 997537607 509526294 90909412 47116375 109649130 627446042 792079365 422159967 63527706 381619286 996121381 529114345 971078378 860779703 11481021 720721820 681710369 536970330 266825190 640961799 111552173 434765251 453723706 953815928 875852941 263389051 500586113 178651880 912627840 870518570 298444791 638949495 608970212 152839268 762510800 539379030 778626479 530353672 571896 324156057 19476742 929098617 878721878 831665530 307514125 57925166 878009600 946949446 85653452 485990463 69212518 760602166 765834430 128391464 475282378 549803594 265056629 872433041 423137940 211798205 539296089 729931069 201151063 311716291 995149357 649878058 438100084 517575841 121004195 224697337 338085562 588308719 230114732 220217384 70993086 631102957 228941784 905420013 859635401 70857349 238004634 668977778 214236807 132311848 935514241 571043093 472671026 784619425 807496998 190409914 96930814 431051182 423578623 467024668 729075850 673364547 984165212 98417871 402621282 339302605 861672537 248656334 190208908 448613548 421881640 278545144 249806448 923265600 443130745 861349105 550325313 50588329 999282469 836027585 968996258 926366983 848695735 166311110 485641125 213747299 401040292 58635400 378973119 985308844 265203058 784070602 455008367 423007486 957317641 995422690 555768323 718408276 154796825 296707825 968709365 579180291 542195201 747975561 57165272 584177595 502850383 852719892 157432728 960778904 80111465 185824961 595035107 675212554 235203895 119886614 890287315 246215348 594519154 619381510 419224915 583672289 522782716 934706258 204259199 716191801 238685952 395785847 671690223 299997080 316177196 751864493 72543114 458285523 998454441 996096448 73260721 213154312 265200415 933259378 880864174 879270243 369527089 157746832 833744955 703539925 611677766 987233064 653976318 7823107 817104135 299378752 663388715 938930004 134291114 115428670 107035977 553223641 272348212 604829827 717612187 203597312 634237959 263983901 488531852 905336491 846103714 92298467 423575772 276680224 3545689 771119223 637113377 261955262 741230909 551680421 427686919 9669699 75243860 883106394 903928572 545590289 834595020 582509567 148093785 127445519 308258350 898981489 796122305 860702582 898924637 210076538 249529739 102793621 780116242 884134702 406377390 620661510 154553338 929881016 864605697 976206033 810771720 881416205 24786361 736564472 332185468 930815886 802235139 864064029 810749317 266805709 787374509 108095626 872166783 858593252 222433717 816586606 460303235 305190867 795345499 227595487 23664434 193129788 328261951 864352942 966889105 279124993 641481739 399678384 981149688 536215733 939237141 115341751 970400611 178567816 962534316 265466362 108402547 434563758 728545061 313677314 606208853 511423060 385195433 576588044 254722506 708785284 1691278 925575166 538451997 719429999 741950078 670628505 364221472 69973811 664237685 330200036 313915645 848015280 719754263 300322268 309284662 408392909 402400387 295655202 127287799 420446334 940363671 677317945 902805546 615514916 300949874 547937213 405939 286913717 429888150 579984781 654705624 464988190 442159799 213701401 473186186 901180826 796024760 169691396 84795536 515452010 632940856 335188255 818423465 751138138 672795671 224640666 199129932 24425387 244842544 475136344 849737695 72828229 414441011 629765381 194435236 696354251 494377169 243984439 656058011 5544818 750964477 770046189 106587296 425146194 175886681 957966043 517957750 50218385 249198279 848336348 456461825 801416602 667577733 987892454 595452319 950039609 891425926 612652323 719273961 504778165 830569170 547871951 897208104 743655442 474674437 259191548 247239737 637661437 765813685 521299813 626748437 274597447 77483353 285728151 271715107 319709568 540152223 138374061 231261479 693949812 706419142 64228850 407599370 542611141 415774234 206834389 420143518 904838479 584079414 695522987 856732033 765594576 380381029 5896083 351758803 753475125 853447951 953430339 419021283 747515669 546132310 603252589 220538694 219421634 435835976 29024819 336129544 679141885 404316669 165044731 467390149 127627797 622256961 26966451 394020256 564391983 27102046 642749648 135699487 461698444 50284633 379103864 211660284 326845805 761229708 379126215 752009824 831924285 252271532 81906232 19383287 539419048 999907829 349960344 650144093 781233050 651754655 754233204 949611733 199360682 20380017 152382345 126220975 669458845 563969582 217964541 699464971 766898099 167789143 607247494 747925652 114532871 819301175 964720773 108098749 25678425 311957244 677347287 958172839 396654441 715014705 75996477 690614416 627242396 101901305 772480885 850293239 600411615 121055065 983844352 782635347 347203765 428378013 370570876 505960790 341231175 849575627 822330918 105538870 960787568 635585106 828707311 707308644 435487145 733795304 965473732 270082396 808199219 538172906 483497504 435574493 731026215 268395538 851713160 830731019 86662898 881631184 243863439 464708467 610331704 378989304 28699997 850952837 181839857 212119850 797832357 340338843 880319980 701183751 276268576 10151114 948062578 85612962 720074664 488577847 758164654 690609340 645902900 490821335 792932868 93053350 221596400 691787155 306206030 581555585 473260489 530921931 425503813 745935437 330791297 702854942 270916427 251403676 120655884 192584293 119554741 535863965 762189610 185149842 216384640 484198587 724585001 976607023 524636869 282998703 100526108 194117578 227483163 179441543 14148367 534135089 274311327 974294932 553358967 697417393 126279493 868461198 490878695 872719735 574064220 469396945 440468798 184363670 51376717 941063597 477729187 822115646 400707442 74082170 629445707 53609074 149197584 562839597 303835512 993918123 118451562 764443446 606317651 790740830 225687137 522572535 450514465 442721004 860166666 990031261 305380244 621027321 609630912 740089306 947590201 207787906 211025195 660428137 157057093 173813548 75064868 2675722 450503705 593811195 291259289 231476234 706955830 702987558 454031326 687384920 923911045 787828027 625058007 661183043 933668459 425138966 544562379 647634724 908411446 826631160 71409836 165922789 307611812 748957722 569207049 288610588 124353658 688677991 699733685 942676241 500472177 493795219 80441851 39860784 432028664 322321583 250367902 91326886 961911103 835958614 575199109 950786278 999572417 672281584 269511026 40231673 756268831 470500823 651509490 916072788 181489147 585329625 634784720 491725802 91242406 347961056 333308393 670133510 857733095 329803663 693673674 288217795 945193540 813566035 550096609 454825909 314517157 323273786 970184727 404175057 514596252 988119215 657660387 542593594 413247571 187582541 361779359 756443154 625408742 759990536 203558238 549219639 927672761 438116095 698250029 121426083 973146816 608871667 239297462 158378163 550839007 552251409 93209201 992257140 912929879 461447894 117466149 832143174 498375505 716603326 508872015 273424896 834723946 980244633 243730906 551265077 383586013 921868150 508240892 879326256 864026935 276247403 790006182 414942423 934248394 507737676 820549474 282838983 298555850 586937723 998902334 489640347 148595418 538580578 345123942 551917417 543430063 455344617 321777350 188652373 697498428 571797642 233562446 775544475 43647299 744705152 705227881 811408903 386078752 663688830 820747552 980818139 495328650 37019611 502291150 590180429 869700314 874190374 440306210 525951087 456928074 722443828 409978620 654781327 154361218 469490601 969203631 338561234 692704599 649836653 851765293 852341337 859342185 380009397 316661154 718717425 759401810 872383018 35899099 68420747 631161017 920929099 997425923 746766367 433971472 98443126 633747829 872579233 443678552 694001163 903424062 45990968 796143465 293367776 374841090 145569795 531166318 565928062 792519474 169983649 78968350 870839599 619710369 240829792 912829016 143117720 461149913 253977339 255326708 9397431 804633077 901209424 677610886 157975622 441729784 345565624 587571705 638938702 424308938 250098224 845303925 199216999 384693249 483208061 237205702 571922692 574811930 992692044 295230754 977944485 658229816 274480380 565929017 685799493 744668841 49044250 606406493 496727287 904155291 286194151 798860120 607064998 352320956 636617878 620891163 677764459 720928377 659181540 838337117 628248104 903403704 646340609 308932884 440823190 579573805 732359768 90133375 295110451 747480865 175640070 132159797 539407759 971489582 530852374 913486975 830472620 256970084 824689813 481847830 806488494 746559351 338715254 115169707 962893293 140757015 966500210 860140597 724216712 979942243 967269748 804587644 365775049 790681969 13918655 536572308 454786028 672828382 672340798 584560092 822417302 940291892 108346102 233821902 25024649 884234846 561407382 915255909 221367200 63217041 823855352 909387639 302190174 408295856 139777012 946261533 304364584 492624619 97191998 887259309 135664048 453643757 670486219 743140122 945974086 419126753 742269015 154522902 414884527 99021634 489347038 408115886 951521526 32716286 370529959 443383086 950555170 855450194 99354624 685680266 544465862 977842530 358673841 398139643 189808562 122159719
样例输出
522931818 921495775 317265883 765193023 690748284 601926879 265336565 208347473 147013789 542601143 278541498 419802816 578498899 629696258 962631844 347890068 426350637 257753554 853302634 510136284 383107500 608616570 460021516 912275016 853352212 419337115 892424686 554366923 686162395 451476468 528422379 543604822 573684660 825367840 564334818 868940497 107508341 138029217 151072046 853870789 413762091 532947690 817538063 44232493 359934625 677039938 912847183 139240511 465631494 176382938 166505627 931857383 799013635 85838969 403659835 414266127 484208200 583158713 508079126 323386792 763665097 983342775 678229253 683960862 400256766 576710006 307869640 769230458 512824016 211290116 337893995 332451526 856422554 750607120 292504633 301628290 144772831 18778353 611988106 58836757 57610701 240980784 340023805 59673352 855331362 398320136 956781241 84724039 484292872 266991143 948804814 353860690 524250224 198555475 404523591 658618033 954921669 480141144 901192826 464373956 220806389 312483852 328772786 449958163 179230597 311147763 650608967 187636047 624518635 792270150 636931709 599241762 331632936 922437348 575513651 694726107 898023240 902337045 755303452 111508457 252560101 145664657 803587633 764330813 400998804 210129495 306849918 944333492 118952422 453469964 933681538 626240829 542156941 15447784 360252662 549822986 433996615 908054661 377315111 659986215 198196292 631056963 956985545 760643706 451058182 688623466 730505106 720384743 243294297 961345071 641530237 373481507 789372716 596580121 871115760 801135595 313888486 81225814 390400071 276107915 987078960 714872975 310745368 927713066 106991266 540043979 41852686 944159339 422522889 705893518 875117621 605710755 640676345 965575132 228530410 280430800 801400397 87269380 11546771 810352236 305006604 195407901 511952337 301554914 283979177 742845526 737858332 484729787 183122561 552154385 325629337 733338847 773555769 890299664 571450305 579734393 390292432 828389367 960767395 604865578 728636577 345143874 385449862 133133201 349161841 821423587 309526449 479676888 118925553 578133135 81964111 543335487 886932357 511281678 661343003 31217270 313036233 811145161 817330638 959801051 954461986 903205152 909078374 555898968 107459140 439388779 366255360 869460859 72100492 292864998 989730421 819289517 300025275 831072570 173362144 542075056 120080564 806499442 679222647 869826033 757659260 124433214 964407151 909898945 371006723 155211146 18812223 16633506 551225290 926783298 708073857 170508430 135781056 844075796 883695511 180485531 904333349 490869849 769006793 873438096 996219195 121998299 610412744 875778233 119825645 81366415 748836822 247960006 865743288 502642548 880200959 336387059 745004534 464537183 481648784 941333208 196544781 278047592 492878540 278716142 751453441 767487777 754201850 666558444 39208367 191799984 137627215 181198895 780672663 58590469 255076128 121898888 493072218 374441927 489134729 858856818 215578650 220384549 788526970 779827636 260675207 944739158 751253964 915251499 593735968 69419530 864141695 761749887 978008809 686650656 973541837 234654187 88721189 640695345 868933312 684835986 149556776 881860481 149758751 798458611 509946223 600205862 335422511 236604125 799866845 837573154 919499088 194038193 156131131 290782623 578838711 766401624 858911000 301748673 617171477 6249536 522497561 668410792 259562610 329727010 345733453 268347100 850262596 685336540 567666344 128352021 266903357 644619276 865561807 608370135 992472843 441889689 332372019 856997268 217064118 258970382 987108980 696578950 400507044 517651829 233785460 613406219 196011319 968543749 464976728 220198536 976601885 795123698 544286797 590819155 456909816 352278555 814432388 17424508 568331126 189401246 836416088 182731457 665223364 282098584 656835528 721311401 388674576 30094626 821103204 618587729 658021155 258185019 645876131 564002126 631547011 647979638 381371014 184288990 630465064 681077085 477587124 341390969 594335487 987664643 442028779 876982517 145540335 196975393 371397526 684635953 819597407 421333899 726191645 322359233 467978779 995751753 344574763 387586396 703234372 580880317 688760906 387351409 296738431 625183460 911807339 438803360 291508521 678114989 721593929 495112169 755242171 323996 47277813 116517345 298148202 530979468 589075604 996374293 777608819 724700403 260242285 374410322 356869844 249828926 53384797 979894502 16334011 453731927 756991256 135170937 113217017 221572707 491924274 182038676 867009149 71237758 120352252 629696345 780275355 212432391 1337644 767986248 639471466 337290074 90646547 436594208 57310774 661068300 45265549 831131080 118784620 652820789 928778923 78978542 180941589 209677837 4342286 532108713 232500052 770959728 138372198 411119611 588489441 591564091 809509695 336393926 887652033 203792200 909072210 124082285 565096766 611000676 860916772 629449801 226228243 48158420 713582562 951516061 495503703 14047058 572889895 17674645 765801353 679212976 651834537 675509857 310266809 925303002 659307553 187291116 920133076 32861490 465721718 191076066 310110944 379919282 269549582 578399716 604406206 777280918 103381324 355259021 782049750 989368889 102178609 146198160 255977387 724079617 741723413 320178842 289772966 664464540 764810371 351399598 327433775 371599026 667034604 985486667 605024478 350738262 427262882 243216494 751995845 894596670 106640188 322940520 258197181 458968362 622959141 379672157 659640168 939497283 519441680 477634429 176725922 877120625 745897872 807283933 944484597 857513945 174297600 918403807 100684242 153120797 440249625 626809652 240850482 822573561 516716705 965059679 262339436 564780548 83926125 434130700 769828988 356077798 809297365 133582339 581445330 867964254 317186620 120658514 931566190 950895538 399355826 317906779 294111605 531589829 984640104 248703916 8563619 667331079 313424773 882700207 950550290 539623261 253275413 994340696 807282422 637516621 979441178 710005550 553321445 964703456 665516000 415350456 714114433 709527227 525305038 355629729 561457914 736594347 954439998 893313262 78267897 667847100 767963685 118698473 11672483 404253869 208583064 806729858 927030164 26630548 638487028 261081413 303054285 872760639 182368839 924042885 491599334 137976888 500873344 785558498 383944557 638585035 972249712 124459559 452561142 85502994 968238142 943211250 889512621 828349650 711041807 722457116 966051264 63019666 662870334 715808325 172725422 12263464 322275001 632022607 441054955 34855117 818356538 715590934 245356513 144985895 426354307 46659819 930532057 401296129 877180516 824892392 649926044 589820416 644793411 648518386 468917448 994119266 424609568 207327871 653484050 975923308 110127870 423633007 155004679 63745981 223596668 161609097 805331505 81650894 893754218 470584748 963755967 662916140 409006636 984093377 338876513 683674578 233980967 861327466 5643080 980226184 737060392 701472423 814501844 15221196 845190650 649065080 236838552 245047949 488409141 556190003 115294388 59257403 975085305 768645366 738179910 24061714 794606605 515507912 812253646 823968265 435364661 586048263 472567454 688285704 665297574 640499331 458509260 479263706 341960653 111121998 703912320 320827994 364733626 745967357 833604557 10146484 301151388 689587362 603825395 416153528 525361926 252906038 811706048 638565936 511894753 132345449 987166109 129182577 184381659 946350640 604274595 434639117 943672986 846975454 811103539 485855711 540201302 544452844 631341815 520183002 611465054 165573959 841120576 44966646 613535673 699168813 673003276 694440238 33784780 206144918 539530279 53806842 980796850 191312916 904271743 224062981 873042256 367631294 26372648 280717671 755233712 289911446 237627759 768499636 570644401 438169818 45324233 108689535 313571135 747380820 626865202 922665156 532303400 425224585 625347683 238752012 982492322 408464438 634311829 787951936 782455056 157540961 201197067 132606238 436411473 143229834 271428673 362175340 72837907 101387718 941984200 402938545 818779179 954948773 435965123 788526329 281167400 749989482 904614361 479357192 465019729 400870181 695220104 562885935 812067119 510792075 293041739 64525821 168690750 30439420 637451941 685818972 988923303 311616116 513944086 581026956 737927853 535226693 358247265 46152957 471980011 69372632 151262952 764569516 444919359 312819676 480205953 219993273 369959429 936627783 640389903 846437852 863642890 885762569 384127122 287026270 740947719 326462971 120358731 341007354 636527655 220148706 279994813 418807206 855189017 674832813 599795312 797690445 822877580 659906569 427854578 863038111 609618847 524235414 838932561 817929661 78994329 795770815 435672423 209070833 160371131 272216132 434057253 47695004 4780898 478840030 572099013 949745625 418083950 332177986 531066960 642438350 560900874 226271097 448697753 450498414 218452108 518193806 867542850 255433986 881242925 220753544 197638953 827460746 278066349 329701784 756985505 685286950 641459977 541835005 633688918 247538365 186556480 45435297 991614797 100528803 66335552 925033305 806550002 602869981 225342878 648238189 23555152 949211349 89118829 694399727 465014347 463823153 236182342 774682471 136401382 208108932 771690052 96402482 928638075 267426336 394341532 383376494 915131812 276030492 359406182 679008407 941972281 890265870 839306771 786292793 983331075 120631414 162989426 912506159 808880330 859138371 985006888 244046267 397393673 304015643 599200882 132106125 630478555 302561997 516356615 277776678 138935199 17465222 882888437 632005158 551283274 338156203 950306285 963967742 488993905 810871780 240292446 388388508 983871581 415747122 364004962 44528817 702506134 510184282 351752589 75783788 576290735 353673304 162934569 165555590 800129523 93550068 315805344 25951281 123815137 254241131 336241252 738918628 193360306 600360248 837159330 625446166 463556747 286211571 108950225 763574757 365836466 245606466 586965288 397238857 543789075 698191933