1000
700464 113962079 33043783 770187105
432338 253747981 140033628 884090547
94910 138768321 72703864 269057710
172045 462054893 276715562 826439371
718588 547903475 529438967 574315990
436699 569900564 521739571 687722677
300933 421081281 407233294 427229390
8396 603859305 350420244 684431939
221274 868125274 816913232 898913019
17040 248023147 93301910 292688230
177939 175583060 141967476 204585281
564974 128456009 21478588 149253814
823584 692755869 173109713 897008158
733631 657397881 593190762 717057833
311716 602147756 539480158 773497649
687373 142154246 447514 355961485
48328 223829333 144467787 425451886
298826 186803743 153356891 457787726
780497 265021297 255378193 375707686
260132 152741499 43783124 171547077
170367 493618071 427304072 891764320
62001 201965078 18031907 460416637
364697 178965956 97308068 513558158
424985 863667981 855650082 869887843
269273 713596536 582015459 841633475
117925 351382577 324893835 982471954
811050 311780937 231318188 569193902
413681 684618296 542742838 706793634
759860 365369060 46660231 961492287
679096 756613484 702134173 780734401
614192 59543220 56598228 930957964
293831 690453452 238699478 731000664
954463 884682591 496320961 924806571
410947 118834940 49573522 206956651
883113 691753622 653168080 782427734
59906 417234903 178854314 925681450
671154 773235864 716364747 931472609
837772 778066926 392840873 868585830
576600 679648044 614259816 725623122
657299 509570240 476590179 523720959
561065 793591723 663595360 958691786
435738 339828576 254894515 721341636
704644 365773721 343212761 511830295
486825 552699960 26521060 777061502
731933 866313709 786353127 906876298
235476 182899878 144908868 329280089
973454 507399401 224638341 886161885
840339 376034071 366428450 535309037
342744 673163585 227316959 681775015
363684 101817658 6669780 137145727
997681 576616206 419234735 606942823
956506 635847156 519087043 809955698
19668 254848472 219485424 555255523
49676 447422244 91741747 784356573
730851 444185884 431559388 518882209
824961 645722452 593293259 872424869
288200 420965280 271463994 527751610
966951 188305158 59431282 673866524
973286 778932722 701037956 933116662
117042 471909002 317203240 983818480
225145 728421720 510748356 772734613
460936 180208609 115751269 817811972
603045 710697743 299050263 720483488
954061 337050399 3840830 420334667
17777 712918454 83351404 738035443
710041 568305601 280305752 581227619
355169 781545777 282178110 808101487
606980 915372755 164485989 967019111
860204 448141939 321364047 463357466
806754 612871510 274394913 850154510
335935 356341493 155908552 363605036
588321 838588553 423249587 882025885
578680 171024625 160356344 186403155
844293 90921200 20003874 217842020
571501 975417664 902168226 984092597
329747 963617547 756439912 991615803
338727 569096341 340259675 588495960
745730 417273587 235799843 712196802
671797 504667246 190861607 976944746
463471 650601692 32840148 810086450
740645 310636098 204000484 459482753
714016 290092697 279342217 293284971
483429 716118377 529506104 733263155
356998 717416659 555469356 962736717
148828 253089003 230270159 605965461
211448 147612620 140853204 258534480
676152 144835924 111591500 949320319
386998 433077405 411625728 449005516
671882 318605347 264388125 544777045
203715 58495125 47922413 124026983
154189 445444573 49282259 558997635
727868 613144273 268646793 856926139
956737 490743627 180104886 574910648
224456 199079803 30530330 422010100
249263 670271419 664205691 761463754
806611 658196583 633601110 761456669
994668 437467645 168261586 654312985
682500 850180482 848299916 850603767
175823 135364036 20579673 405496293
794789 355678470 309350145 374273346
499948 881010543 869435361 950573833
472985 388656619 56142077 399129248
817397 98192334 80653672 599435187
662942 269811371 205796484 288193313
553195 903209155 887817153 909218689
642461 800713523 644113460 873506078
523932 29968988 16706418 376821246
299736 367528352 19191012 681710444
863997 613324430 515159927 711259015
693239 679313091 545416670 684081364
964440 436659787 53698740 948736173
521561 593426365 34148756 688838847
179417 651777171 485589723 974860194
90631 361190972 349130753 903122253
712866 245340115 186992396 499730740
990054 360095282 318925915 360351560
70089 641672608 121449737 713956273
540366 745594873 698620573 883195572
745486 873470573 415062554 908701311
839824 259680733 249898468 276226746
77791 308089515 89705032 462028266
800393 306079474 73692758 445818911
760370 929208973 888910937 938501877
993424 427987468 166497824 838789150
461083 171530405 168882492 175665293
294785 445077587 410190626 805196240
688296 541308352 334597326 929264522
869438 688538444 489768854 808583806
303850 332121209 293249218 901432730
472804 294637482 224211658 946655433
787476 278015660 104283866 394537222
306704 149327821 62991886 196219222
823183 394510694 302391060 434395305
934713 743970497 406369894 974113030
580179 778775961 660597987 792877638
182114 169065497 74071721 430125094
859120 647145736 283481617 945036439
396888 694618001 251945193 943483112
513183 209865700 26061290 351990488
733094 813557934 564015499 967540288
573288 422450106 322285760 450693678
150404 101087371 98801432 125221176
798133 554252822 137451588 773130381
352844 857880127 67881165 951127961
302366 382160610 204922339 969827176
945984 592831084 417745056 652877897
40505 261035505 247104569 271783312
137303 573229112 94214147 718975568
787428 122389252 103832665 124948114
40967 315492245 173661379 357088200
712714 338664942 337606534 374398271
588297 749595553 279210503 816847792
441122 287184131 93684749 938397507
264795 340973439 188757887 427493456
541734 646836231 455518272 783488439
358809 331974097 312088480 348005527
862154 612765661 555650276 708948315
811957 186929816 130620730 520455933
492110 643051729 545322909 809598947
21734 846885311 639438917 944183275
468391 48213858 40938524 242649586
50652 452169542 439575605 477076438
865260 837150196 694399306 891321525
667405 877794080 813297523 925529857
105732 104486475 50700698 250446609
456807 301663277 14823263 451492571
829977 462468934 429333519 584040254
163492 391662410 201219601 610226895
700640 333718181 271587817 407874752
575545 796168501 499033082 864554740
76968 177978518 100946740 484940856
584530 691142684 400614901 766741641
793769 510158752 275142948 927135821
332874 411617319 76242269 747702032
595651 867138424 840148446 982205045
694085 309760280 282231037 491431884
280784 386832533 150126592 396431860
834837 407058170 401656750 433111847
2477 613287216 423467768 658215380
391822 636262094 610329734 731395911
585723 533018110 79860234 715596361
437584 385377720 171065806 431400885
913974 181237573 11428201 521262537
891920 674027712 456144192 887037933
955943 97967295 55772951 215324396
97052 344203411 199154178 992220363
605407 568880910 196551935 703347208
746843 398164949 354759474 459119620
193172 444859519 444030070 446196602
525735 585044906 114740630 848907271
151578 266367042 87238300 429259782
767193 368659241 329376675 458764140
703609 313116236 249913198 554571434
211837 703459625 199090990 939953805
5096 558148055 163619206 825553345
421543 342628620 137458923 760398672
387748 481089486 450516324 496114027
621985 175849365 161002718 192772754
300252 487839052 219971988 998538219
348014 960752143 498274251 977354319
50144 523084808 262486323 745260727
839367 361017683 322884856 640349170
106473 169975405 139561119 235491487
416903 506482618 229721310 528696757
510869 493997220 214283679 626982877
511962 231705104 116883060 463076780
782170 790900693 392493635 860825050
451321 68185043 12138276 70575105
523899 524261095 194846427 985651197
725032 687861571 660062611 773497911
354567 420125033 182934636 786241263
868049 755152919 684446205 798917127
462538 51337779 35060042 103630799
267233 273126691 7815978 782049646
127518 556579759 212130292 716790095
998457 517528140 308665423 741590228
554159 546677792 256582600 645793749
459077 409397724 71471083 596992615
121958 168252704 47758869 552867655
141642 482806562 443397293 634273818
814918 794136025 794077848 794141634
644473 328660285 137986620 371211454
717468 295998179 53274676 728684759
238449 274156732 272029691 289085709
689450 665235307 632791599 671707100
191083 272814131 256523745 598264488
362859 487048799 178057873 842633831
494144 155146739 4071377 688245573
955913 679481305 610856757 794674581
357873 903374272 113611083 907464246
117756 594893019 281912269 908693281
896139 452752517 101046804 647240738
659720 877008501 859362150 884826823
897773 421896400 192313566 710256163
930964 280820159 278641083 922441687
939779 844019518 823489886 898772763
333468 539016968 39832052 978143073
107348 639635483 219351513 805217003
589096 937601887 871267690 953048824
701235 394693046 132775044 476440522
198026 417036054 388774897 437747017
708860 573754024 331049160 744763891
163444 349669779 310664179 673917020
18059 701015000 139745346 952036264
844407 139495486 102598206 426837788
188508 607296850 404513983 925655857
307197 682981175 445767257 978465207
248780 814997834 810869528 825428483
21526 544528107 101108646 664297008
24137 391493869 105112036 671038993
751888 676962904 526195826 830282281
239495 718797966 569642088 881549403
313104 586257910 582536729 593695738
948058 508457086 323295238 830021638
876690 492359567 455790867 566585117
667609 528300475 352568324 661451758
201785 175802825 143208140 188004466
154123 381258559 95338491 575646853
389994 119971086 38510861 321525045
592763 211192883 191963953 419673893
917455 344049339 176422071 429004893
811512 494515541 330537435 685187074
221551 574059824 561618745 577059540
48563 265203651 235015004 685548449
888935 554694011 336795527 706649178
224954 48940082 47299578 57449490
57170 532779554 464555943 571705685
829277 240473283 219334085 247328854
736181 634789186 617686834 707395345
925842 240060640 203180383 661320278
487335 881048074 187958745 906800002
790760 660738002 352943188 737786709
517652 701208446 237077982 715721798
329529 309647202 263858159 413469471
766016 498507348 388360302 680318692
101732 595598295 541597676 897667241
681009 263223546 253875365 301293824
612983 659703936 446735892 771476494
388373 907424384 895063025 949713005
29752 432006395 266027806 963436870
639917 297529080 289634933 543698238
366946 577497089 327839272 617487332
651360 448981240 432307655 477050499
462204 350769443 263083394 480234118
915591 712996814 660539464 713733372
767184 853332815 773193448 895996348
556022 440134722 417550125 576868055
697361 160467589 136547961 243382797
361252 850865888 198162607 858506558
135110 210499481 72064314 264385576
922973 598317968 456389604 640159808
910267 508539186 173508845 683320277
42118 877235170 850690376 885668991
396983 576393263 218601222 643522851
457859 728479667 542433965 765310421
628914 192901068 35105214 465793611
413893 474213415 414017236 612432759
473666 458232964 348039201 757327556
199418 86034965 23087743 217173541
84712 894918665 92725619 926642210
887620 324362603 37380419 381480235
793182 395774200 284643683 412276484
978612 133584320 41080977 185704489
931497 600728615 555924746 740324560
464918 38832337 10386298 41239585
64377 125328947 19132469 365561556
531321 690388811 442011457 963633646
94030 785339897 698283686 797114494
736433 791844426 609299797 903411424
541558 159875115 133667738 174282239
295589 541092407 285163427 683057384
495165 527828598 359537409 939033238
15258 333117955 237951779 430553745
499048 482327447 189026312 964725323
147035 854852944 843106197 995042501
948376 254101884 215195403 289275267
949240 472331260 344091057 759369634
52111 325043816 99285456 340207364
791119 333699320 190819427 409915413
762629 321580865 181390845 326792318
620083 337961470 155124381 823168333
300725 27259801 15831689 57798407
84524 634503480 238362089 733628455
690687 81691745 41383823 87744815
565804 304692379 186547907 935985462
43453 525378409 172931136 525423126
695858 218958230 112741916 509997710
190869 783092043 54692290 946199154
613294 261257529 126354295 333875062
872958 692862784 677123864 750700773
452342 511529309 500846126 648014629
155666 205278012 63538524 242884803
116445 878582832 546348329 884436949
830000 477707820 450640263 867435468
24464 432463624 357106435 456391339
618500 823508397 80903729 926812111
876101 321145324 278410643 366560254
703274 521712956 145523768 989234862
376048 255476932 35244774 277034042
409533 419909704 224872215 915067695
863763 626959358 356588056 714673621
20829 651437526 355410052 732902319
448354 266737546 212993711 547249295
464395 532927581 158679838 542269669
738106 816785784 619520891 931147178
702224 847320201 601206783 858929766
56744 865799564 53835251 871005394
396029 671939991 433214678 839527729
722184 458510937 260391436 512688609
55133 474880653 335501038 551155713
856616 85715631 18670758 435560512
506908 193147842 42419473 337470387
196800 421244543 134476262 501624960
656658 386608837 117790236 413879637
593775 319722140 249997647 750924134
526963 547228782 96545732 684357612
688476 360637776 341034595 370626705
713385 546311622 215544304 704864535
57125 154014179 137636729 189465809
303442 272353185 198061011 842993754
126624 383588023 261369606 518991457
951547 909661356 894467285 988058196
431569 358642955 77362890 662940847
915013 534888309 17399903 978170448
324298 198540536 178156419 895713299
668637 402056773 235181891 882686048
206329 487923593 97539433 845500662
962511 413288107 81409666 770365222
251740 723242669 686167784 770450989
159233 453376873 412766400 594238474
988905 343884335 261854516 406984679
256399 350650482 279810535 757580162
927516 119810633 112422702 134833902
20286 883718315 849579241 886322475
703993 590159821 585320774 737325997
570077 646119700 596322881 733262327
680222 346211213 271581965 499139335
722284 861523551 700137408 944489514
770259 327218817 288760994 771920685
978571 358280993 356978536 436482197
721368 79295719 38130357 157924884
124670 172828467 96442429 231472286
432276 669065222 231528516 795676932
129222 838620350 310522290 924075028
786268 360255422 348021793 471848130
853852 465022484 422183775 711792747
406713 678798933 545496104 836546025
430637 832751189 571513308 929253144
629385 244464673 222321993 244821458
841277 567935990 438774119 584932867
440046 155474917 145476124 201498261
853566 607786069 36389145 955447614
644565 562639736 26841336 899418355
345274 63246352 35628228 829207710
726132 233956217 140898308 964141380
362054 355553918 145605554 519630153
96629 311592755 265576967 808386159
75924 317775416 189371898 548782882
76594 595494956 590112265 610246677
238866 379028300 378320205 382993120
983949 859539184 223101635 986495131
430371 100605110 2601860 319103569
759363 750641383 206343261 834389478
949727 382451732 220448092 574518629
774785 186129345 145819286 293295665
876364 843956119 767078235 971003491
890137 240108287 120914782 809738665
859739 575368559 527040930 580466764
944312 851871777 629400557 909822470
388348 541141870 484072044 567959172
90480 818664478 618452092 939785178
116764 389450209 238166433 939179598
987847 556333777 375406916 760874866
261322 720116742 19989221 830020403
699333 524049200 166216528 591882244
407267 474424826 255899750 493660547
89353 618235222 261219476 854034845
950858 291057846 131273321 294734481
228058 332392234 132851543 466214795
606692 866992188 246799707 954273787
857473 333286991 327531884 438787021
448504 77789703 64363747 101610472
84897 759734265 2213922 931506831
955562 350398632 248539286 725721682
507048 627479177 617320244 656836718
882223 43640974 35935645 442656341
654051 437374450 299629613 786808825
825286 934989808 326783328 956296280
540742 599400005 595234167 687741463
250737 726378408 629276755 744226563
386042 541713077 68957282 793288877
34266 203940951 98175060 291804782
265639 531690892 385796631 756138252
900639 302280673 301636410 309422015
296967 363516942 330314488 661371048
741157 511722953 189996750 877596106
503078 285370646 243312477 545017025
401010 104659105 64267248 115316188
770270 756830024 708559721 840603133
529573 558854403 461030968 735698130
713599 753690754 486992912 782174779
926387 512058521 109243609 564664645
977737 599996020 548844558 938829966
375864 945904742 878657201 965750298
554487 272416437 20504744 549747021
180315 556131705 267660520 952927415
102991 752144240 35609301 786715974
437698 955737655 664270506 985627624
559779 609351259 558132586 681159681
343842 415315521 44253169 671824643
346901 509882913 269893404 557330312
612763 349403262 343932607 358854273
822678 114255430 59450717 159110083
776402 476257208 440458321 758801172
92849 874392509 747150299 990096415
715679 644410179 492159340 767172689
602302 298571062 286406870 514438139
117971 196573050 17577551 389539247
68660 927141186 924781698 935241782
348101 589649374 510538080 873912156
272981 684069471 681583924 692365269
940363 453997850 102482934 700864005
578485 517712590 494750335 870267206
172155 621384212 343073291 660306323
139379 396789961 343741862 836815462
180264 138301186 66432945 152479020
723539 557301630 360160304 683408363
236616 629483699 586140202 704957931
892755 190478971 2985467 508532000
614359 802372375 717386302 820618382
166921 453389745 450470694 499232128
385427 456301762 119332767 577729716
385423 685639216 391538241 828421535
447541 774324624 554218285 832537501
570251 18627211 14457434 60368919
983023 454969510 106338346 647900641
707132 985345821 438901605 999424645
402527 617061548 25785611 617487724
831804 379042863 377966453 607165433
130432 716108768 389879849 870695805
908762 154092072 134146418 814174085
78270 151448318 90893659 340611847
727858 789212444 89112187 812566517
333059 571405224 555791201 677938669
550790 965383363 953466622 983919955
345170 603909419 41556587 633480248
179144 913745663 92868755 914488625
666081 151320156 47839748 882693978
189409 611786613 509392305 822744217
476318 215644085 21311354 760881450
757265 467551805 354789092 603476987
150253 706944808 384151693 745766944
568356 489014277 461519808 673273659
601704 425936625 393389927 525146069
52888 595416527 403152810 597360655
943435 646119583 99346261 651333301
995856 587703177 509315351 686415670
119976 519726705 246222576 734084763
327362 761555336 215072037 940088137
651856 715636058 572038867 828915914
576579 338253934 244035975 633353909
712654 824497161 525229758 909417073
175524 681377727 531837370 876516744
304939 441959892 422001961 707282178
399040 605629936 65839247 676620870
15787 690363685 588661683 706772111
683081 682769759 387518636 968332728
162513 688332343 569152055 946825868
70550 310094170 266756408 842807092
527133 70521043 62421786 86414905
890286 512741822 399882819 588161184
806589 471672983 205229406 685371291
403329 718493537 178824171 931264695
882882 530160162 507696803 719139930
653040 588720219 136855980 636658347
693724 610914135 497594594 621003119
393711 444321727 223915112 613249774
308826 401604521 246616710 586050092
383636 403218160 109467948 588618612
585976 810951603 713319507 943059786
602096 191265853 189905290 237696416
484018 599440352 532096150 757319207
355163 730628898 657567864 910456083
182533 409135442 130946512 587606305
436632 629007951 429055981 968613062
974255 346827050 194575334 939709072
645760 319632386 17489764 437575345
218235 709616733 691678705 717186514
978200 144730408 101157944 573003798
54564 370793804 18901405 901199933
253625 207745476 119234258 323204128
79329 215125466 155177107 916173197
412560 376096788 185627502 571980003
859009 246053543 178024079 261765143
125512 159279901 70885652 856151907
253493 221099259 125284438 552344763
350061 62573072 33226314 171791254
838832 897983685 353807334 913655171
738900 738496844 554127963 796469351
685928 275261087 194838618 546421056
323300 609781039 269427899 793045061
623098 580217947 45228013 690468749
713305 567210078 1206358 888417836
724770 131433004 61547804 150471230
773783 17701362 1629492 315682866
409216 548072645 537117725 589270911
171387 484262178 327210882 685724761
432964 284424200 278963721 437716172
289075 316787202 125222359 398728036
424690 508430911 386319096 803369840
924794 404568536 180498466 777579882
344226 871702516 870896949 878470484
310779 340305200 237014212 450281139
872190 144727175 7671506 525040448
645323 443786513 255478273 525593325
549757 305670590 296194971 378469500
573533 344919864 232838344 702653680
784495 873182184 858891671 922210911
801208 134298538 101258302 953100864
520876 359928750 215132020 472358071
317254 392038629 79031549 431664129
322447 138968824 31354708 892129145
693776 980560136 978939954 983146150
437401 933859555 896213283 974418233
498564 523950202 277280023 900158757
106647 865970406 818952246 897327515
424535 899447973 826604985 908495188
704420 615356926 413421380 978632351
193606 741320770 511602777 902188766
154854 537057776 59563001 547610814
470977 538914950 519475224 572799363
311556 208128251 131101702 609033828
648162 135869965 83684790 406671982
152171 651327897 475565515 682003482
533636 737434607 736466919 778163513
585701 344167270 116360053 463740015
318649 632828671 194009545 934729157
990755 191811963 97698879 641608188
690432 365549784 121165284 754230352
917669 72153129 14901136 148923034
463803 827956327 750955563 845772323
339582 807777044 396792108 844825456
810924 576358780 458352505 830391492
843277 287288186 225964710 650136599
131167 638770851 612988033 664334724
315281 902252733 899891867 912571758
171859 342713390 201905342 605752133
681599 414448829 282710203 820402772
311720 494768893 370019754 606712105
399421 436229109 140373139 726274538
321723 366207178 92557035 431469524
98037 805820929 727445772 852220274
400316 730276390 719206883 756830017
354286 280203960 251467396 376149910
177445 687643475 587789740 998951577
8097 370540812 222862067 442398897
989097 350836478 305948726 385365892
838862 532435723 515753584 726730336
74214 326088287 55480687 832165758
806624 242342672 89658635 793316308
104620 391384175 125573299 738455133
822280 893728501 852041571 916462415
716416 353811622 65639462 475038315
464250 234666414 114531431 265775029
912992 643269046 195105302 942470408
154463 426259833 406535961 497775423
999752 756572720 547189732 936711442
627187 855700527 587603077 875731011
928103 159566434 134727073 224549431
827580 663030197 661692625 836481016
614221 773055952 327484572 817044064
591739 695153503 555040662 726465729
475680 308743815 297792586 378139309
259014 507459539 455004155 596085170
432980 715481361 583966023 729363927
4873 668582783 191586428 733878824
956574 232755735 232700948 232759230
645455 535735478 378661341 910439056
194613 235605640 151522734 612985810
442204 318599856 204531004 487208756
593817 257719572 134043547 542330595
611681 78502686 15188183 86247447
568162 938076947 889928422 968024108
747275 515364210 513544783 701094770
864217 141333111 56997513 225377659
889681 336541870 181992554 814331007
690587 511795821 52816765 875605981
180102 437378513 265335595 722450006
872143 788846598 527153553 879250735
972369 356035004 5710754 577671933
525158 188380267 129200943 319186182
180651 23468604 21030833 32065404
744845 283543345 165830010 293132518
85319 417198368 314771495 670931326
483008 453941991 427370177 601093082
289957 664907138 522842093 829047220
21305 267256551 201501693 293473421
577490 477488739 240395806 998855696
670724 44264019 25663350 142092768
544825 323194279 285637973 328460187
200888 175141046 130796552 388682923
715237 285423854 257856112 298080204
938986 403209581 216640621 618126770
786199 819787619 636916476 897718315
706900 484560905 434221016 500909529
21473 413912444 18463711 930854085
107984 100615890 79099075 632365632
823847 945327645 936177132 946662383
4383 410949789 402938434 505145931
262359 892425232 743670114 892571686
876327 685833900 350192752 819493519
651296 79662579 78086496 90794066
272251 517983688 424511431 901282457
887143 85095832 47707419 745384806
711414 758495052 671860103 792933029
555480 369178332 192863919 889344540
953136 772776737 646686883 929125892
581615 676264772 491855962 921804263
375011 364218911 361257340 380922492
452286 903390890 523043356 979584672
48845 975265896 654704215 986683501
944507 160436666 139100159 180845176
46435 952617245 944915864 961008656
181164 702416402 371237995 739536433
145658 614223632 509904191 672974930
298242 834245754 321818921 861695234
498572 514470564 71232658 764272179
39840 603790026 66115263 666292046
330118 347948163 186915782 569913605
241774 682281065 397581460 824759045
61299 437011590 186129222 496203014
976520 775144368 293986118 958715647
653434 305545499 194058515 596635339
490939 750936383 729069204 773425734
89230 199650671 158877544 217327088
549929 327266220 185601213 361678877
653847 184565717 165840268 189978087
623093 600377860 273222743 736909042
10239 84772702 15938840 117124899
887094 254291946 197080979 701675289
242572 101312203 34453065 700488167
249898 623248731 508795867 710884055
808362 839870100 811808286 879723475
623662 774757002 518616640 784782066
658040 650520865 46897404 676296605
925806 296392629 66314293 441375487
86273 597821161 272165779 891276149
278073 712456872 553459595 763473671
662638 358496441 146497345 756834651
897138 809315334 67201984 843253384
970041 483167373 26968686 555771981
639734 431395800 313315022 913554207
959727 460351218 6081490 956459996
356334 592968939 549205473 697664426
668862 386646727 377811041 498480847
267027 505599240 223735900 742794502
760928 245967412 229840866 259042918
665040 857561461 783017466 872306694
52588 511929234 507507725 613988953
395346 307845861 247244447 371175146
834373 228682615 85377620 229059951
475822 606777229 527985382 681924921
713942 79660040 56060573 326069709
217516 122703823 70616137 235729989
340222 97398367 77254930 544167432
708199 404926556 362866774 470712247
789014 58158677 4689151 63410697
296447 424900799 340967467 464173334
427444 465148337 452027023 475875287
467712 796060883 792934400 797711611
662559 387807279 205072324 770195597
95158 303498920 261983580 358405581
588581 72666416 17610875 95551155
532018 723219826 666697801 850671734
902749 368584361 277872751 481034351
383605 131007461 49037427 625506047
992321 751989954 726031236 823489015
961170 713867117 191925317 786473547
809990 847767710 845100869 870867881
417487 244992300 195967075 271963134
52225 746473191 171051838 839038368
492070 173747144 32012009 735950132
188176 590675941 489910444 999070709
185434 331622340 313566885 539350442
146120 637586437 247104740 763956098
9446 570494226 136043208 680153271
470872 625168577 460404437 663896580
957155 273815161 149591724 332424507
127169 569730206 548009244 985884669
697394 638214621 613596298 698509662
476103 467805544 69558873 767260427
577347 229904436 165679621 369300596
280634 332559699 79284045 586492490
872565 224324577 96277824 884670647
242660 580749667 574350205 853715710
695870 329612396 209033634 539649492
560379 184470449 101028375 367772650
528917 160082194 141983358 456269873
328191 278691886 145788677 569173993
5486 177086073 163639627 915950309
250995 692843180 463222584 694345854
256253 602328833 336752069 828036019
871947 260004467 204037210 655294190
427356 76152526 43220956 130265096
317819 122488733 12912127 700245049
190053 470078348 186260576 593758875
457608 418905009 91724290 425457430
701538 493758972 234187985 551343385
645877 509422553 439081061 779316194
953949 156780704 137663662 682132704
322391 477417536 169306142 679807486
519017 587681160 241029195 651031078
915900 783078528 382749766 942949412
275720 739477570 734020413 787248749
819976 194894469 117374840 370613084
606490 239306579 72791475 705690391
184115 343330742 19322206 355064797
65566 929324658 42893270 992193532
681195 712402161 676206415 841154644
929800 597679717 591051402 944473499
363786 353909189 302920500 459379959
820916 588097484 469138357 767290908
257437 375768964 188191640 923431800
563971 515254478 141778712 896320756
726987 17929943 17102329 17962199
94728 119693920 62159785 400763111
201584 160660633 56882342 346426037
25083 796137111 336311794 867732912
695276 236548193 172901036 258390563
263285 429564890 347753563 833486827
436491 190277598 90049754 838344280
111808 480044324 152560207 849406832
439220 245557994 84756223 553579439
706432 532364710 480043957 600467189
226513 620890839 613134435 679014328
714678 772052027 771563537 780941106
18618 431309224 430809636 432711585
343309 653597355 358855467 801138054
673825 30110280 29691367 31150841
112981 572914867 80250525 884315939
112286 494080699 290520310 622281065
353462 497389981 454990445 540908073
863803 800970426 657332494 997593500
753797 659249055 656641689 783955847
830174 319295048 111484620 363846208
175381 505391146 175804799 883024915
619825 503072548 54503407 689392401
311600 282167220 117483329 464829674
5706 83003957 82879305 364579368
522031 315048586 174191870 382850650
125125 802601662 697606515 929513147
10235 328407368 328116753 328667043
163760 355291377 112027822 439715591
542530 920889127 892988730 950299997
803126 74906606 68990600 117922223
751316 866352854 850449526 892741821
58899 779162660 287649680 991742086
297639 223715178 217372841 898947318
537472 150231164 56056226 459917440
917567 100645969 77409826 198234554
247058 319995892 169452477 628746333
705632 631099032 582828949 915626554
878795 666175960 297482795 674971518
665840 666959415 634267602 704014624
287976 66069523 32168829 165388424
455858 462452728 450165501 472643036
226254 866465364 349266921 982286752
533441 86332882 35644880 97087680
163822 319579930 209149318 464040606
7983 406925832 264804483 684994397
884554 161851811 30671704 387676164
270977 534211451 412108384 774970548
666443 866088976 826150556 867960143
538568 556612568 384648163 562331317
286143 625930405 621379256 633403166
247321 412712432 356910572 650997014
477252 364925165 76314090 481702734
218361 831485633 601787300 910254633
376520 318016209 206086610 720216223
274822 752009276 188084526 753995683
96667 408125158 355953892 832250295
159697 536562392 231403737 644618589
174314 157874566 135093031 308148445
178355 791884548 320453862 829460897
742940 843304325 753567469 951413000
217248 783792576 4524932 893840433
518289 406567422 222963145 884871409
640454 321046825 117891535 709032866
557330 683308489 433987312 825478579
19225 441100934 185146014 705763714
372834 314788060 257449342 563723292
542394 803605132 798859697 818313503
730391 873421823 751142145 896953294
885245 259140264 47277398 352413071
836044 124591111 107784851 830454635
449936 995660310 821528053 999683821
293982 172297965 100084139 189467116
932454 280781420 84217748 548325605
18667 465771624 268754584 564919936
58091 468969643 444104842 526840057
144142 246964389 138215006 784916889
842862 895759472 634366889 956364919
222441 524887975 49792369 587295699
462779 86252808 52110694 325483553
520416 723140158 154116927 745894786
733105 582649622 575120879 595804090
290725 54007282 47021468 87660916
879531 638145460 247284396 662858536
490206 535702578 320759148 644263956
165366 171945300 23191322 175413248
613154 616533465 162974506 994986347
420918 164054424 124013251 656511821
175385 232497460 192390887 260858330
285603 500142155 481874867 550230761
336108 385582692 188881202 428285873
636472 550173641 319822664 762204570
160098 632300506 464951148 750150742
218899 623595178 484877139 783827275
234797 263989459 111505807 320242063
713793 924563453 893987937 927020403
59323 147647980 132214191 322527345
542864 461371014 446460888 592037726
72323 170745367 114840805 246854590
9269 182819591 116797710 235292670
302871 179095916 83750484 271484824
941465 183180795 83025988 714478475
995254 667941833 147318380 958917516
733985 580353989 312287878 947322446
188222 604360084 155221091 821059888
655594 145679883 128211912 217655991
97696 714153826 680289952 786898866
652166 473813650 396827947 995939368
230797 631839818 351685014 680281064
667603 381884786 182471592 552737562
842773 531574359 53322938 570317533
331834 682302353 586523187 686626592
733093 895835453 550636131 913187160
372963 739171094 705338082 827925381
378873 873891520 89702671 945039607
323531 857126585 765209339 923236460
198292 431027201 60002879 653420770
669717 260211845 222678517 926313712
848518 563165707 127772246 877978988
542453 621523840 236619744 906810134
98585 204127059 158469330 433002320
462655 401734034 372051495 416148648
216271 236674483 233312001 430066760
784711 406849724 355311815 445307965
507467 811403073 605424332 925446239
282623 608544660 103805943 959661847
422620 684361576 580149577 904561978
892221 587941269 98316954 835792480
440293 838333494 329746815 840610253
647987 112998988 111246223 129799631
386256 156619461 29134785 240633483
899105 306421171 98464683 343997948
237159 328020350 256606866 382791253
163308 468029801 326954499 608780986
328904 169302566 54320663 896801403
937922 309430525 169076188 334303744
260241 505151661 272253187 512445818
171091 154797751 54037453 726792540
552427 654099630 572760253 892011173
205723 199234928 181999338 257121355
933716 331005403 315663502 367147814
141413 103947038 77148325 375273556
302148 635845073 168993797 891430976
661332 108231481 4585750 242713383
360096 778578521 537235869 991768737
762683 433210913 239249388 738858127
485942 755990825 734632566 892840443
974042 353225854 15622071 848953156
196073 538801905 365951980 660031905
948481 339541524 282825697 385089286
811729 825475894 822941740 853795838
228607 1541290 587022 9061959
696328 468610825 172407913 634552114
112526 704237303 459139683 733630887
697121 257575770 133520838 315207899
706507 847912889 845477618 866810233
968990 355123305 46269335 501960336
1831 746292858 734479845 765936853
539515 655707596 440712117 747098451
799795 639548121 507173992 677911183
469629 804178169 429365771 805993520
364785 80722728 77454478 87032409
394290 346524730 63236826 410922344
488929 350400468 325259358 603745587
805708 130394354 125537712 271993777
485823 443555324 166827110 694928753
737572 184595532 135525448 370574003
304748 877993998 15990361 912191560
975086 614515188 595894196 621761745
43379 291775436 205194539 359910200
134372 189590533 101206400 322354554
655283 891075420 1861196 980604815
589812 236679031 42947377 341058217
655871 723510331 476904260 761200690
241576 861359479 708408837 876445528
178265 319733783 244988050 382918118
275179 483637837 323106234 603282872
978253 343033270 341132334 350244305
623719 252271547 113220275 483303806
513594 639162142 204012541 953817499
991487 461900376 438448771 538800307
366991 533973009 532689859 814890882
804757 381397171 21266705 397155534
960727 672833320 398892722 705597178
562245 714263118 134824105 824079523
823312 516730470 46145204 570644803
223809 869003592 366991567 909107206
527588 895835130 888726981 924582246
282784 185776426 179343917 634079386
185275 376157429 221250270 439496942
504935 302161674 183842124 344123504
723042 215862896 190162819 249227847
366968 644720250 575603983 682342768
114511 99992414 98415787 102004489
766077 302654762 172644248 518566590
649779 152506817 51886156 180633730
46478 478886070 327139578 626440478
289636 584716813 218520205 994203722
902851 919156158 901564537 951548484
874803 597499269 530698937 765411998
174634 61149166 52276160 99468491
747963 249275954 1533756 366419151
123753 690688081 674657440 900974136
450869 750838847 278441595 790111872
38387 363509599 310829591 390990095
578041 603023298 215388735 842592035
821237 568901671 122229627 791444960
310865 763869632 602752989 998139123
978691 847081420 832727680 877399151
38133 899842843 871136442 929644037
955444 675618160 125706834 711339730
374744 236231432 41234672 264217219
861554 593034118 558462815 711723282
911720 483961020 344507510 598784235
359433 114756545 60323335 173284620
340039 338854606 334149589 346109746
817531 481817263 165182913 933487992
696049 692098357 667205617 706781991
981621 283892614 261443879 339085031
147900 172537668 147494473 176826077
632539 22761613 1486898 964292060
250513 223110637 79552253 253753480
633241 171767096 158368476 204827014
254585 125198123 14684766 539013702
465761 328767072 211464125 432955492
697950 320580197 203966919 470300656
249260 650081319 364373935 659270970
545016 516285611 480642057 581096288
729288 280084849 181887605 766075541
881051 484021470 176901948 623014541
473483 148796529 6856918 197656171
282799 704814859 529810705 889679993
932003 812618971 431657601 963271696
813937 236912514 178542832 818909997
346842 543738181 354759215 638669189
327181 262739422 142153552 543810862