0 1
1 1
2 2
3 3
4 6
5 12
6 23
7 43
8 74
9 124
10 195
11 300
12 441
13 637
14 890
15 1226
16 1647
17 2187
18 2848
19 3673
20 4664
21 5874
22 7305
23 9021
24 11024
25 13390
26 16121
27 19306
28 22947
29 27147
30 31908
31 37348
32 43469
33 50405
34 58158
35 66879
36 76570
37 87400
38 99371
39 112671
40 127302
41 143472
42 161183
43 180664
44 201917
45 225193
46 250494
47 278094
48 307995
49 340495
50 375596
51 413621
52 454572
53 498798
54 546301
55 597457
56 652268
57 711138
58 774069
59 841494
60 913415
61 990295
62 1072136
63 1159432
64 1252185
65 1350921
66 1455642
67 1566907
68 1684718
69 1809668
70 1941759
71 2081619
72 2229250
73 2385316
74 2549819
75 2723460
76 2906241
77 3098901
78 3301442
79 3514642
80 3738503
81 3973843
82 4220664
83 4479825
84 4751328
85 5036074
86 5334065
87 5646245
88 5972616
89 6314166
90 6670897
91 7043842
92 7433003
93 7839459
94 8263212
95 8705388
96 9165989
97 9646189
98 10145990
99 10666615
100 11208066
101 11771616
102 12357267
103 12966343
104 13598846
105 14256152
106 14938263
107 15646608
108 16381189
109 17143489
110 17933510
111 18752790
112 19601331
113 20480727
114 21390980
115 22333741
116 23309012
117 24318502
118 25362213
119 26441913
120 27557604
121 28711114
122 29902445
123 31133486
124 32404239
125 33716655
126 35070736
127 36468496
128 37909937
129 39397137
130 40930098
131 42510963
132 44139734
133 45818620
134 47547623
135 49329019
136 51162810
137 53051340
138 54994611
139 56995036
140 59052617
141 61169837
142 63346698
143 65585754
144 67887007
145 70253083
146 72683984
147 75182409
148 77748360
149 80384610
150 83091161
151 85870861
152 88723712
153 91652638
154 94657641
155 97741722
156 100904883
157 104150203
158 107477684
159 110890484
160 114388605
161 117975285
162 121650526
163 125417647
164 129276650
165 133230936
166 137280507
167 141428847
168 145675958
169 150025408
170 154477199
171 159034984
172 163698765
173 168472281
174 173355534
175 178352350
176 183462731
177 188690591
178 194035932
179 199502757
180 205091068
181 210804958
182 216644429
183 222613665
184 228712668
185 234945714
186 241312805
187 247818310
188 254462231
189 261249031
190 268178712
191 275255832
192 282480393
193 289857049
194 297385802
195 305071403
196 312913854
197 320918004
198 329083855
199 337416355
200 345915506
201 354586356
202 363428907
203 372448308
204 381644561
205 391022917
206 400583378
207 410331298
208 420266679
209 430394979
210 440716200
211 451235905
212 461954096
213 472876442
214 484002945
215 495339381
216 506885752
217 518647942
218 530625953
219 542825778
220 555247419
221 567896979
222 580774460
223 593886076
224 607231829
225 620818045
226 634644726
227 648718311
228 663038802
229 677612752
230 692440163
231 707527703
232 722875374
233 738489960
234 754371463
235 770526784
236 786955925
237 803665905
238 820656726
239 837935526
240 855502307
241 873364327
242 891521588
243 909981469
244 928743972
245 947816598
246 967199349
247 986899849
248 1006918100
249 1027261850
250 1047931101
251 1068933726
252 1090269727
253 1111947103
254 1133965856
255 1156334112
256 1179051873
257 1202127393
258 1225560674
259 1249360099
260 1273525670
261 1298065900
262 1322980791
263 1348278987
264 1373960490
265 1400034076
266 1426499747
267 1453366412
268 1480634073
269 1508311773
270 1536399514
271 1564906474
272 1593832655
273 1623187371
274 1652970624
275 1683191865
276 1713851096
277 1744957906
278 1776512297
279 1808523997
280 1840993008
281 1873929198
282 1907332569
283 1941213130
284 1975570883
285 2010415979
286 2045748420
287 2081578500
288 2117906221
289 2154742021
290 2192085902
291 2229948447
292 2268329658
293 2307240264
294 2346680267
295 2386660543
296 2427181094
297 2468252944
298 2509876095
299 2552061720
300 2594809821
301 2638131721
302 2682027422
303 2726508398
304 2771574651
305 2817237807
306 2863497868
307 2910366613
308 2957844044
309 3005942094
310 3054660765
311 3104012145
312 3153996236
313 3204625282
314 3255899285
315 3307830646
316 3360419367
317 3413678007
318 3467606568
319 3522217768
320 3577511609
321 3633500969
322 3690185850
323 3747579291
324 3805681294
325 3864505060
326 3924050591
327 3984331251
328 4045347042
329 4107111492
330 4169624603
331 4232900068
332 4296937889
333 4361751925
334 4427342178
335 4493722674
336 4560893415
337 4628868595
338 4697648216
339 4767246641
340 4837663872
341 4908914442
342 4980998353
343 5053930309
344 5127710312
345 5202353238
346 5277859089
347 5354242914
348 5431504715
349 5509659715
350 5588707916
351 5668664716
352 5749530117
353 5831319693
354 5914033446
355 5997687127
356 6082280738
357 6167830208
358 6254335539
359 6341812839
360 6430262110
361 6519699640
362 6610125431
363 6701555952
364 6793991205
365 6887447841
366 6981925862
367 7077442102
368 7173996563
369 7271606263
370 7370271204
371 7470008589
372 7570818420
373 7672718086
374 7775707589
375 7879804505
376 7985008836
377 8091338346
378 8198793037
379 8307390862
380 8417131823
381 8528034063
382 8640097584
383 8753340720
384 8867763473
385 8983384369
386 9100203410
387 9218239315
388 9337492086
389 9457980636
390 9579704967
391 9702684187
392 9826918298
393 9952426604
394 10079209107
395 10207285308
396 10336655209
397 10467338509
398 10599335210
399 10732665210
400 10867328511
401 11003345211
402 11140715312
403 11279459113
404 11419576616
405 11561088322
406 11703994233
407 11848315053
408 11994050784
409 12141222334
410 12289829705
411 12439894010
412 12591415251
413 12744414747
414 12898892500
415 13054870036
416 13212347357
417 13371346197
418 13531866558
419 13693930383
420 13857537674
421 14022710584
422 14189449115
423 14357775631
424 14527690134
425 14699215200
426 14872350831
427 15047119816
428 15223522157
429 15401580857
430 15581295918
431 15762690558
432 15945764779
433 16130542015
434 16317022268
435 16505229189
436 16695162780
437 16886846910
438 17080281581
439 17275490881
440 17472474812
441 17671257682
442 17871839493
443 18074244774
444 18278473527
445 18484550503
446 18692475704
447 18902274104
448 19113945705
449 19327515705
450 19542984106
451 19760376331
452 19979692382
453 20200957908
454 20424172911
455 20649363267
456 20876528978
457 21105696148
458 21336864779
459 21570061204
460 21805285425
461 22042564005
462 22281896946
463 22523311042
464 22766806295
465 23012409731
466 23260121352
467 23509968417
468 23761950928
469 24016096378
470 24272404769
471 24530903829
472 24791593560
473 25054501926
474 25319628929
475 25587002770
476 25856623451
477 26128519411
478 26402690652
479 26679165852
480 26957945013
481 27239057053
482 27522501974
483 27808308935
484 28096477938
485 28387038384
486 28679990275
487 28975363255
488 29273157326
489 29573402376
490 29876098407
491 30181275552
492 30488933813
493 30799103569
494 31111784822
495 31427008198
496 31744773699
497 32065112199
498 32388023700
499 32713539325
500 33041659076
501 33372414326
502 33705805077
503 34041862953
504 34380587956
505 34722011962
506 35066134973
507 35412989118
508 35762574399
509 36114923199
510 36470035520
511 36827944000
512 37188648641
513 37552182337
514 37918545090
515 38287770051
516 38659857222
517 39034840012
518 39412718423
519 39793526123
520 40177263114
521 40563963324
522 40953626755
523 41346287596
524 41741945849
525 42140635965
526 42542357946
527 42947146506
528 43355001647
529 43765958347
530 44180016608
531 44597211673
532 45017543544
533 45441047730
534 45867724233
535 46297608829
536 46730701520
537 47167038350
538 47606619321
539 48049480746
540 48495622627
541 48945081547
542 49397857508
543 49853987364
544 50313471117
545 50776345893
546 51242611694
547 51712305919
548 52185428570
549 52662017320
550 53142072171
551 53625631071
552 54112694022
553 54603299248
554 55097446751
555 55595175032
556 56096484093
557 56601412713
558 57109960894
559 57622167694
560 58138033115
561 58657596495
562 59180857836
563 59707856757
564 60238593260
565 60773107246
566 61311398717
567 61853507857
568 62399434668
569 62949219618
570 63502862709
571 64060404694
572 64621845575
573 65187226391
574 65756547144
575 66329849160
576 66907132441
577 67488438601
578 68073767642
579 68663161467
580 69256620078
581 69854185668
582 70455858239
583 71061680275
584 71671651778
585 72285815524
586 72904171515
587 73526762820
588 74153589441
589 74784694741
590 75420078722
591 76059785042
592 76703813703
593 77352208659
594 78004969912
595 78662141713
596 79323724064
597 79989761514
598 80660254065
599 81335246565
600 82014739016
601 82698776566
602 83387359217
603 84080532418
604 84778296171
605 85480696227
606 86187732588
607 86899451308
608 87615852389
609 88336982189
610 89062840710
611 89793474615
612 90528883906
613 91269115552
614 92014169555
615 92764093191
616 93518886462
617 94278596952
618 95043224663
619 95812817488
620 96587375429
621 97366946689
622 98151531270
623 98941177686
624 99735885939
625 100535704855
626 101340634436
627 102150723821
628 102965973012
629 103786431462
630 104612099173
631 105443025913
632 106279211684
633 107120706570
634 107967510573
635 108819674094
636 109677197135
637 110540130415
638 111408473936
639 112282278736
640 113161544817
641 114046323537
642 114936614898
643 115832470579
644 116733890582
645 117640926908
646 118553579559
647 119471900859
648 120395890810
649 121325602060
650 122261034611
651 123202241436
652 124149222537
653 125102031213
654 126060667466
655 127025184922
656 127995583583
657 128971917403
658 129954186384
659 130942444809
660 131936692680
661 132936984610
662 133943320601
663 134955755597
664 135974289600
665 136998977886
666 138029820457
667 139066872922
668 140110135283
669 141159663483
670 142215457524
671 143277573684
672 144346011965
673 145420828981
674 146502024734
675 147589656175
676 148683723306
677 149784283416
678 150891336507
679 152004940207
680 153125094518
681 154251857408
682 155385228879
683 156525267240
684 157671972493
685 158825403289
686 159985559630
687 161152500510
688 162326225931
689 163506795231
690 164694208412
691 165888525157
692 167089745468
693 168297929374
694 169513076877
695 170735248353
696 171964443804
697 173200723954
698 174444088805
699 175694599430
700 176952255831
701 178217119431
702 179489190232
703 180768530008
704 182055138761
705 183349078617
706 184650349578
707 185959014123
708 187275072254
709 188598586804
710 189929557775
711 191268048355
712 192614058546
713 193967651892
714 195328828395
715 196697651956
716 198074122577
717 199458304517
718 200850197778
719 202249866978
720 203657312119
721 205072598179
722 206495725160
723 207926758401
724 209365697904
725 210812609370
726 212267492801
727 213730414261
728 215201373752
729 216680437702
730 218167606113
731 219662945778
732 221166456699
733 222678206035
734 224198193788
735 225726487484
736 227263087125
737 228808060605
738 230361407926
739 231923197351
740 233493428882
741 235072171152
742 236659424163
743 238255256919
744 239859669422
745 241472731048
746 243094441799
747 244724871424
748 246364019925
749 248011957425
750 249668683926
751 251334269926
752 253008715427
753 254692091303
754 256384397556
755 258085705437
756 259796014948
757 261515397718
758 263243853749
759 264981455049
760 266728201620
761 268484165850
762 270249347741
763 272023820062
764 273807582815
765 275600709151
766 277403199072
767 279215126112
768 281036490273
769 282867365473
770 284707751714
771 286557723299
772 288417280230
773 290286497196
774 292165374199
775 294053986315
776 295952333546
777 297860491356
778 299778459747
779 301706314572
780 303644055833
781 305591759773
782 307549426394
783 309517132330
784 311494877583
785 313482739179
786 315480717120
787 317488888825
788 319507254296
789 321535891346
790 323574799977
791 325624058397
792 327683666608
793 329753703214
794 331834168217
795 333925140618
796 336026620419
797 338138687019
798 340261340420
799 342394660420
800 344538647021
801 346693380421
802 348858860622
803 351035168223
804 353222303226
805 355420346632
806 357629298443
807 359849240063
808 362080171494
809 364322174544
810 366575249215
811 368839477720
812 371114860061
813 373401478857
814 375699334110
815 378008508846
816 380329003067
817 382660900207
818 385004200268
819 387358987093
820 389725260684
821 392103105294
822 394492520925
823 396893592241
824 399306319244
825 401730787010
826 404166995541
827 406615030326
828 409074891367
829 411546664567
830 414030349928
831 416526033768
832 419033716089
833 421553483625
834 424085336378
835 426629361499
836 429185558990
837 431754016420
838 434334733791
839 436927799091
840 439533212322
841 442151061892
842 444781347803
843 447424158884
844 450079495137
845 452747445813
846 455428010914
847 458121280114
848 460827253415
849 463546020915
850 466277582616
851 469022029041
852 471779360192
853 474549667018
854 477332949521
855 480129299077
856 482938715688
857 485761291158
858 488597025489
859 491446010914
860 494308247435
861 497183827715
862 500072751756
863 502975112652
864 505890910405
865 508820238541
866 511763097062
867 514719579927
868 517689687138
869 520673513088
870 523671057779
871 526682416039
872 529707587870
873 532746668536
874 535799658039
875 538866652080
876 541947650661
877 545042749921
878 548151949862
879 551275347062
880 554412941523
881 557564830263
882 560731013284
883 563911588045
884 567106554548
885 570316010694
886 573539956485
887 576778490265
888 580031612036
889 583299420586
890 586581915917
891 589879197262
892 593191264623
893 596518217679
894 599860056432
895 603216881008
896 606588691409
897 609975588209
898 613377571410
899 616794742035
900 620227100086
901 623674747036
902 627137682887
903 630616009563
904 634109727066
905 637618937772
906 641143641683
907 644683941628
908 648239837609
909 651811432909
910 655398727530
911 659001825210
912 662620725951
913 666255533947
914 669906249200
915 673572976361
916 677255715432
917 680954571522
918 684669544633
919 688400740333
920 692148158624
921 695911905534
922 699691981065
923 703488491706
924 707301437459
925 711130925275
926 714976955156
927 718839634516
928 722718963357
929 726615049557
930 730527893118
931 734457602383
932 738404177354
933 742367726840
934 746348250843
935 750345858639
936 754360550230
937 758392435360
938 762441514031
939 766507896456
940 770591582637
941 774692683257
942 778811198318
943 782947238974
944 787100805227
945 791272008703
946 795460849404
947 799667439429
948 803891778780
949 808133980030
950 812394043181
951 816672081281
952 820968094332
953 825282195858
954 829614385861
955 833964778342
956 838333373303
957 842720285223
958 847125514104
959 851549174904
960 855991267625
961 860451907705
962 864931095146
963 869428945867
964 873945459870
965 878480753556
966 883034826927
967 887607796867
968 892199663378
969 896810543828
970 901440438219
971 906089464404
972 910757622385
973 915445030501
974 920151688754
975 924877715970
976 929623112151
977 934387996611
978 939172369352
979 943976350177
980 948799939088
981 953643256378
982 958506302049
983 963389196885
984 968291940888
985 973214655334
986 978157340225
987 983120117330
988 988102986651
989 993106070451
990 998129368732
991 1003173004252
992 1008236977013
993 1013321410269
994 1018426304022
995 1023551782023
996 1028697844274
997 1033864615024
998 1039052094275
999 1044260406775
1000 1049489552526