0 1
1 1
2 2
3 3
4 4
5 6
6 8
7 11
8 14
9 19
10 24
11 31
12 39
13 49
14 61
15 76
16 93
17 114
18 139
19 168
20 203
21 244
22 292
23 348
24 414
25 490
26 579
27 682
28 801
29 938
30 1097
31 1278
32 1487
33 1726
34 1999
35 2311
36 2667
37 3071
38 3531
39 4053
40 4644
41 5313
42 6070
43 6923
44 7886
45 8971
46 10190
47 11561
48 13100
49 14825
50 16758
51 18922
52 21340
53 24042
54 27058
55 30420
56 34166
57 38337
58 42974
59 48129
60 53854
61 60205
62 67248
63 75053
64 83692
65 93253
66 103824
67 115503
68 128400
69 142633
70 158327
71 175625
72 194679
73 215651
74 238725
75 264097
76 291975
77 322596
78 356209
79 393084
80 433521
81 477840
82 526385
83 579538
84 637707
85 701330
86 770891
87 846908
88 929937
89 1020590
90 1119523
91 1227438
92 1345108
93 1473358
94 1613076
95 1765232
96 1930864
97 2111088
98 2307120
99 2520262
100 2751913
101 3003592
102 3276929
103 3573670
104 3895713
105 4245088
106 4623973
107 5034728
108 5479879
109 5962134
110 6484423
111 7049878
112 7661861
113 8323996
114 9040165
115 9814524
116 10651553
117 11556045
118 12533131
119 13588335
120 14727563
121 15957135
122 17283847
123 18714961
124 20258247
125 21922047
126 23715274
127 25647457
128 27728818
129 29970273
130 32383488
131 34980961
132 37776038
133 40782969
134 44017012
135 47494449
136 51232656
137 55250225
138 59566982
139 64204081
140 69184132
141 74531237
142 80271100
143 86431171
144 93040702
145 100130870
146 107734946
147 115888372
148 124628898
149 133996790
150 144034914
151 154788910
152 166307426
153 178642228
154 191848408
155 205984649
156 221113368
157 237300963
158 254618114
159 273139971
160 292946434
161 314122511
162 336758544
163 360950543
164 386800600
165 414417167
166 443915444
167 475417871
168 509054452
169 544963229
170 583290836
171 624192905
172 667834618
173 714391351
174 764049168
175 817005465
176 873469717
177 933664081
178 997824139
179 1066199783
180 1139055919
181 1216673351
182 1299349807
183 1387400775
184 1481160551
185 1580983417
186 1687244647
187 1800341732
188 1920695745
189 2048752548
190 2184984207
191 2329890596
192 2484000815
193 2647874852
194 2822105445
195 3007319756
196 3204181313
197 3413392178
198 3635694915
199 3871874866
200 4122762661
201 4389236536
202 4672224997
203 4972709720
204 5291728293
205 5630377304
206 5989815717
207 6371268090
208 6776028163
209 7205462790
210 7661015692
211 8144211642
212 8656661028
213 9200064232
214 9776216516
215 10387013288
216 11034455236
217 11720653998
218 12447838262
219 13218359766
220 14034699868
221 14899476618
222 15815451751
223 16785538302
224 17812808807
225 18900503422
226 20052038767
227 21271017408
228 22561237295
229 23926702016
230 25371631749
231 26900474228
232 28517916619
233 30228898164
234 32038622923
235 33952573490
236 35976525611
237 38116562948
238 40379092935
239 42770863654
240 45298980927
241 47970926630
242 50794578175
243 53778228262
244 56930606049
245 60260899584
246 63778778653
247 67494419203
248 71418529175
249 75562374915
250 79937809303
251 84557301517
252 89433967511
253 94581602407
254 100014714775
255 105748561745
256 111799186323
257 118183456809
258 124919107251
259 132024780391
260 139520072956
261 147425582247
262 155762955516
263 164554941991
264 173825446490
265 183599586137
266 193903750110
267 204765661273
268 216214441302
269 228280679257
270 240996502372
271 254395650797
272 268513556254
273 283387423283
274 299056314992
275 315561243187
276 332945261592
277 351253564147
278 370533588234
279 390835121587
280 412210414858
281 434714299827
282 458404311890
283 483340818921
284 509587156562
285 537209768443
286 566278353646
287 596866021430
288 629049451670
289 662909063518
290 698529192224
291 735998272638
292 775409031968
293 816858691774
294 860449177718
295 906287339714
296 954485182586
297 1005160105652
298 1058435154042
299 1114439281950
300 1173307626106
301 1235181792557
302 1300210156922
303 1368548176405
304 1440358716852
305 1515812395023
306 1595087934388
307 1678372537913
308 1765862278030
309 1857762502155
310 1954288257334
311 2055664734367
312 2162127729724
313 2273924129023
314 2391312412594
315 2514563181309
316 2643959706802
317 2779798506661
318 2922389942706
319 3072058846885
320 3229145175280
321 3394004688549
322 3567009663472
323 3748549636271
324 3939032176080
325 4138883693443
326 4348550284770
327 4568498611075
328 4799216816220
329 5041215485807
330 5295028644979
331 5561214800847
332 5840358030771
333 6133069114837
334 6439986718689
335 6761778628053
336 7099143033477
337 7452809871823
338 7823542226053
339 8212137782023
340 8619430349163
341 9046291446963
342 9493631956053
343 9962403841233
344 10453601948757
345 10968265876694
346 11507481926389
347 12072385137612
348 12664161406359
349 13284049694066
350 13933344331007
351 14613397413256
352 15325621302527
353 16071491232072
354 16852548018395
355 17670400888650
356 18526730427543
357 19423291643722
358 20361917166295
359 21344520575938
360 22373099870773
361 23449741078710
362 24576622021183
363 25756016228920
364 26990297022461
365 28281941762866
366 29633536273949
367 31047779449650
368 32527488052771
369 34075601707058
370 35695188097251
371 37389448384306
372 39161722838369
373 41015496705354
374 42954406315361
375 44982245436148
376 47102971889020
377 49320714436354
378 51639779944828
379 54064660843330
380 56600042885796
381 59250813224194
382 62022068812232
383 64919125151286
384 67947525385096
385 71113049765380
386 74421725501576
387 77879837002444
388 81493936533640
389 85270855306298
390 89217715005576
391 93341939785742
392 97651268748523
393 102153768915356
394 106857848722673
395 111772272058780
396 116906172855117
397 122269070263516
398 127870884440397
399 133721952952860
400 139833047841103
401 146215393360860
402 152880684423101
403 159841105768668
404 167109351904539
405 174698647821462
406 182622770534423
407 190896071475744
408 199533499763551
409 208550626391174
410 217963669370655
411 227789519856690
412 238045769300863
413 248750737673266
414 259923502781823
415 271583930743754
416 283752707650971
417 296451372463832
418 309702351193027
419 323528992416472
420 337955604170179
421 353007492279000
422 368711000179531
423 385093550279384
424 402183686925485
425 420011121039481
426 438606776470739
427 458002838146617
428 478232802084885
429 499331527325617
430 521335289869891
431 544281838698077
432 568210453932225
433 593162007238749
434 619179024552705
435 646305751196209
436 674588219497217
437 704074318999089
438 734813869342763
439 766858695938609
440 800262708528555
441 835081982730809
442 871374844696012
443 909201958986889
444 948626419785330
445 989713845568617
446 1032532477379894
447 1077153280809415
448 1123650051842748
449 1172099526715399
450 1222581495904276
451 1275178922428469
452 1329978064614420
453 1387068603471541
454 1446543774868756
455 1508500506684085
456 1573039561091188
457 1640265682192733
458 1710287749191970
459 1783218935286109
460 1859176872512610
461 1938283822761585
462 2020666855159202
463 2106458030077135
464 2195794590005154
465 2288819157515329
466 2385679940599678
467 2486530945644353
468 2591532198295422
469 2700849972527387
470 2814657028206306
471 2933132857432347
472 3056463940004892
473 3184844008334249
474 3318474322117588
475 3457563953157481
476 3602330080683018
477 3752998297527084
478 3909802927577386
479 4072987354900822
480 4242804364934442
481 4419516498204290
482 4603396417015082
483 4794727285548236
484 4993803163877612
485 5200929416393732
486 5416423135123376
487 5640613578506534
488 5873842626174640
489 6116465250271532
490 6368850003936944
491 6631379527555704
492 6904451073373882
493 7188477049165874
494 7483885581620922
495 7791121100116183
496 8110644941631710
497 8442935977547359
498 8788491263062036
499 9147826710069151
500 9521477784307060
501 9910000227606495
502 10313970806154698
503 10733988085682645
504 11170673234487056
505 11624670855301589
506 12096649847020656
507 12587304297286101
508 13097354407055984
509 13627547448265685
510 14178658755700354
511 14751492754313845
512 15346884023221704
513 15965698397607677
514 16608834109906386
515 17277222971619069
516 17971831597135126
517 18693662671062211
518 19443756260564608
519 20223191174229657
520 21033086369118920
521 21874602407661977
522 22748942966074056
523 23657356396124251
524 24601137342086342
525 25581628414731137
526 26600221924375022
527 27658361675007873
528 28757544821555694
529 29899323792499343
530 31085308280082808
531 32317167300383579
532 33596631325693159
533 34925494491673499
534 36305616881800783
535 37738926891793989
536 39227423676750383
537 40773179683761783
538 42378343272984047
539 44045141430163831
540 45775882573685295
541 47572959459412355
542 49438852186640093
543 51376131308536589
544 53387461050683869
545 55475602641372149
546 57643417757379801
547 59893872089213429
548 62230039029837457
549 64655103491011783
550 67172365851613841
551 69785246042387744
552 72497287771663243
553 75312162896863200
554 78233675946696537
555 81265768799045696
556 84412525519854169
557 87678177368409868
558 91067107974546585
559 94583858693604054
560 98233134145090259
561 102019807941133354
562 105948928611150547
563 110025725729280428
564 114255616251286957
565 118644211068006828
566 123197321782549933
567 127920967718642436
568 132821383167892683
569 137905024883917916
570 143178579831469589
571 148648973199116368
572 154323376684221655
573 160209217059176272
574 166314185028299991
575 172646244385025936
576 179213641479232831
577 186024915005076016
578 193088906119895149
579 200414768905055984
580 208011981180105811
581 215890355681879036
582 224060051620499091
583 232531586624785572
584 241315849089864595
585 250424110940123300
586 259868040821257115
587 269659717735481520
588 279811645134360763
589 290336765484361904
590 301248475320602826
591 312560640804686532
592 324287613803220362
593 336444248504021700
594 349045918587481606
595 362108534971318670
596 375648564147406794
597 389683047129878926
598 404229619034531026
599 419306529310053838
600 434932662642191756
601 451127560552818248
602 467911443716475614
603 485305235017559112
604 503330583372288222
605 522009888340226696
606 541366325550812986
607 561423872971402120
608 582207338044007668
609 603742385718705032
610 626055567412780573
611 649174350925475176
612 673127151339021021
613 697943362937886842
614 723653392178993455
615 750288691746596942
616 777881795726855731
617 806466355938032910
618 836077179453316147
619 866750267354666446
620 898522854757139507
621 931433452144259950
622 965521888056575525
623 1000829353176659310
624 1037398445855078949
625 1075273219123526966
626 1114499229242567347
627 1155123585832827746
628 1197195003640283021
629 1240763855987667626
630 1285882229965562915
631 1332603983418677418
632 1380984803784370435
633 1431082268842127108
634 1482955909434833165
635 1536667274224383362
636 1592279996545980685
637 1649859863427803220
638 1709474886844572411
639 1771195377275557990
640 1835094019640070901
641 1901245951685540710
642 1969728844905468149
643 2040622988067275622
644 2114011373432327669
645 2189979785752798566
646 2268616894133032789
647 2350014346845513978
648 2434266869194196125
649 2521472364521174714
650 2611732018455387239
651 2705150406504926039
652 2801835605098046337
653 2901899306180930287
654 3005456935483438945
655 3112627774567884263
656 3223535086779123553
657 3338306247217750567
658 3457072876862286433
659 3579970980969862117
660 3707141091888683633
661 3838728416420060133
662 3974882987871707911
663 4115759822948203203
664 4261519083629335629
665 4412326244191422787
666 4568352263531201613
667 4729773762957212251
668 4896773209618311919
669 5069539105743940609
670 5248266183876518831
671 5433155608281532149
672 5624415182726306408
673 5822259564824737633
674 6026910487150906928
675 6238596985330466913
676 6457555633325494000
677 6684030786134700295
678 6918274830137411166
679 7160548441317115655
680 7411120851607178334
681 7670270123608421095
682 7938283433936326932
683 8215457365463036657
684 8502098208727089338
685 8798522272792600049
686 9105056205847683770
687 9422037325840430289
688 9749813961460241104
689 10088745803781211345
690 10439204268893516354
691 10801572871859100305
692 11176247612337658178
693 11563637372239031639
694 11964164325769379924
695 12378264362249075823
696 12806387522091336788
697 13248998446342820065
698 13706576840198977396
699 14179617950919036641
700 14668633060578759440
701 15174149994111758271
702 15696713643103325360
703 16236886505815166911
704 16795249243933230320
705 17372401256545175409
706 17968961271869744492
707 18585567957275338609
708 19222880548140774506
709 19881579496128270193
710 20562367137455129596
711 21265968381767684773
712 21993131422239611900
713 22744628467534654821
714 23521256496292420486
715 24323838034816082320
716 25153221958660373254
717 26010284318838555198
718 26895929193388980486
719 27811089565063175144
720 28756728225919500358
721 29733838709630288180
722 30743446252333581894
723 31786608782884721972
724 32864417943388931820
725 33978000140921379938
726 35128517631367464940
727 36317169636344231756
728 37545193494191423440
729 38813865846049287898
730 40124503858070862792
731 41478466480846532326
732 42877155747149809122
733 44322018109146554106
734 45814545816242604906
735 47356278334778707706
736 48948803810817794030
737 50593760577305317141
738 52292838706920295524
739 54047781611973989267
740 55860387692751976138
741 57732512035735598463
742 59666068163181425034
743 61663029835579659647
744 63725432908556182434
745 65855377245829268773
746 68055028689878064294
747 70326621092027499995
748 72672458403704695142
749 75094916830671994625
750 77596447052093575526
751 80179576506347270185
752 82846911745547762084
753 85601140860803644745
754 88445035980290262134
755 91381455842279547143
756 94413348445329345654
757 97543753777899254553
758 100775806629724503158
759 104112739487346034551
760 107557885516265031030
761 111114681632260279159
762 114786671664479205548
763 118577509612989523213
764 122490963003554709228
765 126530916342475272973
766 130701374674420416880
767 135006467246257618957
768 139450451279973247890
769 144037715857867047935
770 148772785923293468616
771 153660326400315823627
772 158705146435736665184
773 163912203767065725605
774 169286609220087840672
775 174833631339798993573
776 180558701158585078072
777 186467417105627770533
778 192565550061636653368
779 198859048563122400461
780 205354044160545091908
781 212056856934796268749
782 218974001176598985867
783 226112191233539647215
784 233478347529580558483
785 241079602762038600975
786 248923308281156092371
787 257017040657536542031
788 265368608442866213489
789 273986059129495136219
790 282877686314610303601
791 292052037074894723591
792 301517919557731792115
793 311284410795187052159
794 321360864747174118643
795 331756920580391521429
796 342482511189804439031
797 353547871969634948245
798 364963549841019745143
799 376740412543697355245
800 388889658199292686199
801 401422825153978749811
802 414351802108515595973
803 427688838543889874421
804 441446555451008440005
805 455637956373138210072
806 470276438770026858205
807 485375805712888446960
808 500950277919697018589
809 517014506140494116214
810 533583583902686865199
811 550673060626593954934
812 568298955121782092489
813 586477769475029055094
814 605226503341053769761
815 624562668647463203326
816 644504304725684199269
817 665069993879978229644
818 686278877406972511657
819 708150672078486132652
820 730705687100787295299
821 753964841563781562892
822 777949682394005227779
823 802682402825685310914
824 828185861404522082497
825 854483601539255679656
826 881599871616498160257
827 909559645694739841704
828 938388644793878493825
829 968113358797074748988
830 998761068982200452545
831 1030359871200623229768
832 1062938699721563233729
833 1096527351760760195990
834 1131156512712705303809
835 1166857782106226109372
836 1203663700303756814789
837 1241607775965185781014
838 1280724514297750139675
839 1321049446114036935126
840 1362619157720756353045
841 1405471321661578594486
842 1449644728337964612493
843 1495179318532577494136
844 1542116216860539147149
845 1590497766174488722552
846 1640367562950110321677
847 1691770493679531495788
848 1744752772300743264979
849 1799361978691962483052
850 1855647098260651973331
851 1913658562657725199212
852 1973448291648296098530
853 2035069736171194872748
854 2098577922620349016602
855 2164029498382031676814
856 2231482778662910466842
857 2300997794644780948878
858 2372636343002846325008
859 2446462036825412518842
860 2522540357973897376914
861 2600938710923110607598
862 2681726478122851491986
863 2764975076922985759118
864 2850758018105307962514
865 2939150966066675562190
866 3030231800699106930286
867 3124080681013774508428
868 3220780110557100870606
869 3320415004668470492626
870 3423072759630410675662
871 3528843323763476030418
872 3637819270519482964552
873 3750095873628191075282
874 3865771184354022118664
875 3984946110920934842696
876 4107724500165143062353
877 4234213221476979966296
878 4364522253094864116497
879 4498764770816019825014
880 4637057239190351796723
881 4779519505265661257218
882 4926274894954226381441
883 5077450312092659162692
884 5233176340268883825327
885 5393587347492066910084
886 5558821593783371952171
887 5729021341767501883844
888 5904332970347138679821
889 6084907091544598243780
890 6270898670597278529805
891 6462467149395799499204
892 6659776573356120856917
893 6862995721819366814294
894 7072298242075595802965
895 7287862787110333486368
896 7509873157175328598357
897 7738518445287702817298
898 7973993186764454712701
899 8216497512902132562960
900 8466237308914421623871
901 8723424376243405182360
902 8988276599363343985581
903 9261018117198985880570
904 9541879499283673972077
905 9831097926785855594810
906 10128917378536016813969
907 10435588822189585524186
908 10751370410664948603281
909 11076527683999426312960
910 11411333776769848041119
911 11756069631228265449932
912 12111024216307333847647
913 12476494752653998323660
914 12852786943854325549009
915 13240215214016637306178
916 13639102951884536343565
917 14049782761655956472322
918 14472596720689029600909
919 14907896644280351570434
920 15356044357706133411469
921 15817411975721758183478
922 16292382189720435174719
923 16781348562756939959596
924 17284715832647864335679
925 17802900223365384195165
926 18336329764947272781879
927 18885444622151755760733
928 19450697432091833255157
929 20032553651089869142333
930 20631491910999584218101
931 21248004385249098020413
932 21882597164865330567059
933 22535790644746915436147
934 23208119920459800645583
935 23900135195836909921097
936 24612402201670620262067
937 25345502625794393854281
938 26100034554857669455539
939 26876612928106087134833
940 27675870003487302847891
941 28498455836411031781029
942 29345038771500559097235
943 30216305947681786453861
944 31112963816964928287123
945 32035738677283251503013
946 32985377219762779310483
947 33962647090806640175013
948 34968337469387755199315
949 36003259659953835728363
950 37068247701359193203748
951 38164158992248665055563
952 39291874933330048439368
953 40452301586982793431371
954 41646370354662359534944
955 42875038672571599465421
956 44139290726082787672928
957 45440138183406479448341
958 46778620949016285989130
959 48155807937351866931895
960 49572797867335997050504
961 51030720078255475182519
962 52530735367569896380808
963 54074036851226926305283
964 55661850847077717939848
965 57295437782001480247299
966 58976093123363970976812
967 60705148335450860367589
968 62483971861533484437940
969 64313970132241501647013
970 66196588600934404787660
971 68133312806781706624869
972 70125669466279939920588
973 72175227593953410981751
974 74283599653004906459872
975 76452442736702303946927
976 78683459781307300001462
977 80978400811373230445999
978 83339064218260246601860
979 85767298072737950786169
980 88265001472567970926212
981 90834125925981898502521
982 93476676771993550630596
983 96194714638508632273431
984 98990356939219600776900
985 101865779410298897867287
986 104823217687929700646600
987 107864968927739986928661
988 110993393467233038665416
989 114210916532335507281581
990 117520029989212872085818
991 120923294142531566294701
992 124423339581377212043222
993 128022869074069333498951
994 131724659513144636167656
995 135531563911813438624839
996 139446513453227159587336
997 143472519593928930425013
998 147612676222894409486600
999 151870161877605761306839
1000 156248242018638564648106