1000
262752470 291616944
745387569 502735475
253679061 410905242
87110356 683541095
451484282 345798334
85895323 930466192
730615531 571260801
176988410 694220312
775099217 894057449
906371738 461655421
74697452 68936229
875153689 691754848
318371656 705167729
627571599 19169838
499712413 589413501
13471071 616605076
345776240 642899106
668868096 380891463
628019110 535395532
544910934 467741379
658041145 537761401
872465037 475888256
381046341 617324477
506505785 621022217
119280143 490863661
879943661 605771013
407629019 231936324
702258681 625118932
872081126 481114093
14006033 54732674
662619777 116916343
576145925 632113308
226092459 737978373
542626406 589500210
95922327 563488835
151063475 325138287
79479285 934641753
808595167 994905831
198525601 726659378
874290294 836652498
669640657 387472551
567673532 886348539
263704116 1836556
160996752 593771349
847613187 54248276
207494045 560318923
837818363 250808665
527178161 814018189
25210708 465839924
475151526 16239823
929019715 985077303
749812675 708574288
475924719 863250528
497022446 902361281
254911849 17434520
685664509 456127644
263466109 785654824
483850027 463980594
774549302 48140852
828627865 968939641
525548464 865002286
226653751 291946667
121838259 228215471
319942728 48279147
607256812 224742971
638128797 462273536
605970056 225408965
816978405 636777137
399254312 477772337
994886020 320108462
792053695 147629634
180882695 664620625
895171642 808747590
824460191 568305256
192985830 934110328
949867463 449762116
143646929 796135242
973587426 89514213
879648760 632982796
65904420 462621427
605553074 28172027
899485239 944904141
373723055 741699555
23785191 120968522
109172661 95852818
188108436 508246114
971748228 905493980
118201607 618394437
779153547 912214031
468259510 173819709
804601720 540833773
875285277 636582836
702389632 859581437
595053326 533483243
725144650 607207734
554456796 433589935
559881794 666009868
570841583 206487734
541108489 668421402
302765108 858271718
655433816 383465049
295078842 941055946
593751391 15573932
858822093 368797625
86628471 781888863
485049864 149838879
507330363 565138756
569764987 872400344
277276733 970679813
72747096 726632832
852273080 248435412
162106015 616665056
855472379 258271841
372339392 2672374
215765359 624054282
604517463 745913359
622935062 244117213
761994353 862671803
901169783 807455467
381290063 915562003
760092996 260871835
344575334 267187657
736535222 666890345
319268477 74767054
68529679 8724552
151586094 848705510
927475144 194439975
959451306 358727192
422694440 863158714
18871038 731967842
694182058 508286900
55887719 137060681
518187216 492068104
1394235 575018476
579474123 446272937
34204760 388950996
235747058 312516058
880537933 679941282
270581532 45637453
173649478 489193278
625796116 594946135
27344963 966117861
361148019 573090093
533227244 493321592
72146122 172942520
198419444 644797477
216821053 557611095
67127880 824753437
155149839 907439752
167748423 938047464
557236320 94031964
966243044 360758612
252290 794957334
430519211 969835193
68779454 454166327
497273903 461381880
672310540 370197133
596960668 854068878
794675867 615086527
950229532 946504670
175700095 201206228
416892467 593272380
174538313 400676159
338162821 228766945
216464386 932706589
439802343 146476444
281914700 891274865
200888356 358691120
557315884 884974741
155079587 516658861
122628126 908440547
176982504 974400257
481511798 842359043
477949827 727515321
841622116 175115108
699110128 389505721
661403812 973623278
593450639 636796043
130267127 611541579
329240573 301260345
483145495 91749571
40325889 128439532
768982854 353706093
734673262 992842121
67415505 663764735
379919633 842287666
961525476 559002969
494731918 397189748
374195 750718050
411077916 805578822
63561020 519798741
9386622 913547434
163804069 736157635
255742241 754572507
684797884 341001742
788159050 496956013
519798325 335944650
20799703 815258734
463446298 741101004
658483927 663456012
876361167 729556964
385612698 714517592
795227994 427969151
359282569 708574789
411000466 310376238
800285403 563030052
148840354 180632132
28088359 530143430
885102038 387690500
121718428 128738707
544585825 358187758
78764788 978409844
982593511 970184907
769513222 120691150
270324209 425523137
946419574 788988563
736068655 363985307
482303911 167270073
350890726 40895391
500860421 241569169
92279244 687070748
627007882 174942972
934536908 935315580
92641875 851025097
478918674 430067540
4104156 115025453
783632045 55594695
817719907 793564829
507627332 174183455
948615130 123558883
213023251 413048730
434493849 697942701
28872826 246289195
43151670 190609705
766683683 182419268
804430396 49988311
130671200 812872451
994756939 666593493
843372001 951002267
617204463 666722787
293558598 175184074
249610191 733263944
399640314 591817326
862361200 725937740
627026782 988611885
578181792 166297512
847282893 444521709
992054693 9744835
619225061 278593431
270998308 492796261
14111674 57945958
928387727 288362458
973838173 838183027
268981798 248121907
154510347 434301866
845040803 874884428
979003745 542668138
703068763 831428529
622473596 868620787
394798562 762936847
104189619 375079329
996089790 844204219
987620263 742819714
34986895 898928438
590109055 134204539
300785787 185196085
123412487 749666744
33932603 132120654
378096564 887317333
281010550 196517685
11763036 769421531
623961558 474028455
882541409 797235526
13351914 885074716
963342858 563684514
176784798 572346066
273919044 8889118
107989319 509848526
117072321 150875136
775415628 586905331
808657044 617391772
389804393 780088258
905498737 143394354
851092988 668703276
887735200 842282232
398486025 711242294
901760562 509260715
974627681 118611471
637562366 677703028
698641086 32319608
577793820 651031977
850497668 196635773
133503314 671251184
541010100 611817949
201685422 883144301
569004028 150411512
916035523 741501739
850028490 976258334
66912651 891549483
191415619 462662408
745654255 577850152
724652283 759399518
855989172 34512547
787253768 1886202
978140398 710765442
162032904 951563577
762678814 226400444
41045537 713970858
516945445 152030524
677051134 734533083
823034135 617956150
68205718 436404892
257454527 462441940
956910545 841328405
41759743 136853287
115122765 65117118
252027098 487185090
583962217 166209276
113036213 309456102
837243831 152816330
742550566 395442201
236299958 352660038
830794449 14158101
104580882 600288197
844951604 499356484
603343788 614069386
965205820 884588353
320267456 530323055
521201086 489333105
287579140 717555276
28831508 996274309
858523374 246168921
16933601 532392272
191094195 626534485
315971756 324825713
970695306 840346421
849522368 626846201
120761345 209720728
906572338 238346169
309089596 648909111
621633101 106895124
865190041 182175415
931087396 192430466
441442034 329438201
609435357 275693974
477268838 463825260
943743531 690583228
333403154 993157706
798061595 544602638
76443348 946815879
483525422 530679374
957909610 233806659
771488159 383423460
382684374 509986732
639946288 134702331
209253545 401139465
314008691 211850281
347099785 831389558
861887619 225129829
742495928 508773449
871361814 623171052
571482386 342805241
334950588 484037548
754813711 139629995
273397402 89998601
423808037 365530367
4776756 223834663
504133295 475401026
506181576 501122637
322416063 804874711
730349401 143723560
642715974 186086555
654421616 406717126
822837828 53647578
459590489 646379278
628915296 975156496
148788234 617289989
718129294 682340525
931828817 357747013
923327414 409267231
653837364 816022466
652476645 44420802
950971703 552927769
246574890 271637833
506526885 166349747
947279843 682076174
732405720 312246160
953031472 850881233
999984674 975609600
841215921 46038992
308864405 372798276
814006756 828029608
950083741 645905492
721927725 385123627
343104021 765285965
922703884 745683582
524852562 967453078
40092109 720284507
927609851 375127982
506090069 2632365
163436747 948742086
46394492 353869747
953178285 376516773
22745844 514413570
229135001 632007063
584619680 787436611
133565181 513465872
532266205 80965583
923998737 749672849
151714793 723385776
453021248 384342421
585765603 171830334
440453233 893384717
457554461 315955895
160719393 855786040
772999142 120155635
804675760 529425504
224235575 166034910
566792273 881866173
583939208 330138111
958024445 301961610
109884206 49663592
8201811 490437661
199359475 249226778
849099047 847872005
290949672 424536081
673344804 835515972
607236131 778702473
373435193 674198719
452306040 841389953
795372675 749629812
224372829 924703681
790866473 456564996
579804739 379094473
341151527 284427384
343581894 972347247
949176839 792870532
925817918 856683414
80389876 43021597
722845334 813128247
204488445 471439513
765984286 498436175
785956120 60264326
857703128 303739981
502726029 476629779
890957989 386753688
337044747 640250908
918634034 609365886
786046555 25986147
29600545 567236499
291689443 960366084
971153682 196285212
995645041 857686711
851517753 366704592
274446140 136294247
276830854 980811200
431388003 615541647
7765751 299765709
904541215 413403736
449881058 672654545
783384385 691936919
840335799 862287560
563337171 972908589
728015334 981009303
88977376 608464764
24053816 491832819
656928856 26595627
293425475 453483788
587821041 278411243
146561536 451123516
28257733 158758382
193291359 985701181
466592576 25274897
410376935 885115276
967239459 36400815
919280557 890993670
531254903 599901278
476664944 890263005
886601329 381609496
35502225 213834404
424209981 990769009
507008557 375473607
409178223 409672173
991765971 225883196
696007492 271395055
530996826 106899020
476367943 876983161
322457224 876786520
649418124 306843490
271778501 661083333
974651204 618091206
474543453 936368078
48400904 543811544
497337851 802545111
735843948 182332239
17239717 460567607
996621907 560345904
585130213 319296549
415066994 376197162
243803226 752062778
276457341 82482437
310878539 274577533
591804502 693378032
615202326 876192817
808278326 438801403
800436873 40539564
740639383 34982105
49501396 917026538
193795132 179741596
342810782 339168358
6943544 156748062
482981852 757478027
52710312 839745254
123896686 614287460
415520357 523428772
365297925 757463107
721712024 691483119
172264702 329402895
848656565 794214706
169816441 750058334
678831238 666546250
502946174 537601698
42744011 877119961
723590815 941261174
455632309 646881205
327367711 28459711
135624457 787292595
291340384 515817139
354080278 224426266
905355669 605489331
347968245 650775621
802205633 719744400
380605296 246093740
113372294 733436536
704994222 697713614
473302477 889336722
92141413 294564388
554597670 746822726
534205844 577193647
202624074 331415693
789482177 535810579
373119712 208086653
119412340 100551247
918540673 136974565
858490791 881122961
390020625 924567709
920909398 377157268
924914234 585496024
510942886 43593265
819169936 724731990
860034794 858255223
328847591 317182503
448259959 37565736
201417486 345891682
69595306 751426679
506666730 750991946
202252979 127805259
472099008 787740693
608803727 630637343
376463393 171684389
977110994 80240114
699413697 515693379
889544858 187260775
522196060 293296146
919259184 852966330
128034912 342706028
50225166 274582806
331971404 658407246
940749536 291768486
673643549 282195036
73025498 660913732
676350200 815210947
520918722 833292395
940767166 772526853
90443579 313384347
375538168 561929997
462488758 877535027
719052905 960383784
520350219 178415108
115954139 757883534
908842156 432002990
33094919 25037137
66422607 434653403
309196461 364000258
500897728 628637045
731269580 623153292
817657198 810665678
78188598 296403094
405195185 182312273
739506028 670563584
941931972 716734717
804763289 689706999
689080594 736826032
477547847 664156177
322446892 756447009
68834153 462191405
882675575 19953602
245787675 914491317
251258242 223914191
610124125 537981641
100525695 39113332
231747905 725038436
347031983 5083840
526063143 2031489
770493051 78450698
165147896 191586683
937022346 865957938
848926988 982869551
813365433 732634653
295259255 840729403
47127121 691035309
981485677 930319881
968991646 701812821
26671141 893390978
101146138 708479809
804257868 566430506
437597140 159440848
684419520 921185321
30897417 278786789
286916960 933506647
639823439 268791709
280909859 774753640
830246467 142257613
735637879 936388289
542272035 135628064
559947491 966139348
442047329 397298235
486559733 927699953
905216326 404219083
721026563 503197409
440722906 983292422
682315024 581299698
644889223 4196622
832632670 686605953
905943230 357946861
731606185 874348827
708902579 371856861
802305761 756977710
5618965 946767452
774262571 91447596
464275867 62592713
68813886 94270890
973981380 322477897
978203369 71986147
78242098 494138026
700563657 702659490
905555516 803838037
391523654 632803089
496561914 998733504
875939584 455714792
213430972 669400609
769758878 839315314
359730977 868518338
439487400 126273772
130236490 234765282
918883784 84208536
343018241 679316361
988673139 633897224
104425889 831426371
276994886 250355704
371558832 525918602
157176484 87018189
521991575 92763767
883362601 641579380
973774213 453607695
637494904 25573767
702664154 806188480
578909783 298169679
23006839 986883526
313426354 671896873
300189206 373502412
253666265 988847609
821654139 94722148
488307210 604095498
551029650 252650551
529518357 322225694
905904531 711365748
901593934 881006258
530958367 28235070
684916867 345537876
752256587 275000336
348682004 641531449
523701499 892200446
937773748 767863759
878090838 393586100
777294790 926894892
270581918 188068568
952819283 832270072
592035577 24622902
933488709 586500572
236100097 905949774
122593800 34210748
522454703 514432340
111011662 660394179
4176017 135381283
955199366 666742437
519083830 835246263
138983713 783028489
692049138 60776718
467031389 220830818
727070447 549303908
270669282 636036467
564631104 371889786
41831139 849103994
896368188 395542645
284483803 953215669
750723985 637261326
988262377 55073511
182381891 743357990
312266479 907419454
885091736 517707568
25830286 22198738
949048161 982426020
433365296 668188269
460865056 183746448
695140229 280614735
902098885 938274635
891616685 292501398
832296779 717117256
606726613 254566402
60336063 801096726
475147921 67457895
446328559 367258459
154075077 590608757
496168972 818262163
479417395 105131922
273311234 856715981
328296527 506214327
113256539 653644963
92196071 579201666
706916041 428763677
755761288 542570037
572798528 484381574
352483449 338797852
863380097 276281850
223519708 578192579
713755247 852343425
13571497 147978999
944926160 621089587
706535124 644586950
256913922 204374193
593341971 615746915
575524775 366094083
455591442 616357609
953162312 174486248
319831738 993215168
980309844 794061093
899998514 184211224
777584036 375258611
303589720 404282328
254183549 30253384
867397498 283886455
286884114 887633997
264273082 358815917
36842030 556919064
314333232 186758475
761817375 177284941
291985907 10293138
984223537 713503929
609983085 265286379
979926661 622994994
795649925 410508671
803310581 638732568
65214639 576676961
302804829 629837002
389701000 362570574
835328714 824353624
683715675 76596491
880676176 530338437
652292290 79122211
997577132 762225522
850698793 450611662
46768517 159274225
190425493 572811718
393323104 186771389
996435716 423288666
448376647 272637549
559358851 908961638
535095415 516657352
147736712 14380667
193559399 476022057
569519082 984229286
988918922 704533793
966156582 697580509
514247095 320411866
475652758 620119247
66132889 868074080
247965313 211820410
349984193 908592088
181168091 552623576
881082979 845899573
611920841 453035121
996701938 214438483
473814631 681918329
242309004 504091365
8790784 543158340
544793078 627475782
79877687 832513388
744123674 784061808
923070042 87575282
599026274 917036698
159810363 720017565
844840586 718665631
429304666 901929889
162070901 72469856
642868037 73487583
156451507 440414790
476713510 180832395
92558042 983560601
986345747 832639439
582467302 605330438
775615602 505846830
67545748 606311742
119174879 921164046
633017472 690594750
448257215 767792806
89321281 85272621
968982256 224605177
718021372 685535447
370215118 670120534
285156372 993841000
82621497 431991868
691133128 271067413
838875077 558022795
285068140 776482818
600004838 211337778
15151640 255064458
787280988 849471272
497940770 222568956
93023370 130654753
280099381 501840304
537362323 712777322
232789614 493288082
495897634 103129328
707553431 884129556
592685160 408849043
886703139 476352896
233335828 592443388
350457192 733926887
147848258 972674711
573094232 377202208
354341659 117805441
879245900 253858888
775597093 970445385
61395609 606594207
269726364 460127082
598771502 787218543
588023202 261219864
53236464 459024798
54434243 976069038
237306124 146008966
304965200 862639462
586596695 872090790
723981007 742508920
507249682 620104582
73964412 233002980
242518813 516563423
669905825 377531808
622326129 487644119
258264236 805075272
393713266 411744170
145680715 808481418
435840350 653966754
254285020 113251062
308009061 683137951
962446568 348152073
330249953 715368817
964705588 436588961
40777336 570269379
960275351 56018499
921093817 180357619
247187611 680543043
132478946 836178358
36393931 754469734
965490831 374396334
609338766 882133890
664201675 916193499
760213132 188595083
598366970 867084893
636759019 771073950
952598910 189042488
823958935 928753335
385951747 78187892
824590572 406292859
309331414 117088314
126718719 243951675
216594831 323226216
594862877 686125385
542525284 956991432
649326557 253146646
580082051 145604866
267859002 238601990
288939398 953943329
318684584 407279148
902675837 449012102
813660780 730090142
51912200 37657787
18916294 629609256
626979565 179256588
679548643 805085637
749506247 248234454
187482664 796280566
292458862 666124883
25026862 273797454
904266833 143577235
315330594 304986060
680776609 224430448
729575855 213638181
206259191 412279001
691850407 160195277
962122651 15352638
754648790 168376004
323155713 424049457
262149081 406176583
871743154 910686785
827106640 219245801
641051041 879675031
989125974 569770574
154841322 894701837
842439746 579983642
429925557 737098876
379128807 181313643
52256297 607854912
203361805 802341865
714901043 223346456
527313782 969513788
706284968 642014688
340663361 690477364
853725438 709963375
636934646 490197758
321538488 554481318
515429651 942247630
33559451 163433568
847216258 518624101
865101950 504998701
593117963 556142438
862716392 643939602
158188860 290573704
7143757 913509266
828483043 233491248
131153005 884432038
924100277 693099059
500060172 943686621
659874037 579315273
943262919 958489487
200086051 986899245
181927223 275698602
308634220 963799390
722211192 136840256
556769453 457044116
654607854 94287302
236205656 948435224
268456549 396313369
939590233 595538415
481195292 70754887
399531064 949152170
313841405 951428765
853042820 564204688
36558636 336173867
677569405 208198958
130926955 584035428
978247459 974263258
601693819 371640307
350755930 732225197
260567983 741944975
826958816 25180435
24852736 443417437
633875389 774390329
642890823 750436691
73130439 758611704
37360671 385255547
326445135 229443195
142533852 416964596
816940458 525444460
418935645 456417972
905355454 960949829
981564964 794714277
780808665 325316028
625555170 32026691
358263237 746950446
15050404 470112940
46942398 27663670
202447997 277835390
275868129 487095722
509467536 922805215
277123440 522224017
357528748 981666825
322177854 558936199
866411855 208071854
243889911 895236548
721954391 282230349
821750447 219884813
232737535 90405592
389582277 310192567
202543509 353333301
560649603 998862950
937748364 90673591
121751398 675871693
921904155 724085814
691110304 751485095