0 0
1 1
2 2
3 3
4 5
5 8
6 11
7 16
8 23
9 31
10 43
11 58
12 76
13 101
14 132
15 170
16 219
17 280
18 354
19 447
20 562
21 699
22 869
23 1076
24 1323
25 1625
26 1987
27 2418
28 2937
29 3556
30 4289
31 5162
32 6196
33 7413
34 8853
35 10547
36 12530
37 14860
38 17586
39 20763
40 24474
41 28792
42 33802
43 39624
44 46368
45 54163
46 63175
47 73572
48 85543
49 99326
50 115168
51 133340
52 154186
53 178059
54 205355
55 236559
56 272174
57 312772
58 359033
59 411676
60 471511
61 539487
62 616624
63 704061
64 803122
65 915238
66 1041998
67 1185242
68 1346960
69 1529366
70 1734996
71 1966601
72 2227247
73 2520412
74 2849886
75 3219881
76 3635147
77 4100876
78 4622826
79 5207461
80 5861855
81 6593831
82 7412152
83 8326408
84 9347190
85 10486322
86 11756736
87 13172716
88 14750142
89 16506397
90 18460649
91 20634141
92 23050146
93 25734277
94 28714865
95 32022928
96 35692558
97 39761403
98 44270648
99 49265520
100 54795856
101 60916146
102 67686174
103 75171689
104 83444552
105 92583505
106 102675009
107 113813516
108 126102403
109 139655018
110 154595102
111 171057941
112 189191684
113 209157944
114 231133241
115 255310635
116 281900563
117 311132684
118 343257856
119 378549334
120 417305052
121 459850067
122 506538232
123 557754987
124 613920439
125 675491568
126 742965702
127 816884392
128 897836272
129 986461427
130 1083456185
131 1189576860
132 1305645240
133 1432554483
134 1571274026
135 1722856382
136 1888444471
137 2069277988
138 2266701809
139 2482175138
140 2717279628
141 2973729843
142 3253384650
143 3558257517
144 3890529543
145 4252563572
146 4646917254
147 5076359255
148 5543886709
149 6052741748
150 6606431582
151 7208750098
152 7863798730
153 8576011267
154 9350180605
155 10191484928
156 11105518362
157 12098324128
158 13176427192
159 14346872216
160 15617264457
161 16995810466
162 18491365028
163 20113481491
164 21872462492
165 23779417757
166 25846326121
167 28086098548
168 30512649214
169 33140971896
170 35987217961
171 39068783801
172 42404404768
173 46014251494
174 49920037344
175 54145133683
176 58714688688
177 63655759246
178 68997452199
179 74771070680
180 81010275705
181 87751259135
182 95032923612
183 102897080232
184 111388660177
185 120555935452
186 130450760499
187 141128830876
188 152649953531
189 165078341881
190 178482931451
191 192937710418
192 208522079582
193 225321236971
194 243426581624
195 262936152019
196 283955094313
197 306596154899
198 330980213687
199 357236853658
200 385504960652
201 415933371467
202 448681565856
203 483920395840
204 521832872596
205 562615006050
206 606476690736
207 653642660080
208 704353503935
209 758866743330
210 817457986284
211 880422159826
212 948074812300
213 1020753511720
214 1098819335976
215 1182658448811
216 1272683789960
217 1369336875758
218 1473089704024
219 1584446794832
220 1703947363717
221 1832167621624
222 1969723236577
223 2117271953785
224 2275516369663
225 2445206897954
226 2627144925584
227 2822186154958
228 3031244174131
229 3255294254427
230 3495377372836
231 3752604505243
232 4028161191852
233 4323312372931
234 4639407546755
235 4977886252379
236 5340283877644
237 5728237849988
238 6143494214574
239 6587914603272
240 7063483657840
241 7572316915122
242 8116669160882
243 8698943322372
244 9321699911711
245 9987667029934
246 10699751010268
247 11461047717333
248 12274854516076
249 13144682999092
250 14074272493941
251 15067604369951
252 16128917244180
253 17262723113955
254 18473824442982
255 19767332312397
256 21148685672238
257 22623671728732
258 24198447592011
259 25879563230026
260 27673985773232
261 29589125310899
262 31632862236468
263 33813576197310
264 36140176809223
265 38622136205814
266 41269523492304
267 44093041285772
268 47104064426899
269 50314680950593
270 53737735521060
271 57386875435766
272 61276599305698
273 65422308644694
274 69840362495970
275 74548135225728
276 79564077749593
277 84907782346746
278 90600051218566
279 96662969096026
280 103119980081261
281 109995968913388
282 117317347006176
283 125112143479206
284 133410101412288
285 142242779719948
286 151643660911435
287 161648265011952
288 172294270098677
289 183621639769261
290 195672757871446
291 208492571014204
292 222128739238790
293 236631795240024
294 252055312736713
295 268456084439212
296 285894310078517
297 304433795185624
298 324142161150331
299 345091067112038
300 367356444473253
301 391018744662128
302 416163200798392
303 442880104171297
304 471265096270588
305 501419477142051
306 533450531114971
307 567471870774792
308 603603800089610
309 641973697899262
310 682716422792972
311 725974740446352
312 771899774811668
313 820651484365605
314 872399164675181
315 927321978888364
316 985609517563383
317 1047462389317098
318 1113092844144981
319 1182725431071793
320 1256597691867556
321 1334960892967820
322 1418080797541081
323 1506238479733490
324 1599731183562303
325 1698873228728926
326 1803996965727340
327 1915453783102450
328 2033615169509726
329 2158873833354948
330 2291644883309192
331 2432367072794575
332 2581504111685844
333 2739546049031635
334 2907010730407873
335 3084445333686700
336 3272427987615173
337 3471569477413744
338 3682515041801532
339 3905946266526309
340 4142583079298647
341 4393185851262936
342 4658557610870262
343 4939546375850808
344 5237047609260328
345 5552006806371190
346 5885422219032811
347 6238347724447356
348 6611895846176533
349 7007240935077463
350 7425622518234459
351 7868348824911220
352 8336800498459462
353 8832434503546574
354 9356788239121384
355 9911483867482234
356 10498232870309080
357 11118840843684408
358 11775212544115498
359 12469357198152214
360 13203394089472383
361 13979558437352321
362 14800207581113876
363 15667827486546651
364 16585039590422502
365 17554607999993400
366 18579447065923369
367 19662629347304642
368 20807393988299232
369 22017155527681034
370 23295513162843236
371 24646260490869428
372 26073395751189846
373 27581132594743800
374 29173911405769044
375 30856411204468929
376 32633562159345964
377 34510558739373130
378 36492873538540865
379 38586271806019954
380 40796826716767450
381 43130935420044178
382 45595335904199724
383 48197124717905468
384 50943775590969472
385 53843158998965481
386 56903562718013432
387 60133713419346796
388 63542799354650240
389 67140494185579364
390 70936982014556507
391 74942983675582932
392 79169784346599064
393 83629262549043736
394 88333920602258602
395 93296916603584808
396 98532098009620675
397 104054036896501863
398 109878066980736706
399 116020322487323661
400 122497778954723184
401 129328296070474684
402 136530662637083970
403 144124643771177090
404 152131030443764947
405 160571691476014278
406 169469628108908256
407 178849031270738936
408 188735341673739660
409 199155312875868587
410 210137077450115800
411 221710216412007662
412 233905832061497228
413 246756624402711585
414 260296971314391320
415 274563012650297657
416 289592738457207674
417 305426081508675928
418 322105014360249485
419 339673651141382296
420 358178354311198899
421 377667846614002636
422 398193328481356464
423 419808601140999294
424 442570195703025747
425 466537508506249304
426 491772943022849183
427 518342058631183226
428 546313726580920592
429 575760293491812082
430 606757752741039118
431 639385924110392487
432 673728642083935280
433 709873953202535539
434 747914322900291252
435 787946852269801487
436 830073505221391144
437 874401346522670468
438 921042791229611292
439 970115866041247673
440 1021744483134370002
441 1076058727062651201
442 1133195155328718964
443 1193297113265352422
444 1256515063893761482
445 1323006933454562605
446 1392938473338614236
447 1466483639180845738
448 1543824987911955779
449 1625154093598825344
450 1710671982945199210
451 1800589591360602795
452 1895128240546436944
453 1994520138594277461
454 2099008903633140565
455 2208850112109126192
456 2324311872833041738
457 2445675427979382892
458 2573235782273148700
459 2707302361660080041
460 2848199702810542780
461 2996268174867712782
462 3151864734917657212
463 3315363718721339775
464 3487157668317341056
465 3667658198179872147
466 3857296901687972017
467 4056526299739974374
468 4265820833433140092
469 4485677902809754595
470 4716618953759864708
471 4959190615268003975
472 5213965889284098369
473 5481545395599728488
474 5762558674220969500
475 6057665547834835418
476 6367557547081081227
477 6692959401465706096
478 7034630598873014459
479 7393367016763393190
480 7770002628284989506
481 8165411286664685831
482 8580508591391684212
483 9016253839866638901
484 9473652068345415515
485 9953756186174397099
486 10457669207494936829
487 10986546584772118408
488 11541598648693385850
489 12124093159187089059
490 12735357972512796137
491 13376783829591166264
492 14049827270972547610
493 14756013684072719707
494 15496940488549036505
495 16274280465951962104
496 17089785240047328479
497 17945288914482131150
498 18842711874762724324
499 19784064761809781210
500 20771452624668758720
501 21807079260289424225
502 22893251748623251676
503 24032385191643554344
504 25227007665271830416
505 26479765393573954090
506 27793428154993020856
507 29170894930813675944
508 30615199806483662344
509 32129518136874719960
510 33717172987048730235
511 35381641860583265850
512 37126563728027157956
513 38955746368603359774
514 40873174038829431345
515 42883015482310184754
516 44989632295574682367
517 47197587665455928778
518 49511655494172280160
519 51936829928967311034
520 54478335313873502657
521 57141636581912087199
522 59932450106829337799
523 62856755034271278492
524 65920805113143069836
525 69131141048788976776
526 72494603400535494918
527 76018346047094171508
528 79709850244324918996
529 83576939300885666491
530 87627793898371748112
531 91870968083681838734
532 96315405962505698700
533 100970459124045811526
534 105845904828363884287
535 110951964989051931456
536 116299325985301393012
537 121899159338886407476
538 127763143293055430594
539 133903485331875833815
540 140332945680203140716
541 147064861826115346211
542 154113174109402126850
543 161492452421533269060
544 169217924064414163448
545 177305502817209435832
546 185771819262583816104
547 194634252425834523885
548 203910962782614578441
549 213620926693277164975
550 223783972324268254346
551 234420817119503221184
552 245553106887289327058
553 257203456571058866297
554 269395492775005075304
555 282153898118671131468
556 295504457497589518095
557 309474106330254689872
558 324090980875043526097
559 339384470704131801484
560 355385273425043347478
561 372125451744219715452
562 389638492970866616488
563 407959371063374508272
564 427124611324833266464
565 447172357858517812373
566 468142443898771252989
567 490076465137464154818
568 513017856171114276332
569 537011970198872030512
570 562106162106923599384
571 588349875080385704641
572 615794730889528430468
573 644494624003176703677
574 674505819688355228631
575 705887056261724144126
576 738699651665116219320
577 773007614544477486940
578 808877760018803883796
579 846379830333270926792
580 885586620598616371533
581 926574109827033398036
582 969421597483379700108
583 1014211845779348979961
584 1061031227947466368712
585 1109969882741375208171
586 1161121875418821072268
587 1214585365474094958068
588 1270462781397490016885
589 1328861002750495223564
590 1389891549857084803400
591 1453670781423584958002
592 1520320100412148089330
593 1589966168505934346062
594 1662741129517714094333
595 1738782842107699947255
596 1818235122191094034928
597 1901247995431120783573
598 1987977960229143422369
599 2078588261639940575840
600 2173249176657375704505
601 2272138311333461636264
602 2375440910212318129878
603 2483350178579773403160
604 2596067618049304739887
605 2713803376025768517174
606 2836776609609970831138
607 2965215864529509315544
608 3099359469704601969880
609 3239455948081848228651
610 3385764444393973271948
611 3538555170529724029440
612 3698109869225256879312
613 3864722296816514445819
614 4038698725821376156282
615 4220358468150831125227
616 4410034419779994328354
617 4608073627742621006656
618 4814837880346921677545
619 5030704321545873215455
620 5256066090432023017174
621 5491332986865051013187
622 5736932164280020896423
623 5993308850765490955372
624 6260927099543530444644
625 6540270570028133013825
626 6831843340684719668120
627 7136170754961451026864
628 7453800301612857339751
629 7785302530788042785356
630 8131272007309506539869
631 8492328302624384337947
632 8869117026967862163796
633 9262310903338735451904
634 9672610884949523007314
635 10100747317878420679676
636 10547481150717792554827
637 11013605193083790715068
638 11499945424924310307695
639 12007362358637932429418
640 12536752456094730964449
641 13089049602731080370690
642 13665226640975018854776
643 14266296965346248482412
644 14893316181665768866308
645 15547383832904576399336
646 16229645194298776222527
647 16941293140460147903215
648 17683570087316824932400
649 18457770011828260052540
650 19265240552532373784026
651 20107385194100885528744
652 20985665539201281524440
653 21901603671091026644228
654 22856784610501658908349
655 23852858870507303051849
656 24891545113214274230276
657 25974632912256016046040
658 27103985625230627215040
659 28281543380377079051856
660 29509326181951134490985
661 30789437138932961683026
662 32124065821875923335092
663 33515491752890264440783
664 34966088033946445454002
665 36478325118881141497320
666 38054774734694725919974
667 39698113957942426618984
668 41411129452242789854636
669 43196721873156914304637
670 45057910446930197212592
671 46997837729835609982892
672 49019774555114131346756
673 51127125174774006192870
674 53323432603786557869545
675 55612384174502737068639
676 57997817309411563416813
677 60483725520669746388674
678 63074264645151477255628
679 65773759324098817546457
680 68586709736796965465340
681 71517798598055423146200
682 74571898429645904358688
683 77754079116231467158141
684 81069615756719343277289
685 84523996822382495970203
686 88122932633522888760004
687 91872364166893359549156
688 95778472206555143929639
689 99847686851325368114792
690 104086697392463868259471
691 108502462575761817272939
692 113102221262726820562320
693 117893503506111080279630
694 122884142055601310325836
695 128082284310082365321916
696 133496404733501804891542
697 139135317752000301981885
698 145008191150634068888676
699 151124559988701181314859
700 157494341053394354492324
701 164127847872239618724074
702 171035806305544412849710
703 178229370740870470962769
704 185720140912367887284778
705 193520179368657968661239
706 201642029613834624382619
707 210098734947068591459256
708 218903858027246927965368
709 228071501190062732056264
710 237616327545988590099411
711 247553582888623130360461
712 257899118443994178833804
713 268669414492536163492530
714 279881604896635040869947
715 291553502567852173379360
716 303703625909201217250512
717 316351226269160794643676
718 329516316445461712660507
719 343219700278092891205343
720 357483003372426749602408
721 372328704994873933304900
722 387780171185041274076188
723 403861689129987740730613
724 420598502847852387514719
725 438016850229868503443492
726 456144001491581492830463
727 475008299085956209268046
728 494639199132995328274279
729 515067314422496298090192
730 536324459048652410367827
731 558443694737356659859254
732 581459378929297995474144
733 605407214684250508767116
734 630324302474350435755504
735 656249193936636532647685
736 683221947657698906224895
737 711284187065943439320136
738 740479160509736838729023
739 770851803602553834286600
740 802448803919207239392894
741 835318668130307085780247
742 869511791665269996239842
743 905080530997488822893632
744 942079278648679386519090
745 980564541012949409374126
746 1020595019104789344471008
747 1062231692338970230269247
748 1105537905454253865819092
749 1150579458696880896715906
750 1197424701384007764774422
751 1246144628971618294669347
752 1296812983755945891557188
753 1349506359342113369469718
754 1404304309018534228292954
755 1461289458180628257628726
756 1520547620952591715850337
757 1582167921161333491517972
758 1646242917822250760338644
759 1712868735302277394431764
760 1782145198331601874856823
761 1854175972041626576303080
762 1929068707213134434817948
763 2006935190925248991270748
764 2087891502802628285482622
765 2172058177065430242746774
766 2259560370593934640470902
767 2350528037227313995441432
768 2445096108523921822192807
769 2543404681218620136780547
770 2645599211621109300621740
771 2751830717207962323559410
772 2862255985670111983736722
773 2977037791686904110156096
774 3096345121707525175896430
775 3220353407030647430090359
776 3349244765483522851940394
777 3483208252012510469512952
778 3622440118508151680939019
779 3767144083199429122075608
780 3917531609963769857715046
781 4073822197911696155185715
782 4236243681617802214263212
783 4405032542382957910359645
784 4580434230926325207988557
785 4762703501919936354583896
786 4952104760793241772504133
787 5148912423250205654572364
788 5353411287957227281790472
789 5565896922876414250919209
790 5786676065735547790605996
791 6016067039143480688079826
792 6254400180877715179577188
793 6502018289889541066792569
794 6759277088591395914595020
795 7026545702011061698597053
796 7304207154417957420616195
797 7592658884048149886432808
798 7892313276576809597819852
799 8203598218009709611722632
800 8526957667689029670803011
801 8862852252133213021712410
802 9211759880455955761588578
803 9574176382135618468489690
804 9950616167933467205500346
805 10341612914787205249224606
806 10747720275535281313631680
807 11169512614357487651733400
808 11607585768848424881608354
809 12062557839672546293636073
810 12535070008782739205215412
811 13025787387218790777947174
812 13535399893537660894006148
813 14064623163964285426060642
814 14614199495389699505429716
815 15184898822382646562827380
816 15777519729421569362292932
817 16392890499596008177942458
818 17031870201070007525843483
819 17695349812645205412917013
820 18384253389807896769756730
821 19099539272692579382015920
822 19842201337444360217793961
823 20613270292514176574498520
824 21413815021474129157993168
825 22244943973995392600434965
826 23107806606688222694383771
827 24003594875562583966686360
828 24933544781928941787950002
829 25898937973621865926885072
830 26901103403494349087050890
831 27941419047198226886664105
832 29021313682335867749241344
833 30142268731140461274232608
834 31305820168916851638639912
835 32513560500552018803128775
836 33767140807484091731643973
837 35068272867601272418296564
838 36418731350627345948026057
839 37820356091638645828203982
840 39275054445448532321817967
841 40784803724689722369714753
842 42351653724522288270440188
843 43977729336995925365869946
844 45665233258199284546806642
845 47416448791436889397042151
846 49233742749785527870505662
847 51119568461497143654910827
848 53076468881834280416117976
849 55107079815047182518461593
850 57214133250328859928623000
851 59400460815715923240789252
852 61668997354038929823382164
853 64022784625166498802399097
854 66464975138932705449364800
855 68998836123287411693354092
856 71627753632364388564532454
857 74355236799322508362452244
858 77184922238981102271520487
859 80120578605441968955169789
860 83166111310067668319206340
861 86325567405368832654976014
862 89603140640542468613755100
863 93003176694598813588604622
864 96530178593216458799379441
865 100188812315674372257186324
866 103983912598425374032684702
867 107920488942098764679391040
868 112003731828950420502846812
869 116239019158016995396015048
870 120631922905477162180391129
871 125188216017977345854740409
872 129913879546942420430401741
873 134815110032163639605313353
874 139898327143236934630923033
875 145170181587714941163809198
876 150637563295136018146400798
877 156307609886403409828116492
878 162187715438307907641825336
879 168285539553318230025944780
880 174609016745105201036551149
881 181166366150619036303606242
882 187966101579904009566510844
883 195017041915211855008628648
884 202328321871364859551887918
885 209909403129722124285735429
886 217770085858518343766308334
887 225920520632774105294143032
888 234371220767420597316838643
889 243133075077740197176742808
890 252217361081698166278062704
891 261635758659230109970282543
892 271400364184055466407472814
893 281523705144109603823198594
894 292018755267226672753762067
895 302898950169262735628994841
896 314178203542424463697251116
897 325870923902163448058180474
898 337992031911610529974651452
899 350556978303159155985346352
900 363581762417462262400793326
901 377082951380784264737507909
902 391077699942349073974934408
903 405583770994047404890996660
904 420619556795612722147075988
905 436204100929145759914806680
906 452357121007663443588694561
907 469099032163170050818733864
908 486450971340597422321979096
909 504434822424837841773722928
910 523073242228998742278120806
911 542389687372943596364122812
912 562408442082149163964690604
913 583154646937906690397889018
914 604654328610924687220088516
915 626934430611454643823230084
916 650022845090159485578923678
917 673948445725078938614497630
918 698741121731217335935163094
919 724431813030488989525666297
920 751052546621005291544566392
921 778636474185977461857833282
922 807217910983840630311442264
923 836832376062580084022818672
924 867516633842660413675928292
925 899308737114424387356210351
926 932248071497342151599007727
927 966375401410054334090148598
928 1001732917601766369830263948
929 1038364286297217523017538874
930 1076314700009168306474858888
931 1115630930074126031554289718
932 1156361380968861843169629704
933 1198556146467165646323525042
934 1242267067698239702784269206
935 1287547793170149332321748768
936 1334453840823832110513575231
937 1383042662185317289454866348
938 1433373708686027032102099776
939 1485508500223322659969689216
940 1539510696035824744305158062
941 1595446167970477884721356736
942 1653383076220851845968689064
943 1713391947618772861190827528
944 1775545756564064949246282769
945 1839920008679953699313723939
946 1906592827284546888551769044
947 1975645042771760359067266362
948 2047160284998106711543555361
949 2121225078774911580653187313
950 2197928942568770657075034068
951 2277364490516413417663949329
952 2359627537863600015976802514
953 2444817209941249385504048087
954 2533036054795682831988742266
955 2624390159593671854527835023
956 2718989270926905382144991002
957 2816946919144543896258697552
958 2918380546846709994092242644
959 3023411641676080938011838120
960 3132165873549202854876586982
961 3244773236473742843728336453
962 3361368195102638818095213836
963 3482089836181002080576896681
964 3607082025046679166223153162
965 3736493567350592327471284944
966 3870478376168357241125117071
967 4009195644680227318590497056
968 4152810024602141796455287548
969 4301491810556565135844284350
970 4455417130577903888118590687
971 4614768142953580010262499587
972 4779733239608332728186066405
973 4950507256246020720515813384
974 5127291689470109113482763598
975 5310294921111158214006560012
976 5499732449996989933016358344
977 5695827131408800567270255276
978 5898809424474322327267136349
979 6108917647757218247355132146
980 6326398243310233671378925894
981 6551506049468230381940574984
982 6784504582666104877347546600
983 7025666328575748817371943734
984 7275273042865656028144970888
985 7533616061896525706678065833
986 7800996623676264926037993544
987 8077726199408164817974983564
988 8364126835976723788236801236
989 8660531509726628015696790760
990 8967284491901784816447113487
991 9284741726123049044542882775
992 9613271218295397735090590590
993 9953253439347805186545806599
994 10305081741221961480507275269
995 10669162786539274290477677864
996 11045916992389309339787869140
997 11435778988696972008757468518
998 11839198091640324760949574869
999 12256638792605986053562654808
1000 12688581263184580420335828578