P19538 [HackerEarth] A Dice is a really great invention made in the history of the mankind. They try to capture the notion of randomness and one can experience how good they are, by trying to throw a dice su
提高
题目描述

A Dice is a really great invention made in the history of the mankind. They try to capture the notion of randomness and one can experience how good they are, by trying to throw a dice such that it lands on a particular integer value written on one of its face. There are many games that revolve around the use of dices and this property of randomness of theirs. Casinos use them heavily to attract customers who try their luck in the hope of winning against the randomness.

However, by the use of modern technology, the star gambler HackerEarthly has made a breakthrough in trying to beat the dices. He has developed a device which can throw a particular face for a dice. But, like most of the devices in the modern world, it needs energy and sometime takes different amount of energy to throw different faces on the same dice.

The Jindal Casino has smelled something fishy by the winning streak of HackerEarthly and has introduced a new tournament to try to stop HackerEarthly. In the tournament, the player will be given N dices given and on each dice, there are Mi faces, with a value written on each of it such that no two faces have the same value. They have done so in the hope of increasing the randomness of a game. They believe that more the number of dices, the more randomness would be there. Now, the tournament consists of Q games, and each game, you will be given a set of N values (K1, .... KN) . The participants win a game if they can throw these exact N values from the N dices given to them. (Note that it is not required that the first value in the game has to be thrown from the first dice, it can be from any, but the value on the top face of each dice will be counted only once.) Note that it is possible that Jindal Casino is cheating and there is no way you can win a game.

Now, HackerEarthly was given the N dices in the beginning with which he will be playing the tournament. He has already computed how much energy he has to use to throw a particular face on a given dice. And he has computed this for all faces for each of the dice given. Since there are multiple games to be played, he is inclined to use minimum energy to win each game. The energy used in a game would be the sum of energies that HackerEarthly requires to throw a particular face on each of his dice. Help him compute the minimum energy value would be required to win each game.

Input:
The first line of the input consists of N, the number of dices given to HackerEarthly.
Then N lines follow, each describing a dice. Each of these N lines start with an integer Mi, the number of faces for that dice, followed by Mi pairs of space separated integers, u and c, where u is the value at a given face for this diceand c is the cost to land that face when the dice is thrown.
Next line consists of an integer Q, the number of games HackerEarthly is going to play in this tournament.
Then Q lines follow, each containing N space separated integer values (K1, .... KN) that he is supposed to throw to win this game.

Output:
Print Q lines, one for each game. Print a single integer which is the minimum energy required by HackerEarthly to win that game. In case, he figures out that it is not possible to win the game, print "-1"

Constraints:
1 ≤ N ≤ 100
1 ≤ Mi ≤ 100
1 ≤ Q ≤ 10
1 ≤ u ≤ 1000000000
1 ≤ c ≤ 1000000
1 ≤ Ki ≤ 1000000000

SAMPLE INPUT
3
4 1 5 2 30 3 30 5 30
2 3 20 4 20
2 1 10 5 10
3
1 2 3
5 1 4
2 3 4

SAMPLE OUTPUT
60
35
-1

输入格式

见题面

输出格式

见题面

