1000
63787341
369701812 911877131
697367753 849786938
198597999 383805543
491826261 804929952
298433131 712294277
232000456 400250434
464093140 580750555
478286604 592215964
193321429 267011647
129515869 794545557
231899188 999003460
63573179 455568945
371280245 786207167
128811910 381099980
378932659 571152891
384491178 392337810
51788984 320027845
264799049 350047931
791630777 926038244
180100863 232926070
220251103 842031831
553382086 581342823
486431094 662941398
170367331 422068310
355285500 547201199
149079731 292547565
20711543 484315325
423256652 970868763
863261461 924906540
443451555 694936456
469741535 830664199
50244536 814690735
81931491 595792459
219856315 357475111
473792405 930988642
286332773 770718481
315224302 450391480
132895233 134369789
50385347 133153538
602953721 868445227
153013315 604806708
317952818 860482467
82336550 902814898
170320271 496910030
14529371 144906942
496652746 597917325
346882727 667233636
321672400 764199154
206091290 536650118
9788229 17548425
772316950 777685889
52463192 56193926
115853646 322522688
346318232 971638641
724493295 740919568
285825742 823078007
306873720 668147618
206794666 372494068
337270549 964458925
501326724 794443887
812218120 889512796
116734936 876213210
55241522 820895215
288101046 455864796
931546393 971533201
603390946 645159419
280927719 585323648
276411497 934049766
33546378 182746588
60422693 666988276
645864769 865042810
721292765 951371285
212255915 518301551
681503722 758800790
239752499 787703951
604680682 999938656
74781358 140048266
39059929 427448318
138923944 685386476
141832324 419323900
80896429 808675962
155553162 533644714
58117317 955642591
791786641 826235460
45319994 428575206
631359274 877582430
714189089 917153138
178646126 556702916
36656335 459535698
258852126 946968164
489440283 961100692
46414287 500129694
539145725 554257673
425927518 999494033
156428377 442475046
367836691 827345373
481013638 642328349
461244436 760094947
115318328 957830483
664250164 942254282
69257872 176271872
501056857 890316730
53114972 146960481
947662450 974480514
353619691 769510688
192413648 665749453
385274622 819234623
142867132 704456080
222661994 678041385
291873037 516970903
155421285 473877125
276066222 324992019
681810625 712662771
274027558 274694351
3257446 354368311
34899300 498197802
827298770 972655951
332593834 933081609
393727122 750833844
469745700 984064565
462178450 921510564
131915078 767887727
121975859 399196475
336044536 348445819
930168471 931896634
220589294 770402433
70274367 645983680
237816828 809549983
104549985 771078337
931568203 936183813
193626960 687217363
18874376 768200916
461064146 597082350
1209379 668749316
103100829 794654061
445718866 921719650
22477668 178970577
75825235 944960188
80417548 124505644
101030873 401397374
427673759 665522745
220384952 221203247
812087076 972441461
75057347 410392868
747533516 810001083
56151522 398490485
814276490 915293981
271359884 964635735
458027171 905268543
297918714 429617031
112552300 181927152
536978426 620467392
235164112 498599323
832750921 849862287
533466117 877143976
499535595 743775265
583453295 674992661
419427150 741763137
734732813 958903986
291509890 693678456
72142855 955629350
625308023 814831790
73575862 367558921
603345861 723848591
320836095 757756238
165729576 733526131
431046342 945787914
163838810 911871696
556065435 994676523
213252440 527962459
472076389 977502614
866803690 920763718
344441410 826127171
846296678 853850976
825701273 873619968
431553845 433230181
383859316 811953153
488903313 896295885
469327398 545281597
17217687 987828958
15561337 610234746
352807535 587560142
423789099 708447987
434802856 661283400
549896041 851350790
305241852 537589519
105008594 803113818
105485314 920595272
461484838 622624588
298102411 537203317
116990005 562993215
277178397 755700440
134786719 141601404
14165725 57524872
677987758 821044468
434452925 702558201
69413190 700678973
815457388 821815291
127269703 132568942
532458431 623283213
32260701 954051177
100629223 381686784
127262875 606429501
662931574 796926453
582554578 782347074
38042336 435534662
169466826 626807706
768347495 948498661
243697804 347303001
795855142 795855143
828361683 903868734
860574963 998680891
156687628 381220985
44775816 682012608
289771770 351880810
615477106 980488315
97259253 591450595
99073353 418243337
381927521 656097735
64585149 662461243
264988400 628534720
365255359 821479162
263804895 297079227
302568191 833797633
117865642 799255348
650362718 868676686
239327690 975205832
221919219 313319523
192332325 240906355
623677020 844420133
245049029 600062574
138197343 564681313
123711452 826476277
259764905 592947836
453426686 774768938
39054802 196104320
497032117 630484685
587876563 853571648
147060599 522671143
21497599 976102766
367817124 962256438
435902535 455244478
177650232 790181267
164033740 175628795
698362718 997075582
392069112 889657609
626778446 630894626
307869617 680050545
572494779 824953444
526197670 817171861
244477811 800765363
142561017 386883851
36596433 921745299
242241229 497104538
281463345 426547235
65015883 724862463
368534312 378300044
289712469 337338430
222825493 701723507
386075878 993683883
113018212 621959172
95078579 766552827
227697746 681744907
444917204 968166661
569004143 816902178
310164562 971623876
340652216 824080542
629485544 988273904
439059206 975948773
151008682 580328281
80773976 795510151
41504983 985802124
126915116 392134268
619594642 744819248
274565159 676016412
27860621 466825958
568714644 892835168
366286795 598665194
415569393 605099722
341269843 453156016
446711048 449550701
62502176 998834516
39422734 435692124
11138474 421044693
276570712 735804233
895548893 898863566
394791196 827019419
378531825 875097935
519868895 970515186
261194533 938085590
123632899 812842811
287878545 496525563
436991184 525341593
38832709 539593613
184917733 626172017
82110455 304941957
138236799 690301780
592879321 877332156
44626027 592314245
613831735 706547481
469281377 855769288
542631470 880039767
257632272 557737262
20941504 587023068
401661194 458321343
302963398 631817800
127735268 705907009
29245542 305732030
218971635 985100472
702011840 880521506
670892773 978052710
142109545 524064112
193366254 499336299
154684758 770793702
625675205 662405802
294999214 584583663
46182950 930471177
186270746 369242392
76336962 466149327
351482299 405743413
250821600 300264509
541385771 734801117
769022277 823776779
194319966 669787196
333431882 613062065
11323594 77920855
290693318 333403920
250457460 296777857
29464295 438106712
62408677 977981852
543895906 582477129
26000077 28218511
371982666 724600764
132339045 143353240
63751455 368022806
799409603 828894039
880632611 974832812
213597461 693245216
275409131 642552272
662644092 773362781
399932355 474085805
290965727 744199323
32126840 553453925
214729491 477236541
871790580 887825458
587357974 875469296
534864831 775374399
218931728 348231432
539810520 915382752
811412406 818307675
476178825 679181521
261371358 323000645
40328546 275376771
110556325 116294703
520687259 885144225
112255275 369547396
867631074 991167430
53048002 364615486
477207995 880553936
215453384 838126221
94408914 202308022
519253884 863333485
562449206 802586329
781927895 946186445
127282101 630021252
320199670 748455140
472576341 781800162
49277125 578525469
639359958 649387031
143613945 336707989
845280447 998209108
17739873 863691537
122770043 642851822
378508136 656432689
53108556 585699842
513302011 557612728
638128791 782830949
590549377 642591993
3149138 11965664
566853503 710067548
86572719 720227199
113837624 304156243
65018436 863220977
436235413 971240224
536458674 967895097
70502216 462489563
350265613 622509958
492460449 826922260
276981273 627275116
638971299 726246467
715030791 745430671
122307188 341740641
560285630 669810660
518433094 681392918
175670617 537784959
456823286 907287753
666968375 796160664
343854879 349430127
575511879 988912633
392055698 445676432
5495417 740662620
258607264 649644042
451080397 884914067
131708249 636461758
348430232 663785235
72605253 348117386
152702243 395761887
166942869 293005657
283850914 803372976
539497459 958450506
540584295 803764760
151085247 389054428
166263285 323800716
449946284 718821195
16359550 415044843
256547386 645258405
683320116 784251536
53633220 714995567
59501859 711650920
767616782 945808856
218152006 801260333
887410345 899660430
551189901 900865961
646572821 674753932
509521731 512829842
526898504 858764622
274445226 552972609
46847246 693554240
520095189 656482951
450196393 781353050
7573421 629524930
575332888 962863077
587871830 651259449
278614874 402704589
517931763 718472970
611952569 763357321
566806230 814277049
36320249 755246689
486385785 690028157
957455067 962564326
30583729 244008717
34164225 769631346
289720823 805696724
80590619 827111020
403631738 875598268
100420527 243147797
76455386 366350151
614167552 750587273
191180395 763501743
196121454 513478172
571438908 661621415
364257298 364788258
380223451 540676256
586715618 587385659
18396373 307323104
522257033 956483287
103797912 294317555
142166806 242294403
559759639 572254976
149937642 669420368
836485061 957220303
26932492 385264054
262079521 523650405
339281006 968860464
228369930 457643584
279558751 580179383
227720976 234831648
687913189 701813632
900886230 901006266
14158977 732426791
315546167 975330252
625249711 898152135
686818042 803182559
218446416 546326273
264166049 517729823
423454120 738877588
153563755 436154402
175339958 715355774
564954832 903080358
32415563 968680609
195684569 676101586
545124494 697616865
126090765 737619958
178465752 292226986
683258121 787290050
202682065 662212669
347420503 762924216
132758499 898904324
348633815 985662670
640965418 770407358
421777495 442646172
322145751 648713650
24247231 343619043
186625949 215628561
48450150 339484633
246250566 601682192
608846197 620935823
361273556 698532279
449887849 959894952
175802800 363488975
325825235 593528469
444171158 832142397
94318906 915131031
352537425 635932175
468850166 821318734
234347535 234885394
144809925 634236056
167567116 706750197
273630013 799576855
671850593 721339144
506598259 554677582
455883844 489239813
304874831 863697425
315772666 792673385
643490048 964898157
609831148 644064655
516551958 604500511
307046206 867648978
339910413 937414813
251460405 349518066
607229428 968281243
253120163 321000489
316161896 325006440
794847078 834123649
806352370 861786989
311089886 390230399
557921635 980945439
554848148 860329711
736478904 904186471
93421805 803400038
854385411 866549066
131176155 443489641
348095294 602605183
204811533 444037902
157275259 361047401
951989922 956427129
630177111 634202912
303149938 961590199
242462598 992003181
186572641 887806162
151064393 445539799
602816526 926859990
321621061 402129827
24541561 989281795
276494433 421315050
660601720 762891709
455627176 688055619
141116391 724027590
62723828 559979859
820359599 935720156
407943437 457372554
336642948 802756586
99303895 847892512
430693345 828229054
18442325 257713541
801082137 891258031
296274518 664737773
291369148 680061077
285675780 766403498
128559178 504609551
187764946 766857914
272195987 871905482
215703218 887613648
404107256 605175205
619567831 923004530
129935322 198903619
804269915 805089541
642177336 933257368
875674090 977330900
493790669 748627772
61162074 422947548
386153065 833162887
142988942 987499684
525259787 573421229
29690106 444494186
565850534 930139998
912512374 925825828
128826035 439302308
503807369 892430819
481035355 879060717
223708334 235574223
860907286 883382901
645896881 831801878
276961126 390380349
389496867 499851389
645557894 885240013
615083768 818771241
420122546 881213558
945239364 949987940
269680759 531472220
102733884 401765828
193926697 768954649
601559733 836434055
174886289 609914013
58363585 388240699
93664594 907069551
24704785 629382135
27330348 573211724
220604120 819960402
436955384 879051818
34958718 680905176
681506462 923886080
338426495 534702215
60532746 321710097
383054813 427297934
18494617 21615803
200486497 275790879
793039484 953979335
393246080 823336070
270108440 590922507
238664730 876453207
309510314 580621530
637180717 739059243
642416998 670611201
209454057 827992485
147504085 191679014
218886031 567106959
458759898 784383266
92821995 125896392
180321098 977590936
608942548 642080529
19849850 163062866
179782428 830722552
296091425 737165709
8642144 855492156
243062823 943480969
517244088 997980528
324285649 326318985
258487960 512680719
312612925 894542230
489562270 519981446
255256189 871172172
187374188 521974683
147716099 253623104
941496837 989281328
202104456 544495195
107531230 813755818
144152125 199561734
244677443 987724282
104226082 799491784
569940093 770694601
460038770 878626692
338962318 753097459
249764234 618820807
169141461 911302647
129795539 443965032
542820313 598205274
449881509 487343902
265284877 431637596
598687818 724727923
944188787 973546940
150621820 716222865
298741673 509995163
254400465 415638892
178556216 337928433
186318122 617749768
407830241 749632620
652810255 856879167
193907425 550632989
492507589 731256790
260104048 967582913
24497051 439858863
339723224 896630233
487027735 976670894
206574190 318626364
770259642 856674806
52559702 198332982
576891332 965512119
481453968 539426077
971687008 982863316
604957030 928748910
114425558 458010620
356211629 764932195
532411188 928837468
300617230 878296138
909384753 982302750
261736552 723718421
293107147 528958345
427507718 699956354
110690049 851352734
39230512 210821989
945197083 976116679
657971587 693869150
27346198 471540738
123352523 418372049
134462205 254257078
347522664 671556712
86088272 243804305
207578684 608599887
61905039 161829377
749955335 882222559
88850392 396784941
13052346 990726054
346758648 857998105
308196627 377798942
488319859 927653733
450796461 912144287
204713794 701095975
23169860 56184509
326924085 381836227
20142026 529891095
284912906 901868176
648681878 971842246
158070202 423066027
326591715 696635065
296210605 952981059
76079422 440652001
344591525 982925767
690986096 728831329
86263197 563453305
994884554 994884555
313646404 933789624
41565180 301699103
381346338 444708825
812099558 825845821
598570944 754320909
216696573 983691864
10869587 885992023
483554935 686811865
666604972 972373276
632956477 904283595
279831568 916687966
527746991 536026611
371222277 995806398
11599805 563652519
428520179 740428066
346619562 513604144
221107302 226620099
106303198 720490758
126203177 825211419
223636823 774434804
486678993 684087573
561208306 674627566
14049556 344132640
274951485 974921225
848940411 960154164
161738763 284965296
535869366 970329677
36356086 967795348
155767043 923133653
611595547 921661334
251895613 810698750
389257506 481101552
600118598 617040985
207051373 232823847
280645967 850096572
302847666 725428325
81862053 531899042
90768661 184486632
488942500 705378285
41438827 813644945
409689764 917296006
226092255 265884592
15255663 704806810
378575333 466361248
654359244 817104492
486015339 832475883
81291347 103407875
230326193 513877651
666632477 938144930
305542408 423397209
836900293 871177402
490928532 580087344
19510872 563376997
352955181 984331134
95007765 176630952
593994855 819122654
90419503 547227235
181663178 207236411
59512653 992629075
340001706 845980735
3173899 695948050
190943699 451606515
705550232 891960225
597841869 597974197
707631420 872458911
46078778 702831251
321337154 905521565
14854839 52150047
299939203 530036936
388700098 405773869
633072961 824934004
249623216 957727078
34180063 597049988
392554849 937670537
335713636 866635608
295030367 353752976
366167068 371797979
618373423 868706372
94182176 236798988
150135740 153023615
295069575 794147683
379410274 617034515
228125085 487311599
796674378 913896387
163498537 471492608
959242996 968155572
118483355 655193476
552756029 844534464
43898076 506046496
325371613 444301806
586769272 809305435
72685157 107124206
7675736 517697380
256981300 603011956
453772648 801409220
325711720 329281638
133704313 247012853
177469244 299643729
123039587 140167120
367301978 716642870
713774477 951898962
599581890 606774963
44523618 517247944
124896277 660024721
16491112 274333862
293810497 773832298
778510694 815596036
759835201 777046259
109369031 498414178
230818849 252796094
545768312 746291450
161463158 823077447
649124999 959281563
453177304 834812252
175866673 664176735
543322760 770358275
806804809 896072988
369979620 674353863
563283951 808842077
4927888 602188754
205736841 834936693
110808170 601671465
176866559 815874582
300012992 601070527
237673661 555355465
7472204 360949866
54234811 72438998
153722332 863738785
245271066 378340947
40072874 619985405
96236322 511115347
625358794 637091346
73644014 671513345
133451993 186340495
538844470 541611003
151216220 904777783
102637854 207144835
82103012 714658279
79967569 971288392
120314219 161768427
42601405 922527729
523081780 776811846
783275719 818274709
717856650 804640655
157530637 367310835
3409647 828286333
195600496 641612715
225223663 225485834
779394158 914653985
473120513 514251329
217631067 402902955
160977913 265846115
492572891 495280483
297522264 647715504
21961769 70423968
224665498 789277451
136325274 286954520
3568393 416418923
450568209 956758737
765600970 785810612
912422529 973685943
792401556 963618648
592098335 670433053
679623282 766281871
766700702 854539276
29787463 584469371
651684976 931184775
575392118 883867612
434193805 895946793
564681310 775997362
424119905 548756851
213063706 592596152
87377717 944498814
30168287 737337388
58190021 603481256
426620206 780554894
138685527 151013496
500190887 943748441
174131725 754531077
685616662 871097196
545141515 606408238
705889399 764204419
126555396 930030804
472455388 890652782
225835327 865615510
110981733 253671428
196923054 489729127
363283624 598415777
102413821 497026939
6866409 974116782
104250050 514301588
214642195 465025175
72520395 475593958
363774001 462318432
179639508 778942299
14285966 214708236
281495497 997083167
232228541 887284910
228869469 504196436
193235234 824832580
430509960 596216895
81250824 374646038
745701811 958388721
253494101 314249842
194249824 721852292
404224258 635389765
486307595 807072010
145869755 632976955
493480057 587259653
718417940 760590452
563942403 759645604
74578011 925452628
696423425 761359533
114829713 348527444
626356980 958593027
766569974 929119218
365118758 566275898
381114899 518246298
99275392 645430222
300026896 980761804
492815669 811069659
286632747 487110621
147855268 590099595
289384587 530764574
573784078 639843811
215875660 748923450
893864969 939604078
453401044 833015176
299632010 546535466
31628005 889825350
91249315 219282028
398740436 776388572
417056322 527972959
742150531 895301567
387982112 447038315
170068185 882171005
138043857 350427746
185563791 456371612
827969914 832747052
565392172 737030132
65496147 73160932
361202575 393464294
559054273 696052003
128816198 467081813
350765264 945378386
76874738 347347255
199490616 918051932
366607112 777119136
235933919 252690124
239048771 518289292
598296484 648773433
170755743 377718767
53534657 831574626
190546196 925071829
149720982 583002480
272053067 933668038
8134865 640838862
576318977 594950275
237204804 998596448
201894226 536589599
139377319 698701501
75997430 102577999
415076353 836296544
295820002 947843962
579641045 999913436
233141735 774601464
602531663 977062304
493370479 681465568
219220453 600013449
687053659 767833316
214752579 315689463
280995847 711850194
158546796 579582217
312866877 315338306
544362941 567097390
349093956 667851518
40081374 705789679
534556591 583204465
75400652 286449879
305383147 471892806
214921804 921379042
633457668 767115393
742587032 870038410
411878563 418684581
79662671 730397058
301910208 517066984
270187315 437662871
468886371 607235856
666325187 670080525
