0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 42
11 55
12 75
13 96
14 127
15 161
16 208
17 260
18 330
19 407
20 509
21 621
22 765
23 925
24 1127
25 1350
26 1627
27 1934
28 2310
29 2725
30 3227
31 3782
32 4446
33 5178
34 6044
35 7000
36 8122
37 9355
38 10791
39 12370
40 14195
41 16196
42 18494
43 21012
44 23887
45 27029
46 30596
47 34492
48 38894
49 43689
50 49082
51 54952
52 61525
53 68664
54 76627
55 85266
56 94868
57 105264
58 116778
59 129232
60 142982
61 157826
62 174166
63 191788
64 211131
65 231956
66 254755
67 279274
68 306051
69 334804
70 366130
71 399733
72 436263
73 475390
74 517836
75 563255
76 612427
77 664974
78 721756
79 782374
80 847761
81 917479
82 992551
83 1072522
84 1158494
85 1249970
86 1348157
87 1452536
88 1564405
89 1683201
90 1810340
91 1945235
92 2089406
93 2242220
94 2405326
95 2578068
96 2762214
97 2957053
98 3164504
99 3383831
100 3617081
101 3863468
102 4125203
103 4401470
104 4694632
105 5003814
106 5331561
107 5676973
108 6042759
109 6427958
110 6835484
111 7264346
112 7717642
113 8194318
114 8697698
115 9226697
116 9784844
117 10370990
118 10988909
119 11637423
120 12320535
121 13036993
122 13791077
123 14581506
124 15412805
125 16283627
126 17198796
127 18156930
128 19163134
129 20215950
130 21320810
131 22476230
132 23687942
133 24954387
134 26281657
135 27668162
136 29120326
137 30636482
138 32223447
139 33879524
140 35611893
141 37418782
142 39307792
143 41277126
144 43334784
145 45478884
146 47717893
147 50049906
148 52483815
149 55017642
150 57660779
151 60411221
152 63278835
153 66261534
154 69369726
155 72601310
156 75967199
157 79465214
158 83106856
159 86889929
160 90826485
161 94914251
162 99165913
163 103579186
164 108167351
165 112928052
166 117875246
167 123006573
168 128336637
169 133862998
170 139600998
171 145548200
172 151720631
173 158115793
174 164750498
175 171622250
176 178748614
177 186127025
178 193775891
179 201692668
180 209896561
181 218384967
182 227177997
183 236273070
184 245691157
185 255429623
186 265510409
187 275930912
188 286713994
189 297857010
190 309383850
191 321291915
192 333606086
193 346323717
194 359470799
195 373044745
196 387072592
197 401551732
198 416510377
199 431945982
200 447887894
201 464333544
202 481313531
203 498825377
204 516900877
205 535537546
206 554768515
207 574591396
208 595040601
209 616113746
210 637846664
211 660237086
212 683322206
213 707099780
214 731608501
215 756846262
216 782853210
217 809627263
218 837210173
219 865600016
220 894840073
221 924928482
222 955910215
223 987783580
224 1020595192
225 1054343424
226 1089076683
227 1124793550
228 1161544158
229 1199327180
230 1238194649
231 1278145461
232 1319233484
233 1361457726
234 1404874065
235 1449481760
236 1495338629
237 1542444074
238 1590858026
239 1640580170
240 1691672496
241 1744134841
242 1798031441
243 1853362449
244 1910194259
245 1968527226
246 2028430102
247 2089903579
248 2153018711
249 2217776404
250 2284250199
251 2352441391
252 2422425931
253 2494205368
254 2567858276
255 2643386619
256 2720871520
257 2800315228
258 2881801629
259 2965333428
260 3050997193
261 3138795959
262 3228819188
263 3321070417
264 3415641940
265 3512537644
266 3611852883
267 3713592092
268 3817853585
269 3924642213
270 4034059492
271 4146110856
272 4260900958
273 4378435673
274 4498823017
275 4622069516
276 4748286462
277 4877480877
278 5009767586
279 5145154302
280 5283759299
281 5425590832
282 5570770881
283 5719308450
284 5871329134
285 6026842541
286 6185978137
287 6348746341
288 6515280420
289 6685591431
290 6859816715
291 7037968204
292 7220187201
293 7406486362
294 7597011241
295 7791775420
296 7990928631
297 8194485220
298 8402599369
299 8615286438
300 8832704961
301 9054871137
302 9281948157
303 9513953292
304 9751054297
305 9993269346
306 10240771064
307 10493578774
308 10751869870
309 11015664660
310 11285145611
311 11560334263
312 11841418078
313 12128419634
314 12421531711
315 12720778204
316 13026357088
317 13338293404
318 13656790663
319 13981875294
320 14313756263
321 14652461205
322 14998204863
323 15351016372
324 15711116144
325 16078534618
326 16453498234
327 16836039010
328 17226389312
329 17624582548
330 18030857369
331 18445248863
332 18868001855
333 19299152930
334 19738953445
335 20187441772
336 20644875715
337 21111295217
338 21586964907
339 22071926625
340 22566451691
341 23070583652
342 23584600916
343 24108549023
344 24642713381
345 25187141320
346 25742125626
347 26307715761
348 26884211772
349 27471665036
350 28070383278
351 28680420112
352 29302090830
353 29935451074
354 30580824121
355 31238267979
356 31908113790
357 32590421725
358 33285531208
359 33993504911
360 34714690448
361 35449152755
362 36197248074
363 36959043982
364 37734905205
365 38524901751
366 39329407289
367 40148494592
368 40982546178
369 41831637362
370 42696159949
371 43576192191
372 44472135054
373 45384069489
374 46312406104
375 47257228922
376 48218958075
377 49197680428
378 50193826119
379 51207485246
380 52239097824
381 53288756962
382 54356913033
383 55443662548
384 56549466140
385 57674423463
386 58819005914
387 59983316722
388 61167837895
389 62372676008
390 63598324206
391 64844892797
392 66112885963
393 67402417502
394 68714003137
395 70047760608
396 71404217046
397 72783493874
398 74186130181
399 75612251502
400 77062408759
401 78536731349
402 80035782578
403 81559696154
404 83109047631
405 84683974786
406 86285065972
407 87912463483
408 89566768368
409 91248127158
410 92957154173
411 94694000674
412 96459294090
413 98253190164
414 100076330033
415 101928874366
416 103811477904
417 105724305979
418 107668027512
419 109642813012
420 111649345440
421 113687800203
422 115758874926
423 117862750404
424 120000138796
425 122171226015
426 124376739380
427 126616870433
428 128892361511
429 131203409524
430 133550772453
431 135934653087
432 138355824944
433 140814496391
434 143311457135
435 145846921679
436 148421695750
437 151035999720
438 153690656014
439 156385891380
440 159122544833
441 161900849215
442 164721660784
443 167585219057
444 170492397390
445 173443441676
446 176439243074
447 179480054408
448 182566784506
449 185699692834
450 188879706595
451 192107092476
452 195382795908
453 198707090520
454 202080940678
455 205504627531
456 208979134271
457 212504749245
458 216082475206
459 219712608328
460 223396170750
461 227133466188
462 230925536929
463 234772694806
464 238676002144
465 242635778592
466 246653107250
467 250728316236
468 254862509276
469 259056022639
470 263309981468
471 267624730809
472 272001417085
473 276440393812
474 280942829486
475 285509086744
476 290140356005
477 294837008730
478 299600258055
479 304430484916
480 309328925056
481 314295968545
482 319332874556
483 324440042998
484 329618756295
485 334869423892
486 340193352317
487 345590961199
488 351063581060
489 356611641394
490 362236497543
491 367938589597
492 373719297566
493 379579071800
494 385519317861
495 391540497061
496 397644040376
497 403830419755
498 410101092474
499 416456541848
500 422898251301
501 429426715201
502 436043444007
503 442748943869
504 449544752172
505 456431386488
506 463410412046
507 470482358626
508 477648819120
509 484910335197
510 492268528361
511 499723952897
512 507278258812
513 514932012671
514 522686893906
515 530543482176
516 538503486186
517 546567498335
518 554737257584
519 563013369856
520 571397604230
521 579890579812
522 588494096784
523 597208788248
524 606036485337
525 614977834820
526 624034699768
527 633207741429
528 642498854706
529 651908714949
530 661439249912
531 671091149920
532 680866375396
533 690765631306
534 700790911794
535 710942937278
536 721223735518
537 731634042032
538 742175919220
539 752850118603
540 763658737070
541 774602541775
542 785683665184
543 796902890956
544 808262386999
545 819762953120
546 831406793760
547 843194725776
548 855128989992
549 867210419972
550 879441294016
551 891822463297
552 904356243489
553 917043502981
554 929886595948
555 942886408960
556 956045334513
557 969364277010
558 982845668430
559 996490431910
560 1010301038812
561 1024278430641
562 1038425119274
563 1052742065582
564 1067231821810
565 1081895367810
566 1096735297395
567 1111752610363
568 1126949941965
569 1142328311574
570 1157890397082
571 1173637238435
572 1189571556020
573 1205694410000
574 1222008564463
575 1238515100786
576 1255216826663
577 1272114844277
578 1289212006170
579 1306509436395
580 1324010032165
581 1341714939043
582 1359627100191
583 1377747683679
584 1396079678526
585 1414624274930
586 1433384509015
587 1452361594205
588 1471558613588
589 1490976803416
590 1510619295059
591 1530487348662
592 1550584143754
593 1570910963990
594 1591471038380
595 1612265675188
596 1633298152766
597 1654569803619
598 1676083956767
599 1697841970055
600 1719847223085
601 1742101098621
602 1764607028210
603 1787366420704
604 1810382759424
605 1833657478939
606 1857194115746
607 1880994131230
608 1905061114982
609 1929396554813
610 1954004094778
611 1978885250319
612 2004043719822
613 2029481045951
614 2055200982867
615 2081205101626
616 2107497212051
617 2134078913196
618 2160954071994
619 2188124316704
620 2215593571239
621 2243363492686
622 2271438063390
623 2299818970473
624 2328510254638
625 2357513632609
626 2386833204939
627 2416470719234
628 2446430335735
629 2476713832550
630 2507325431140
631 2538266941323
632 2569542645710
633 2601154385430
634 2633106505744
635 2665400880410
636 2698041917217
637 2731031522133
638 2764374167052
639 2798071791434
640 2832128931177
641 2866547558831
642 2901332275879
643 2936485089282
644 2972010665990
645 3007911046990
646 3044190966285
647 3080852500209
648 3117900449759
649 3155336926174
650 3193166799072
651 3231392215995
652 3270018115031
653 3309046679638
654 3348482918044
655 3388329050946
656 3428590156658
657 3469268492709
658 3510369209136
659 3551894601738
660 3593849892166
661 3636237414063
662 3679062462411
663 3722327410098
664 3766037625351
665 3810195519894
666 3854806536921
667 3899873128433
668 3945400812488
669 3991392080974
670 4037852528540
671 4084784688403
672 4132194231761
673 4180083732711
674 4228458940770
675 4277322472437
676 4326680155412
677 4376534648204
678 4426891858511
679 4477754488297
680 4529128525222
681 4581016714293
682 4633425124913
683 4686356546697
684 4739817130699
685 4793809710710
686 4848340521300
687 4903412441962
688 4959031790714
689 5015201492338
690 5071927950170
691 5129214135850
692 5187066537946
693 5245488174563
694 5304485621377
695 5364061944527
696 5424223806776
697 5484974321843
698 5546320241499
699 5608264728696
700 5670814624094
701 5733973139484
702 5797747206382
703 5862140086992
704 5927158803672
705 5992806668624
706 6059090796981
707 6126014552641
708 6193585143440
709 6261805984537
710 6330684378491
711 6400223793381
712 6470431626442
713 6541311398258
714 6612870602766
715 6685112814758
716 6758045624808
717 6831672661522
718 6906001614144
719 6981036166798
720 7056784107400
721 7133249175136
722 7210439258673
723 7288358154050
724 7367013850587
725 7446410200782
726 7526555296736
727 7607453049115
728 7689111652812
729 7771535076246
730 7854731619194
731 7938705309667
732 8023464552277
733 8109013434192
734 8195360467042
735 8282509798950
736 8370470048542
737 8459245424481
738 8548844654579
739 8639272009884
740 8730536327353
741 8822641940027
742 8915597796205
743 9009408292767
744 9104082489383
745 9199624846316
746 9296044536853
747 9393346086576
748 9491538782315
749 9590627214580
750 9690620786040
751 9791524153985
752 9893346836962
753 9996093558629
754 10099773955671
755 10204392820100
756 10309959906717
757 10416480075455
758 10523963201585
759 10632414214906
760 10741843111165
761 10852254889616
762 10963659668843
763 11076062519549
764 11189473683142
765 11303898301386
766 11419346740883
767 11535824216453
768 11653341219952
769 11771903038803
770 11891520292536
771 12012198343266
772 12133947938150
773 12256774513610
774 12380688946903
775 12505696750760
776 12631808932609
777 12759031081083
778 12887374336217
779 13016844364687
780 13147452439143
781 13279204303877
782 13412111366687
783 13546179451580
784 13681420101540
785 13817839219884
786 13955448487323
787 14094253888634
788 14234267242274
789 14375494614100
790 14517947962865
791 14661633437658
792 14806563137622
793 14952743294631
794 15100186150821
795 15248898023100
796 15398891296582
797 15550172372832
798 15702753782600
799 15856642014268
800 16011849744328
801 16168383547581
802 16326256248881
803 16485474511752
804 16646051309452
805 16807993393809
806 16971313889206
807 17136019638035
808 17302123915878
809 17469633655296
810 17638562285799
811 17808916832431
812 17980710878684
813 18153951541716
814 18328652561740
815 18504821150344
816 18682471204595
817 18861610030073
818 19042251683493
819 19224403566844
820 19408079896509
821 19593288170521
822 19780042767782
823 19968351284695
824 20158228262827
825 20349681396564
826 20542725392951
827 20737368046831
828 20933624230807
829 21131501839772
830 21331015914804
831 21532174453276
832 21734992664854
833 21939478649009
834 22145647786921
835 22353508282644
836 22563075688966
837 22774358314169
838 22987371885586
839 23202124818215
840 23418633014109
841 23636904994557
842 23856956839325
843 24078797178586
844 24302442269879
845 24527900851911
846 24755189363047
847 24984316653027
848 25215299341232
849 25448146388063
850 25682874596931
851 25919493041551
852 26158018709486
853 26398460787373
854 26640836450049
855 26885154999680
856 27131433798534
857 27379682263940
858 27629917948729
859 27882150388058
860 28136397325458
861 28392668413577
862 28650981589789
863 28911346626901
864 29173781656352
865 29438296570699
866 29704909698648
867 29973631055282
868 30244479166678
869 30517464170114
870 30792604792301
871 31069911295393
872 31349402606973
873 31631089113718
874 31914989947307
875 32201115621779
876 32489485473078
877 32780110142231
878 33073009172783
879 33368193335542
880 33665682381859
881 33965487211977
882 34267627788399
883 34572115143656
884 34878969451588
885 35188201876698
886 35499832807522
887 35813873543391
888 36130344687810
889 36449257674549
890 36770633325501
891 37094483211843
892 37420828374008
893 37749680520272
894 38081060913091
895 38414981400710
896 38751463467899
897 39090519102541
898 39432170015163
899 39776428336320
900 40123316002516
901 40472845286627
902 40825038354692
903 41179907624895
904 41537475493068
905 41897754522380
906 42260767342026
907 42626526663209
908 42995055348725
909 43366366257520
910 43740482489574
911 44117417054629
912 44497193290177
913 44879824356391
914 45265333831921
915 45653735030539
916 46045051772258
917 46439297524167
918 46836496351354
919 47236661877293
920 47639818412495
921 48045979736515
922 48455170408958
923 48867404368697
924 49282706424707
925 49701090674854
926 50122582181273
927 50547195204012
928 50974955058682
929 51405876167218
930 51839984102509
931 52277293451631
932 52717830045046
933 53161608634709
934 53608655312472
935 54058984998427
936 54512624046205
937 54969587543697
938 55429902110195
939 55893583004766
940 56360657112625
941 56831139863764
942 57305058413271
943 57782428365338
944 58263277145336
945 58747620531383
946 59235486223042
947 59726890175805
948 60221860363764
949 60720412919491
950 61222576095638
951 61728366205257
952 62237811779938
953 62750929312950
954 63267747618865
955 63788283374636
956 64312565678175
957 64840611389890
958 65372449895093
959 65908098241119
960 66447586101134
961 66990930709094
962 67538162030146
963 68089297488462
964 68644367341495
965 69203389203416
966 69766393628182
967 70333398423453
968 70904434440167
969 71479519679234
970 72058685292729
971 72641949478481
972 73229343690104
973 73820886322087
974 74416609133865
975 75016530720206
976 75620683146812
977 76229085208503
978 76841769281544
979 77458754364496
980 78080073144612
981 78705744824003
982 79335802405222
983 79970265297625
984 80609166819590
985 81252526587448
986 81900378239784
987 82552741603725
988 83209650638456
989 83871125381722
990 84537200117763
991 85207895098657
992 85883244934248
993 86563270090747
994 87248005508015
995 87937471870294
996 88631704447935
997 89330724142991
998 90034566560846
999 90743252825212
1000 91456818877024