0 1
1 1
2 2
3 2
4 3
5 4
6 5
7 7
8 8
9 10
10 13
11 16
12 20
13 24
14 30
15 36
16 43
17 52
18 61
19 73
20 86
21 102
22 120
23 140
24 165
25 192
26 224
27 260
28 301
29 348
30 401
31 462
32 530
33 608
34 696
35 796
36 909
37 1035
38 1178
39 1338
40 1518
41 1720
42 1945
43 2198
44 2480
45 2796
46 3148
47 3540
48 3978
49 4464
50 5006
51 5606
52 6273
53 7012
54 7830
55 8738
56 9740
57 10850
58 12075
59 13428
60 14922
61 16567
62 18382
63 20378
64 22575
65 24992
66 27646
67 30564
68 33764
69 37278
70 41131
71 45352
72 49979
73 55040
74 60582
75 66640
76 73263
77 80500
78 88399
79 97026
80 106434
81 116696
82 127882
83 140068
84 153343
85 167790
86 183514
87 200614
88 219205
89 239412
90 261360
91 285199
92 311072
93 339150
94 369606
95 402628
96 438425
97 477206
98 519216
99 564698
100 613928
101 667196
102 724809
103 787110
104 854448
105 927218
106 1005825
107 1090712
108 1182357
109 1281258
110 1387970
111 1503062
112 1627164
113 1760940
114 1905098
115 2060412
116 2227682
117 2407794
118 2601670
119 2810308
120 3034779
121 3276204
122 3535814
123 3814888
124 4114821
125 4437088
126 4783256
127 5155023
128 5554162
129 5982606
130 6442383
131 6935668
132 7464788
133 8032194
134 8640540
135 9292610
136 9991399
137 10740088
138 11542049
139 12400908
140 13320478
141 14304858
142 15358381
143 16485664
144 17691635
145 18981494
146 20360820
147 21835496
148 23411808
149 25096428
150 26896428
151 28819358
152 30873188
153 33066432
154 35408097
155 37907752
156 40575572
157 43422318
158 46459460
159 49699118
160 53154186
161 56838328
162 60766018
163 64952650
164 69414486
165 74168824
166 79233951
167 84629268
168 90375348
169 96493939
170 103008148
171 109942378
172 117322528
173 125176000
174 133531793
175 142420656
176 151875058
177 161929446
178 172620208
179 183985872
180 196067214
181 208907306
182 222551792
183 237048848
184 252449490
185 268807624
186 286180212
187 304627536
188 324213206
189 345004546
190 367072611
191 390492500
192 415343575
193 441709578
194 469679066
195 499345440
196 530807403
197 564169132
198 599540569
199 637037850
200 676783422
201 718906620
202 763543830
203 810838972
204 860943910
205 914018740
206 970232438
207 1029763084
208 1092798547
209 1159536888
210 1230186869
211 1304968656
212 1384114184
213 1467868024
214 1556487819
215 1650245080
216 1749425913
217 1854331627
218 1965279760
219 2082604636
220 2206658463
221 2337812104
222 2476456039
223 2623001502
224 2777881284
225 2941551126
226 3114490613
227 3297204544
228 3490224193
229 3694108500
230 3909445730
231 4136854616
232 4376986189
233 4630525212
234 4898191877
235 5180743736
236 5478977250
237 5793730100
238 6125882889
239 6476361480
240 6846139214
241 7236239058
242 7647736412
243 8081761258
244 8539501228
245 9022204188
246 9531181201
247 10067809836
248 10633537010
249 11229882838
250 11858443768
251 12520896528
252 13219002020
253 13954609136
254 14729659452
255 15546191176
256 16406344242
257 17312364956
258 18266611073
259 19271557428
260 20329801040
261 21444067498
262 22617216622
263 23852249104
264 25152313235
265 26520711582
266 27960908816
267 29476538796
268 31071413052
269 32749528888
270 34515078092
271 36372456399
272 38326272524
273 40381358750
274 42542780859
275 44815849328
276 47206130752
277 49719459450
278 52361950464
279 55140011950
280 58060359316
281 61130029120
282 64356393910
283 67747178064
284 71310473406
285 75054756800
286 78988907218
287 83122224560
288 87464448915
289 92025780336
290 96816900490
291 101848993844
292 107133771267
293 112683493528
294 118510996309
295 124629716634
296 131053719396
297 137797726592
298 144877146217
299 152308103664
300 160107473970
301 168292915104
302 176882903886
303 185896771770
304 195354743934
305 205277978724
306 215688609331
307 226609787738
308 238065729200
309 250081760536
310 262684368570
311 275901252084
312 289761375485
313 304295024210
314 319533864018
315 335511000734
316 352261044625
317 369820176020
318 388226214233
319 407518690044
320 427738919630
321 448930083834
322 471137308614
323 494407750456
324 518790684889
325 544337598032
326 571102283732
327 599140942492
328 628512286821
329 659277649392
330 691501096232
331 725249545425
332 760592888936
333 797604121964
334 836359475292
335 876938554868
336 919424486633
337 963904066608
338 1010467919146
339 1059210659134
340 1110231063508
341 1163632247964
342 1219521851672
343 1278012230330
344 1339220655180
345 1403269522982
346 1470286571805
347 1540405107800
348 1613764240454
349 1690509126762
350 1770791227490
351 1854768570952
352 1942606030625
353 2034475611756
354 2130556750560
355 2231036626362
356 2336110484114
357 2445981973278
358 2560863497073
359 2680976578428
360 2806552239705
361 2937831396916
362 3075065272424
363 3218515820656
364 3368456174661
365 3525171107824
366 3688957515239
367 3860124915338
368 4038995968838
369 4225907022372
370 4421208669867
371 4625266339312
372 4838460901848
373 5061189304044
374 5293865228358
375 5536919775682
376 5790802179219
377 6055980543612
378 6332942614427
379 6622196579370
380 6924271897878
381 7239720167954
382 7569116022777
383 7913058065860
384 8272169841944
385 8647100844680
386 9038527567442
387 9447154590656
388 9873715716423
389 10318975144200
390 10783728693610
391 11268805076466
392 11775067214798
393 12303413615212
394 12854779791862
395 13430139748348
396 14030507515984
397 14656938750361
398 15310532393626
399 15992432395976
400 16703829508989
401 17445963144476
402 18220123306511
403 19027652599494
404 19869948309576
405 20748464571764
406 21664714614772
407 22620273096328
408 23616778526529
409 24655935782592
410 25739518724232
411 26869372903134
412 28047418382137
413 29275652657444
414 30556153694129
415 31891083078874
416 33282689288126
417 34733311087068
418 36245381051049
419 37821429225700
420 39464086923856
421 41176090664616
422 42960286266496
423 44819633088256
424 46757208437091
425 48776212137748
426 50879971275897
427 53071945122078
428 55355730235344
429 57735065766348
430 60213838951758
431 62796090820492
432 65486022111687
433 68287999411964
434 71206561528218
435 74246426090232
436 77412496408017
437 80709868578784
438 84143838860797
439 87719911324056
440 91443805778996
441 95321466008424
442 99359068296233
443 103563030278592
444 107940020120786
445 112496966030982
446 117241066132466
447 122179798691326
448 127320932730586
449 132672539028996
450 138243001527092
451 144041029155686
452 150075668092006
453 156356314475548
454 162892727580825
455 169695043479936
456 176773789203001
457 184139897413854
458 191804721629594
459 199780051985738
460 208078131586741
461 216711673444976
462 225693878039347
463 235038451515528
464 244759624540002
465 254872171849518
466 265391432498970
467 276333330851404
468 287714398325090
469 299551795924615
470 311863337594684
471 324667514405966
472 337983519625416
473 351831274681640
474 366231456068940
475 381205523222606
476 396775747387638
477 412965241536940
478 429797991350643
479 447298887315816
480 465493757972536
481 484409404346724
482 504073635624036
483 524515306085028
484 545764353372582
485 567851838114068
486 590809984959433
487 614672225084154
488 639473240193866
489 665249008107464
490 692036849944383
491 719875478996972
492 748805051331517
493 778867218177446
494 810105180181724
495 842563743566254
496 876289378284649
497 911330278220548
498 947736423512891
499 985559645081928
500 1024853691414926
501 1065674297717504
502 1108079257479166
503 1152128496563752
504 1197884149895408
505 1245410640827984
506 1294774763307284
507 1346045766891562
508 1399295444762115
509 1454598224796384
510 1512031263824593
511 1571674545179124
512 1633610979630234
513 1697926509854494
514 1764710218519848
515 1834054440141132
516 1906054876816178
517 1980810717973320
518 2058424764285136
519 2139003555856538
520 2222657504869587
521 2309501032802524
522 2399652712396415
523 2493235414529712
524 2590376460146064
525 2691207777440144
526 2795866064437959
527 2904492957188328
528 3017235203733079
529 3134244844050084
530 3255679396190266
531 3381702048779180
532 3512481860139475
533 3648193964217472
534 3789019783563871
535 3935147249603460
536 4086771030415052
537 4244092766311336
538 4407321313432110
539 4576672995658572
540 4752371865101173
541 4934649971446678
542 5123747640482280
543 5319913762059160
544 5523406087858032
545 5734491539237788
546 5953446525526763
547 6180557273101825
548 6416120165586100
549 6660442095577886
550 6913840828238452
551 7176645377176168
552 7449196393005293
553 7731846564996510
554 8024961036277896
555 8328917832983414
556 8644108307863388
557 8970937598782968
558 9309825102624993
559 9661204965102918
560 10025526586975202
561 10403255147249308
562 10794872143871847
563 11200875952527436
564 11621782404108586
565 12058125381464808
566 12510457436091166
567 12979350425352150
568 13465396170971485
569 13969207139426324
570 14491417144988309
571 15032682076148730
572 15593680646153708
573 16175115168488150
574 16777712358052068
575 17402224158917884
576 18049428599497000
577 18720130676001110
578 19415163265147460
579 20135388066993030
580 20881696578938910
581 21655011101850324
582 22456285779362010
583 23286507671437960
584 24146697863251944
585 25037912610587266
586 25961244522856446
587 26917823785012684
588 27908819419563722
589 28935440589974292
590 29998937946820972
591 31100605018002208
592 32241779644490673
593 33423845463015916
594 34648233437216873
595 35916423438811252
596 37229945880337640
597 38590383401185360
598 39999372608526843
599 41458605874973508
600 42969833194716830
601 44534864100014712
602 46155569639983236
603 47833884423596120
604 49571808729017607
605 51371410681293912
606 53234828500614676
607 55164272823378222
608 57162029098317954
609 59230460060143658
610 61372008283052473
611 63589198816713512
612 65884641907280283
613 68261035806111262
614 70721169669011160
615 73267926548757126
616 75904286483944362
617 78633329687093032
618 81458239835184740
619 84382307465845824
620 87408933482439520
621 90541632771572552
622 93784037936433652
623 97139903149681452
624 100613108129570731
625 104207662243168716
626 107927708740688486
627 111777529124938304
628 115761547660213144
629 119884336024881636
630 124150618112200733
631 128565274983975985
632 133133349981765936
633 137860054000630054
634 142750770930356598
635 147811063269472012
636 153046677917337194
637 158463552149853038
638 164067819784526834
639 169865817540660524
640 175864091600821810
641 182069404379719260
642 188488741506953997
643 195129319030255806
644 201998590845947276
645 209104256363756506
646 216454268413075728
647 224056841398217108
648 231920459710267122
649 240053886403435494
650 248466172144098420
651 257166664440799664
652 266165017163973966
653 275471200364164808
654 285095510397961624
655 295048580371087076
656 305341390908278914
657 315985281260093152
658 326991960756790315
659 338373520620042444
660 350142446143317812
661 362311629252200466
662 374894381456311400
663 387904447204640444
664 401356017656735250
665 415263744882276400
666 429642756502154415
667 444508670784476014
668 459877612209246440
669 475766227516103652
670 492191702249604225
671 509171777817296884
672 526724769076046920
673 544869582462614856
674 563625734685053766
675 583013371991745984
676 603053290035719103
677 623766954352080868
678 645176521467175808
679 667304860658532072
680 690175576385137358
681 713813031408407090
682 738242370624470781
683 763489545629348404
684 789581340038977661
685 816545395586786550
686 844410239022272008
687 873205309834475032
688 902960988825298773
689 933708627557995032
690 965480578707145939
691 998310227337149174
692 1032232023136903334
693 1067281513639474320
694 1103495378455995148
695 1140911464554279032
696 1179568822613245562
697 1219507744485265608
698 1260769801799575196
699 1303397885740591160
700 1347436248036338373
701 1392930543192833860
702 1439927872011605144
703 1488476826428498060
704 1538627535712930548
705 1590431714068186066
706 1643942709674110590
707 1699215555215192196
708 1756307019937944811
709 1815275663282905530
710 1876181890137982074
711 1939088007760928762
712 2004058284420545804
713 2071159009807195048
714 2140458557265013535
715 2212027447899600018
716 2285938416616384918
717 2362266480146820200
718 2441089007120716488
719 2522485790245201608
720 2606539120652174304
721 2693333864478038475
722 2782957541741466524
723 2875500407586480716
724 2971055535960563736
725 3069718905799022084
726 3171589489789236349
727 3276769345790411940
728 3385363710986478810
729 3497481098852389384
730 3613233399015849740
731 3732735980099388176
732 3856107795629714430
733 3983471493103950096
734 4114953526305018558
735 4250684270960725090
736 4390798143844301146
737 4535433725416433444
738 4684733886112051597
739 4838845916377950858
740 4997921660570193252
741 5162117654823752450
742 5331595269009498444
743 5506520852897464504
744 5687065886648304144
745 5873407135758458402
746 6065726810588285560
747 6264212730605634754
748 6469058493481702867
749 6680463649179295860
750 6898633879178024140
751 7123781180984900640
752 7356124058082840082
753 7595887715474332480
754 7843304260981384605
755 8098612912468003552
756 8362060211155734406
757 8633900241207741800
758 8914394855762055922
759 9203813909599216734
760 9502435498635427638
761 9810546206437053936
762 10128441357958298659
763 10456425280709391738
764 10794811573568273508
765 11143923383455242768
766 11504093690095514053
767 11875665599101639468
768 12258992643613745812
769 12654439094742399750
770 13062380281065967826
771 13483202917440865286
772 13917305443391050493
773 14365098371349839244
774 14827004645035295082
775 15303460008248110676
776 15794913384388766574
777 16301827266999596904
778 16824678121645151160
779 17363956799453759892
780 17920168962651637534
781 18493835522430301428
782 19085493089497786968
783 19695694437673304118
784 20325008980895797326
785 20974023264026349056
786 21643341467835530662
787 22333585928577441768
788 23045397672563102988
789 23779436966157938506
790 24536383881639002488
791 25316938879360540804
792 26121823406688266993
793 26951780514175706938
794 27807575489469305834
795 28689996509441789254
796 29599855311067979490
797 30537987881570563108
798 31505255168378534746
799 32502543809455777980
800 33530766884572359736
801 34590864688107591368
802 35683805523989188453
803 36810586523390451900
804 37972234485823813135
805 39169806744286892100
806 40404392055135528066
807 41677111513376047098
808 42989119494089033682
809 44341604620715430588
810 45735790760956566170
811 47172938051060058024
812 48654343949284410534
813 50181344319357601002
814 51755314544766229317
815 53377670674735737028
816 55049870602784972476
817 56773415278762794517
818 58549849955299500962
819 60380765469630541576
820 62267799561777193795
821 64212638230094645100
822 66217017125226275656
823 68282722983530947968
824 70411595101078858146
825 72605526849342155804
826 74866467233736037738
827 77196422496198595924
828 79597457763029147653
829 82071698739238220352
830 84621333450696704762
831 87248614035405756804
832 89955858585246073410
833 92745453039600785956
834 95619853132284887041
835 98581586393252579526
836 101633254206593430428
837 104777533926370004912
838 108017181051890372038
839 111355031464053215424
840 114794003724446575125
841 118337101438926981918
842 121987415687452692032
843 125748127521991598800
844 129622510534374812829
845 133613933496015965156
846 137725863071468990656
847 141961866607849882244
848 146325615002202025436
849 150820885648941666164
850 155451565469576078508
851 160221654026947314900
852 165135266726313865670
853 170196638105644986962
854 175410125217566549688
855 180780211105461565920
856 186311508376297101986
857 192008762872816677276
858 197876857447808982391
859 203920815843235888272
860 210145806677076717766
861 216557147540823250356
862 223160309210636775204
863 229960919975260471236
864 236964770083861812813
865 244177816317064794314
866 251606186684519127854
867 259256185252441578822
868 267134297104657728387
869 275247193440764761804
870 283601736815133416099
871 292204986520565687516
872 301064204120525896500
873 310186859133968044758
874 319580634876887544927
875 329253434464836684280
876 339213386980754418449
877 349468853812576914264
878 360028435165214130062
879 370900976751597907256
880 382095576667633423641
881 393621592456011966692
882 405488648363975455334
883 417706642800257264154
884 430285755996561486852
885 443236457879085778334
886 456569516155736412693
887 470296004624835137344
888 484427311711269007105
889 498975149236191794778
890 513951561426547070348
891 529368934170846777646
892 545240004527810475918
893 561577870494642258736
894 578396001041902067426
895 595708246422110467656
896 613528848759413012816
897 631872452927824223552
898 650754117725766574703
899 670189327354824400428
900 690194003210838812653
901 710784515995683315260
902 731977698158278880036
903 753790856673629832440
904 776241786168893926029
905 799348782405733638336
906 823130656128439158870
907 847606747287561029980
908 872796939649044226742
909 898721675799118053298
910 925401972555461629690
911 952859436795441497512
912 981116281712497745877
913 1010195343512044388598
914 1040120098558546485930
915 1070914680985738473270
916 1102603900782261972903
917 1135213262365318415432
918 1168768983655261095874
919 1203298015664386604103
920 1238828062613529393892
921 1275387602590418352290
922 1313005908764114056233
923 1351713071170219396228
924 1391540019081935430278
925 1432518543982425655122
926 1474681323154353219716
927 1518061943902864526356
928 1562694928428716500033
929 1608615759368674189536
930 1655860906020750177111
931 1704467851272310783128
932 1754475119249539007528
933 1805922303707223639312
934 1858850097178330890348
935 1913300320903319630764
936 1969315955559674075563
937 2026941172812656248160
938 2086221367708822449308
939 2147203191934400715466
940 2209934587961197912581
941 2274464824103285511420
942 2340844530508313113527
943 2409125736107911104156
944 2479361906552271536024
945 2551607983154642881416
946 2625920422872131974691
947 2702357239349886707780
948 2780978045056425210930
949 2861844094538589872280
950 2945018328825335125662
951 3030565421010303794120
952 3118551823043916787101
953 3209045813766484042736
954 3302117548214652849647
955 3397839108234335044522
956 3496284554434100655584
957 3597529979513896114344
958 3701653563004831881000
959 3808735627456699874592
960 3918858696110813836924
961 4032107552096725205152
962 4148569299192350544452
963 4268333424188051268402
964 4391491860896242137510
965 4518139055849159765652
966 4648372035728509502747
967 4782290476571819857632
968 4919996774801472140826
969 5061596120123543534780
970 5207196570344795282469
971 5356909128157368192372
972 5510847819942002521479
973 5669129776641889083710
974 5831875316760580384290
975 5999208031538741664522
976 6171254872365913002861
977 6348146240484871890424
978 6530016079047645834034
979 6717001967583717164706
980 6909245218942491867764
981 7106890978773675847440
982 7310088327610805780349
983 7518990385624833183148
984 7733754420116345862285
985 7954541955816742195824
986 8181518888070447962726
987 8414855598972079484588
988 8654727076534322977165
989 8901313036964204033556
990 9154798050127379470251
991 9415371668282086368578
992 9683228558166435153500
993 9958568636524840592290
994 10241597209161536188527
995 10532525113611330799356
996 10831568865520026760803
997 11138950808829239331276
998 11454899269862735069968
999 11779648715413838652504
1000 12113439914935957214405