0 0
1 1
2 1
3 2
4 4
5 5
6 8
7 12
8 18
9 25
10 34
11 47
12 65
13 88
14 118
15 154
16 203
17 263
18 343
19 442
20 568
21 721
22 914
23 1149
24 1445
25 1807
26 2255
27 2800
28 3468
29 4270
30 5250
31 6425
32 7855
33 9566
34 11635
35 14103
36 17068
37 20584
38 24784
39 29754
40 35670
41 42653
42 50934
43 60688
44 72212
45 85742
46 101662
47 120293
48 142144
49 167652
50 197484
51 232233
52 272773
53 319888
54 374716
55 438295
56 512081
57 597446
58 696263
59 810338
60 942103
61 1093923
62 1268920
63 1470200
64 1701754
65 1967609
66 2272875
67 2622740
68 3023696
69 3482422
70 4007163
71 4606512
72 5290961
73 6071496
74 6961436
75 7974809
76 9128461
77 10440230
78 11931387
79 13624528
80 15546398
81 17725545
82 20195542
83 22992402
84 26158251
85 29738398
86 33785601
87 38356791
88 43517889
89 49340215
90 55906012
91 63304425
92 71637799
93 81017275
94 91569929
95 103434018
96 116767124
97 131740921
98 148550511
99 167408791
100 188556959
101 212258474
102 238811118
103 268540325
104 301813065
105 339030684
106 380644615
107 427148829
108 479097804
109 537098350
110 601830372
111 674038298
112 754554640
113 844291275
114 944266380
115 1055595290
116 1179521490
117 1317407298
118 1470769198
119 1641268763
120 1830753018
121 2041245471
122 2274992534
123 2534455074
124 2822361327
125 3141699708
126 3495779486
127 3888224935
128 4323045171
129 4804630374
130 5337831695
131 5927960557
132 6580880313
133 7303009008
134 8101425056
135 8983874672
136 9958893064
137 11035818238
138 12224930383
139 13537472919
140 14985813291
141 16583473447
142 18345314955
143 20287581729
144 22428113478
145 24786402848
146 27383842114
147 30243798293
148 33391897325
149 36856121554
150 40667137908
151 44858421446
152 49466634847
153 54531784140
154 60097656592
155 66212015700
156 72927107044
157 80299899101
158 88392668710
159 97273297693
160 107015949151
161 117701431847
162 129417982719
163 142261710370
164 156337501411
165 171759558753
166 188652449689
167 207151757724
168 227405295411
169 249573888589
170 273832781513
171 300372578432
172 329400869209
173 361143357818
174 395845744070
175 433775069740
176 475221898300
177 520501918055
178 569958465024
179 623964430199
180 682925180687
181 747280821623
182 817509580314
183 894130484758
184 977707280398
185 1068851598247
186 1168227488757
187 1276555159155
188 1394616222799
189 1523258102504
190 1663400103927
191 1816038598295
192 1982254048748
193 2163217097649
194 2360196696142
195 2574567245747
196 2807817997755
197 3061561424752
198 3337544088035
199 3637656435758
200 3963945368177
201 4318625694942
202 4704094655458
203 5122945305054
204 5577983291195
205 6072242471842
206 6609004295508
207 7191816007631
208 7824513025727
209 8511240145902
210 9256477370392
211 10065064579534
212 10942231337902
213 11893625574817
214 12925347963420
215 14043985235498
216 15256649823472
217 16571018519290
218 17995378174850
219 19538670531244
220 21210544878404
221 23021410006728
222 24982494869244
223 27105908734481
224 29404711047084
225 31892981030313
226 34585898100614
227 37499822352856
228 40652387091482
229 44062591825465
230 47750908708093
231 51739389918265
232 56051790040452
233 60713689984440
234 65752637642567
235 71198290790424
236 77082578693840
237 83439866798650
238 90307142321374
239 97724203944389
240 105733874872191
241 114382221189044
242 123718796364199
243 133796892466873
244 144673820640926
245 156411199971278
246 169075279101495
247 182737268195613
248 197473707599806
249 213366849127029
250 230505078461150
251 248983352870092
252 268903685002066
253 290375645095981
254 313516914888631
255 338453863535455
256 365322181519742
257 394267540779924
258 425446319897174
259 459026360338338
260 495187795752908
261 534123917906719
262 576042124645229
263 621164910971098
264 669730952249718
265 721996237964370
266 778235309011092
267 838742554084714
268 903833622424352
269 973846905504374
270 1049145149509860
271 1130117148029758
272 1217179581822365
273 1310778951707048
274 1411393676837752
275 1519536300928856
276 1635755884470409
277 1760640521818247
278 1894820067533301
279 2038969006919638
280 2193809561965072
281 2360114963594625
282 2538712988764065
283 2730489689045891
284 2936393417262211
285 3157439074300761
286 3394712691330439
287 3649376264944846
288 3922672969755066
289 4215932661134298
290 4530577802826574
291 4868129727027649
292 5230215372655193
293 5618574404260640
294 6035066869139687
295 6481681289731315
296 6960543361833100
297 7473925150114270
298 8024254965480373
299 8614127810156736
300 9246316590164743
301 9923783975286769
302 10649695122759547
303 11427431138816515
304 12260603512258507
305 13153069388292209
306 14108947936185463
307 15132637673022604
308 16228835018343077
309 17402553935889710
310 18659146960291508
311 20004327459104037
312 21444193452966320
313 22985252838583747
314 24634450364633129
315 26399196199644042
316 28287396471658072
317 30307485613560903
318 32468460926087087
319 34779919187566465
320 37252095757730281
321 39895906000167741
322 42722989509191019
323 45745756962092818
324 48977440124307864
325 52432144825596707
326 56124907480587046
327 60071754969710036
328 64289768503820822
329 68797151287901844
330 73613300661491340
331 78758884531925495
332 84255922837726851
333 90127873860377524
334 96399726186985882
335 103098096146511852
336 110251331593123072
337 117889621866028320
338 126045114877462346
339 134752041167308982
340 144046845961441770
341 153968329084893785
342 164557793860192274
343 175859204858139853
344 187919355733923091
345 200788047035923290
346 214518275332396702
347 229166433568703022
348 244792524123067785
349 261460384504325755
350 279237927294781606
351 298197394318442806
352 318415626785958486
353 339974351441027792
354 362960484621956411
355 387466454315805764
356 413590542297571379
357 441437246493585996
358 471117665857821693
359 502749907973218366
360 536459521881992548
361 572379956442031735
362 610653046950554689
363 651429530430511070
364 694869592581654936
365 741143446906284289
366 790431949298006677
367 842927248735506525
368 898833477685464527
369 958367483008007439
370 1021759601316239377
371 1089254479757633201
372 1161111946550824461
373 1237607932445050858
374 1319035447857145835
375 1405705617080665694
376 1497948774786015025
377 1596115626466108341
378 1700578478557078479
379 1811732540184192514
380 1929997302826040093
381 2055818000182455765
382 2189667155160205269
383 2332046216643101155
384 2483487293644560290
385 2644554989940818024
386 2815848347537915956
387 2998002902558190171
388 3191692862731926764
389 3397633410631733685
390 3616583142752999613
391 3849346649200518022
392 4096777245098168323
393 4359779859182839110
394 4639314091817547344
395 4936397448675618699
396 5252108763563907729
397 5587591817526213772
398 5944059169056823951
399 6322796203564095919
400 6725165418416956926
401 7152610952837170296
402 7606663380628385333
403 8088944776264643603
404 8601174074161158554
405 9145172733061814572
406 9722870727388245183
407 10336312879068264176
408 10987665553920085853
409 11679223737882717912
410 12413418519634459540
411 13192824996872408609
412 14020170635516970741
413 14898344101332895028
414 15830404596235525263
415 16819591721252969646
416 17869335901732556425
417 18983269399530371025
418 20165237951437857716
419 21419313061676382308
420 22749804991760672742
421 24161276479011910093
422 25658557231492539248
423 27246759234489760197
424 28931292921257056488
425 30717884247430048473
426 32612592727277005922
427 34621830475978821773
428 36752382322120378203
429 39011427039908239595
430 41406559771945605629
431 43945815698003845658
432 46637695027962111625
433 49491189380945937751
434 52515809636944161259
435 55721615330264933239
436 59119245680062044523
437 62719952335444309162
438 66535633940281423164
439 70578872604278546522
440 74862972396346154861
441 79401999956900524893
442 84210827357168821915
443 89305177313312734547
444 94701670896742081193
445 100417877860842081587
446 106472369740167038311
447 112884775856094707933
448 119675842401198543951
449 126867494751613277917
450 134482903197533969485
451 142546552258072031062
452 151084313790347789090
453 160123524077832410325
454 169693065129601217722
455 179823450396341284844
456 190546915158808483353
457 201897511817657805920
458 213911210366862304091
459 226626004305210268930
460 240082022297353042962
461 254321645867209928920
462 269389633467474134787
463 285333251239376362356
464 302202410842050211920
465 320049814700353238771
466 338931109089750888539
467 358905045445516024136
468 380033650358147659850
469 402382404684740441946
470 426020432285955297522
471 451020698865300954916
472 477460221473019752289
473 505420289203236685889
474 534986695704697695779
475 566249984091181980570
476 599305704935889899726
477 634254687999353722252
478 671203328445685615825
479 710263888266836802933
480 751554813747389501074
481 795201069767021696020
482 841334491858802020422
483 890094156906006534166
484 941626773489969176427
485 996087092866127996879
486 1053638341684724570218
487 1114452677537606122728
488 1178711668562096183265
489 1246606798298479910609
490 1318339997158190626052
491 1394124201826253960873
492 1474183944093966580870
493 1558755970585484872565
494 1648089895027246748214
495 1742448884678447399336
496 1842110382739886548720
497 1947366868529843401591
498 2058526657429673162729
499 2175914742575692986329
500 2299873680504109713904
501 2430764522932692643629
502 2568967797110528375082
503 2714884537147855863831
504 2868937369004458660077
505 3031571651800168797507
506 3203256678397899272177
507 3384486938199890325943
508 3575783445406765325878
509 3777695135985345202875
510 3990800336923917103922
511 4215708311357085255362
512 4453060883500883403340
513 4703534147350430483489
514 4967840263478898550217
515 5246729348297580049458
516 5540991460553558609778
517 5851458689873302841143
518 6179007352609970938705
519 6524560300296341958616
520 6889089346490242111852
521 7273617817857492959285
522 7679223235860791610866
523 8107040135497023284167
524 8558263028090556852333
525 9034149515242182104150
526 9536023561643575501822
527 10065278934579656768502
528 10623382818600395820263
529 11211879613979068749189
530 11832394928286287573529
531 12486639770570379092270
532 13176414958404658893819
533 13903615748252399692057
534 14670236700432791430132
535 15478376790193966367715
536 16330244777299540708148
537 17228164846794282854167
538 18174582534588590815457
539 19172070951801309839205
540 20223337322854482418194
541 21331229852658907348473
542 22498744939370329584436
543 23729034749592006567238
544 25025415174134720647138
545 26391374182897657167068
546 27830580598771392476273
547 29346893310979379300945
548 30944370949723532370567
549 32627282044584430561167
550 34400115690696923366688
551 36267592747384348261843
552 38234677595636375501347
553 40306590481563923139495
554 42488820474809400113116
555 44787139071734282076284
556 47207614475206316932107
557 49756626583758025603352
558 52440882725057469358235
559 55267434169698557220417
560 58243693463671286290317
561 61377452619067929731737
562 64676902205134221634113
563 68150651383113200824318
564 71807748931099810917476
565 75657705306620956718623
566 79710515797662660446991
567 83976684814536969494742
568 88467251378245510559154
569 93193815862860084167763
570 98168568052984824249402
571 103404316579440262256190
572 108914519800158324833863
573 114713318195587112222886
574 120815568352084402978941
575 127236878609346510402455
576 133993646452459805912340
577 141103097732013901285387
578 148583327800648624993393
579 156453344657571180387460
580 164733114197940148965563
581 173443607667521225202376
582 182606851428844675327714
583 192245979148981069848126
584 202385286525382916150427
585 213050288670542266241856
586 224267780283096198039821
587 236065898737771615448430
588 248474190234042067596183
589 261523679148631007466555
590 275246940745129707770118
591 289678177399811188747567
592 304853298511565659417880
593 320810004270301500931616
594 337587873467773178553965
595 355228455541880390580655
596 373775367055941883650750
597 393274392822259114309603
598 413773591890660430742010
599 435323408631327580790113
600 457976789153579359101457
601 481789303311774804703228
602 506819272562957331274457
603 533127903951309376919334
604 560779430509128354134065
605 589841258375535540059209
606 620384120950057647638812
607 652482240410874846419066
608 686213496944858088400693
609 721659606050435461233745
610 758906304293181502596228
611 798043543909323003679889
612 839165696672869173162568
613 882371767458887204702743
614 927765617957765843905823
615 975456201013779010514512
616 1025557806085550317412647
617 1078190316346300965941049
618 1133479477968193531753335
619 1191557182157348023300750
620 1252561760534867385899014
621 1316638294483641107609436
622 1383938939111993283028027
623 1454623262512042959881438
624 1528858601024703362741380
625 1606820431252638695935436
626 1688692759599561108375273
627 1774668530146473608121485
628 1864950051715799143729717
629 1959749445009652703569071
630 2059289110752406854036062
631 2163802219806397105514635
632 2273533226277380297461252
633 2388738404668745942210469
634 2509686412195462067429430
635 2636658877415154207505622
636 2769951016390283899545717
637 2909872277646210446327292
638 3056747017251477508206207
639 3210915205402286614662498
640 3372733165960106814414599
641 3542574350452232311250752
642 3720830148117993789674762
643 3907910733649911874256782
644 4104245954358401018296107
645 4310286258561455294195629
646 4526503667087057861626172
647 4753392789855686251488497
648 4991471889604199767126986
649 5241283994899449757181716
650 5503398064692138545759029
651 5778410206756602620172344
652 6066944952473376469410117
653 6369656590515369446984739
654 6687230562119452177856946
655 7020384920738846329427915
656 7369871859003315211433706
657 7736479306038236195738180
658 8121032598336809313033118
659 8524396227515167319404579
660 8947475668435906086577690
661 9391219291333516189602508
662 9856620361744628434720648
663 10344719132207512265838616
664 10856605029879569020678509
665 11393418944397863128127411
666 11956355620508204028304038
667 12546666160180684029124958
668 13165660639147621113695808
669 13814710843009770343650026
670 14495253128293813931227602
671 15208791414073132670499722
672 15956900310021770138941074
673 16741228387021262608074567
674 17563501596720481191494348
675 18425526846721000571131394
676 19329195738365504239144555
677 20276488474403707256558264
678 21269477944141919697532390
679 22310333994006117919149621
680 23401327891808986384035303
681 24544836993364266439914494
682 25743349620483801504231437
683 26999470159777232042870936
684 28315924392100521867648886
685 29695565062918532550353841
686 31141377704310215974951764
687 32656486719801521641187333
688 34244161743714795008324393
689 35907824287220740960900243
690 37651054683826506195452211
691 39477599347575064448617685
692 41391378357826137746494083
693 43396493385078715098566602
694 45497235972941938485796490
695 47698096192003349331517677
696 50003771682046292521547073
697 52419177099767448842984843
698 54949453989909178911399572
699 57599981098482429480760434
700 60376385147585793839360315
701 63284552092154645096896366
702 66330638879875891994029799
703 69521085736405314826212962
704 72862628999004000239752125
705 76362314522691198221972797
706 80027511684075074524883846
707 83865928009089885154903756
708 87885624452024057495771931
709 92095031354384397559404174
710 96502965113397236630494124
711 101118645591209808213268170
712 105951714297218861896914493
713 111012253377326484196270774
714 116310805445404132647713527
715 121858394293738819497009803
716 127666546520843709309325808
717 133747314116638570899420742
718 140113298046751950744093224
719 146777672879461502546407731
720 153754212500685144576410835
721 161057316964353757652090324
722 168702040527554875588649090
723 176704120921921431128272657
724 185080009914974613456287622
725 193846905217395269777174102
726 203022783794624429927086677
727 212626436643655058469478889
728 222677505098510580838806339
729 233196518730580074704443611
730 244204934912838241662610287
731 255725180119883501553053966
732 267780693038829497444715471
733 280395969569240979397949897
734 293596609793671217184768590
735 307409367003785425407293331
736 321862198870707319710243856
737 336984320851947874868767254
738 352806261931238501879687904
739 369359922791632306445458382
740 386678636526536799771797420
741 404797231997729309677309558
742 423752099954070816457720642
743 443581262029397420200309601
744 464324442743128426024964725
745 486023144632300710318857649
746 508720726649227170819841770
747 532462485964589135578341069
748 557295743321724887273316139
749 583269932093966955023833228
750 610436691203335976304168719
751 638849962065507933730906538
752 668566089732971505110769932
753 699643928415463159328882939
754 732144951564357705187242442
755 766133366715471744602848235
756 801676235292966776533437267
757 838843597585478111011401272
758 877708603114517372598168660
759 918347646624350445198029838
760 960840509932224108320216032
761 1005270509887742849980480584
762 1051724652700680669985263258
763 1100293794907279462464821017
764 1151072811256448057822158089
765 1204160769808950964009926125
766 1259661114554990220932982349
767 1317681855868242264602239550
768 1378335769127756601969458924
769 1441740601852846591951441267
770 1508019289710563117568996652
771 1577300181770218572776081964
772 1649717275395096635946619391
773 1725410461177608396821617704
774 1804525778341130457921455775
775 1887215681049237248228173729
776 1973639316081429368107999316
777 2063962812353399362882742190
778 2158359582779796669969502577
779 2257010638997976511248466248
780 2360104919492794269509283848
781 2467839631684743617566064501
782 2580420608567105677377301137
783 2698062680501867720868136806
784 2820990062809477973483494761
785 2949436759813601013447033542
786 3083646986029443999065989171
787 3223875605212493075440299852
788 3370388588014174187463967384
789 3523463489021570595494976112
790 3683389943990458659201540510
791 3850470188114082570992209516
792 4025019596204872547227713654
793 4207367245702218711678058851
794 4397856503457067546667242315
795 4596845637282988381543481256
796 4804708453304116464562266789
797 5021834960172474904066759668
798 5248632061271293635830393937
799 5485524276066516180136771588
800 5732954491816430199978644971
801 5991384746898690046297558017
802 6261297047065668500658005351
803 6543194215992472009701475222
804 6837600781537864444030947107
805 7145063899196136172843035054
806 7466154314278451031379090263
807 7801467364424746303741976526
808 8151624024112712402867314612
809 8517271992898056798929609103
810 8899086829191064351041166016
811 9297773131447694584668741133
812 9714065768730052246242795721
813 10148731162670294629352216915
814 10602568622954889650321115660
815 11076411738531848508906817497
816 11571129826833165516649467166
817 12087629443397412602181407936
818 12626855954374346549414906127
819 13189795174493670857281884528
820 13777475073184893082791912864
821 14390967551643679816846328702
822 15031390293753431924190330259
823 15699908693888098171841599014
824 16397737864744770531268141847
825 17126144728481442849897413705
826 17886450194567781587273412564
827 18680031427893903369771539669
828 19508324210825358309639513214
829 20372825403040796849689091077
830 21275095503143597360380983212
831 22216761316199033470530715390
832 23199518731515880533353215341
833 24225135615164645642134765452
834 25295454821905445514441548624
835 26412397331385860731725763095
836 27577965513664531244486542457
837 28794246529318698711641639708
838 30063415869605095804220174102
839 31387741042362364842512911008
840 32769585409571393586343483208
841 34211412182726379450198494305
842 35715788582416000692559950818
843 37285390168769539277049546770
844 38923005349689185914031171221
845 40631540074065777844326307895
846 42414022717462994906946166285
847 44273609168053242785767524110
848 46213588120899309836862748277
849 48237386588998027240636904161
850 50348575639837927782028927949
851 52550876366570875687465002475
852 54848166103260281420031124661
853 57244484894044367681320005025
854 59744042226444591401391567220
855 62351224039455254493615319523
856 65070600017473257941165598555
857 67906931181565329054913208413
858 70865177790026720695608203276
859 73950507560658759759415971664
860 77168304227685693586338121072
861 80524176446742419091447026070
862 84023967061897014411710081681
863 87673762749223854680622718961
864 91479904052017775125569837554
865 95448995823335530198662644225
866 99587918092171147266709969275
867 103903837370214928151103500924
868 108404218416815448395328717249
869 113096836480458140140012950421
870 117989790035796742868468583911
871 123091514036023222250969170473
872 128410793701141710077260189215
873 133956778863520721492336372165
874 139738998892939585668197710936
875 145767378224217755885421064360
876 152052252511423889387543667766
877 158604385433603340471108986567
878 165434986177942667167951388651
879 172555727627305909290418325622
880 179978765280134671882062052563
881 187716756931800404484540519657
882 195782883147637878226746326237
883 204190868559071657621874991459
884 212955004015477788402273239150
885 222090169625698874267164456088
886 231611858724457926731022390762
887 241536202800292713432353111065
888 251879997423063836481181574363
889 262660729210574289878362822637
890 273896603875382128557016029375
891 285606575394488957474550224195
892 297810376346251910065547470164
893 310528549460593442210874157850
894 323782480430378670409078571035
895 337594432033691931829299777037
896 351987579618680166631339737338
897 366986048004638415721703694628
898 382614949855100016479525487879
899 398900425580858763352574088439
900 415869684833100628390175288142
901 433551049649156416467392968326
902 451973999315812656727614842098
903 471169217017633930691574176133
904 491168638340364876891511698756
905 512005501702192143134623989944
906 533714400788465249302331620782
907 556331339068398563510694305020
908 579893786475314580929145330518
909 604440738335139362310058574408
910 630012776631135097666917463902
911 656652133696250303560370725675
912 684402758427996493489942658759
913 713310385124419346594268758487
914 743422605043534422868590301585
915 774788940792540487386098343391
916 807460923657220160917485951202
917 841492173986186167311969475699
918 876938484749045254926182359267
919 913857908392129308894059287700
920 952310847120198347898573797793
921 992360146737451532569826543995
922 1034071194186304901430538705494
923 1077512018927706975536619234192
924 1122753398312281375232374965543
925 1169868967097308037993171177342
926 1218935331270498148652372843630
927 1270032186347681569171818783677
928 1323242440317926965179322174397
929 1378652341416253285787493538791
930 1436351610910985347317566584985
931 1496433581099955584028769847391
932 1558995338717178211807557013671
933 1624137873959320989013098099772
934 1691966235349294236228682309074
935 1762589690662567015879384867935
936 1836121894150428359077744259940
937 1912681060303337759394316138461
938 1992390144406777092894803815479
939 2075377030151626688303639690322
940 2161774724571066076861529738131
941 2251721560586346480829710047340
942 2345361407454523408121335451308
943 2442843889422375805719824616050
944 2544324612902300670709091225083
945 2649965402497961391736586028130
946 2759934546219913604390499814658
947 2874407050244337186396792234895
948 2993564903581398127914353492497
949 3117597353033653275785941720461
950 3246701188839327138477066283536
951 3381081041410237699204372278800
952 3520949689589662239148579417380
953 3666528380871520005533730087208
954 3818047164038942965415429294791
955 3975745234697615267536766350872
956 4139871294197225391678237901276
957 4310683922452999704970064443769
958 4488451965198613613363510624595
959 4673454936221815201323625875439
960 4865983435154890034560867867519
961 5066339581413654369359964853707
962 5274837464901033862929340489461
963 5491803614114477035747665200829
964 5717577482320516518625862379234
965 5952511952484738980884897362659
966 6196973861671308906749226628070
967 6451344545653026084031794514735
968 6716020404500737316388178980079
969 6991413489949785189132570935092
970 7277952115371119637889346814579
971 7576081489205739163081671581785
972 7886264372753330355515779654406
973 8208981763239356538045168810835
974 8544733603119475199242056658699
975 8894039516616061276285226568645
976 9257439574518849759693279501785
977 9635495088320310700199785894134
978 10028789434796407398905622337639
979 10437928912184891096490674928112
980 10863543629156332408759352949329
981 11306288427817710626518578398665
982 11766843842034661337060321524276
983 12245917092406453212632100629595
984 12744243119277516068334893523932
985 13262585655220910290447269354423
986 13801738338482607933467999503037
987 14362525868930887618795905652719
988 14945805208112630303971366563796
989 15552466825077884328118401358999
990 16183435989695853741998832062507
991 16839674115249501277162917422958
992 17522180152162361085783641965011
993 18231992034779978587200572768792
994 18970188183199757348610556038432
995 19737889062216952788064929100426
996 20536258799531239329261256271479
997 21366506865437753622629109655165
998 22229889816308919551003668693598
999 23127713104258758828853668906543
1000 24061332955469930867287221544924