0 0
1 1
2 1
3 1
4 1
5 1
6 2
7 2
8 3
9 3
10 5
11 5
12 7
13 7
14 10
15 11
16 14
17 15
18 19
19 22
20 26
21 30
22 35
23 42
24 47
25 56
26 62
27 76
28 83
29 100
30 108
31 132
32 142
33 171
34 184
35 222
36 239
37 284
38 306
39 363
40 394
41 460
42 500
43 581
44 636
45 730
46 802
47 914
48 1010
49 1139
50 1262
51 1415
52 1577
53 1753
54 1956
55 2163
56 2423
57 2663
58 2986
59 3268
60 3672
61 4002
62 4495
63 4885
64 5493
65 5953
66 6685
67 7232
68 8119
69 8772
70 9830
71 10610
72 11875
73 12812
74 14305
75 15431
76 17200
77 18558
78 20628
79 22262
80 24691
81 26665
82 29493
83 31867
84 35162
85 38026
86 41841
87 45278
88 49703
89 53834
90 58939
91 63879
92 69776
93 75688
94 82479
95 89514
96 97340
97 105714
98 114713
99 124629
100 134990
101 146727
102 158637
103 172461
104 186165
105 202436
106 218199
107 237262
108 255403
109 277719
110 298596
111 324610
112 348655
113 378948
114 406644
115 441791
116 473707
117 514440
118 551235
119 598284
120 640710
121 694998
122 743933
123 806390
124 862836
125 934616
126 999737
127 1082023
128 1157131
129 1251367
130 1338007
131 1445693
132 1545580
133 1668529
134 1783677
135 1923787
136 2056439
137 2215980
138 2368749
139 2550136
140 2725916
141 2931996
142 3134169
143 3368000
144 3600286
145 3865456
146 4132181
147 4432570
148 4738501
149 5078625
150 5429270
151 5814064
152 6215477
153 6650633
154 7109803
155 7601588
156 8126174
157 8681788
158 9280585
159 9907981
160 10590648
161 11298923
162 12076494
163 12875761
164 13760335
165 14662087
166 15667464
167 16684525
168 17825820
169 18972732
170 20267112
171 21560119
172 23026419
173 24483881
174 26143408
175 27785892
176 29662016
177 31512671
178 33631782
179 35716575
180 38107617
181 40455723
182 43151277
183 45795397
184 48831249
185 51808048
186 55224372
187 58574976
188 62415901
189 66186278
190 70501281
191 74742977
192 79586426
193 84356978
194 89789692
195 95153526
196 101242424
197 107271330
198 114091130
199 120865453
200 128498399
201 136107467
202 144645301
203 153188984
204 162732737
205 172321941
206 182984140
207 193742642
208 205647328
209 217712399
210 230997558
211 244522248
212 259340035
213 274493780
214 291013336
215 307984805
216 326392710
217 345390570
218 365894005
219 387150217
220 409977867
221 433748696
222 459154267
223 485724262
224 513987829
225 543670935
226 575103034
227 608247407
228 643190888
229 680180341
230 719015018
231 760274558
232 803419863
233 849417616
234 897337841
235 948591632
236 1001799440
237 1058879053
238 1117941602
239 1181476611
240 1247020043
241 1317702758
242 1390419234
243 1469013680
244 1549667248
245 1637013020
246 1726447667
247 1823470503
248 1922617523
249 2030333966
250 2140221442
251 2259751312
252 2381513211
253 2514085574
254 2648972755
255 2795940251
256 2945331856
257 3108178337
258 3273594533
259 3453951867
260 3637067798
261 3836725169
262 4039386012
263 4260309659
264 4484547503
265 4728892433
266 4976943918
267 5247076646
268 5521403568
269 5819916817
270 6123226734
271 6452966084
272 6788237121
273 7152318868
274 7522824139
275 7924666564
276 8334003806
277 8777349316
278 9229469635
279 9718420942
280 10217664436
281 10756711900
282 11307841406
283 11901905448
284 12510148974
285 13164613145
286 13835703901
287 14556464645
288 15296691279
289 16090198396
290 16906452262
291 17779766722
292 18679601634
293 19640444909
294 20632132783
295 21688954696
296 22781556204
297 23943594216
298 25147024750
299 26424383598
300 27749496463
301 29153219947
302 30611884291
303 32154048088
304 33759247161
305 35453045443
306 37218968441
307 39078822855
308 41020980532
309 43062643680
310 45197977093
311 47438660478
312 49785676574
313 52244174761
314 54823074806
315 57519914857
316 60352753868
317 63310343899
318 66421181943
319 69663986574
320 73079075762
321 76633792588
322 80381755897
323 84277521372
324 88389571417
325 92658171072
326 97168321060
327 101844430175
328 106789750342
329 111911183688
330 117332049642
331 122940043845
332 128880436673
333 135019945396
334 141527744597
335 148247769579
336 155375103616
337 162729044088
338 170532635411
339 178578675044
340 187120250201
341 195921769844
342 205268465080
343 214894496140
344 225119336630
345 235645046711
346 246827424004
347 258334647667
348 270560878865
349 283138689560
350 296502578653
351 310247908635
352 324851399677
353 339869712271
354 355823548235
355 372229562988
356 389654048175
357 407572528812
358 426598302705
359 446164904587
360 466933830660
361 488296024711
362 510962098448
363 534280159720
364 559010545581
365 584458634958
366 611434730206
367 639202048623
368 668620692384
369 698912744405
370 730987464474
371 764027404710
372 798989825798
373 835019935219
374 873121238823
375 912404493047
376 953917058483
377 996738850350
378 1041957961779
379 1088627928939
380 1137873686645
381 1188727718124
382 1242347034613
383 1297749398750
384 1356118222623
385 1416463904399
386 1479989552496
387 1545706728181
388 1614830473765
389 1686383230619
390 1761583024747
391 1839474239470
392 1921267721564
393 2006042220687
394 2094989893556
395 2187237798962
396 2283946527617
397 2384306928753
398 2489433641638
399 2598598479961
400 2712854235250
401 2831572567253
402 2955726862625
403 3084809370131
404 3219694866022
405 3360018799998
406 3506536336398
407 3659050750206
408 3818174828340
409 3983906310094
410 4156690927665
411 4336749667207
412 4524334679388
413 4719921110002
414 4923539009504
415 5135950840756
416 5356934135022
417 5587574041596
418 5827363127463
419 6077746896348
420 6337898608913
421 6609664038815
422 6891860790466
423 7186777123071
424 7492836807416
425 7812815021277
426 8144701609400
427 8491805335699
428 8851640343333
429 9228097764576
430 9618172532157
431 10026389008661
432 10449177968235
433 10891749788654
434 11349924685017
435 11829653662387
436 12326098896811
437 12846008250259
438 13383837334964
439 13947188558445
440 14529761851943
441 15140073046527
442 15771016782677
443 16432082141191
444 17115308913918
445 17831219876708
446 18570950631396
447 19346118379628
448 20146906063799
449 20986085921001
450 21852840878705
451 22761158269898
452 23699175532029
453 24682154114300
454 25697142707600
455 26760734313616
456 27858848728998
457 29009465787332
458 30197339785167
459 31441889841305
460 32726672721678
461 34072595784618
462 35461991349923
463 36917299677574
464 38419608014091
465 39992929113637
466 41617091475722
467 43317713933485
468 45073360842880
469 46911283819189
470 48808786739666
471 50794772734723
472 52845299419852
473 54990931217853
474 57206505163534
475 59524246562789
476 61917810661818
477 64421071958899
478 67006556868790
479 69709764721075
480 72502162028260
481 75420834733583
482 78436275529576
483 81587103354961
484 84842942293839
485 88243873977230
486 91758779529363
487 95429114607530
488 99223165583234
489 103183653743067
490 107278442911303
491 111551390058606
492 115970134924164
493 120579517252407
494 125347178957125
495 130318764743308
496 135462175147032
497 140823655659586
498 146371653702297
499 152152783000115
500 158136360416551
501 164369105514256
502 170821563152326
503 177540264407645
504 184497379223215
505 191738922526952
506 199239126693340
507 207043127389517
508 215127699601016
509 223536699844058
510 232249970435602
511 241309650008943
512 250699220008295
513 260458622425434
514 270575598362469
515 281087372404692
516 291986617018105
517 303307275663486
518 315047676577361
519 327237873603477
520 339882630148823
521 353007456524081
522 366624387024635
523 380753687532765
524 395415557304592
525 410624269666865
526 426409142322963
527 442777659467334
528 459769271841100
529 477383829758191
530 495671993365345
531 514625085410235
532 534306114845666
533 554696935134953
534 575874106655377
535 597809023673267
536 620593064497387
537 644186127762613
538 668695739704742
539 694069220923197
540 720431639023006
541 747716610815137
542 776068201014852
543 805405154967231
544 835892051659725
545 867431559072737
546 900210347016834
547 934113764483052
548 969352206139774
549 1005792429607060
550 1043670242884540
551 1082832512797617
552 1123542200494081
553 1165624961998414
554 1209372698511172
555 1254588519799448
556 1301595096671364
557 1350171649847759
558 1400673486319118
559 1452854594428715
560 1507104814941176
561 1563151569941660
562 1621421155426058
563 1681613111414507
564 1744192126705122
565 1808828573645656
566 1876027478630064
567 1945428801606511
568 2017579848919542
569 2092088978712060
570 2169547706396409
571 2249531667226599
572 2332678489759147
573 2418530050583780
574 2507771957592376
575 2599911393741392
576 2695683760445969
577 2794560732659804
578 2897329252411382
579 3003424811098266
580 3113687554788289
581 3227516277348982
582 3345805891171540
583 3467918161383080
584 3594804208628972
585 3725788646783250
586 3861880106381681
587 4002366160516820
588 4148314088988898
589 4298974796890056
590 4455475167855184
591 4617030101622095
592 4784826830657675
593 4958045234660031
594 5137933405177467
595 5323637540853253
596 5516466840153866
597 5715535549713526
598 5922213932583154
599 6135586436967960
600 6357084027466722
601 6585763972054277
602 6823117222810039
603 7068176988277424
604 7322493109649665
605 7585078403146892
606 7857540083669623
607 8138874830044922
608 8430745262532770
609 8732136812580988
610 9044765049651894
611 9367609727777773
612 9702436383396151
613 10048225393748875
614 10406788717227152
615 10777114433596015
616 11161056775188257
617 11557619436123137
618 11968694133561233
619 12393308971273206
620 12833387679326740
621 13287992506488764
622 13759073002155527
623 14245736288856183
624 14749950777518181
625 15270880245522903
626 15810504204389585
627 16368055975019916
628 16945517562885707
629 17542205889157490
630 18160095962851274
631 18798603586742777
632 19459686357556716
633 20142875526912067
634 20850099901927163
635 21581024093016329
636 22337535739326018
637 23119452123965880
638 23928606305876970
639 24764989014801678
640 25630364247345103
641 26524918473763676
642 27450331048258709
643 28407008049645591
644 29396527480755909
645 30419540528408913
646 31477505984778891
647 32571347326352996
648 33702385101028830
649 34871843991931318
650 36080886081850031
651 37331067958606655
652 38623371816987880
653 39959718675703498
654 41340888214554327
655 42769200276429600
656 44245208191686041
657 45771666926776353
658 47348878432173595
659 48980071033307208
660 50665269085141441
661 52408214472307875
662 54208626581229139
663 56070803039357151
664 57994129762200677
665 59983504303001082
666 62037949521901981
667 64163009085007965
668 66357312179098482
669 68627096774736201
670 70970566804114407
671 73394704726364468
672 75897256747279999
673 78486001973209501
674 81158195618201735
675 83922467537235197
676 86775547994493093
677 89726973598075602
678 92772915139317128
679 95923873832354803
680 99175426040799935
681 102539097221414860
682 106009834086584645
683 109600247674867156
684 113304619725004909
685 117136709805867661
686 121090099464357605
687 125179761246452996
688 129398541604580841
689 133762691881354447
690 138264289095586327
691 142920930434205593
692 147723889964591957
693 152692178832219910
694 157816235754515452
695 163116554834308572
696 168582708469374548
697 174236743401976694
698 180067336522515701
699 186098157354983714
700 192316960243354490
701 198749107850920386
702 205381407498595804
703 212240985294207414
704 219313680050523312
705 226628451280629742
706 234170151275541301
707 241969642254007939
708 250010775940178041
709 258326385555898018
710 266899312733187668
711 275764428624292113
712 284903560334105103
713 294353682106048696
714 304095607801253457
715 314168477727457374
716 324552100152563931
717 335287841781411970
718 346354520016438984
719 357795785174502555
720 369589486329704690
721 381781610997113330
722 394349071065506150
723 407340240670206200
724 420731135083691672
725 434572559748996011
726 448839684204554095
727 463585784560159662
728 478785246727528060
729 494493850883605300
730 510685273627456368
731 527417825992863536
732 544664562793837601
733 562486345411011441
734 580855708693137611
735 599836075849468438
736 619399578979726562
737 639612205849687627
738 660445819600173460
739 681968965765814494
740 704153390095229017
741 727070178790357719
742 750691130827918956
743 775089844851602890
744 800238364041205799
745 826212759287660413
746 852985530679001345
747 880635168338428889
748 909134865095654542
749 938565463586903123
750 968901109816811162
751 1000224917627799264
752 1032512272723992645
753 1065848463347500292
754 1100210429081229535
755 1135685519357406048
756 1172252571051348788
757 1210000864245981238
758 1248911507405496352
759 1289075562485862639
760 1330476816379783769
761 1373207944975133128
762 1417255854700641865
763 1462714647376701366
764 1509574826074096902
765 1557931709584492307
766 1607779912514852735
767 1659215739845636740
768 1712238472190237727
769 1766945147256464434
770 1823340307550126771
771 1881521446568223006
772 1941499007840394845
773 2003370639453997320
774 2067153370211294948
775 2132944676625321582
776 2200768903988795230
777 2270723005432711658
778 2342839422810469409
779 2417214207842841918
780 2493888729717287301
781 2572957733963569024
782 2654472400449192506
783 2738525736570697752
784 2825179670617630593
785 2914525012405646467
786 3006635432611038870
787 3101599056322021037
788 3199502348553891662
789 3300430234715409294
790 3404483085851924506
791 3511742085009249364
792 3622322682363902529
793 3736301748370504188
794 3853811048485902281
795 3974922543200836538
796 4099785613988338542
797 4228466687399730687
798 4361134127729712800
799 4497848177804345034
800 4638797618976785264
801 4784035835717092895
802 4933773529386904930
803 5088056527881483481
804 5247119025370539173
805 5410998572833291122
806 5579954500926282630
807 5754015343049970305
808 5933467281764171664
809 6118329073955039289
810 6308915541961807804
811 6505234891380667545
812 6707632445189082695
813 6916105069800126564
814 7131030523026285787
815 7352393534245521259
816 7580606303766244098
817 7815640619615902182
818 8057945205648390040
819 8307478101748868549
820 8564726709419540697
821 8829634515508847061
822 9102729825750139227
823 9383940775883773097
824 9673838874071222985
825 9972336119062054664
826 10280049590116277132
827 10596874381279731635
828 10923475580587423318
829 11259730634317015593
830 11606355144179876639
831 11963208197430499159
832 12331058479441543877
833 12709746046717727568
834 13100095300866144099
835 13501926643915945053
836 13916122885980272684
837 14342484207981157326
838 14781954577224705145
839 15234313453908958805
840 15700568763923660027
841 16180478824749091289
842 16675118370808257257
843 17184224244004247791
844 17708940881197396847
845 18248983417256186961
846 18805568924259850352
847 19378390713236601913
848 19968741457577188562
849 20576292656391689096
850 21202415577711341976
851 21846760064516067973
852 22510778993451767658
853 23194100867058751589
854 23898263198084061298
855 24622873641400648743
856 25369557379185061211
857 26137901906646588857
858 26929623106319735953
859 27744289216359267324
860 28583709839390821384
861 29447435094144898088
862 30337371302486994188
863 31253051858094690145
864 32196482770685695469
865 33167182382829943352
866 34167259319611604690
867 35196218850226866466
868 36256275090419513770
869 37346922542929844863
870 38470483625493028043
871 39626444737348448830
872 40817239333303061087
873 42042348756184764451
874 43304320143799285694
875 44602633243412520026
876 45939951419174865581
877 47315756728329647915
878 48732831188114502077
879 50190663548501660339
880 51692156775448611558
881 53236811205498867164
882 54827652902783741431
883 56464199230880387457
884 58149601339874402963
885 59883399644388504732
886 61668872190565164444
887 63505589090261487668
888 65396956901749288440
889 67342582742549181014
890 69346003088315532123
891 71406870074698738971
892 73528851272136607476
893 75711652594168144105
894 77959073638189286005
895 80270883647692250202
896 82651014916491590281
897 85099310408882862319
898 87619835504142333168
899 90212518165249807504
900 92881556947911119334
901 95626977028407825443
902 98453109914050370990
903 101360091197236863636
904 104352384778788124936
905 107430250911126641257
906 110598284979873380725
907 113856887237098274353
908 117210783277023107062
909 120660529842714097895
910 124210981076792639057
911 127862867914080700389
912 131621170985630842006
913 135486814387196801939
914 139464902763393817674
915 143556573669102564427
916 147767052858669747324
917 152097713035147102967
918 156553897716707437479
919 161137237897790686564
920 165853191060747204289
921 170703671153224434912
922 175694245358013958520
923 180827136822182096588
924 186108017692662337242
925 191539448213289003148
926 197127200279552757581
927 202874200848483068561
928 208786315864894645771
929 214866870403230536174
930 221121818272626659675
931 227554915926659722194
932 234172198368806232396
933 240977888621264175105
934 247978095730483976448
935 255177546475567854091
936 262582416320315418861
937 270197975059144534506
938 278030456483876831306
939 286085714804606997163
940 294370033602942261542
941 302889895118802677081
942 311651623755359286768
943 320662375682309431148
944 329928506750121957606
945 339457895315731118651
946 349256918925452705246
947 359334228809956312168
948 369696214117509186964
949 380352352138909450448
950 391309033228565848056
951 402576616493982738451
952 414161482845353680615
953 426074931602862050746
954 438323323381701645540
955 450918958818317298262
956 463868167243696021713
957 477184314488428575300
958 490873687541482036256
959 504950784145004925518
960 519421837898374232188
961 534302548075462689767
962 549599083936546840707
963 565328418871395425607
964 581496647047835837302
965 598122091578450561861
966 615210761089758515940
967 632782407103043397501
968 650842942679114186884
969 669413629565983099649
970 688500275790367960700
971 708125738327256794163
972 728295711401581174081
973 749034735444233419692
974 770348382969083755127
975 792262969363310218280
976 814783938551281463768
977 837939475686861252228
978 861734890444377022390
979 886200335899059255818
980 911340983235988817323
981 937189054980181163832
982 963749581229382475724
983 991056958885075476625
984 1019116076238649648863
985 1047963612912124118114
986 1077604316806680956498
987 1108077262039897917966
988 1139387059950255765783
989 1171575294364437324027
990 1204646446593342562173
991 1238644728826234982546
992 1273574501907528542834
993 1309482728477312637841
994 1346373661841044917062
995 1384297140600744888132
996 1423257327181568990845
997 1463307065062429615994
998 1504450446566884232231
999 1546743452343266497567
1000 1590190129927671651048