1000
591 591 325201207 7416430 214112571 733856002
284 284 519044057 333944056 169023348 138913283
563 563 88664064 25209355 840890660 248450021
750 750 806299601 274126835 301928327 230005321
113 113 314445672 684374427 43115573 661329716
308 308 235675188 795267081 264051720 656885894
181 181 112861629 646280812 496348317 613422497
742 742 876584555 175508564 41307292 885326133
345 345 279994395 742345441 615658574 154773971
889 889 647282906 319412940 926411405 137120299
441 441 266193670 252238488 343754215 536328623
853 853 496899599 532352755 90014910 656955821
852 852 365768498 734310490 795931475 331298349
33 33 687142134 423786194 496761406 707820818
740 740 638467955 513706539 918364259 568380979
133 133 79140505 70709450 250602287 535638170
344 344 420778549 401281748 768088858 680093059
863 863 547485683 790385494 50684336 656151916
588 588 615939267 355110076 531901238 659481497
543 543 291328669 217465777 930767424 136344919
283 283 867982529 497907746 67647454 296915926
256 256 960560004 629108688 94517068 859343976
321 321 536290907 612520188 528985688 803027212
358 358 278135144 180561749 666283276 639401808
233 233 643149844 475855785 226768644 544059934
463 463 136975337 925874241 631899163 921884794
8 8 281272356 253572344 349206252 725935760
6 6 369988989 490366271 10446750 106509348
825 825 469256771 492809930 141204284 11388366
10 10 460893591 250993659 185992558 293231437
815 815 174718798 482969054 798899337 306273026
116 116 389992374 71740465 539178777 784028182
821 821 876709407 287104631 282338321 792156585
504 504 353979921 82872612 428885030 114322430
13 13 534695290 877810895 748519211 18645939
660 660 577166463 895747075 311587539 947043260
128 128 431093039 12443124 67877669 548315421
673 673 680853171 820538173 469867415 483122486
228 228 166382443 582212003 173361531 786025597
353 353 604188776 550428444 748221792 800291710
222 222 175183264 427689011 752403779 860236122
329 329 621412796 282497033 819732448 796214940
128 128 733787517 708379373 38183518 633021615
262 262 699576913 873098547 690917393 146748939
348 348 380548910 295515092 767316429 601125980
711 711 623510753 716408700 635493057 710766338
809 809 23665364 32585588 288113149 450476911
414 414 454301299 18595169 138024996 5129026
306 306 624543060 772312384 267811758 508156412
756 756 86078737 38484341 603282562 552654094
554 554 607144338 470080055 914050745 637095467
248 248 670229636 161587373 72040144 662482050
572 572 481412007 64515295 999813521 923576770
563 563 910409047 956027064 381569828 775029755
254 254 352439671 860616635 29565684 476514911
497 497 799313771 942305789 599213754 967355130
754 754 450008062 313587125 604274629 966090221
738 738 542568625 990843883 588693518 614297816
702 702 369090075 518886805 572823573 219276883
782 782 97102091 444790444 394900341 129070750
510 510 76465549 157478906 440037402 910772757
627 627 505009184 409968962 636485018 271368822
75 75 17363823 159029403 943445544 722766558
922 922 438284080 909645220 104922586 39493464
670 670 617504993 63928783 393126107 724368801
426 426 708115746 113804440 837776204 360138215
499 499 477971028 133107057 118175157 256459481
947 947 279059348 838741197 95375998 85773663
917 917 924129030 154323989 71838577 723177872
754 754 114058869 943649360 553996265 657656522
12 12 937913016 576569145 403105209 358208820
366 366 917324940 714200704 827781720 493711001
639 639 680129802 72146750 837653269 808952512
775 775 150186155 351059358 676864979 243666611
221 221 473790126 960150579 599508394 820798183
392 392 240103426 466215022 258697223 497887872
429 429 675896792 663048987 623842370 389401030
5 5 136049654 673104774 218424480 788378921
95 95 853093930 299071941 153855771 77268590
874 874 760599336 871568637 210418971 381288641
424 424 859507529 965989437 945203244 557837225
846 846 106683581 79023698 706786184 725607550
981 981 95520283 235979429 466278008 612343372
633 633 606934849 707837918 574853453 829615840
10 10 51453725 614595994 793383339 271875792
345 345 52074850 103919573 493464866 184003708
194 194 652242229 591712047 785327642 528616894
372 372 278910522 41751727 63023922 163512517
188 188 394472990 316655349 552187118 77270973
425 425 634439242 383787026 133007563 112756134
177 177 710639825 544006770 467154533 710305271
394 394 615700206 881875765 404246226 445423969
284 284 777432954 799442445 913033519 924835621
138 138 902763949 678746480 330912376 757790821
719 719 748258851 426195190 540948948 505165883
902 902 447162616 144664412 494621463 244413331
617 617 11718196 595947933 136966987 751420621
204 204 756505020 330166970 683297500 318974714
660 660 393139170 102630224 765595858 607307144
985 985 211584903 806296955 877659175 707909991
225 225 961156025 132443988 171578565 60084599
489 489 522186971 498919393 834983094 762018994
87 87 374129251 138503930 96012575 437961313
477 477 690440339 140216248 446727775 560565412
572 572 15643144 928851044 120348006 690365866
885 885 960148099 545654512 755662099 761290117
680 680 127654497 197035245 901620051 198790046
525 525 339968675 191997505 570653800 591403752
538 538 706337805 393318628 333803665 867952451
346 346 330751275 74094649 686477585 526719906
904 904 325231985 279903570 191914175 822542791
713 713 666275669 255734225 419818671 207414999
813 813 718241550 983458543 14045744 37451639
368 368 560170635 539698259 570580905 968103765
204 204 379280150 460294068 302582076 961547887
82 82 139486632 988752926 588512597 754204802
615 615 608375147 476952153 744664364 789893147
80 80 724123807 716383574 2395453 670923962
63 63 955024548 575305375 761382251 821915027
70 70 434115991 262794228 645672394 426644304
183 183 329761094 912253674 918467003 113595173
688 688 145850277 18895016 413107709 310903200
165 165 836825155 675447201 642910017 968670819
895 895 937420940 361108572 722821389 689435066
690 690 487578956 974816921 621461349 488191689
204 204 486229367 248394989 14353725 237803930
496 496 950508546 230064190 380418609 381391749
547 547 45650377 798472506 670579148 181236958
60 60 584981012 419273195 703260376 160476495
40 40 147432750 916108224 554921242 39361274
45 45 742750859 393191569 797115204 492564954
41 41 279131114 221856395 223843847 398094416
512 512 759452397 995424605 553307848 937216166
867 867 962198405 729054377 524712592 581183203
773 773 859448386 63406232 537696254 612669973
233 233 451685504 538007526 9046574 105967973
134 134 990708308 852149880 153189104 21945185
345 345 66411404 938034088 160302427 509865427
675 675 81390361 190813696 573219699 83294776
383 383 452224041 908110173 532990191 232687011
370 370 321927411 688102189 431735767 683674717
459 459 740756679 546671962 568180255 30887328
11 11 760045137 462104286 307395032 463294995
335 335 565989349 505184540 816196504 814460626
488 488 160272462 82587878 917277154 659423439
678 678 538838905 611551496 594383204 317945146
384 384 730116399 751281763 553224841 281324657
76 76 505378507 227750425 331016607 236827996
982 982 200499442 98470990 279564865 498301695
710 710 81008346 46677938 331889504 76685772
561 561 142578031 513708594 79360377 168612075
704 704 357647067 351539949 645991355 953914654
104 104 522305249 267708091 691999652 266114874
644 644 138528740 753025307 945529611 543443005
741 741 919012773 437677669 912108616 326094569
377 377 69367479 337283614 728339875 539419238
88 88 579755085 106727415 951305108 689626406
829 829 949200842 921531413 511293750 834051023
384 384 526727210 98873581 122384411 48437771
223 223 442679887 751056724 480520122 493443931
741 741 96466779 422449698 957484851 290128853
709 709 757715544 781626712 119855366 47454555
403 403 550957559 885193699 510557816 284212503
183 183 90194158 192318477 687126304 49950852
241 241 58122379 785208475 435419447 396573383
537 537 570820431 334912318 734743721 868856575
109 109 944507890 991508669 696969738 562442981
578 578 675554518 891449504 437904935 905222822
275 275 876560137 850235845 372099640 425369211
219 219 324150419 519000531 24454135 283566203
410 410 292511184 727423521 351599424 717728231
237 237 259252188 596202020 414296251 430711550
722 722 867622006 250223287 166875289 654743334
788 788 941463591 423833969 566716852 438565982
582 582 397461223 687220170 417172405 220771651
528 528 223040909 812384375 106061930 728709244
866 866 102638228 808343456 118293314 569775588
317 317 472664787 913152569 645458706 81753009
746 746 263087703 694769330 286205026 80473673
617 617 583962356 793775539 280685844 297537723
843 843 922274747 539742379 944302218 163683650
910 910 771496615 508263869 442985667 97032902
141 141 763013324 494929827 805304133 194298077
488 488 951143510 471458763 536878871 772402521
964 964 438573118 818983128 727754082 582184918
219 219 509695777 892284126 691799573 532648428
989 989 576413306 105147831 348903037 536344468
135 135 28267129 509957414 907722577 264647349
659 659 71888054 985618036 294056018 957928086
649 649 426783244 722321943 354438943 108082921
422 422 139327094 297169990 986636400 423067801
214 214 958066997 856132679 426515616 58460553
434 434 622881489 362301774 927364305 647100467
284 284 615777542 729196226 758985276 577431419
138 138 138745416 521761805 168494181 932178491
667 667 858225686 372852787 250428958 266776247
657 657 923355550 749422848 217564042 507864553
918 918 821347910 316532572 80173497 501111778
327 327 150991976 812730878 476078527 630384776
174 174 456114298 830710877 325210010 328046728
322 322 609989497 765756452 957054466 684169176
584 584 749652549 718240522 395872373 806080760
366 366 649437454 728590036 577609948 733949126
940 940 876773712 544700496 542683953 723008143
669 669 474337490 439167505 910288242 363050624
203 203 887511267 992603956 76908174 508927724
198 198 9013792 548718418 381930536 599465940
491 491 616749666 693110007 934298603 48162415
846 846 501678219 439937781 871589268 177298768
155 155 11205869 116512288 722832299 17777038
47 47 95774085 809166114 9420301 97716455
72 72 860344632 116200712 549950608 762412461
664 664 338378253 847539713 632570567 27202101
893 893 217302035 487236285 390956160 761924479
174 174 86265325 712693461 648998132 467970913
651 651 772798945 900244890 774686343 752271336
227 227 564846731 477575219 186366170 781450737
880 880 199304018 838790698 202729357 773142744
70 70 684531036 464103198 383758255 436570292
629 629 608907114 605969070 285922093 134848538
357 357 325447565 432620037 1182440 8415464
470 470 302938629 390148566 285460819 240761053
68 68 841987771 180192112 104237819 201606601
861 861 569985021 444453429 622351244 699605883
349 349 301401616 15300106 207562937 656592699
552 552 736297524 220167385 323197381 601755294
46 46 893089281 494184259 34690252 699720884
5 5 963508361 608593959 385342354 382216541
185 185 165085113 115945141 127861213 108175156
416 416 191649051 150629973 253642894 467214132
895 895 931376946 140778801 315514986 452560021
89 89 599375592 700789430 859940732 22387559
943 943 299346405 451248737 281790193 897431946
715 715 901389516 446835812 53807076 751729093
678 678 100856958 242375757 703932460 574855146
11 11 421977564 582512746 128622549 614622907
876 876 50393380 955712203 868595861 864150497
758 758 868151987 762337963 434197282 626015120
466 466 169588738 641983171 873517226 403740914
191 191 839263030 553851581 705871704 26872727
529 529 915251581 415084609 250229745 442490226
251 251 575668159 988794445 421416285 452417307
436 436 238881159 196379328 468048268 412021969
498 498 22382295 552149780 777553784 164536475
500 500 534825477 231693657 622633742 394894404
112 112 817166395 686943147 485873519 5149877
68 68 309687481 128744741 824006128 150280832
279 279 653316832 897671609 767410028 48990329
609 609 368660988 987878434 300689603 193261177
947 947 332974958 720061694 19930941 393333061
314 314 724089959 587825030 447292880 115196412
724 724 40615777 666194947 941368641 147338598
265 265 517875793 22273407 810750059 503577436
570 570 793656974 481098149 516118480 101929091
237 237 214672825 902440894 91246600 918854827
640 640 970059213 363234292 333746806 684579785
384 384 601534756 650161789 413395171 200636354
612 612 33563134 896193225 998616557 294363946
336 336 279997802 312341241 572699926 715211144
461 461 896556412 800400801 154262903 464396899
15 15 95388388 539748044 548232027 425769135
262 262 635864756 11229492 779414075 872461784
202 202 887454706 310436105 635806698 996108730
153 153 516112067 9276626 721722340 183546309
751 751 725075218 783327965 844096864 674739466
895 895 685212848 845075668 884831890 503789383
739 739 672840401 59147187 769948506 626290500
130 130 416740285 850659239 302263821 982892844
877 877 562117654 860994889 226782380 375226285
945 945 362306568 122301815 560447261 936154725
672 672 381094340 643786285 230731846 866384532
378 378 394482527 381236807 623222969 261398590
769 769 154677617 645218523 491244579 862016222
902 902 2434521 19185729 57036473 8397476
335 335 462389224 37254295 562502088 936949714
545 545 185023011 237964110 369097479 269904830
78 78 61439458 925310835 320185762 20353701
817 817 47559347 347216168 592799653 762705464
95 95 606201423 445048465 824703900 613454307
858 858 166965473 963454851 258876912 543701429
952 952 192242356 120822641 775239455 991326894
99 99 418398754 746096722 771448791 866932560
762 762 88215956 887715421 5395406 829345344
21 21 281589093 985089736 619193477 906103421
822 822 73433903 325290570 860144685 252586552
924 924 578241229 554459638 166634085 721777608
635 635 782343504 824911756 53646365 373863640
252 252 172520900 739241233 560967700 516479009
844 844 829208124 713584822 213031935 639232789
11 11 747782021 864163073 549853410 785211879
254 254 106729044 301686628 650807530 784319035
676 676 842169478 557636292 753065590 492313829
63 63 329942937 815155650 722104798 621260114
399 399 841739567 99369003 908789009 153824706
501 501 907462307 416614451 534827397 804968832
181 181 169298722 450652456 680555953 625125297
477 477 125895566 971511176 79617276 903521782
107 107 332626678 506901687 51047702 667256414
747 747 523159549 685645242 958038159 568019126
133 133 449499814 540185505 809509965 204947554
808 808 174023738 861111311 320135966 276541366
508 508 321651882 924974186 225761350 210269070
400 400 918900270 790369507 813929139 605814677
695 695 800633415 136059297 618752561 635874185
499 499 347681023 235027679 184210252 694818002
293 293 436580167 504228508 848594991 297065427
1000 1000 212524495 62973746 53540698 606397368
569 569 945903324 734637619 827510867 22083974
433 433 325964185 412557794 777118726 976704110
918 918 425708779 656391520 344549674 852699358
431 431 719504217 999459002 40570068 528931885
215 215 47940766 94593703 53257129 780611672
420 420 473383981 773339989 715940347 592238733
496 496 428164529 645924908 649877927 37593438
324 324 440222433 99125415 26759417 328986015
500 500 452981817 135639561 788244896 567176041
390 390 356935809 29774636 794957728 657425685
370 370 902065921 353929032 544472655 937200542
592 592 392393788 898987548 870381000 887899551
952 952 493381162 568423003 791888565 948784613
494 494 648988847 681743125 974469997 526329241
211 211 657440199 488410018 70779956 699579123
461 461 678846 309544715 375883980 749135791
326 326 528126305 690986642 70808218 899017577
550 550 305875202 798324429 271725501 531343490
642 642 150936266 120104625 131118501 792131294
197 197 146836304 601590001 651132229 56407320
818 818 763706705 473602083 322963163 473679373
152 152 285078328 873047407 139380959 976227751
615 615 74405383 275125503 647566178 184966643
407 407 104539813 339834054 514334477 551214010
318 318 20049814 35619647 983573491 215860556
282 282 495432290 761982115 244604461 755161993
5 5 337070085 131184157 842403347 254624316
294 294 458717889 997482235 9980810 940268364
540 540 935789815 846652538 502711592 254826601
642 642 789419690 674414924 378701019 842046425
779 779 926525923 696423263 769785342 587196646
816 816 263943460 736137979 86453400 470000904
406 406 489612994 933144408 514899573 841606559
568 568 686267263 17013560 330289633 566762377
339 339 419997992 109767846 114067617 826415208
808 808 311812733 391129475 526093271 877564722
235 235 802124351 402512047 750251260 546158205
523 523 107702769 155219387 214834365 163618991
74 74 522477272 347766926 331697595 410353106
113 113 695573153 809692655 387533083 604125831
398 398 811344336 49872050 694777969 915568465
860 860 490345304 948742863 662426440 369934931
477 477 469395821 697467769 490605924 428019434
225 225 272952141 771791652 225301984 765415197
471 471 776770567 871006458 50855551 292325838
633 633 436899852 312136401 366817794 975397193
615 615 191496311 413430245 770521848 156435368
122 122 798746157 783070752 183036119 771125813
879 879 483886088 891003743 351694536 436116906
997 997 165934863 695825011 354909499 588279242
651 651 641534143 689645870 912455219 568472540
478 478 355504275 983410933 606234058 275228243
318 318 233772967 351775458 897174941 855033501
929 929 777523295 199174745 141514371 978907254
392 392 205639727 990733001 135893774 707549757
816 816 590757237 443621999 385921235 431470049
332 332 523286984 849429040 953834008 154343597
591 591 341021582 674043302 708978316 604045554
639 639 647413150 885879284 358564758 124918390
416 416 634191653 628674250 706229625 484242116
898 898 764514697 778953982 287630566 641318809
620 620 516489655 923837691 315986761 672677175
257 257 311188694 914563072 4549878 577137092
531 531 69782958 413243536 398939223 871890209
803 803 465516854 827507053 741657902 890623389
28 28 549119104 679983023 911703480 312768069
64 64 992211241 689293033 438853124 679007005
576 576 566602963 607792390 660085065 151706123
973 973 743170627 226114812 217282803 36073190
555 555 798217477 867352939 374057039 894531036
368 368 183003981 841853678 294046139 274401639
400 400 614737211 312838605 492562965 523185319
484 484 744922449 679409851 238802018 425658136
276 276 799162863 610999479 366171504 855073997
102 102 262871878 997628503 447388129 936264886
72 72 968900070 254821537 896974698 732284439
486 486 74837720 254403170 24353928 218699827
683 683 92549466 570373665 639362812 929238558
811 811 86576329 977846916 735221479 667144265
735 735 491336717 314572189 208458397 601224817
913 913 958286268 950432939 527697678 150967792
147 147 241314672 433808824 348210330 206326162
180 180 798342300 697842790 836851293 829567674
482 482 578696884 714653370 174489239 925593122
614 614 946336520 691190309 744335990 957154556
706 706 903586591 836855520 693800254 400356371
698 698 382716905 33000387 346463317 379593975
506 506 997418356 819653664 286880281 157278995
180 180 616042056 786952484 81335336 756517416
499 499 552277622 957214396 157989721 913389836
573 573 792765423 840123764 293234749 382739694
351 351 794504513 911863814 592849709 509752829
992 992 254112076 358651608 650192495 120201284
620 620 226541214 512819800 496117529 605106264
866 866 654415780 507130399 639281934 677150764
497 497 50807050 200929 62866985 77979137
739 739 834105090 818733799 298166477 206379909
980 980 783018874 545092306 670831318 319460928
963 963 430854053 204957191 758271871 368577752
501 501 225810409 796738230 152401805 665476314
819 819 342001225 616271529 888964482 760843008
541 541 435177474 261412293 747563314 385949104
136 136 371249843 910011857 870327825 964725778
905 905 395267054 852912997 576678676 315058811
416 416 37016173 133481568 638748753 201786823
187 187 235187410 70245657 479951140 943618604
394 394 725178967 128341140 285330665 204444084
123 123 440507656 470461395 755603582 684609046
412 412 996956816 696704497 901895205 505575711
464 464 760446884 22482540 411036995 268065911
171 171 438325719 7532371 573956102 741852453
831 831 482149628 400578195 796923382 401555965
700 700 954153338 917469076 623524892 86127736
35 35 842256911 164429652 445951300 8798490
515 515 370854995 822272517 552058225 589822775
278 278 628492768 451784447 536709370 681200020
744 744 690350489 474319449 318874411 273960340
815 815 347253215 383255464 545814279 298375204
785 785 544233741 849012926 103549845 530303541
610 610 387350506 505882658 377625832 915420215
918 918 211015368 465102853 921761185 40775246
131 131 782568962 234873186 741347963 338778131
175 175 133037193 906802953 9286388 25589562
963 963 911499065 781293156 357105585 430833743
790 790 818488759 275960977 719699166 450647283
948 948 532866073 154561548 554395156 493942145
993 993 816707783 168631437 26006096 20051886
152 152 556792016 889639769 762172206 712094252
518 518 604872555 588824631 200604213 530443441
423 423 855465611 274006134 8179157 386068065
835 835 876156399 699571821 674258099 136956976
41 41 203847403 934986163 91508313 781499179
191 191 894324345 496667427 566432560 350873815
156 156 647927301 873734107 331070144 776135460
47 47 76680714 904667336 717238479 619467626
188 188 257336980 423933360 226633134 348713376
694 694 455654934 370088849 823740498 43796945
147 147 972366865 20140011 58333285 234221414
949 949 339654691 955002675 595414127 541568182
8 8 392603785 683637776 210747976 1126228
22 22 686016232 540743750 662150098 250896180
588 588 283896201 547600706 112289462 715590867
618 618 514552282 934035165 156210536 806920494
27 27 269515589 899347157 516296391 517117698
924 924 533230345 840511849 133777359 392962688
748 748 12363704 923581892 948855126 376825166
133 133 638233866 651188569 373566726 771917173
520 520 313324324 910161320 431237757 491067511
339 339 320877284 520301452 225797948 571928765
625 625 173937349 458926469 85320543 97170962
834 834 993842724 556039558 956376834 894786429
93 93 501948391 166689580 352980026 473929345
937 937 610969802 857251289 623797595 621260923
722 722 716298130 946936621 824132738 985662164
893 893 269773155 649546092 229279243 457155041
862 862 920367234 427863616 312270331 145193532
218 218 525378004 198117174 920790200 71567938
279 279 320374536 344256270 39636378 272317528
581 581 843899335 804178317 690479445 512908646
956 956 5423159 920292970 295798745 951174800
590 590 140990155 601887380 256443900 341690218
443 443 197254619 9546006 497216070 892148219
10 10 50847952 634790373 764602629 576795556
640 640 145534769 734971078 219342530 253490917
219 219 996694121 862693735 453213582 857975810
701 701 500324444 898628719 61029307 663385974
694 694 397784693 452807599 960458078 560367448
597 597 382981923 62712743 606250680 853517373
123 123 805919161 741318795 183010861 822174105
279 279 502185765 690360122 178729167 441650681
507 507 613440038 825774944 343799979 283499652
810 810 612939991 135493939 683278791 377186060
310 310 499282058 280822005 714545915 114274362
239 239 153381333 424345136 795859173 88027568
855 855 678148515 992344192 333928778 845416126
920 920 918774202 414854607 439718009 322008815
799 799 972122371 181232269 581144900 42209790
82 82 690015700 708493652 360281223 541975697
265 265 856808988 18741991 857699579 293105661
796 796 428183126 968700980 268561518 194926206
944 944 368377384 829425336 356130017 306648332
278 278 536476789 386312033 962716776 948288726
411 411 574191028 591264618 179675644 677886749
933 933 54149509 726694581 779451288 20201851
442 442 824160149 38030534 649041282 814061050
80 80 148497286 387293461 233807962 727051251
668 668 526276650 350152370 839425117 427316504
652 652 761614335 876173343 566407425 434613361
892 892 348371196 627508906 610081929 475128109
236 236 98172835 599020949 242193378 30494323
855 855 349373529 506065608 817154484 600291771
215 215 708108762 264606104 521922341 256864731
822 822 172158794 34172256 363142390 721862328
487 487 615250797 315338432 633350317 644143113
544 544 923123365 995503508 995573814 970589053
881 881 19060231 741639893 236965509 794976275
557 557 479785526 374191254 676077902 872936417
316 316 846185064 993624737 469789345 791991776
303 303 466200138 453206167 720682055 425236214
183 183 496735461 877501719 727215219 239487006
444 444 138830905 901568038 628306783 180545245
769 769 38234213 449204674 678334244 368518717
238 238 474533182 520486844 130011017 309066144
343 343 621337971 773698229 48672435 745669005
493 493 676388805 315697979 436938217 853643761
386 386 290228544 284914407 97366236 866663674
970 970 394649408 94114119 716290046 291221188
306 306 943594227 843215440 631963288 54465513
303 303 729868691 852191121 154248900 943119944
199 199 776833766 255923031 370508659 980573552
918 918 555237296 364065192 315067849 230692479
751 751 913361305 951900545 602441700 637812835
556 556 857202687 457577685 583557930 551181281
348 348 338067413 950039518 847878318 156382658
892 892 598307566 919881443 501592762 8424028
134 134 761103386 717797178 942817605 757565736
396 396 808825889 105781521 903405277 954700760
748 748 629729768 993179434 337365974 887806034
670 670 978078660 106590528 905163993 234690852
11 11 158436011 997137056 392678343 756940253
519 519 806015791 566358973 38439126 829391572
635 635 388569075 751768254 389536317 161196829
849 849 691267983 556157030 782101438 306394207
337 337 172590882 622305077 911681756 962094210
676 676 688865007 618598934 319521029 687669866
537 537 229712902 672999530 809571573 86540805
282 282 258080191 874071510 178391084 368924173
544 544 625427506 712059336 175622392 649959025
263 263 839150107 779586146 289396673 40446052
808 808 244753190 720621056 355303880 253094292
104 104 911329475 680184630 797472604 341611769
226 226 59122672 940659713 863939484 801253141
733 733 17411538 337598914 433751291 185340805
191 191 844852432 47896664 504955630 647863845
287 287 259051176 92349144 247825483 287140594
663 663 373056433 923882059 487796522 697322521
369 369 843215882 334759887 560916186 459550966
701 701 430933917 737563074 571783617 620513822
845 845 82177603 20613651 159335872 977533662
758 758 388457070 146770253 397564220 941225067
741 741 619937816 373766879 893151048 437499344
273 273 870186504 801724986 146807313 905291573
26 26 175004589 279691422 982219657 751741927
469 469 151535707 179682466 444997664 345602376
410 410 629374022 399034830 252163962 238508355
979 979 366431766 109173173 607926810 67414347
320 320 223995717 584650405 953383754 193647568
742 742 149705883 236487273 726312673 32218173
363 363 214504385 140172330 258571680 98476796
636 636 822799564 315690685 373734517 956513443
391 391 832446215 625085020 692748269 571870218
959 959 263926930 55366939 366024246 20264522
378 378 504620826 292736651 563411327 491317036
650 650 696593351 641415675 1098583 506065568
624 624 558960892 722462392 945065345 135899691
932 932 791614330 729201905 192996199 700320840
439 439 692116676 910322255 458580136 954798065
53 53 193172806 586760416 390100045 117855337
965 965 481120650 846155198 218133982 662709374
119 119 724295508 554813610 763988892 997603554
722 722 650162491 443467495 561881634 835623171
198 198 135020740 534552829 128070296 126340855
758 758 307714014 890855657 582943560 964638700
431 431 890403569 954916001 536440180 832048673
693 693 837021656 604450087 548324637 845357566
205 205 729169686 999262430 655286033 668072746
191 191 332567175 260581685 254967788 223784070
449 449 536994623 232574233 343647474 67138032
206 206 371024932 590295270 746075270 166235657
490 490 554016176 533076257 490577778 748393068
584 584 902394013 292825280 761293243 19977834
132 132 943216517 225148018 990346632 560323898
681 681 68738204 181246256 433452089 14108073
671 671 143896272 586961987 131184122 787395868
419 419 856451246 347371787 214906918 211578116
205 205 173322137 105411049 885044718 417103619
862 862 611805698 872620607 296754017 462110906
115 115 343962863 196095226 871256244 701067819
724 724 772771937 743484514 211496238 229501360
433 433 505405285 739149189 719992962 528867617
787 787 222076315 647723283 120121949 758107235
297 297 55723226 903528039 636367983 940336739
412 412 357165672 277897240 17188943 856407197
601 601 337149081 106492379 918484580 802853210
371 371 464331734 20675314 543667962 513308980
287 287 115356532 432972392 128344874 260317400
558 558 833240446 965194378 986259602 828014678
717 717 652727350 481374635 128119214 461158068
145 145 567455541 83599505 628493590 103511142
126 126 159380676 689180036 598498129 174730450
213 213 227326227 193468705 904531192 823189054
996 996 216719432 440511483 815721136 992220040
703 703 809853629 372264141 7917526 511035107
379 379 46769634 669312068 735837521 279108944
88 88 989145272 294111445 684710971 127415755
753 753 102287507 498249629 149522821 309159274
634 634 738730045 426968036 815440326 863151798
156 156 52276796 144639613 57897366 434492691
353 353 732223746 965319597 183225354 610964103
216 216 153832753 999302670 3560246 414876584
620 620 711382528 619542246 474408970 728716548
437 437 677701358 250803709 528792530 130458781
408 408 95722074 96096809 245153380 998422237
190 190 289299861 785399522 117415366 244821375
794 794 556182294 292535269 634456649 519850715
374 374 884853220 510320738 253476154 994848856
632 632 579221812 402303672 295509286 904900235
802 802 396384145 383058171 822531223 573333963
350 350 967298835 726393665 349713731 28324810
895 895 768200656 839798687 101479999 16325595
63 63 714733686 809461141 386041167 596501611
274 274 469754921 421779223 199352639 905820751
147 147 220250803 271391173 807102362 568688504
905 905 182152868 229677585 582000870 870152412
18 18 41080315 561198929 990413999 129507296
777 777 984701099 510740345 399402614 171967547
707 707 577486387 108925390 959121517 390793063
680 680 6504077 714365465 409277684 804693800
844 844 653830528 479757731 980301833 282480660
708 708 633296253 451476833 467976597 415574788
462 462 577040343 182977941 496342449 995714042
792 792 155483403 142598558 400100697 199726279
556 556 804585246 620148187 468003101 309792621
911 911 855922572 67865409 971198574 252557444
933 933 215757039 677747799 603531872 679821665
883 883 432729472 688059576 371755771 225209031
122 122 652519581 50978083 354752067 546213480
796 796 978192373 17142564 499071805 176860754
171 171 524862968 625308419 217393897 902101020
804 804 522265010 287520467 517029057 887678567
650 650 213615890 174399136 787973544 32199734
146 146 964524630 228861260 893985712 321705797
142 142 829906704 593873236 729672930 791532967
559 559 274411492 221325400 467374975 599402729
530 530 851159145 936579460 816437504 544179938
40 40 476202259 302401871 924037485 408619004
233 233 422189918 661573909 851536738 736548224
387 387 83953064 797398721 768825360 503052479
492 492 891815138 693159154 922901578 266587659
168 168 754128357 1310504 329147490 925791171
139 139 258061908 130285912 35897025 193412875
220 220 51913673 681800401 499859762 675325131
742 742 91638021 945233592 156933074 374977902
772 772 510872578 32005164 650876750 660416462
878 878 109733866 78323406 40937769 666385117
916 916 556328653 227479809 31623282 885121440
824 824 509450646 84637913 616541506 661103365
659 659 986262441 531214080 301374017 890972333
113 113 471393438 233729193 938400133 450992047
357 357 160460212 329970363 622580706 908590725
40 40 610446101 610624623 988506363 910967312
930 930 763124065 408650635 204576978 952718299
831 831 384182540 650745695 491363440 60010933
737 737 572052830 659708385 447372572 773760846
280 280 128606199 202954394 799728998 251465547
514 514 723309848 785667449 414410645 777826974
121 121 306306501 526260428 879892089 754177169
890 890 633028743 172378432 170244721 468525911
555 555 612067062 927407757 512428554 864947324
628 628 992083922 812779609 151687719 898075260
986 986 814016937 905710898 968828280 56333998
335 335 934166327 436606999 358659331 436988099
171 171 677775763 112330591 531832521 6038605
271 271 201087986 390837266 172428343 349329561
216 216 217459583 675595913 402770463 891925894
884 884 546375604 337712095 216709880 452632730
277 277 960497046 610579787 627515805 744427005
265 265 164068483 78256785 169849691 972127462
360 360 262059651 248029298 22262533 688654314
755 755 152829117 261094880 985329273 498301011
795 795 637693682 410500735 197750829 212072093
994 994 334184397 549137813 196780756 261539898
993 993 124639404 272739158 550351756 652357993
884 884 91358460 961480868 543847209 60643276
666 666 876506872 398210424 314559352 956822408
568 568 360083003 868853897 370824238 485007338
359 359 642500992 529566723 31432610 726027113
824 824 66803290 757461415 889442639 297751430
511 511 896429030 870937236 122812470 18434372
334 334 952667413 555806156 126742883 940459429
954 954 604926474 866927217 48857602 305548298
637 637 659870374 95920007 549628364 983224976
532 532 590112188 221032836 487458046 246057332
746 746 113514535 282630141 891646364 854623276
485 485 300835332 632052723 545390417 331847266
354 354 373822118 339011945 64732695 919281779
16 16 884514987 925977575 893544227 307079356
897 897 415319016 824818622 632314325 530897370
54 54 655858994 546422013 520480843 413894021
47 47 534239391 216543629 587728749 673905054
567 567 125646601 859365490 974423182 336710372
14 14 80782287 752019449 341342796 758327984
516 516 243168676 150664113 539100524 989106820
375 375 736459228 704023355 418384659 65086040
577 577 439569552 482116489 766278819 839090150
612 612 627946989 754643869 428146513 134874865
646 646 709663081 956061193 184979612 789142873
230 230 278751086 55907270 90362070 528551211
818 818 294957952 599982012 365240306 422970343
575 575 314516259 716541175 352369961 605603022
961 961 713258644 183998076 612404463 455694592
426 426 837225560 656407866 611647879 99724146
731 731 570568155 445585015 891094331 918657428
162 162 634301932 837637701 677679456 976367701
415 415 339234489 573369254 374824281 552162185
366 366 622460941 457476772 188954931 302186073
550 550 211856197 337706800 222325798 206764386
326 326 824678573 476527076 222037015 183235877
498 498 803720375 884645009 961649275 879731344
450 450 260960722 458760540 211966462 347611669
303 303 853982231 533701403 303298402 845483948
466 466 13715220 848032998 164880552 22894614
843 843 314784015 237801401 6231033 108442902
90 90 495927297 219453749 652109209 691593520
553 553 507048728 435655511 681347056 335641945
935 935 965405775 816151759 210196603 408286042
511 511 451196469 938692028 469752990 632342644
974 974 543670992 535568804 191769101 978735030
773 773 201203679 750737437 144679933 169678151
418 418 781767827 875027136 82959578 467856005
713 713 118510428 798379960 593338917 203449767
147 147 813922205 31942931 639228577 101329339
938 938 606117934 793285652 350524080 135179221
459 459 734457606 175760769 874873205 959130194
191 191 631011032 884196834 800987488 323796896
736 736 754807397 105123915 111191788 331734284
865 865 650181752 21015023 978211902 860277172
793 793 54601732 463994169 564249791 232537273
823 823 528651868 190491149 91794300 288636469
437 437 381541025 702563024 705974493 40762241
869 869 62222617 228018241 18784414 840874177
403 403 568979362 841539497 97081203 552671881
783 783 345591980 905975605 986108797 75193223
853 853 663856612 136139017 944839264 633295873
769 769 735642927 701883738 948649900 256314073
612 612 152331434 953659807 367662816 96004888
430 430 466722381 805053720 803972400 808592871
385 385 137473891 966854318 811105119 997521090
436 436 973137181 836231891 429743276 28435811
893 893 63191315 837789474 197724660 864141726
402 402 854841324 523502431 521674720 976611236
809 809 731905182 992526103 473518071 389669683
645 645 531748958 291505831 971067219 356672806
413 413 990756673 697370755 221400947 389821025
664 664 372525579 899142596 954727126 271403570
930 930 765468513 814328977 126167211 330258470
622 622 773300658 633836028 720560217 348303782
516 516 337384344 1416273 939168819 521174939
435 435 713546501 827619355 53072469 156844387
647 647 495949539 282458783 615646348 430220938
482 482 654671524 687806226 788267089 826783499
192 192 612752195 207714915 713310152 594639533
264 264 252779279 820818613 19153141 367842254
397 397 950373820 340530256 789378567 417437198
898 898 113347238 158882670 262019543 140025192
653 653 469808140 502470711 737917003 131723754
680 680 787176417 249871814 74620847 118280190
122 122 709952384 246798096 550556671 599638588
305 305 628748743 558453123 502492030 369354101
520 520 566687857 644005336 308854126 79668599
453 453 295138559 882747774 375954235 352857918
649 649 7994691 492296441 591717214 784936082
444 444 566146546 858831638 746545072 268844913
236 236 242036300 182621993 11167376 830320256
277 277 353195279 506587008 550290460 440140431
858 858 761380162 91062939 952926702 904233758
312 312 333588155 747498361 430167731 544511376
392 392 883883572 353278791 184492866 800127852
715 715 392226190 410978989 731461357 119082712
637 637 682119985 566044015 656186990 289240413
244 244 611699787 440452091 371924323 792196164
761 761 615948983 453339293 578312340 562310978
722 722 118868245 319658911 767116502 551654816
68 68 873053646 193410855 949882055 220128578
337 337 96103094 926929322 488618486 210564963
510 510 889247227 562421777 319221073 447725561
904 904 551614492 855948015 451023333 884953137
530 530 30613682 689878750 69910496 377297908
517 517 717991038 824319352 612915453 938732101
513 513 340188540 303026835 182252140 53550806
483 483 69251173 144388210 489516249 241171558
769 769 782819660 712444490 356445315 206335227
395 395 16866110 917947676 749918368 855882967
504 504 238814887 993871875 161872389 642203038
9 9 274078403 119029869 320587515 280083521
987 987 536827748 685328502 226410835 188524693
232 232 507919583 22223873 595277868 945006005
897 897 255066819 247351267 522401842 788075843
90 90 691362801 362359657 594437754 11386830
914 914 423026920 350238691 455861051 482592199
535 535 65080492 943892434 745727442 146604468
331 331 162009868 773473320 317097251 808348873
521 521 463901440 5798971 58351866 259501173
447 447 849075099 902036682 656569048 961957451
198 198 754243965 881526538 856831436 733218074
184 184 987245595 736418057 472429068 49386342
482 482 317072754 161877574 474812699 986029922
888 888 778107230 627113416 14901564 953445336
525 525 451017022 853495877 968188389 449893071
35 35 390345141 550136159 865588328 953732695
986 986 442626728 222931275 362169462 59733921
912 912 717388389 941339884 339990634 596663268
519 519 408359540 501359564 501174463 992660040
228 228 353159495 257661491 410949312 409270205
761 761 258999550 378288981 793154689 266865269
924 924 776877861 246884131 64839394 265411593
718 718 436404095 998720690 265484804 205794401
737 737 848295847 63488258 98571754 834746341
562 562 609275859 446374688 777628077 947166191
837 837 65134575 842705753 142972002 553537423
809 809 903275748 695553779 180433840 298168742
61 61 987411896 645619068 765810393 265443933
226 226 126957145 906215134 728612804 792767733
983 983 77883212 842938001 471204647 624061076
973 973 601198753 462668435 10640073 848606888
370 370 54161902 976131945 551249825 73999106
307 307 975437548 640369296 87835666 49896119
139 139 192335156 952431 529463148 419031433
367 367 448139618 321126641 878228415 685544727
159 159 946958203 14401837 539616199 123694299
176 176 491599241 366976534 469652710 208260897
830 830 497130578 232810389 557755387 769784154
478 478 803455484 913309247 280929747 453012213
519 519 539772069 965949353 357911173 340834218
687 687 441088221 112467795 206368454 886524486
190 190 224887836 71183774 116810152 990966342
145 145 569982819 963006989 649320688 663941289
350 350 527307742 559902000 303716113 365077544
562 562 467155035 857991117 813423107 994111797
223 223 718897703 691486027 293461521 6629562
884 884 323039896 527596745 440843947 831336014
175 175 164118333 806989684 328007580 643543592
268 268 779885417 333018770 94165592 888919830
699 699 453476937 495303882 802802882 640650773
610 610 255610639 320273271 557653595 596278599
511 511 692461356 833564144 519689728 383682281
983 983 805462965 690270325 129716800 552534565
325 325 731104081 625573889 634089809 458519350
55 55 663363057 781179036 523310906 415650820
717 717 201296722 528721316 916970747 369016537
714 714 21091620 129194681 193079246 35844391
275 275 244014892 827619928 400548798 717427701
808 808 306362482 25147315 125789037 411532803
275 275 811361680 493259447 548461483 609880832
942 942 137404960 157088738 255202620 944048744
320 320 726352702 778425052 263299047 336070162
184 184 663100736 802481289 469638247 358835860
853 853 355847346 850028496 31547995 186241027
845 845 172324183 182182858 674749581 744493249
695 695 572901434 702602660 325976997 133770974
45 45 913444876 710889756 465839707 888715751
64 64 237063619 195081555 923296867 273803431
247 247 235728890 735987705 505031473 90082988
213 213 12415158 973612652 262541272 502928621
388 388 601217579 580258677 849584023 894654840
465 465 264017189 544726399 450013777 726870845
329 329 558485700 917409372 711433858 517663392
600 600 503456672 856464104 518096692 141668972
637 637 541632881 204217464 986169927 470673437
896 896 677521000 834983138 474094512 901883945
20 20 969046946 361153739 601400533 921481487
80 80 364768590 38722440 556281860 423829726
514 514 126826123 843761260 556352214 406960566
125 125 629769121 311448114 680926317 986848161
684 684 958012166 688783943 515217070 781751812
194 194 940150021 964976910 359332386 361215560
679 679 264552366 228639866 162849751 869633609
235 235 568002116 829260881 499064099 424725798
624 624 68955466 346326619 217952153 595352817
431 431 826590813 282914042 787965450 902760548
793 793 436363003 392687119 699080754 516677184
14 14 765447215 621540487 480776485 423530680
29 29 108577653 305229036 238992610 545681939
901 901 541534720 476121975 60221943 824865887
676 676 37957307 933278669 723847842 603081381
835 835 279995812 58939059 604168784 136120053
80 80 764671280 250295937 502057423 688994042
209 209 339884823 647315086 131676555 476783427
365 365 485257923 45648257 935347262 923128529
489 489 884941805 564097477 539647236 471602041
318 318 925582731 72991524 783521764 558986019
398 398 141037666 601774004 872835884 747172317
818 818 850081649 14693689 892811340 201690602
812 812 719278683 11369408 433297303 738427069
267 267 255113708 669673261 249013942 360110103
851 851 747284105 781969635 182368869 749728276
8 8 726372110 773133900 133297308 505852300
824 824 391976394 263685438 900112240 956112253
159 159 165686449 404132399 150797521 475749216
946 946 548994883 659720334 469282706 223027995
573 573 825089821 693991807 129188440 769829243
316 316 589270456 554103819 778560485 288193539
99 99 8642374 42942418 743075344 706698544
240 240 913930241 715869986 633932334 87287645
5 5 14688526 913986043 691034164 562869253
865 865 981119586 803405608 9634142 82358007
539 539 201627976 353862226 619758640 575173170
508 508 727677817 453618053 782833047 938406502
563 563 80779206 759239111 290072452 309409911
375 375 163418699 764044341 954952563 626696723
886 886 974517692 889528790 866737323 975000924
242 242 604471895 936689497 125486259 891812297
596 596 810573639 228989264 102326974 904133941
761 761 535295502 162946848 774203518 442378442
407 407 673585667 871430053 680802882 956604373
157 157 974845340 230603618 129481660 98007534
357 357 60351535 555212153 885945198 856500738
975 975 419707034 138540494 992933907 661340215
619 619 971980661 464351788 927917738 709557967
442 442 269174330 503213676 204036788 989353601
50 50 129939651 221016973 486197333 777478519
265 265 72647493 900756058 390071160 615885141
948 948 358669403 847041668 466428149 781010448
358 358 520607264 510199283 441984747 220823662
402 402 726283434 287628226 132838175 584598030
4 4 478074908 504129548 505270592 596075234
647 647 827594440 370595252 61580385 858034336
45 45 259862507 550033212 167572875 121978294
948 948 395148066 126963651 165939127 677861464
917 917 567308457 68972825 921415420 352628926
461 461 351087729 866847634 985897306 626791202
642 642 611675916 836673858 787352544 465763130
970 970 889489787 796596258 914881258 273584337
596 596 606961544 171967920 294734752 361977501
737 737 399853415 185224216 602443475 922461024
387 387 662699382 429996233 927251594 672181783
35 35 115540151 672824773 388522243 757953089
309 309 261184759 717944626 800579794 219575813
217 217 509012201 611322459 141710052 869531461
209 209 794236751 695128798 306808016 468154256
991 991 74426451 257265733 357780701 55618189
200 200 980133680 24479174 489725188 649350491
827 827 580626563 38007129 514358683 597857941
218 218 571292748 262513339 321120303 265421769
956 956 608963404 757696018 227588827 96866921
914 914 554549481 250107137 697071418 899989965
223 223 947665026 950968546 307982882 610612777
267 267 336855089 419127247 159082997 934418592
747 747 887767033 624894363 598008904 689254445
181 181 289168583 893450458 978997807 564786261
608 608 317234118 210905388 80830309 910155144
857 857 868824973 633734468 314429622 389176732
885 885 793073965 65913288 944399550 907573390
495 495 155652098 157893726 735361426 908717559
314 314 711503470 304041506 365380690 48015216
520 520 946538325 278227969 495321741 553754127
476 476 260594889 142896468 597592987 748170597
362 362 944374746 338527203 964387235 461491374
728 728 301007406 561498964 155688922 736703684
492 492 897299620 870634532 860099491 974522962
472 472 459407032 375717572 745712461 850999017
596 596 745162999 427519516 782178328 317880661
329 329 442584350 743156736 108907578 626536431
634 634 61005013 985874606 254388579 325042707
534 534 307938922 674786956 627968292 207409245
161 161 855176356 246325167 975160320 354364401
32 32 447308171 591401572 790153639 456082991
17 17 686386047 472433933 374899971 913584205
154 154 953938226 628728508 610846360 164058480
641 641 670554159 794234760 101270481 743711480
90 90 302117367 308963977 305229228 537347368
636 636 628617430 542144799 138561116 997387831
654 654 22177129 716241416 208603241 178523988
317 317 375768036 955968588 309664364 252186785
840 840 801254607 561320097 107235104 578883851
801 801 322527716 880895718 515160040 653946110
988 988 223306131 928226525 391915176 446833003
81 81 323057363 214785738 136738774 262914804
909 909 527998114 743760920 649623062 678288617
807 807 571909389 766754177 739049660 714856776
916 916 365448612 529705417 67005068 474982949
149 149 564791959 188013134 707695643 308944615
138 138 466821213 263573958 306486257 148562679
561 561 50307724 827064325 424019482 846495513
524 524 221835799 810130789 236558943 682898354
417 417 605688972 259757169 725076408 760715261
596 596 425504783 823074673 595030220 447103898
749 749 980287365 172401079 878430422 636786400
709 709 300516164 623229090 74012560 377087322
482 482 237926296 166515990 999019867 619923745
493 493 49632303 21962026 882468092 182229002
238 238 708234698 10098486 387790090 268212195
501 501 572821022 396285220 688114103 912190219
326 326 892656942 416554711 367258543 220816631
424 424 278487941 886072862 713887977 784500611
922 922 970896540 874664740 262597934 70714362
330 330 984793632 436819770 836630456 518367961
384 384 155159902 983718243 589838020 832149900
153 153 612013639 711730930 374734504 910300468
85 85 482209759 740466022 734677597 292209022
864 864 731606071 285933716 336274828 701660645
211 211 772141472 881290455 840422521 521963169
790 790 861188687 323432978 725241708 56917942