样例输入
54 19 165159376 355308 269629339 812542 533672708 254611 451533246 954062 384985130 545763 988877035 492552 613602746 621804 404007286 193192 350095742 505012 186218563 328091 202783512 155442 990905164 583750 946571385 414868 647276062 286525 207013483 866938 735706716 392972 503307529 675128 633267259 263474 72014402 717848 33 36188449 420761 596438870 331734 201286912 987047 723721186 959970 579644777 183640 185407521 839533 902295659 897450 497036397 891473 356713289 768561 819466640 226236 279193848 133078 735390029 173359 688832165 433299 339792087 533312 327064109 255608 685590360 126553 827058340 261546 313938540 383414 763618511 577311 380543651 725483 263084969 575714 866694146 454428 777242850 850645 429426818 774915 119435611 651114 315111568 568814 184838571 958122 132660620 140543 962313885 837742 91347530 984938 874263984 635496 522941332 922042 802001814 247515 25 254593612 89653 37216607 409263 8320850 389993 86944990 487126 50741649 295104 276260762 555636 994131171 281852 553930597 280019 256336054 223381 539127014 591158 693095052 947956 431918619 338448 898734713 112057 389381842 592202 176078760 530039 503925550 234306 410160342 749747 332695592 632135 339273941 512680 831027212 682910 229305099 865477 163336440 400832 299838960 673581 787085152 102105 556302740 398134 97 271173643 374230 7497451 469337 429804969 786542 40289546 254708 328526844 878628 247641799 151330 194806146 43222 217946055 55931 230579626 208054 837089766 542122 807944025 281674 145579954 360879 366104936 336107 529309933 480285 84273955 451526 528320270 387612 137488587 435166 443192257 811624 738917397 18440 574004067 488464 826237098 837549 622950790 925816 707194533 456971 679141747 357079 751668504 443829 767152803 255802 445562503 521231 18185029 988671 596148586 784594 661921980 185819 797294768 75790 561973278 43669 925033527 960739 571333814 441992 757058901 105415 779748482 549 37397330 29443 992015029 2799 926817259 195510 45301302 463165 576464337 148048 255780384 399995 840552232 808728 105924160 217961 401857032 53991 520760730 542682 601933568 88939 630214885 615223 197500302 953061 345026314 358266 835572904 18795 827911593 695987 253408566 457575 812806547 156423 958185109 936341 731786577 512683 806325013 721609 994232220 563437 445827196 280615 605097443 984748 273772674 541737 318217928 435739 534688083 96925 76673699 155330 725816336 720932 600246781 713917 13792590 722165 953136662 673787 656454037 670935 581566817 95680 515192290 159594 710739459 362595 709235749 213087 341621847 338129 969044420 284475 720878956 542856 854700566 421337 240775045 339293 863515881 868709 708310168 623223 298541309 68641 803349712 262801 446075527 668323 640720140 889212 148657583 203349 128755549 248474 919189778 665972 802101644 335396 240510528 237458 72287121 91685 424971327 269013 725813789 159101 762088454 595829 791513361 634848 423804675 728706 908207621 371540 533770134 696731 34 907927606 195668 665890808 295240 5745526 365764 280996001 389577 722275798 16485 568876404 906284 883282607 551463 494788003 296651 342601387 223085 136759540 385589 907113036 560849 131429439 813165 86027364 2592 773740020 981929 8938139 303066 15660690 805395 35494381 267635 278034737 470220 221879593 369685 452577273 769828 323026803 976860 71020201 552291 212689602 434392 893999377 949124 873539683 455438 492141975 697588 972832628 576440 670759350 708183 897192810 951360 921613435 406276 411296907 397385 85758727 851204 549697141 823526 640007439 688087 29 525899489 34143 198911214 503729 582131318 507218 671257522 315935 922965333 102172 42440892 918731 796734819 505153 349403035 999989 330357369 924443 600375569 360689 913967332 981271 303911830 213413 861574627 96056 778342356 597582 924323885 208275 494867241 622011 636100712 287762 199080488 847696 48561075 600242 571788568 428613 464848413 425924 223367283 278821 691985707 721903 6766440 712272 639287382 36332 905180250 374521 630106507 19145 899776352 782952 321309609 246503 15 375208696 993350 238386108 571266 410690458 321131 747838290 868369 634595601 759443 164073990 682261 143374644 641072 258978186 196714 919589168 116070 250255907 241373 811010563 843470 883963179 391859 470599426 341685 925372304 546848 228390996 905434 7 426603793 816564 529540083 45259 864110563 694323 582907049 589728 274085161 471667 850506199 595152 213978218 924653 71 362636268 321248 878569516 938325 579502428 20282 336300048 795042 280356055 833498 655171724 671074 105349100 487832 894870633 142326 546669629 810622 660956609 918515 607753726 31691 252893828 333729 134405242 157936 254221558 261246 199739534 27029 283729967 103288 733079340 620949 90064538 778614 898625498 441277 234035318 427920 543761201 82513 42782808 194578 145008478 76872 666493351 903230 145183395 943307 91672351 794631 509060567 670138 427028303 130134 879056098 597863 194280219 550408 321794883 822488 700552762 403758 101889162 293001 216433592 853643 704999133 517480 620246134 554394 347508087 322968 474286501 738950 602459429 734958 258194255 689072 447194311 586487 220423886 497453 656806869 740528 511207763 389957 580839639 334348 422281312 880757 374322156 948082 262813774 769838 150545220 35837 278511816 40724 12233638 462394 201177422 926335 244310251 216621 24021940 29821 199422081 417804 992396960 373198 798148585 850882 83343887 262503 543073080 433134 658978256 441840 33246106 227681 358400007 287174 509082059 977380 373301164 649913 322036892 575664 744352522 154511 834777972 418227 195309120 275199 670483148 234130 144975299 805431 3398322 998689 70 159592535 137927 189400813 125985 918092660 683841 911646707 482567 699461270 699946 255002854 350991 863212602 832735 357309805 566931 474851792 538641 668148066 662268 25369150 177735 114918228 768843 472214107 920475 224089862 618836 187023733 273464 292310510 274046 841653708 607267 599127478 530180 196437780 513455 167125183 719798 546236151 126151 226180249 18489 225729937 286632 389260941 305987 659425778 379939 152087571 293472 643356320 221664 409607516 316656 673569810 571670 16060873 939046 994571062 615316 927002225 690314 780155883 367420 104944799 394552 246548872 184194 202524242 436575 538093908 409457 641633980 517316 578718987 152870 924895940 109948 739769183 558931 537956228 785077 873485941 33341 11811019 629677 995403364 911551 960288155 26681 28486586 623365 307850412 497280 406166006 693650 436376808 508670 123548175 233466 525260781 454402 829384939 443752 659094670 344175 956993001 597274 345729362 718143 313012568 513760 687869172 1723 322485501 132192 290990305 611524 524158097 60053 476949437 578126 725187137 649675 60744158 971680 914267948 761125 789215183 552021 761065449 567832 553735887 792925 89925886 644845 412289359 725949 14 168856835 462840 594511755 177436 913054282 209891 501737459 376377 920227721 930526 332706868 4954 743562328 230254 216427492 487947 829100007 180615 322847080 885902 52156790 305622 11390589 736342 417010395 733176 599611570 185997 87 910381632 604715 126566606 599265 255234165 991392 191718891 14801 838313169 497947 53261608 797046 339769347 563902 271268222 586121 307041262 307643 634993753 138712 116290088 305050 373429275 153668 663688828 237110 147891863 490435 523780456 451392 815345046 770398 500851872 512443 604139861 25652 733483401 432766 935662853 374902 5588927 162485 257526602 559209 335929743 804769 425460413 731815 132641405 921299 107187306 423582 955460032 968309 783253586 449295 375898305 950017 161484266 280720 94470048 501767 143136923 324299 574005167 520940 350937152 905341 296881653 164902 644655019 582007 653053868 758721 768684832 45217 163090626 12700 963738327 353906 805249628 518061 34266494 80249 962455887 609785 619518134 508183 600945318 4957 747877777 988547 578313759 630280 519698715 100101 435297965 458942 516608718 391355 304129783 528406 7362843 871575 60966360 945405 269772776 729566 712658653 266034 451898125 345450 214876874 318151 426710 653738 806075413 587046 582149252 914525 436389737 10058 727631052 692186 513799205 113154 412832342 279308 930011867 234801 91049023 375214 139468753 501201 258521751 77843 948421507 452587 590847716 237792 644189983 520544 12226206 550160 469116679 152484 943864241 309423 518496083 623869 989438718 828512 143289932 101000 734425817 546200 631471346 677749 829226380 724704 441222520 756486 805447635 982422 646798274 326612 325722463 788140 549446638 15114 313632083 120232 850940104 244328 10 123615011 106004 46949441 378575 631212874 576776 700307709 808035 237132192 51791 357524056 917882 382925754 935623 440585633 831166 679147585 378052 495601788 312523 92 690675723 348320 761684145 20067 465813079 343962 449079414 875573 156497176 530633 869731025 208483 45617647 377311 538023152 685499 753693748 415782 894162163 74526 912408944 290425 943756398 729729 983080931 798406 523274475 283248 181106431 11603 252354662 497351 430147563 565558 841333711 546807 942582785 108188 437021068 39815 875848016 516035 172534772 515408 917756698 880319 502148564 269568 516445783 966137 235833070 891224 239269425 550827 574754422 341038 501258886 428389 449281939 859628 713179241 464012 437906916 459087 570605217 722197 513660920 534504 491342889 202958 539309012 80991 998898350 485782 599410546 812587 958891796 930592 108682556 629339 760759282 924340 72613525 779600 862637585 785710 223691856 85760 608700656 892221 253982007 789749 159452995 113573 46478469 441036 322179952 638 214374508 421175 634563601 248050 859044497 654395 184198772 42563 710937739 130291 315316510 99267 383778407 155083 712923204 425945 220969767 875781 34098256 784643 60156222 999608 76291170 172431 8006421 768012 976442060 559648 18209162 595199 941428117 617199 357983852 65891 270016759 50120 603559680 588317 157598178 340297 264654463 72168 669570679 437286 289245845 899664 725294221 503272 970581988 779192 690615343 796329 821604479 393044 993783835 290969 886026863 54447 839869509 708476 799071282 105511 165181522 780394 644873527 269932 109622302 901838 643872867 982853 244070966 333672 193205903 232074 233137246 286859 519801095 834667 373137421 670367 569647628 904871 46887148 6432 904141139 567318 55 667059357 142661 793194336 925612 104763322 545341 809673476 235430 910485294 714765 161779410 158787 710729350 22777 13094769 339762 212067104 971770 373782682 854230 651888817 644348 47195546 147461 446750656 565280 874146260 137865 678609960 839739 151719229 59235 715680666 770069 83898591 395139 575995929 824619 38986070 481041 759902844 560110 735630678 785192 87454447 979650 529340963 372821 848687474 446336 327305239 483100 79421016 870964 2034463 838515 844930762 749407 881683774 737286 163558210 550902 403977481 911601 969333776 808161 721158186 716873 390149592 652093 623931870 469779 145065490 874651 400701815 781771 898779529 813630 62830298 233695 380725981 895841 841619713 450930 442247937 607663 963147386 277017 485507005 596361 265924582 480481 650497581 833348 420519035 915271 328487744 717224 746215555 735806 510311482 784242 340426715 385005 157740338 736274 806967413 975726 244851605 990830 10 500137361 221217 215348446 345432 764990103 223467 828416621 461033 598260023 254425 177503198 870283 689517980 411305 968349029 300498 104482468 330024 871075114 545833 63 603346044 110474 128501389 253278 785517851 914965 611243920 522641 675778129 713105 188109655 670634 729895422 417909 927438877 145227 256124502 555375 333480878 297355 226782815 181215 687507436 806454 404509814 627866 727456590 831113 794489035 269928 930026844 695671 33054176 129157 140545332 263974 17533709 206628 793764360 740338 427718911 562023 962086302 178090 763476533 323497 327210191 260750 927638914 971956 650605576 343959 910754446 97931 876168140 293039 167439445 142946 552318767 99444 172759462 497632 162343516 471738 304068005 26852 243298577 337926 359368777 748797 584888606 537299 986464991 256305 998280426 962001 583451269 323191 607448046 831073 766763696 175101 742582071 8986 902686118 629474 654829544 74439 486016773 596541 87985078 878311 398636090 827092 126926186 318636 542515979 862374 820836195 711805 615183886 823330 142035473 992371 548588847 233133 56632955 940895 446258734 91744 252325050 220227 276407582 833800 35855484 182165 800776424 663717 711957890 102143 136865222 851883 353812002 637473 789157320 283587 69 887384270 728914 145204747 922730 418821578 682844 666796626 204258 726173651 544177 502118365 537106 618080789 428848 657674789 694004 196335860 754126 311627031 208213 157928070 874067 967881106 581849 995596054 711256 92227052 375155 2885539 894863 862840942 210797 384183902 328251 390015443 853222 134309680 539571 175274957 997455 710710321 818852 889305472 294957 111089202 876812 549438981 187547 482169652 866688 123485929 210308 384853231 236966 877028011 876525 699009356 776700 603536705 61609 739178219 127439 447942804 168163 663715230 17605 581485311 717016 925808364 461588 876682196 364122 177899151 676936 701002199 649678 549816054 11201 573706177 796143 945234884 212658 26566846 669833 295680079 634148 723116783 146558 395953186 591473 141200361 897029 230771579 817865 616454965 282918 980706254 230512 694236366 895999 129369664 937086 215356838 153730 38933548 757662 783882785 234612 522683298 600143 558771351 106416 794852323 522982 794393047 332642 72088038 37066 931784607 654413 926010583 733047 820427557 561541 319361170 181948 644342673 446134 66844204 241533 883488896 796891 994764907 908337 828323971 136903 823843401 217764 42 144664608 214261 457274999 113993 942778271 917585 784875483 653234 914116049 622389 13078874 360377 73391513 391659 703511118 842291 964531308 747505 848957928 78824 820491475 249978 603937706 255765 351380204 753901 852422637 618859 514687722 367140 689443932 146318 145070993 727663 701842551 128406 606650042 759119 149667858 260881 975773141 270587 600355283 399679 672002658 465054 547364279 922709 11910775 693782 347509645 384315 323370301 495095 872259449 86350 721002867 250886 317925491 346143 617620458 631935 119464646 56753 324615687 383504 705370257 103807 904578116 902811 107708489 444724 572376238 243064 123334965 706352 271091048 186928 450592753 917514 622407975 851011 863889132 255625 77 135517411 516137 345404266 37807 168207991 777986 523323357 345479 850513945 468384 804516808 192834 56355417 440516 541705218 796218 388101367 934914 684563417 895325 107906924 18177 500776845 258540 18078050 954044 507283666 322813 407557431 833795 917146450 98554 47121535 217467 904981801 452576 527532159 897882 882951015 816705 802737331 367148 923526802 771522 795262280 32209 292366113 720350 302418850 21180 407725570 291041 814269656 269941 874464021 654957 711561779 921688 928249774 572792 232947635 406228 69969687 171916 713340554 965869 105537291 146438 644726686 317179 598700093 637464 262329867 135401 372251855 333832 657375647 300982 329220827 249774 478345565 476535 254780142 740474 475051515 405779 127293063 862315 963999843 170566 516961437 756953 235086902 190367 210828310 156588 373860420 930113 405310033 783522 546175765 311398 331549085 533965 645238115 487063 657993663 729363 70156958 355189 361668209 438380 381348711 928116 59448285 241576 283675157 784538 976067366 801511 771266355 651653 966402783 58270 617488895 409634 432528785 486873 334331629 493431 570005562 618483 336269859 660441 412254409 141599 875556858 385847 6164643 250403 606709635 197709 549931297 989912 807405311 680242 396086800 93483 487411302 340939 9073711 609439 595388386 807829 96 717768201 863889 149135711 314312 988264594 15430 857583693 541574 453289465 999943 70611607 533312 875858639 212049 739855431 47738 333564472 996368 3934527 895597 904412784 895656 925322161 107205 203321668 431407 997969573 569572 477940885 150320 918081654 867037 187088601 322025 876842837 343161 927844762 697165 145935813 728821 653548020 259396 281661725 616386 64121115 444390 188734473 211460 815155923 494916 532218121 245204 749452278 596831 545919729 36286 632272114 557743 82546024 346052 257450056 998813 664287593 254937 928162574 370953 393913284 303334 12753774 828933 210855326 533576 36704549 463063 954817261 302032 864735237 462331 910204669 693250 600830579 75743 821715693 354646 966729193 578918 753177139 867387 845048693 842470 158509844 497295 647876153 677481 599467309 791144 393823209 126192 710713325 812878 621249872 707307 613720344 148606 371612363 300290 285270853 707945 316383948 890575 520641121 958258 571655768 609762 134302763 928180 333688202 223740 965346485 314810 779389454 572244 726817513 915653 47484326 872213 493531394 247882 879687849 138142 826249999 102705 83397759 558080 744429939 827735 676886566 679044 979434855 257421 561536176 359651 62886263 221014 73003971 193483 300846593 715501 920682519 931937 682437561 615869 912167420 910330 694135336 73319 937154001 684704 711331368 206464 284898958 450771 751866474 844816 410654267 734085 24558576 67539 999787639 896605 247690387 657788 713792242 732981 759354750 266286 801070066 721692 26177969 186497 205770962 592853 394270847 301827 580760191 417366 421187600 902836 815373818 602826 23757280 197512 96 822328144 377534 548762217 889797 6649017 119310 462237811 97148 989843725 26055 67435574 248977 440207879 458294 372641912 53287 413344277 194553 202506224 346746 867704537 651845 236226508 893143 385149354 231585 242665004 382751 883228692 746665 234632356 294664 87857236 711755 930034366 485403 39229405 458957 479312502 984375 801237973 952901 353492156 776973 181801880 569504 589328374 447522 660938036 26524 628698235 347856 128113132 225485 528204057 765124 335204022 632668 977864079 561026 369251005 958979 508832532 185885 83391967 679762 843662030 903487 373327151 341229 364474972 735463 901119860 785356 25384013 476710 114259881 471930 789919399 762657 950369659 109975 449770849 122258 851803086 783638 441661672 9863 450951992 439807 681226398 862818 965722756 11502 723290966 677079 261765937 230674 809444826 651313 881118705 503855 222967141 196877 569275690 974621 932138026 454236 623570808 923590 657172939 373990 307876905 92908 263500258 691458 44119999 860256 480167035 982815 365585522 766796 267472536 685887 409418924 543851 266998956 727094 829439371 260555 765371681 728367 995766626 47058 706543826 562855 515964984 784822 695076241 652784 4816455 764228 137954978 44592 6454910 681690 725012286 272927 161273600 975852 256378130 375053 577632163 687683 703517373 788505 6985330 708409 31017045 915131 60046380 408254 447549923 204155 117947586 670742 577379810 601783 175952861 329305 26053572 724193 756681045 164018 46377581 482367 627365819 807073 193193142 246570 372394704 66361 455605739 333839 266384908 713762 947521613 352177 591551256 975576 703842194 975524 100 282810666 971232 475270356 778322 412556284 335061 285436540 950616 808239301 761666 54709232 629859 75614994 263979 105673683 139743 214407233 167561 267123169 274607 56861191 592264 251013479 80939 696275691 331401 789097926 628509 746145480 397089 422070516 158723 7787855 765784 634307578 499665 825815682 761323 584904055 547244 985717563 941387 546901531 378223 995640739 82524 692377389 955946 672007099 173303 229069574 376734 355866070 890216 635534740 956290 850291485 177200 414183128 459649 964828170 394564 630841192 571386 143507693 391372 249070317 175935 706997866 764581 776688294 581846 14068729 492448 643109860 587067 164117605 512641 103740556 482652 991863886 270976 966360984 289179 402018471 993675 915790230 192912 802683704 732802 571800871 335493 786742557 231162 332617601 257848 249000773 426555 430227694 321052 487021300 958850 757715275 279256 433745473 897856 272715914 152646 630004889 769240 919926064 615605 561959738 94821 195669720 421160 125257145 391730 403504302 938261 970332796 681024 781079540 333415 236264769 354307 12532352 138941 89200533 127397 900654396 819368 246831966 169538 900152485 685489 640830802 350891 897583949 370577 409444221 778211 598282330 310774 451089343 746917 537267716 60356 403086924 894171 35816986 488786 136400426 709672 124291710 473705 101019062 218528 546924964 367561 593867551 147723 997389079 577380 645791466 703397 535325173 211553 725525100 51105 450821486 868186 296104019 535905 880505160 582174 820779294 106688 292060766 912944 835457952 9608 291107100 7686 218154369 369212 884756485 684811 323872189 360656 511840814 803421 594468131 224299 882081728 232591 766599383 349356 904937593 819112 72 886057058 986028 383846563 473499 709567123 890236 546986669 705878 235586806 582565 233737771 955382 209651769 616372 511551985 332033 725514747 919561 173793035 980181 389746515 601372 726419256 517023 364997959 151030 986311530 132517 733028694 374643 489436231 87869 318589423 880839 488523947 947091 86488311 706934 727717924 677479 507510856 980505 941566837 255436 841688620 78688 257339155 46123 316521446 94411 155200939 555774 609259049 230640 466034842 584469 443313055 289657 400586355 32340 196382563 897890 785277 593651 804732807 492543 504987698 536893 516752783 453172 870176706 11793 967030004 745339 930691726 826148 602001315 626338 532870317 996861 60504699 119562 352715882 432120 857183699 229097 43688131 832772 499643377 951817 797912556 813349 149933972 715527 468642250 88306 234403946 537492 587055737 277016 88884123 652408 684367047 951637 944732733 115402 122045622 325886 881507293 305785 193003006 543929 496303868 101766 401585800 504772 406885263 992647 230404340 862188 477235583 19302 167031572 387863 330737959 661856 535652463 758011 400121305 975815 766972095 915556 14200921 559233 216753779 745074 547292000 163654 730229550 815128 182619162 709669 515557446 840671 9 551912512 227270 840685857 61600 328266635 116332 832249870 799112 789893841 252459 58423786 261470 131340527 153707 438736333 719123 932527831 462596 25 621944587 248719 445973511 670376 992339359 998191 945559861 835060 262676379 116711 745261253 918637 600006336 872886 142193122 699087 212236867 725940 43594859 519465 483539276 526025 923349874 161374 549152120 889523 279274429 402536 753011032 611269 504007240 12176 796104944 19810 956873409 600375 728824888 287046 951484939 75601 58962846 411325 281587388 552293 973009539 751658 799585694 161998 727493561 38914 65 694266749 504395 472570318 664168 240647668 27062 614482157 169832 971014796 740904 305620879 603532 667395312 255688 276436603 517283 827553440 561517 712058762 186288 291637615 70821 208374825 8554 231481862 176816 122490331 895994 876968031 192323 331230389 537919 747579978 616134 966346209 160525 59457515 571926 489804827 815081 657091642 823300 746550839 270543 397810049 316947 615817625 437933 50119138 73534 701776059 320677 223413711 37104 250687403 810319 981406864 226762 149017226 988660 425001153 384416 964121102 648468 434415312 621820 726028288 498721 147401603 858842 543238079 256770 630448241 95338 436828348 646353 383866500 164178 599153404 837469 683269245 657065 53947289 346601 335741296 270781 171398977 123307 832233795 27278 540501685 752398 450562868 944465 645988172 499568 925379664 552301 490478957 800293 755932669 9217 442747672 572402 607547505 401116 370825310 433810 873306936 486468 998336485 79221 434238898 226608 926198117 475260 649009554 775310 15195181 570431 302399840 727486 426311582 830407 998729464 438804 222941103 317012 448075785 316890 32 248299863 495767 510028300 838695 31708537 385466 911668250 503198 677055891 765533 549075497 38802 52550004 554303 173312082 300638 102448159 244725 651181858 155438 38520905 80358 187988505 456645 903459551 706126 354681387 607863 592814462 461948 874453570 288815 315011833 423059 838259129 257898 69241303 152077 781695202 904251 973421779 132915 649391490 24453 806444378 150694 622258000 892420 212316688 425114 750351993 830212 269618507 164693 828145695 384424 480138135 742901 374720725 873381 654230064 713575 118917413 91076 7 253730096 141066 967496675 857165 462189480 394102 978718325 402962 86607866 920333 815977021 385384 962457958 517992 75 962484113 587264 430310164 930928 152706181 45614 2292880 552457 708948525 967917 405085714 109751 939523433 711372 654534083 211110 858598987 73647 1132606 103314 412213914 328141 822739221 449420 575871568 530739 997858124 202811 125866013 684864 942682588 423512 458744801 297767 846957105 694449 647318837 784240 162727085 997287 975965667 912502 67148067 234672 436905578 802090 11566428 3605 773240955 751695 884701590 412533 282877310 618172 572329727 93248 903735566 578589 545802814 437694 122287993 962610 943907307 134790 706295873 154255 94410514 711303 274040989 765914 383773109 624514 278554104 548497 753599815 271437 60089457 364673 49885489 640082 296951642 102160 237633360 406606 813109178 892403 392504437 328594 702427851 563128 489824484 827718 295106172 211006 225592534 174305 561763823 922680 970622711 764146 262561788 260335 428870888 568986 399507373 221949 418238910 241487 349308096 105298 664880257 719771 571059240 478066 976663214 732507 827385997 396852 180765878 444673 529261767 394565 349439101 579539 833169510 868707 980958171 314153 995261485 821603 885209886 46066 640984211 561260 824926086 431664 558768193 823226 887018440 464759 140081302 401691 860369036 742194 969766438 862581 90540271 439327 838647606 267902 14 536129422 48258 240662467 232777 788069861 497848 387429602 446140 266290975 996603 846273743 324297 821749640 709088 257058067 226448 12189059 28468 321499272 484710 72230404 204212 9638366 657363 86141207 348243 583534106 156372 55 7579384 795538 203449497 739255 892328061 652786 343286664 782717 537728497 180537 93451064 958402 46218071 823037 258579255 305715 994779749 153635 907893253 231123 403021574 12840 430305175 646391 894992344 926427 490203092 114952 856604335 95008 380846363 201541 763863312 66414 43964092 412414 835724471 487826 582934394 300314 747278353 730218 866529295 953298 357509315 805035 903956392 455923 877861409 880028 999285861 754144 852573111 681305 902807003 947726 671791044 927376 557354385 395527 982273978 577223 550552454 884903 904659136 748372 9130665 378914 270593584 561315 797048672 261180 884914201 782005 261224962 223695 297807806 448347 374023005 826377 853812756 687935 67829040 189483 840633928 247323 970213042 708555 498415159 897983 27387146 305875 730742517 526159 953051604 281984 371623751 338307 246296994 706275 276711976 960870 68964985 642595 849693000 48536 676445264 637114 659718536 383500 29 556216884 27839 894326730 653927 442276147 436472 737180142 439644 634601133 711282 91189031 57021 708050732 440927 919509753 902790 46421709 137829 285982140 840807 663616962 652704 173265178 60165 364212432 118878 621452437 152953 82926546 699809 691069438 790480 282335796 312609 734047231 904073 630995832 268167 263128211 297562 561797044 593971 522451336 233772 359186450 890360 21199620 115674 837858128 481626 532691965 606838 908689982 354391 301576383 547652 735799362 557403 34 540711677 296407 41182858 823666 971269262 316169 797075898 156701 890121878 620667 182003638 82185 144292139 51233 682857788 907939 195100246 629830 728977984 925424 87394962 14600 410713703 4872 313467217 810711 326429069 833814 599824759 784889 647427647 602 161286109 244809 391787586 367335 942949327 775283 456568074 813413 127678351 38330 533530180 605712 810438864 717491 877631564 660983 61059387 601927 574845111 841918 958652653 654453 108909771 389596 429559543 997005 738892802 395230 309237213 370806 9749643 883618 181572632 779433 85379529 470045 100 89459251 546002 727700246 260018 595470007 866673 404617832 673095 78900650 296036 966573060 824475 19218453 57822 640266220 497068 670124695 837702 881070841 401256 249412065 830903 688254807 401206 464877367 39742 239351044 595054 347587317 386079 975381076 590428 352234760 733521 964171888 427137 913732465 423165 376289234 406354 378263238 663875 478959818 56631 275188913 890292 86837756 304205 191998063 694809 153499360 293989 325696849 350379 604495937 895427 419429182 701657 291998399 105119 740590384 364869 446676301 936359 202353074 77831 985426867 294843 189056873 756904 128836877 265840 804550024 947368 573380682 938894 366488154 71866 799432365 638610 93117372 747395 770753104 37613 425930143 411422 868272796 585090 39933067 858778 486144211 637868 650972183 509114 2155142 606902 758238066 562996 664801311 897121 740861917 166835 109636953 703521 357004591 89750 550290882 629728 101576784 970286 653016896 906682 767721406 892291 493724809 729792 777860107 351568 265766313 863221 183607900 546243 655033472 40596 899927276 424830 446755650 412488 155308935 136153 952560373 155185 682383887 671453 270087670 38246 73460475 473610 760970868 567598 804140499 345874 307546356 999366 166262709 285788 103614155 482782 131282387 631682 883312295 201628 179010547 316691 359356679 530583 441115885 361554 159214270 324189 181280049 851189 690418548 216237 40059710 114726 478691877 351678 657289260 810950 690586528 669943 519018531 111589 18241288 854452 20507874 182539 20762711 897928 133979705 319539 349518550 487541 948774543 341706 761067943 221685 562826589 221620 943147579 184373 213691312 114888 166356700 769749 655383211 277135 181524261 747113 39 690156936 355012 845673211 907521 21926439 880511 836517702 955396 780851730 979820 523097276 686652 987871267 891447 49993026 764464 66921449 251552 519119023 204409 959634470 37114 443601744 51589 737729362 187310 548907111 383893 216656919 457782 380029095 588350 457948115 214882 125908666 292716 382022937 327894 636374971 368603 803979824 740042 79079868 59612 570005394 351369 752162370 91990 525835886 433778 653774020 355202 724537639 116474 433626927 427374 269342676 69288 157015141 65531 745686718 940568 327707321 208224 506326244 979321 831261812 214884 128433274 341263 133160532 60327 949760869 473969 318685192 890970 383345601 297420 77 71123714 889499 939507358 19828 920145849 258936 790704444 102993 612140205 385676 219529484 315789 177886944 824900 401869708 794846 195043302 113469 59159561 99498 11755114 899530 473331241 564687 925254825 409969 503244386 559006 31572725 919663 323820672 243675 506779699 947696 526975523 600767 222507613 192791 533421886 502582 657997570 262588 24460954 111906 931291585 31465 497277520 782038 666329297 657437 673035347 40603 510603132 835465 299134692 800814 274067104 349333 802049308 769280 218345773 953116 898738533 617845 535380137 698219 314238977 671334 174462895 263046 837882242 401759 625282667 38820 301529424 521569 866228512 964974 852618279 58913 978129058 481796 817606806 535239 380343516 322616 512705408 948976 952174924 260752 982158495 988717 168914818 725960 233268988 861122 737306021 531150 895066488 816104 674295021 55173 639303 810827 504529450 273794 915660912 501644 967898684 713362 967200334 680640 475783832 871666 228873746 333231 743035850 51605 789021502 263318 422412781 732642 304882219 342373 448990005 729204 408243844 556546 603833957 424024 8388553 911237 655096665 576146 799661005 995706 233519486 701272 89767737 836642 447731797 501909 341021703 764273 151463412 194344 618059783 841873 569914244 283170 487936861 845470 929801668 823948 17 462139049 969604 558770591 954365 807548533 738539 593118921 611571 928459197 806066 159920943 924181 208385580 694887 606971557 845675 199351395 200363 261202232 774288 971093110 232052 268983205 35061 983662191 96332 37207519 277661 503720650 691920 399068557 627743 371553016 484017 65 627104872 645148 324615735 584418 440900086 901393 757855929 77339 341810718 631457 29255654 208106 688735430 229711 651406463 491385 981292 838479 778825178 742249 651724381 75145 622602337 328522 643958207 606425 593856017 588452 779899272 619794 111464188 377714 779076420 186422 553314247 321122 123357779 441471 483169836 136918 152556136 734874 520831865 59813 611096075 907111 906056976 746202 539578648 801210 420773605 881460 394144574 799709 330651139 399909 416173185 155084 334404871 315220 526702521 73911 850126499 990043 157616401 983427 466588701 765705 353596552 808714 945271757 736992 101058675 678550 449447842 849432 143219705 278762 666916766 209883 820367254 949817 30056533 216391 720240536 350637 909966195 320879 545085605 687329 595392051 984218 602862131 52711 849184232 318659 793988367 524100 636724856 518423 444728791 494639 128055515 158138 350063488 278101 274939809 941058 57301968 347928 850665321 742906 902317028 654091 856195435 644257 678391468 159032 496719343 309096 716834666 852698 700518100 227640 83856951 137827 30185482 296618 423261310 264567 96 33792460 163007 723589295 859607 714589987 984333 971356440 338100 46955939 805969 446398449 375538 757520761 815429 802034545 446438 567537538 516409 537338302 927353 164466129 548753 789365622 820650 531594285 815748 410565674 684425 223233168 943327 468067038 631037 626605993 916033 244982411 70399 394689371 211101 82621086 123677 866628924 85050 547056502 241528 686843159 460086 719548649 158598 963170666 675839 180681407 272017 952116713 51481 561958198 698677 114065401 752859 55266173 679718 284895030 829617 178679865 590440 362579437 116699 328230402 657173 511778722 153325 340654567 351067 829689740 230925 533017062 765435 989632788 725369 899692917 907979 200723546 562942 446620668 723637 950273712 914497 484370776 194422 836198172 140730 671183962 433120 534584538 175540 839243590 746392 73943512 194319 101273685 385624 387630393 68990 607335475 38062 849212371 600330 386687617 132604 86218929 752652 242886228 35190 297770897 4343 624161972 451751 173455718 2380 651848478 136236 462649047 923747 239594499 653751 408882879 710889 325445959 183245 243492523 959196 536399042 186633 102760799 684881 290406082 865495 175882065 375919 253939848 209273 211483948 603570 499585222 273158 354643535 552232 775580199 456102 22907724 976567 840756679 72599 510898793 88405 133236151 916011 706043426 968975 975708027 707080 54043557 433731 773063307 731878 121857364 60837 213643989 597653 761183559 310014 824858937 172276 272059847 239400 205913100 90427 877013460 987475 414328214 114866 399668128 613316 942326932 538679 300025618 286673 526432438 370237 911246405 756774 813495586 637959 34 880458946 875439 580511025 795289 385048571 875371 858494440 894644 802325302 296662 178176940 346306 468837360 608741 421283861 575073 699067768 84928 123659211 885157 959982962 433603 440899341 792723 625380949 936897 146228779 835814 674673134 960764 534225932 932558 5802971 166063 794628777 981740 469672465 887364 421477264 748376 73228631 486750 91447394 742683 677258184 466769 902384981 184245 560356181 175717 197242802 437848 211933761 90390 896936024 703531 49163171 954455 423305271 571720 334427623 578890 568132822 578494 422938957 818249 719201999 220943 17 550640289 211789 570555507 331809 253222866 428308 859985620 912051 911218512 161657 316504464 938604 484207173 273318 443824570 236081 182662732 168088 568452121 733498 576273912 793057 503514536 187346 262558027 896678 30002708 211097 226655807 202081 98963009 832898 121303361 565408 66 412178005 176880 778419332 711212 383213550 110371 644536260 722738 2889788 387040 80975271 955020 207517379 737062 768512589 461920 77572058 978852 858265063 471176 650991918 604287 244869435 708946 479942717 581392 669489185 133955 598872284 698596 262632456 108623 554028978 686010 970986097 649187 287819963 258760 684734323 815132 276260293 652279 227106870 615565 645151478 610594 166598520 459453 205706052 16283 465958923 40486 521402107 628839 657917781 601848 608113723 994749 837937102 867603 267262328 170634 885730693 153425 102490616 625839 816919708 519610 530434136 62210 524817351 872589 609507080 840841 683656402 352254 740901578 228354 613466392 660786 343960375 756638 697129484 669317 852257594 253569 46544820 28100 63237011 213316 906190120 917939 106448725 644915 896461592 33481 413428840 456336 708033092 743983 749937160 928654 437370881 555205 175594308 771670 281780923 429469 874807168 133573 999781997 959550 781996275 400492 413187370 503714 199491882 24399 109425048 142648 990048131 990951 168075120 524195 252208563 107040 913135104 441016 24166465 115355 575566505 460164 60 62801389 404512 195752965 221817 125091423 200433 306093548 829398 969065452 982007 422503841 191608 769209158 711846 922031678 597707 237896848 603650 975088531 472717 380749797 159461 473165985 207250 14701520 522621 901111327 46466 494470098 963403 143694073 744922 604473056 546661 320448203 853031 652991970 869044 921664618 768334 989309493 527543 54418523 498247 333334570 83071 659675482 379293 566446981 925873 919234261 379184 93189630 908551 904725871 696883 646175683 360143 143593341 538606 93487605 880746 962629516 977084 585796390 433166 836701401 281486 82386913 67333 83087831 751911 56806690 468204 36497581 909023 620926170 754229 689716149 681760 291349101 977061 612056575 996524 643003187 279190 438961612 529044 403195130 999990 683735315 280642 871104642 382919 199137279 286065 546719232 969821 723838318 330543 632692124 584931 748574068 150818 517730802 693270 426498518 804096 813182613 969672 683636368 355349 855823495 584542 12735568 380545 208750275 869651 104787704 528119 44 62140915 850591 438309056 994747 218959521 266769 188866870 868012 546676049 952331 798112969 98001 961787278 732736 444803069 501414 736853110 406422 987835946 806171 760792377 173801 90254331 522710 465171357 460616 954511344 537646 578487421 843379 718955228 325681 242832453 654435 672243303 962527 80389496 810178 456054669 420844 259156266 701102 814438685 735362 531151239 271163 362095162 3836 614832202 357998 605562590 744749 870585670 11138 133614162 341399 15320801 499111 206298552 694132 532909204 426238 2140801 543217 554492268 192990 740116215 50350 816280204 212562 880979124 6591 555113385 745881 511834409 272750 660656524 41125 895647257 249526 782607508 865437 404171803 54473 723277105 678490 587216667 594956 22 990000813 495193 8518678 320216 364609496 109672 460993396 469609 306858129 47217 808547304 797982 203750274 676974 24869925 621581 842616331 672431 457117397 832735 95090879 152792 724112147 598163 570508770 499681 874648818 669178 725946354 54421 938691060 407609 518671387 700179 714836883 136842 719326913 506000 704256443 989371 761827834 107411 990597454 723757 77 384931960 155743 688764310 273157 239295854 715447 845377728 475271 384874937 952916 184254344 298048 532603184 453541 985542047 211464 891269376 993103 391116620 863984 319390759 857387 861836777 399033 978052090 161733 953232482 718171 510313119 707231 200289209 372095 125282196 535212 83221892 302725 930887718 208789 693020269 899583 675077627 812535 929096881 363316 815351177 821283 437457570 23326 821081244 391261 595177253 549868 349493972 129118 655428661 205185 205835812 405458 559440734 746675 234909012 504987 87990850 86669 373754496 996492 598524184 920973 266052504 961838 613639976 428775 94701278 646078 140910928 347136 652699498 277933 680336002 915699 899877801 589087 297832516 981712 566079450 143149 821559598 117912 980598416 379875 421004655 830338 59490099 218050 160148809 991674 966112895 183551 719023505 590812 360813314 505986 938427440 937469 922090914 905384 171138212 834915 411107862 677570 702720639 716808 78664552 513044 497409511 321819 358998649 763159 597128213 472062 83122813 788599 194042326 292745 554806139 958677 980685837 865926 293066958 217222 603248175 328243 130443174 516754 798683845 756163 965991816 864566 513312238 105181 800639178 110754 610118106 985243 402834712 947004 559481680 685645 669907442 120028 270001705 127668 203337003 926606 38 543418311 40044 559959571 776718 182318705 359151 199910688 358898 465723216 983492 849345309 557928 333408440 700815 410144486 105772 956015790 23432 464406606 947794 3607406 201209 429594264 22782 660346854 122436 572306684 173034 100305464 395419 352293160 439076 686516796 581958 428189628 27597 428420091 756064 907391181 981019 672187445 273946 377572451 399959 92264668 769591 730844410 811360 994714007 563150 323885061 655591 263764544 562572 203840102 649905 472335206 295663 196138744 868440 472479948 986444 696458502 674570 644180456 239497 540400336 9928 871411301 446244 55154701 18664 402622625 468970 523018852 420692 20 700415616 670897 649423881 394263 974363550 964551 806759065 125138 644190800 517096 961560745 671566 273618419 847375 772734964 305519 627028030 482918 734004678 94412 911342006 542928 643129729 80494 158197304 213728 376554780 731285 607606643 82336 777188767 52339 703185259 825164 917660072 786414 507529976 251924 927281129 179554 73 299969501 522087 499580445 569233 74524737 977917 887801506 159601 564902026 5783 2104295 751820 557298235 715511 325639382 83550 209101895 854388 797519119 651189 667193752 254198 189494117 633847 5310857 240443 364686941 872026 676966509 59605 470593202 195883 482067974 313770 402465748 689416 857776654 719795 10664036 772198 118190770 258109 949692089 484683 801234193 902891 76063582 308564 281482689 491185 806257553 480305 426419019 960987 458382790 920996 305189034 261060 785673763 392966 6518224 790431 41851649 307202 6500898 724274 760055153 403928 275493111 97558 783813556 941275 940325916 428473 258378690 13364 178376275 571611 767803333 491549 420871631 900052 766082203 630566 247902393 45389 295698519 160883 740714927 767810 898700479 132155 149984831 7431 61079504 993739 139660657 216512 863061046 920642 425311802 455271 319404501 394194 494176778 826249 912940099 142597 928903999 264841 664743243 548214 634041263 216412 222625643 712660 803606819 188876 523607638 221282 807758806 677430 256808820 231674 689697530 525835 83808861 173957 591740723 248466 346448226 983044 798091546 322789 501025284 389835 258337211 549167 822638970 511296 582466839 506805 369751856 717472 383095971 984778 7 947897531 311559 743455256 695557 983617971 464417 192087006 725247 586415873 557055 423157677 375018 53476336 531304 14 746868277 235232 320831700 475216 17065347 963076 343000175 238251 208513706 77413 921336602 659421 129601204 258332 998949866 870044 422655329 679132 696143335 163570 700031396 245990 743072910 44092 337477666 387794 214742608 251052 78 655744973 831633 516635080 126256 147088469 306730 72460456 389137 106676351 875239 478669243 771152 475524402 781641 417503939 37656 247983273 688836 569723412 937800 725751029 231555 941682969 61233 643276409 888224 116012239 863580 929956460 680428 377113160 223554 950970715 630573 287187242 27985 695929764 370970 959170094 808750 648773115 813729 641701793 106029 317421033 155810 798599142 774363 501471304 433778 811192817 968821 929356232 488857 960401357 100654 784376174 869716 993666328 578221 692392720 876051 814945154 376460 632383450 367996 390267730 303002 399509707 465126 242084832 465562 463123256 630495 594424860 156674 96242505 789223 699684102 189757 900515447 443379 532086323 526954 934029845 16555 520686159 71962 425597380 75884 147469205 979797 257110524 306054 933383769 823382 160741002 140606 260701055 131531 658564364 81806 382389505 76310 132855671 109665 559448684 83726 193953426 921175 265907555 234111 203547768 372551 925592091 721702 486652186 205496 959649246 404917 256473787 199078 143038344 855125 168506994 509956 386443277 569567 819932843 446772 790069489 382626 780396966 465872 859052238 377761 6889975 478501 961291730 224850 616119556 517619 49699902 971615 462351242 750702 525825768 611689 48138265 199424 783694778 524160 542295443 623877 210430512 547372 53 760483149 508254 644576296 696894 816619293 859560 854559201 731482 941564206 77769 210954747 594680 712700397 15436 928437004 815840 251015353 659414 320731615 519854 151925353 838490 699953651 422737 39325635 706915 56135674 650829 298145798 30094 193298522 620665 643823969 11149 655491503 724802 39894905 400101 779693383 221414 15886823 874224 343556004 900474 147203256 422044 810692862 90789 342819563 552683 416177087 69986 611154679 970417 124266245 852674 939069762 748953 469809955 4072 462681771 868448 745566240 801675 728745217 49560 965995062 550135 844330889 557991 576382548 502348 459683196 825989 690214557 190462 159404166 47106 751911655 363091 513395529 264253 520289597 383976 478642136 813806 692936798 245037 997387836 810141 533784635 874212 105057010 762024 233182332 661542 771437931 728898 319078652 333342 98997899 958318 830354505 992715 354385707 237320 10 253222866 295680079 799432365 382925754 906056976 2292880 87454447 290990305 371623751 911342006 621452437 744429939 438736333 234909012 167439445 546669629 53476336 422655329 306858129 191718891 644180456 291637615 626605993 46544820 257058067 978718325 582907049 462139049 684367047 614832202 654230064 148657583 988877035 978129058 968349029 745261253 168856835 723721186 309237213 475524402 254593612 421283861 665890808 437021068 919589168 345404266 6985330 784875483 76063582 56861191 349403035 965995062 646175683 523097276 973009539 274040989 199491882 183607900 163558210 124266245 258978186 58423786 598260023 672002658 437021068 391787586 988877035 182662732 540400336 780396966 357509315 896936024 781695202 737729362 577379810 457117397 766082203 114918228 399668128 963999843 86027364 462189480 410160342 684367047 875858639 335741296 2885539 404509814 644189983 86141207 237132192 621452437 366104936 422655329 954511344 983617971 274939809 266052504 850506199 921664618 12532352 258194255 195043302 671257522 322847080 184838571 627028030 371553016 121303361 520289597 143374644 333408440 962629516 149017226 644873527 94410514 59159561 96242505 808547304 561958198 967496675 336269859 158197304 373327151 678391468 387429602 131340527 920227721 574845111 524817351 884756485 2140801 553930597 192087006 31708537 548907111 320831700 451533246 119435611 261202232 495601788 602459429 48561075 815345046 605097443 221879593 486144211 510311482 912940099 426603793 445973511 334427623 763476533 877028011 285982140 587055737 747278353 759354750 123548175 968349029 457274999 203337003 846273743 173312082 813182613 86944990 644576296 933383769 334427623 699009356 812806547 472479948 130443174 161779410 208513706 578487421 920227721 820779294 713179241 40059710 973009539 958652653 808547304 123615011 734004678 747838290 462237811 815977021 73943512 175594308 790704444 832249870 149135711 794489035 380029095 145183395 730742517 852422637 316504464 37207519 627104872 861574627 14200921 735706716 983617971 356713289 600945318 975965667 323026803 21199620 281482689 832233795 426603793 911646707 396086800 500137361 376289234 915660912 943756398 550552454 719023505 104482468 5745526 254593612 529540083 724537639 240775045 901111327 603937706 226782815 86607866 609259049 587216667 655744973 53476336 712058762 223367283 549816054 682437561 644726686 273618419 83391967 98963009 971093110 874648818 143374644 139660657 91189031 133236151 325722463 503307529 161779410 844330889 534225932 840685857 41182858 537956228 697129484 129601204 536129422 196138744 599611570 440585633 262676379 945271757 834777972 808239301 654230064 858598987 827058340 86141207 870585670 142193122 534688083 58423786 586415873 28486586 280996001 958652653 898734713 362579437 904725871 967496675 959649246 175274957 94470048 442247937 913967332 195043302 8518678 547364279 575566505 214742608 859044497 393913284 980685837 52156790 506326244 928459197 644190800 128113132 723721186 177503198 540400336 747838290 609259049 433745473 440899341 887801506 295106172 490203092 998336485 850126499 779693383 182662732 556216884 582907049 153499360 451533246 283729967 102448159 237132192 252325050 9073711 676966509 330737959 16060873 181106431 988877035 192087006 925379664 390149592 498415159 932527831 724112147 228390996 737180142 404617832 522683298 850126499 506779699 968349029 672187445 796104944 500851872 462139049 484207173 760792377 880458946 93189630 276407582 37397330 992396960 773063307 46949441 959649246 703185259 8938139 692936798 899776352 582907049 599467309 850291485 890121878 651181858 821559598 422655329 205706052 257058067 569275690 913054282 506326244 833169510 622407975 978718325 928249774 522941332 8320850 56135674 282810666 50741649 412254409 274085161 846273743 614482157 199080488 594511755 127678351 131340527 656454037 500137361 164466129 569723412 72088038 281780923 734425817 704256443 271091048 620926170 339792087 451533246 2034463 508832532 357524056 487936861 659094670 173312082 908689982 720240536 273618419 405085714 507510856 72613525 334427623 747278353 182662732 542515979 815977021 831261812 640007439 586415873 510313119 945559861 216433592 807548533 89459251 766082203 994714007 998949866 613720344 375208696 723277105 176078760 925033527 438961612 719326913 279274429 2885539 270593584 72014402 177503198 894326730 894870633 639287382 410690458 293066958 94470048 373782682 771437931 422938957 687869172 643872867 332706868 37207519 236264769 911218512 383345601 266290975 932527831 69241303 815977021 636724856 522941332 430310164 24166465 507529976 69969687 672243303 410144486 586415873 74524737 998280426 323026803 747579978 682857788 49699902 713792242 998949866 399668128 44119999 572376238 506779699 727717924 985426867 213978218 382925754 145204747 998729464 737306021 447549923 316383948 383095971 238386108 927438877 497036397 864110563 240662467 122045622 586415873 445973511 452577273 197242802 478642136 877013460 871104642 737180142 520831865 525835886 570508770 225729937 437457570 199910688 276260762 273618419 966573060 582131318 73391513 978718325 443824570 46218071 643872867 215348446 255780384 11390589 832249870 700307709 31708537 72460456 17065347 438309056 225592534 94470048 757715275 186218563 928459197 456568074 175594308 83343887 881683774 361668209
样例输出
27290117 26960207 31249441 26482109 25220281 25311227 29369832 29655556 31372347 30059598