1000
836213242128707626
505478714179501855
186760622781655506
974700947363872852
130983282628488344
13900344450642679
239530976257112861
779690320688982934
821690396200723320
603528343756979194
327636142848273657
224419204092505068
717080264577826245
850007108831596513
632778725562118409
423899054953992563
120143012631115898
229926601510293929
345308387019356995
877379563498541625
865747079010302431
42330675191820060
469415459697204865
226393659040624530
309209336777853665
300466518853434023
613858644753564353
27838209238844022
262820678243073328
234410007013324076
53507353385383542
537056980615559975
242609959104262545
744080111563058983
108338833613090143
450568930453765221
595829388927148732
955985068524273851
238699854140919013
797507426666372867
798908881248470973
703659585539082148
307823640251628088
880763728585815010
454825584177213718
747210436518042268
872962976631691697
667157099627060387
177027717763771809
906806549392898745
867323496228138758
381010016901568680
776827289788378768
306249803879743396
625257048195634147
244657934134024354
641842601717765390
102123840430809105
218450408005354846
175129993475800921
743951382059012685
686023282259198859
201148843827411040
654794906309270673
118163788904331129
899966970943095487
79399703760692001
462067851016462969
153160966545178026
670505375042615582
7230721468245763
727707630517174860
870491934671460724
40033794263985670
985931557608309731
176418373918745267
95247576112073471
905697882962649623
986811528823895862
672406497718293631
169139086134230217
163584879512799561
568972040961927383
965641838481287681
614665779461329730
110762033221914610
128500041655559172
511600955158900884
964151730303408053
85262944893081698
81123416277046432
555420764730312791
390808614642826284
981472091245353418
1198329001710032
378675033717490990
721963394070354058
627846996513804862
685956114583235305
730413439941603176
798536728114450144
20260400439606225
795914967222601110
34057788369076617
156775780957227731
828074234064976663
42457103994261828
624008197693263399
725155048727072139
50515910308216874
854293636602104848
997895506067475942
310993440944890067
777398488484077063
687230325537226054
773143951318762902
794316685854451733
279863157608765248
649361022023378129
913415770198365482
590899444217205541
119965823872960971
771566532368705312
871062001793541921
412159606296906252
273692859005012704
218353027329542189
231139739103193071
994247055228620932
126514508080226684
125179561128953734
286135269731909307
137438234882148696
559435127760869514
697928675075347438
869480677430151992
161713562747925308
133823087998192951
237584869934274003
889310872589953350
514276656517792807
64561601314695163
132065172048008287
122023693361772657
738556249778697846
443232119310498021
384689271892691873
565005121572210999
580684295406654506
788927351279808934
12207959090180596
29212580889377659
981995542755036823
998463315546008171
7617308926850533
212023569074029142
472850974406260029
633539321027319357
237157001317093031
116243088113205139
729641669921336968
518681674837783450
448386925525158816
83912301738554977
91960196249913370
918061389438109499
497526466476996515
696277920829549923
307408272760554150
402167851970152510
250272832270758726
249251452743320681
13882977059436109
442809882126886092
701325929394446892
839270547672202654
901340372602050730
169220901141144122
132094716883826794
950097734324926242
621058210709468464
693411176093707210
889718740801132764
280721968780354848
451201976595558553
825605646312704161
429198145287312759
817120714828938743
546187951811512743
749949365645267097
827538700157627462
786426222013501802
102384284541022765
3371047358285503
852212932285312159
688808879466028650
802585711464695236
881554169754180915
523118654328907725
132602293773344729
100276054868264569
468146941499224397
609706046993504391
370071611834715567
694701897079049363
65461834271510572
752732778719411989
629805170688396271
165314510770197744
651348576209783367
89804582213520384
687909326501126057
716341485435572103
506458271519743238
568262334482322441
707286598809023023
695659546035650701
857085887347376728
453148057332078038
774319302463043322
762249152127670138
926010032045999565
907345186351558538
911048207450673285
138332794865118771
467296097837388571
923974464305497060
285272195268739174
192174722158368984
617250603139556347
24727166384592301
407990652622456882
660190133327593725
777416389257464051
226844257943457701
531930172461107104
573774994459601972
891724919894598667
861787974255741060
818106284018906923
284989288481466527
898287506667493210
265795404434276131
921312511647642947
513820256177726304
284524964951347257
490288324311150819
735169054990729850
561132437290504154
501521263284969733
488155446627281803
555974812772041401
633340577658127039
82659440330739248
246969678325152396
477013418152929962
780725249284449355
880785610313898998
92842248095640662
442063594183173246
404672557347884453
605030907410324994
631761778010411626
371361005121955703
257333419010924699
627249844301241296
398872521881639048
397605807611846933
123828692390906485
338031219753334290
757075392850894737
120575992580365643
89565643552874871
605485202745044421
516427870018518604
874563363459155104
44170275606378097
234217663860031428
710395214616704475
403180537262502840
746529984888696881
13376380066809962
717060096358371100
249285877394474347
749541306093890957
291751863684399018
458490237350056859
387914687767862827
820420544574917195
825245290515009280
176598165553589493
112397035795204481
359944929664345100
549461681229956207
824245650960877700
559251745629531895
549809906636794186
1070337997842572
36286348413228672
479254805345670916
895135029752399840
597892661762822504
14869821969709194
95460014216324845
332090198718284184
316847560829515919
848908052285982753
692996729247728032
957676447546289596
716297393870460293
901799589803921832
672814862406456122
329612371510954304
265499928326378510
12318405557715363
327834975121736144
392387340431815484
472222420979204363
617605544082838295
930190622328679720
666424727895580661
574004919249992994
373413477958041161
94570862376391343
663701165355241227
697959678414541189
699586095601349676
284581879354719778
271802202077817962
963918052171635704
668964028997783662
209887605649698695
57423431506893283
85669861680479989
826288367690411065
221391223614647867
614229426563176723
655356789687674241
423135639708557916
134869914709345156
285476291205370600
939605097453912478
117332952970352234
44415461360318974
6291398450855625
281584282006236161
93001159638065640
413591972825370929
922494062128679597
698393152632296388
570088200794611761
472665056714972631
879593695256110200
176238971941040635
501836530671307731
572263268279070680
542808209822907060
450324729628086521
41808504685339553
545654031656975824
847648833822067724
194913717959908898
974172304776945025
867896495586130365
698733705763590289
528409980652872809
305837053016838293
60386802844886588
917796645287182662
471916784933369538
712547166606514045
808821068620302515
675625943408917222
725132335234285526
32211119524933337
481712150906201294
89560018926590731
934249131972325548
64029221171022361
443371883066305453
81862936953873423
888735945746902348
622637652908174159
535779900421949170
865167494048329413
902276229934191316
759037587970619578
882770827007033957
835975157313831902
590741354919143941
177551189117207179
958854210279067585
13068409277391551
525864284415798981
715557000975040617
349823683908319103
216024508251072103
40009865204953644
641866519256448511
91076391132442808
843458865242551259
387743521337601881
875272321916741474
243573425445048229
927259923593610956
52254979452395061
701035362793217254
254816666215135825
811331566466271358
247725849703511917
878011911803032576
274910037485083852
999643579056869170
346568537273699115
155332965466943547
22357914866203328
419003022583911514
104061629885871995
196030993753521462
209773037680385253
767300721458350209
751473618720720496
123375310344466090
523485807584220302
658397689628094603
404426250677824622
570615324201478678
472062689679535468
469104414314006431
884443212482755023
948881021644848661
106477942781330480
143028637861610690
715974664746449425
153287177724511925
278996672727646107
922202136587210220
511660126731136628
564020497721674640
555455520068466232
714130690748091163
92325358528969902
174633862103001948
377792449105866878
187070221743827198
528596352782144177
939331817356414060
454605011775941713
482108558717143337
982385491904887018
778522010532246295
352104706802917568
408262462507951822
485472040846138922
976153412038242903
88700294778737526
821819049282558192
663639030800122647
835762405678282065
595388722884828403
625166081912741287
405145101245996161
881769200794263609
354454560248950635
650171970263375977
384128190696913935
936719885504942965
209577810394080804
459591333827396278
311260415543790386
910231029869322071
193973448635689258
33335727070392345
494279801925795287
137969089485145293
608218982103198132
238294480933755483
202908124760382639
125716810616771755
965582021566755317
80570767995465865
424193752649663880
323294752433336838
263905792494501214
752957091627970660
190538452193868803
982676654183513384
886570599989770962
622439250728553014
983623656688212030
423727146782165785
534194301354470239
466784316694943842
865859996637478586
88499311637763066
625789963603086457
883704950648710762
400805458572378101
234008285807076546
876191989526878360
186713186371696240
43512638513252575
409418309412864739
55099498234685566
77473859647368560
323205099992702166
637475528751830044
439539119965237132
430547356163510154
593438511775404756
249646623136047767
77725554734622981
387630928575934163
631811731695240925
262516714506025002
511010641722162192
870866704298895563
116320606577766108
7352580148407151
532479194194392696
333207667068230614
963954545629999061
92157443737381694
954254635537043381
466384775851194413
378479442187152747
225957226786342896
169348025304370210
906522283600864068
693525980605306458
903282297105032773
807323747051025663
135240911193023140
915792739112338123
655647306678621221
485943103500180671
543457424007130544
605030626976249325
396221659316506480
191955721869529249
125214927583867418
236276784779122168
696201089723121152
925627673160364696
197678473699989214
722417596235041882
180970777109625779
278098444913002581
987316478153831987
198384102430304652
298206350451434204
26732472752058434
75693292792125687
515753960528234180
524316968920876033
365730778801285159
176309035496697402
439519670806587939
405881970475304812
778379698654123847
239210592088932303
574888884179315158
717517457719083828
611615699514583985
954693949351671857
519554743732177039
784901370843760708
371467614750056698
512277837831871650
211139840437148395
285897651213076801
102051038606000232
66062963499450635
51126295876993827
233541654265793814
30961059874191070
686420146295150081
665570668844642094
739595667293598081
366697313264047845
942555276974729005
684148925801571403
720877277694724693
448247208871536263
887385501539855777
239827549672589745
782853314554441656
433629868595547748
764216751355265359
161642761486197842
587158182782407909
930280084877440167
714430814695162260
436183915294404273
302842990119347817
47017149610234519
908742051285554655
63944593078815714
618245239236368008
290015463154808161
447847667182166917
166226581624495624
488342055160988287
31025701048429450
149939311831036550
879306852483928606
244747384571712273
294318702758462096
412247147137857519
581447113945931057
293404266415258437
494024440433705832
726911042859461303
743412674353806714
751157752397252852
567794490679282351
889081055798723349
584832112733049430
475262224479484805
206111264518565244
318215731774564455
806824873371320520
347293117174957667
187069673046642818
84232571853186578
589009199102422420
433696663091634691
260940714883810536
948909121585200414
372185313540150692
63429032032616313
897849466494317723
661926864740511929
341373303864234644
878013735655611139
679999422756973424
351149971345480522
871290576471919528
33746494759141970
239139820076618149
17632221619934357
205143789885717115
273335069757300222
463605402386462775
646633336359747723
390822101903329783
25686087158147064
230292863152832555
122271096671113177
845273297232516290
434193754224566335
578185102018924287
7964399480712471
720497624758139653
646868650496712182
28377800616591368
180047337451717281
427119483836600670
966975932643527019
472101697798525156
802866143925519167
957117079592229365
710519949791053432
547056941541128
848659230801946190
992347384405694472
942212475649695867
672172065601946521
31773791963790759
331397970024574697
985850280639032424
232478405706018684
60429567748286045
353834327085191229
496938189446572964
223122926013192985
923280638571692953
25716039881380196
21257674267687097
437046949883411577
936754850416025727
238341369839512302
802909881859094023
599010439463127742
150038796585608577
166406709254223538
59925802214211935
13684954123609466
522155199919154545
261879124879554943
678120334557835520
829142482897677956
423899558128809025
106500452625717510
463730111458385324
255836816276898040
626340716813199821
527693510343586739
16397443174074441
176361415375275726
237345004988358621
483331690247422833
635756959867113307
330545135914101312
950416929685968182
529312584355393509
160384120530003807
808407588050686462
935868277510014831
432741238569048153
604508594323698568
37974990383018508
373018461136148775
595540511076940520
878291195146628187
396362481302758248
915630112818601323
25446440923754854
314047215942979253
855158469559559447
943525862843209627
20811403999284239
191026324075677530
322013069110481823
306682581403981020
795943071344125517
379663484591163565
239828178437347204
386579123073615093
202409292623470461
820407656183731141
585533031718968941
793483225572192852
327413240323837345
599239594713568140
131163308347230790
13913740204421984
854289727653979453
83686744369440280
938602349383816054
600957196576051279
12466300166804772
21233470846227475
260078378476645513
320632919088481783
597294220383785386
803601906924576837
785401518366553901
391314622522357880
255361282373534897
987506144379322384
880280835229225959
426668948191515165
942282913045638015
747669206748324233
95125147749234797
867966652804331033
385901496372117164
897532190136323811
374484726974001515
512671170492153358
122345415876595503
459930513171803397
371040697190953152
212187454019917045
856346509356813184
413995401835662825
693773835501610960
891694279467699051
758558308790525637
696782788244579758
179309551750838458
297796723249291904
779537209952504255
135072614437098205
492813119907293449
282546602374408297
74875678510485491
643721605186499829
895136454639864878
744516283425226029
738583546901283884
38655461138462656
802449387355008034
339784931545550721
261044165320849806
506873132280899501
141195715740918534
370191523309003326
83518671948741611
537171197653185407
934683893522890253
165993888902621352
78428025046752880
651039799858737259
852850509664775726
389607540482540711
69986768298726990
462104676272810420
384197476024067581
143849209481476832
899830263955456555
584222133282732537
949903388270625521
247480571697836395
904756331360852417
197815954615360523
197716607035185021
145098037252233244
245708151131026508
541683501539804169
540958879954428737
296579368639643708
737857464882567574
812997190917242550
949681613476691393
666153130875948935
216466288904300996
706150710528439519
603097157165599306
877331205294781
945019853699661864
275796623084918776
879617494166360546
192839232216748964
942043041765653992
271189144276669158
502011948931593415
300209481496685906
190501905949102251
49726636912277828
722877679413576725
178617045638039158
477665680726043553
945177273763364993
815984204448968707
756721835401176822
400306884437705226
300104267748604046
989170081836625548
183008064593573704
635296054301079259
561597185743283947
618643699525828424
983160302124421931
365078580612036183
500420972562883928
31841618813674530
239975017764420829
736299792333455658
973325325659066854
705086009183956770
19697595701115661
716010985862390317
632005670223841262
479166729540674907
289819767497876928
739652071978394319
268684102074047142
944028413400719124
73680127981129143
756979424566783840
558942112564245338
613636973083729153
554622216251596781
842471960526479358
829660322583553655
497465957402739400
815383459760878643
668988235383766034
694962712820574775
870478165670765734
51842980118963837
229063419156629954
311497632870112170
409119969954336266
587601892993994405
116758359699793007
446660294308995737
378944353439973399
579299217412367813
131679503223698942
82677048529051994
591498192874821965
845938451851762847
986485859527823281
278248225781658289
160291182194177999
768996447425199135
339337339547919261
747516536587775876
115948616325545068
221716477473495781
454893982716528244
989911016882980853
575683501530966471
449104004175668997
500345190931570314
435377543487997897
27640225870195761
264411771022430161
725216368710427042
10565833736166093
687331636513445900
718322856465555724
92282127984578416
392262901680084694
575627129688001672
350096331973944143
336025879440022959
611070564000265838
933622690043757032
517788201171499910
563590468575494386
657262335842050508
253125937399643547
742736187633379138
197284651701544613
807124488550154666
729870518067131566
861979303296061550
329686187325835
197222766463302943
637275421884384383
334238612893023796
356794082583481335
263713716372361429
747072327635416673
118920304186462559
266462538901974150
348342281138544786
358959735739974941
327435716588937600
738024884387856833
960170327247125768
440494116726818517
375015756356117292
903375976458216318
179388733014374759
630325468328094968
287452889177706315
56928838978523869
569921271336533712
24891349464040611
805491521010450760
808937048772458909
939593955150799347
68536396604253789
356148940102031877
708165386008914855
355617812242031352
379097320172882504
881062055558420831
129477335991787672
953256657270995471
984057077100627821
694476067544105780
614154612272403601
147277125458724434
646245596428750598
274077164212498298
412382325477266745
230494030280352927
57718295978334868
845401388936886265
724363765692678375
944184200953810417
977121615052723673
989873752430802085
263616616097910250
968291954863542990
773991425320967332
334862992795629239
389594084305249651
282333590930559688
132615435159224938
276606953976699924
792934217583590048
86029131926187847
563754873883331114
489844229931093331
960970006920748401
744791700418843387
380084788215461094
523623503508854944
215475358208401252
736461760657838812
475263215613586519
661816154810749477
300294845501133915
793913073178414692
410793602023096239
707895481262752662
755050253850334291
435382672577271082
308363634241147158
505941501468845379
81265381291363253
675631382606733039
299283757315312536