0 1
1 1
2 1
3 2
4 4
5 7
6 12
7 19
8 30
9 45
10 67
11 96
12 137
13 190
14 262
15 353
16 474
17 625
18 821
19 1062
20 1370
21 1745
22 2216
23 2783
24 3487
25 4328
26 5359
27 6580
28 8063
29 9808
30 11906
31 14357
32 17282
33 20681
34 24705
35 29354
36 34824
37 41115
38 48468
39 56883
40 66668
41 77823
42 90723
43 105368
44 122229
45 141306
46 163166
47 187809
48 215939
49 247556
50 283501
51 323774
52 369406
53 420397
54 477968
55 542119
56 614333
57 694610
58 784695
59 884588
60 996387
61 1120092
62 1258154
63 1410573
64 1580274
65 1767257
66 1974921
67 2203266
68 2456316
69 2734071
70 3041180
71 3377643
72 3748930
73 4155041
74 4602267
75 5090608
76 5627417
77 6212694
78 6854854
79 7553897
80 8319608
81 9151987
82 10062189
83 11050214
84 12128962
85 13298433
86 14573272
87 15953479
88 17455915
89 19080580
90 20846551
91 22753828
92 24824271
93 27057880
94 29479298
95 32088525
96 34913691
97 37954796
98 41243457
99 44779674
100 48599392
101 52702611
102 57129604
103 61880371
104 67000544
105 72490123
106 78400099
107 84730472
108 91538813
109 98825122
110 106653550
111 115024097
112 124008977
113 133608190
114 143902013
115 154890446
116 166663574
117 179221397
118 192663808
119 206990807
120 222314193
121 238633966
122 256073831
123 274633788
124 294451899
125 315528164
126 338015002
127 361912413
128 387390098
129 414448057
130 443273273
131 473865746
132 506433140
133 540975455
134 577721036
135 616669883
136 658075046
137 701936525
138 748532075
139 797861696
140 850232497
141 905644478
142 964434102
143 1026601369
144 1092517566
145 1162182693
146 1236002861
147 1313978070
148 1396555546
149 1483735289
150 1576005640
151 1673366599
152 1776354975
153 1884970768
154 1999799255
155 2120840436
156 2248736471
157 2383487360
158 2525792146
159 2675650829
160 2833829120
161 3000327019
162 3175976905
163 3360778778
164 3555642840
165 3760569091
166 3976545556
167 4203572235
168 4442727876
169 4694012479
170 4958595515
171 5236476984
172 5528931725
173 5835959738
174 6158941230
175 6497876201
176 6854267087
177 7228113888
178 7621041269
179 8033049230
180 8465903742
181 8919604805
182 9396059696
183 9895268415
184 10419301405
185 10968158666
186 11544073807
187 12147046828
188 12779499147
189 13441430764
190 14135450906
191 14861559573
192 15622581931
193 16418517980
194 17252408825
195 18124254466
196 19037343564
197 19991676119
198 20990788348
199 22034680251
200 23127171546
201 24268262233
202 25462055531
203 26708551440
204 28012176953
205 29372932070
206 30795567558
207 32280083417
208 33831599820
209 35450116767
210 37141123837
211 38904621030
212 40746518322
213 42666815713
214 44671843576
215 46761601911
216 48942899059
217 51215735020
218 53587396103
219 56057882308
220 58635022063
221 61318815368
222 64117632770
223 67031474269
224 70069324745
225 73231184198
226 76526651841
227 79955727674
228 83528705520
229 87245585379
230 91117355684
231 95144016435
232 99337340760
233 103697328659
234 108236537955
235 112954968648
236 117866063149
237 122969821458
238 128280570574
239 133798310497
240 139538364613
241 145500732922
242 151701735197
243 158141371438
244 164837081510
245 171788865413
246 179015283104
247 186516334583
248 194311837961
249 202401793238
250 210807276679
251 219528288284
252 228587314891
253 237984356500
254 247743310522
255 257864176957
256 268372433490
257 279268080121
258 290578174809
259 302302717554
260 314470533572
261 327081622863
262 340166577900
263 353725398683
264 367790652606
265 382362339669
266 397475002187
267 413128640160
268 429359999169
269 446169079214
270 463594829142
271 481637248953
272 500337743810
273 519696313713
274 539756820141
275 560519263094
276 582030238122
277 604289745225
278 627347114024
279 651202344519
280 675907807511
281 701463503000
282 727924842967
283 755291827412
284 783623245959
285 812919098608
286 843241552626
287 874590608013
288 907032180966
289 940566271485
290 975262544697
291 1011121000602
292 1048215459368
293 1086545920995
294 1126190360692
295 1167148778459
296 1209503751772
297 1253255280631
298 1298490544779
299 1345209544216
300 1393504549293
301 1443375560010
302 1494919937326
303 1548137681241
304 1603131780131
305 1659902233996
306 1718557658629
307 1779098054030
308 1841638248686
309 1906178242597
310 1972839076944
311 2041620751727
312 2112651162981
313 2185930310706
314 2261592945791
315 2339639068236
316 2420210982827
317 2503308689564
318 2589082047130
319 2677531055525
320 2768813893040
321 2862930559675
322 2960047553329
323 3060164874002
324 3163458171580
325 3269927446063
326 3379757499324
327 3492948331363
328 3609694806242
329 3729996923961
330 3854059610771
331 3981882866672
332 4113682668129
333 4249459015142
334 4389438934390
335 4533622425873
336 4682248645232
337 4835317592467
338 4993080552181
339 5155537524374
340 5322953092082
341 5495327255305
342 5672937895512
343 5855785012703
344 6044161061619
345 6238066042260
346 6437806982639
347 6643383882756
348 6855119724103
349 7073014506680
350 7297407165458
351 7528297700437
352 7766042502503
353 8010641571656
354 8262468754697
355 8521524051626
356 8788200389824
357 9062497769291
358 9344828197988
359 9635191675915
360 9934021057584
361 10241316342995
362 10557531233211
363 10882665728232
364 11217196282949
365 11561122897362
366 11914944780190
367 12278661931433
368 12652798384081
369 13037354138134
370 13432878050853
371 13839370122238
372 14257406267430
373 14686986486429
374 15128713752256
375 15582588064911
376 16049241876713
377 16528675187662
378 17021549929375
379 17527866101852
380 18048317725235
381 18582904799524
382 19132353433386
383 19696663626821
384 20276596402187
385 20872151759484
386 21484125634761
387 22112518028018
388 22758162830100
389 23421060041007
390 24102081506380
391 24801227226219
392 25519410289622
393 26256630696589
394 27013842779675
395 27791046538880
396 28589241086433
397 29408426422334
398 30249646438486
399 31112901134889
400 31999283002838
401 32908792042333
402 33842569344061
403 34800614908022
404 35784122527514
405 36793092202537
406 37828770429000
407 38891157206903
408 39981556161759
409 41099967293568
410 42247751357447
411 43424908353396
412 44632860916903
413 45871609047968
414 47142637262450
415 48445945560349
416 49783085458068
417 51154056955607
418 52560478569913
419 54002350300986
420 55481363155896
421 56997517134643
422 58552575734420
423 60146538955227
424 61781248694356
425 63456704951807
426 65174828024971
427 66935617913848
428 68741079646301
429 70591213222330
430 72488108400270
431 74431765180121
432 76424364859031
433 78465907437000
434 80558665749989
435 82702639797998
436 84900201242110
437 87151350082325
438 89458556804848
439 91821821409679
440 94243721036573
441 96724255685530
442 99266109149855
443 101869281429548
444 104536571342011
445 107267978887244
446 110066417906746
447 112931888400517
448 115867428219033
449 118873037362294
450 121951877689753
451 125103949201410
452 128332547364908
453 131637672180247
454 135022752723260
455 138487788993947
456 142036353970154
457 145668447651881
458 149387786918987
459 153194371771472
460 157092073979641
461 161080893543494
462 165164857123782
463 169343964720505
464 173622409657988
465 178000191936231
466 182481671543133
467 187066848478694
468 191760261952210
469 196561911963681
470 201476516943800
471 206504076892567
472 211649502904483
473 216912794979548
474 222299056876071
475 227808288594052
476 233445800882607
477 239211593741736
478 245111184911362
479 251144574391485
480 257317502236221
481 263629968445570
482 270087935387841
483 276691403063034
484 283446572473424
485 290353443619011
486 297418456136036
487 304641610024499
488 312029600994472
489 319582429045955
490 327307045962851
491 335203451745160
492 343278872810573
493 351533309159090
494 359974261842190
495 368601730859873
496 377423511715517
497 386439604409122
498 395658098895965
499 405078995176046
500 414710698732806
501 424553209566245
502 434615248687968
503 444896816097975
504 455406970822873
505 466145712862662
506 477122439258951
507 488337150011740
508 499799604075051
509 511509801448884
510 523477862999674
511 535703788727421
512 548198086888658
513 560960757483385
514 574002696158233
515 587323902913202
516 600935687842980
517 614838050947567
518 629042716769708
519 643549685309403
520 658371124382670
521 673507033989509
522 688970025219211
523 704760098071776
524 720890337502241
525 737360743510606
526 754184874917654
527 771362731723385
528 788908379181722
529 806821817292665
530 825117617743277
531 843795780533558
532 862871418326026
533 882344531120681
534 902230772555496
535 922530142630471
536 943258872704615
537 964416962777928
538 986021221930455
539 1008071650162196
540 1030585673223079
541 1053563291113104
542 1077022546252082
543 1100963438640013
544 1125404668771754
545 1150346236647305
546 1175807500836569
547 1201788461339546
548 1228309178662664
549 1255369652805923
550 1282990646212276
551 1311172158881723
552 1339935701789292
553 1369281274934983
554 1399231137825899
555 1429785290462040
556 1460966790212205
557 1492775637076394
558 1525235686285102
559 1558346937838329
560 1592134097199067
561 1626597164367316
562 1661761695038565
563 1697627689212814
564 1734221608230030
565 1771543452090213
566 1809620587777808
567 1848453015292815
568 1888069066053781
569 1928468740060706
570 1969681333166239
571 2011706845370380
572 2054575599127147
573 2098287594436540
574 2142874180353946
575 2188335356879365
576 2234703565585750
577 2281978806473101
578 2330194613631937
579 2379350987062258
580 2429482623037276
581 2480589521556991
582 2532707541077308
583 2585836681598227
584 2640014037578514
585 2695239609018169
586 2751551726378819
587 2808950389660464
588 2867475243302801
589 2927126287305830
590 2987944480087318
591 3049929821647265
592 3113124666958984
593 3177529016022475
594 3243186620366597
595 3310097479991350
596 3378306830160882
597 3447814670875193
598 3518667721133720
599 3590865980936463
600 3664457745288499
601 3739443014189828
602 3815871658651167
603 3893743678672516
604 3973110618631191
605 4053972478527192
606 4136382476104434
607 4220340611362917
608 4305901878401531
609 4393066277220276
610 4481890578273017
611 4572374781559754
612 4664577542505120
613 4758498861109115
614 4854199277767140
615 4951678792479195
616 5050999945439936
617 5152162736649363
618 5255231706101387
619 5360206853796008
620 5467154840567573
621 5576075666416082
622 5687038113016318
623 5800042180368281
624 5915158898883225
625 6032388268561150
626 6151803568549781
627 6273404798849118
628 6397267622094246
629 6523392038285165
630 6651856093544320
631 6782659787871711
632 6915883693181929
633 7051527809474974
634 7189675234457583
635 7330325968129756
636 7473565783849059
637 7619394681615492
638 7767901110437450
639 7919085070314933
640 8073037844085456
641 8229759431749019
642 8389343949972257
643 8551791398755170
644 8717198895091412
645 8885566438980983
646 9056994147744556
647 9231482021382131
648 9409133353191286
649 9589948143172021
650 9774032860598819
651 9961387505471680
652 10152121907843865
653 10346236067715374
654 10543843175918246
655 10744943232452481
656 10949652983792958
657 11157972429939677
658 11370021873010357
659 11585801313004998
660 11805434812610410
661 12028922371826593
662 12256391813909448
663 12487843138858975
664 12723408146476631
665 12963086836762416
666 13207014986063343
667 13455192594379412
668 13707759641629871
669 13964716127814720
670 14226206236425442
671 14492229967462037
672 14762935947143864
673 15038324175470923
674 15318547721390449
675 15603606584902442
676 15893658528966616
677 16188703553582971
678 16488904115723700
679 16794260215388803
680 17104939268145988
681 17420941273995255
682 17742438607099827
683 18069431267459704
684 18402096865715093
685 18740435401865994
686 19084629723029598
687 19434679829205905
688 19790774096443831
689 20152912524743376
690 20521289019085181
691 20895903579469246
692 21276955946835950
693 21664446121185293
694 22058579679417392
695 22459356621532247
696 22866988683371205
697 23281475864934266
698 23703036061004007
699 24131669271580428
700 24567599889322307
701 25010827914229644
702 25461584236837418
703 25919868857145629
704 26385919519956343
705 26859736225269560
706 27341563572154433
707 27831401560610962
708 28329502017822188
709 28835864943788111
710 29350749393805660
711 29874155367874835
712 30406349542333834
713 30947331917182657
714 31497376789800771
715 32056484160188176
716 32624936358773569
717 33202733385556950
718 33790165604016246
719 34387233014151457
720 34994234445344252
721 35611169897594631
722 36238346666188005
723 36875764751124374
724 37523740367293954
725 38182273514696745
726 38851689327827768
727 39531987806687023
728 40223503481829227
729 40926236353254380
730 41640530347576895
731 42366385464796772
732 43104155526796839
733 43853840533577096
734 44615804202288786
735 45390046532931909
736 46176941661959113
737 46976489589370398
738 47789074870919817
739 48614697506607370
740 49453753020345776
741 50306241412135035
742 51172569174046532
743 52052736306080267
744 52947160844381432
745 53855842788950027
746 54779211720005051
747 55717267637546504
748 56670452268840213
749 57638765613886178
750 58622661546997054
751 59622140068172841
752 60637667831225341
753 61669244836154554
754 62717350516271429
755 63781984871575966
756 64863640776809878
757 65962318231973165
758 67078523553238304
759 68212256740605295
760 69364038245697521
761 70533868068514982
762 71722280796131967
763 72929276428548476
764 74155404414398371
765 75400664753681652
766 76665621756591754
767 77950275423128677
768 79255205686067787
769 80580412545409084
770 81926491556509865
771 83293442719370130
772 84681878007865156
773 86091797421994943
774 87523829354152748
775 88977973804338571
776 90454876417354494
777 91954537193200517
778 93477619029087547
779 95024121925015584
780 96594726902450001
781 98189433961390798
782 99808942247557814
783 101453251760951049
784 103123080684633906
785 104818429018606385
786 106540033983275453
787 108287895578641110
788 110062771016786442
789 111864660297711449
790 113694340625175336
791 115551811999178103
792 117437872614267303
793 119352522470442936
794 121296580753040903
795 123270047462061204
796 125273763817519991
797 127307729819417264
798 129372808722449426
799 131469000526616477
800 133597191613786366
801 135757381983959093
802 137950481146174153
803 140176489100431546
804 142436339624033000
805 144730032716978515
806 147058526424832052
807 149421820747593611
808 151820899192882684
809 154255761760699271
810 156727417420718395
811 159235866172940056
812 161782143695590717
813 164366249988670378
814 166989247438956942
815 169651136046450409
816 172353006210105635
817 175094857929922620
818 177877809617033173
819 180701861271437294
820 183568160677198862
821 186476707834317877
822 189428679899790288
823 192424076873616095
824 195464106708358805
825 198548769404018418
826 201679303708725999
827 204855709622481548
828 208079258173499547
829 211349949361779996
830 214669086495620794
831 218036669575021941
832 221454035739881156
833 224921184990198439
834 228439488297471329
835 232008945661699826
836 235630963504498236
837 239305541825866559
838 243034122497535868
839 246816705519506163
840 250654769904632354
841 254548315652914441
842 258498858918331171
843 262506399700882544
844 266572493059168337
845 270697138993188550
846 274881931466163990
847 279126870478094657
848 283433590738719680
849 287802092248039059
850 292234050462310245
851 296729465381533238
852 301290055128781202
853 305915819704054137
854 310608519897240920
855 315368155708341551
856 320196532599088483
857 325093650569481716
858 330061359753097279
859 335099660149935172
860 340210448655173335
861 345393725268811768
862 350651433647630322
863 355983573791628997
864 361392138300486703
865 366877127174203440
866 372440581955357177
867 378082502643947914
868 383804981998288640
869 389608020018379355
870 395493760678268068
871 401462203977954779
872 407515547478883600
873 413653791181054531
874 419879186233307787
875 426191732635643368
876 432593737594783797
877 439085201110729074
878 445668486448084030
879 452343593606848665
880 459112944486649873
881 465976539087487654
882 472936857944010965
883 479993901056219806
884 487150210277578502
885 494405785608087053
886 501763230220025152
887 509222544113392799
888 516786394578102457
889 524454781614154126
890 532230436629093039
891 540113359622919196
892 548106349034652099
893 556209404864291748
894 564425392582331914
895 572754312188772597
896 581199099223432313
897 589759753686311062
898 598439281186552105
899 607237681724155442
900 616158034139448532
901 625200338432431375
902 634367746674615628
903 643660258866001291
904 653081103604751862
905 662630280890867341
906 672311095849163067
907 682123548479639040
908 692071023862838273
909 702153521998760766
910 712374507923677206
911 722733981637587593
912 733235491705468134
913 743879038127318829
914 754668252996821405
915 765603136313975862
916 776687407418049306
917 787921066309041737
918 799307919571805640
919 810847967206341015
920 822545106914856031
921 834399338697350688
922 846414651373388839
923 858591044942970484
924 870932603369675911
925 883439326653505120
926 896115393902054834
927 908960805115325053
928 921979838738253260
929 935172494770839455
930 948543150995361881
931 962091807411820538
932 975822945499822328
933 989736565259367251
934 1003837251867390868
935 1018125005323893179
936 1032604519042347700
937 1047275793022754431
938 1062143628915124843
939 1077208026719458936
940 1092473901040736829
941 1107941251878958522
942 1123615106794072782
943 1139495465786079609
944 1155587474280990919
945 1171891132278806712
946 1188411703071602053
947 1205149186659376942
948 1222108969304027902
949 1239291051005554933
950 1256700940995676016
951 1274338639274391151
952 1292209783353988893
953 1310314373234469242
954 1328658174708691327
955 1347241187776655148
956 1366069312029530331
957 1385142547467316876
958 1404466927479494906
959 1424042452066064421
960 1443875294154870157
961 1463965453745912114
962 1484319243305399641
963 1504936662833332738
964 1525824170296653676
965 1546981765695362455
966 1568416052497134268
967 1590127030701969115
968 1612121455479277386
969 1634399326829059081
970 1656967551622459787
971 1679826129859479504
972 1702982126552635257
973 1726435541701927046
974 1750193598461243334
975 1774256296830584121
976 1798631024800919380
977 1823317782372249111
978 1848324122372624797
979 1873650044802046438
980 1899303274277430930
981 1925283810798778273
982 1951599550771870776
983 1978250494196708439
984 2005244716494356675
985 2032582217664815484
986 2060271252144433383
987 2088311819933210372
988 2116712361983829551
989 2145472878296290920
990 2174601996339612162
991 2204099716113793277
992 2233974859399689909
993 2264227426197302058
994 2294866432599323329
995 2325891878605753722
996 2357312982711080080
997 2389129744915302403
998 2421351586114700772
999 2453978506309275187
1000 2487020137202582408