0 1
1 1
2 3
3 6
4 11
5 18
6 32
7 48
8 75
9 111
10 160
11 224
12 313
13 420
14 562
15 738
16 956
17 1221
18 1550
19 1936
20 2405
21 2958
22 3609
23 4368
24 5260
25 6279
26 7462
27 8814
28 10356
29 12104
30 14093
31 16320
32 18834
33 21645
34 24783
35 28272
36 32158
37 36442
38 41187
39 46410
40 52151
41 58443
42 65345
43 72864
44 81078
45 90012
46 99718
47 110240
48 121651
49 133965
50 147277
51 161622
52 177065
53 193662
54 211502
55 230608
56 251093
57 273003
58 296418
59 321408
60 348079
61 376464
62 406696
63 438834
64 472974
65 509201
66 547640
67 588336
68 631443
69 677034
70 725223
71 776112
72 829846
73 886483
74 946200
75 1009086
76 1075274
77 1144884
78 1218083
79 1294944
80 1375668
81 1460361
82 1549177
83 1642256
84 1739788
85 1841862
86 1948705
87 2060442
88 2177249
89 2299287
90 2426771
91 2559808
92 2698652
93 2843448
94 2994396
95 3151680
96 3315541
97 3486105
98 3663655
99 3848358
100 4040439
101 4240106
102 4447628
103 4663152
104 4886991
105 5119335
106 5360436
107 5610528
108 5869909
109 6138748
110 6417390
111 6706050
112 7005008
113 7314525
114 7634930
115 7966416
116 8309361
117 8664006
118 9030661
119 9409616
120 9801232
121 10205727
122 10623514
123 11054862
124 11500112
125 11959584
126 12433673
127 12922624
128 13426886
129 13946757
130 14482611
131 15034800
132 15603754
133 16189746
134 16793263
135 17414634
136 18054267
137 18712547
138 19389941
139 20086752
140 20803506
141 21540564
142 22298370
143 23077344
144 23877991
145 24700645
146 25545873
147 26414070
148 27305717
149 28221270
150 29161274
151 30126096
152 31116345
153 32132451
154 33174934
155 34244288
156 35341099
157 36465768
158 37618948
159 38801106
160 40012802
161 41254569
162 42527036
163 43830640
164 45166079
165 46533858
166 47934579
167 49368816
168 50837242
169 52340331
170 53878828
171 55453278
172 57064326
173 58712588
174 60398783
175 62123424
176 63887304
177 65691009
178 67535229
179 69420624
180 71347960
181 73317790
182 75330957
183 77388090
184 79489925
185 81637167
186 83830631
187 86070912
188 88358904
189 90695280
190 93080824
191 95516288
192 98002537
193 100540209
194 103130251
195 105773382
196 108470435
197 111222210
198 114029624
199 116893360
200 119814419
201 122793567
202 125831688
203 128929632
204 132088369
205 135308628
206 138591466
207 141937698
208 145348260
209 148824053
210 152366102
211 155975184
212 159652413
213 163398654
214 167214897
215 171102096
216 175061332
217 179093431
218 183199566
219 187380654
220 191637740
221 195971832
222 200384069
223 204875328
224 209446842
225 214099581
226 218834647
227 223653104
228 228556150
229 233544714
230 238620091
231 243783306
232 249035519
233 254377851
234 259811561
235 265337632
236 270957422
237 276672012
238 282482622
239 288390432
240 294396763
241 300502653
242 306709525
243 313018518
244 319430913
245 325947950
246 332571014
247 339301200
248 346139997
249 353088603
250 360148362
251 367320576
252 374606695
253 382007872
254 389525664
255 397161330
256 404916278
257 412791873
258 420789632
259 428910768
260 437156907
261 445529370
262 454029631
263 462659120
264 471419422
265 480311811
266 489337984
267 498499326
268 507797378
269 517233636
270 526809755
271 536527072
272 546387356
273 556392057
274 566542785
275 576841104
276 587288740
277 597887094
278 608638009
279 619543002
280 630603753
281 641821895
282 653199227
283 664737216
284 676437780
285 688302504
286 700333140
287 712531392
288 724899133
289 737437897
290 750149679
291 763036134
292 776099087
293 789340314
294 802761764
295 816365040
296 830152215
297 844125015
298 858285340
299 872635040
300 887176141
301 901910316
302 916839718
303 931966146
304 947291576
305 962817933
306 978547322
307 994481488
308 1010622665
309 1026972726
310 1043533725
311 1060307664
312 1077296728
313 1094502735
314 1111928002
315 1129574478
316 1147444296
317 1165539536
318 1183862465
319 1202414976
320 1221199470
321 1240217973
322 1259472699
323 1278965808
324 1298699650
325 1318676194
326 1338897927
327 1359366954
328 1380085571
329 1401056019
330 1422280733
331 1443761760
332 1465501674
333 1487502660
334 1509767098
335 1532297312
336 1555095823
337 1578164757
338 1601506777
339 1625124150
340 1649019341
341 1673194758
342 1697653010
343 1722396304
344 1747427393
345 1772748627
346 1798362558
347 1824271680
348 1850478691
349 1876985880
350 1903796092
351 1930911762
352 1958335530
353 1986069977
354 2014117892
355 2042481648
356 2071164183
357 2100168018
358 2129495883
359 2159150448
360 2189134594
361 2219450779
362 2250102036
363 2281090974
364 2312420414
365 2344093116
366 2376112055
367 2408479776
368 2441199408
369 2474273649
370 2507705413
371 2541497552
372 2575653136
373 2610174798
374 2645065765
375 2680328826
376 2715966989
377 2751983199
378 2788380623
379 2825161984
380 2862330608
381 2899889376
382 2937841392
383 2976189696
384 3014937553
385 3054087777
386 3093643795
387 3133608582
388 3173985339
389 3214777202
390 3255987536
391 3297619248
392 3339675867
393 3382160463
394 3425076336
395 3468426720
396 3512215081
397 3556444420
398 3601118370
399 3646240098
400 3691813004
401 3737840421
402 3784325918
403 3831272592
404 3878684181
405 3926563950
406 3974915401
407 4023741968
408 4073047324
409 4122834663
410 4173107830
411 4223870190
412 4275125348
413 4326876840
414 4379128445
415 4431883456
416 4485145826
417 4538919021
418 4593206751
419 4648012656
420 4703340622
421 4759194042
422 4815576979
423 4872493002
424 4929945927
425 4987939499
426 5046477713
427 5105564064
428 5165202726
429 5225397372
430 5286151926
431 5347470240
432 5409356419
433 5471814061
434 5534847453
435 5598460374
436 5662656857
437 5727440862
438 5792816606
439 5858787792
440 5925358821
441 5992533579
442 6060316210
443 6128710784
444 6197721631
445 6267352560
446 6337608088
447 6408492210
448 6480009182
449 6552163185
450 6624958664
451 6698399536
452 6772490435
453 6847235466
454 6922638999
455 6998705328
456 7075439014
457 7152844083
458 7230925288
459 7309686846
460 7389133242
461 7469268884
462 7550098451
463 7631626080
464 7713856644
465 7796794473
466 7880444169
467 7964810256
468 8049897532
469 8135710246
470 8222253393
471 8309531418
472 8397549041
473 8486310903
474 8575821923
475 8666086464
476 8757109644
477 8848896024
478 8941450444
479 9034777664
480 9128882725
481 9223770105
482 9319445047
483 9415912230
484 9513176615
485 9611243082
486 9710116796
487 9809802352
488 9910305119
489 10011629895
490 10113781764
491 10216765728
492 10320587077
493 10425250524
494 10530761566
495 10637125122
496 10744346400
497 10852430525
498 10961382914
499 11071208400
500 11181912609
501 11293500582
502 11405977653
503 11519349072
504 11633620384
505 11748796543
506 11864883306
507 11981885838
508 12099809600
509 12218659968
510 12338442617
511 12459162624
512 12580825878
513 12703437669
514 12827003587
515 12951529136
516 13077020122
517 13203481746
518 13330920031
519 13459340394
520 13588748555
521 13719150147
522 13850551109
523 13982956768
524 14116373282
525 14250806196
526 14386261362
527 14522744544
528 14660261815
529 14798818629
530 14938421281
531 15079075446
532 15220787109
533 15363562166
534 15507406826
535 15652326672
536 15798328137
537 15945417027
538 16093599462
539 16242881472
540 16393269403
541 16544768968
542 16697386740
543 16851128658
544 17006000978
545 17162009865
546 17319161804
547 17477462640
548 17636919087
549 17797537218
550 17959323427
551 18122284016
552 18286425610
553 18451754187
554 18618276604
555 18785999070
556 18954928118
557 19125070188
558 19296432047
559 19469019808
560 19642840472
561 19817900385
562 19994206221
563 20171764560
564 20350582312
565 20530665726
566 20712021949
567 20894657466
568 21078579093
569 21263793551
570 21450307895
571 21638128512
572 21827262696
573 22017717072
574 22209498600
575 22402614144
576 22597070905
577 22792875409
578 22990035099
579 23188556742
580 23388447443
581 23589714210
582 23792364392
583 23996404656
584 24201842595
585 24408685119
586 24616939480
587 24826612832
588 25037712673
589 25250245812
590 25464219994
591 25679642274
592 25896520052
593 26114860629
594 26334671654
595 26555960080
596 26778733805
597 27003000030
598 27228766305
599 27456040080
600 27684829156
601 27915140631
602 28146982558
603 28380362286
604 28615287516
605 28851765848
606 29089805237
607 29329412928
608 29570597130
609 29813365341
610 30057725415
611 30303685104
612 30551252518
613 30800435050
614 31051241067
615 31303678218
616 31557754511
617 31813477851
618 32070856505
619 32329898016
620 32590610910
621 32853002988
622 33117082414
623 33382857248
624 33650335915
625 33919526109
626 34190436517
627 34463075094
628 34737450161
629 35013569934
630 35291442998
631 35571077200
632 35852481389
633 36135663675
634 36420632538
635 36707396352
636 36995963863
637 37286343072
638 37578542992
639 37872571890
640 38168438406
641 38466151073
642 38765718800
643 39067149744
644 39370453083
645 39675637242
646 39982711023
647 40291683120
648 40602562606
649 40915357795
650 41230078032
651 41546731902
652 41865328370
653 42185876292
654 42508384907
655 42832862688
656 43159319148
657 43487763033
658 43818203473
659 44150649488
660 44485110484
661 44821595094
662 45160113001
663 45500673114
664 45843284729
665 46187957031
666 46534699595
667 46883521216
668 47234431748
669 47587440264
670 47942556228
671 48299788992
672 48659148301
673 49020643113
674 49384283455
675 49750078566
676 50118038079
677 50488171514
678 50860488788
679 51234999024
680 51611712423
681 51990638391
682 52371786732
683 52755167136
684 53140789693
685 53528663692
686 53918799510
687 54311206722
688 54705895304
689 55102875117
690 55502156426
691 55903748688
692 56307662457
693 56713907478
694 57122493901
695 57533431760
696 57946731496
697 58362402735
698 58780456210
699 59200901838
700 59623749944
701 60049010736
702 60476694833
703 60906812032
704 61339373246
705 61774388565
706 62211868491
707 62651823408
708 63094264114
709 63539200578
710 63986643895
711 64436604330
712 64889092563
713 65344119155
714 65801695085
715 66261830496
716 66724536666
717 67189824036
718 67657703466
719 68128185696
720 68601281887
721 69077002357
722 69555358569
723 70036361142
724 70520021117
725 71006349414
726 71495357378
727 71987055504
728 72481455441
729 72978567987
730 73478404366
731 73980975680
732 74486293459
733 74994368376
734 75505212268
735 76018836114
736 76535251322
737 77054469177
738 77576501396
739 78101358832
740 78629053511
741 79159596594
742 79692999675
743 80229274224
744 80768432146
745 81310484475
746 81855443428
747 82403320350
748 82954127022
749 83507875100
750 84064576679
751 84624242976
752 85186886400
753 85752518481
754 86321151189
755 86892796368
756 87467466304
757 88045172398
758 88625927253
759 89209742586
760 89796630557
761 90386603199
762 90979672991
763 91575851520
764 92175151584
765 92777585088
766 93383164384
767 93991901696
768 94603809697
769 95218900161
770 95837186083
771 96458679558
772 97083393131
773 97711339218
774 98342530688
775 98976979504
776 99614698859
777 100255701039
778 100899998784
779 101547604704
780 102198531865
781 102852792420
782 103510399762
783 104171366370
784 104835705180
785 105503428997
786 106174551086
787 106849083792
788 107527040709
789 108208434510
790 108893278329
791 109581585168
792 110273368492
793 110968640839
794 111667416006
795 112369706862
796 113075526740
797 113784888840
798 114497806829
799 115214293440
800 115934362674
801 116658027597
802 117385301743
803 118116198512
804 118850731774
805 119588914458
806 120330760771
807 121076283978
808 121825497815
809 122578415883
810 123335052257
811 124095420064
812 124859533718
813 125627406684
814 126399052902
815 127174486176
816 127953720787
817 128736770061
818 129523648621
819 130314370134
820 131108948745
821 131907398462
822 132709733774
823 133515968208
824 134326116597
825 135140192811
826 135958211202
827 136780185984
828 137606131855
829 138436062544
830 139269993096
831 140107937586
832 140949910574
833 141795926481
834 142646000216
835 143500145712
836 144358378227
837 145220712042
838 146087161927
839 146957742512
840 147832468918
841 148711355283
842 149594417080
843 150481668798
844 151373125418
845 152268801780
846 153168713219
847 154072874080
848 154981300052
849 155894005833
850 156811006617
851 157732317456
852 158657953900
853 159587930502
854 160522263169
855 161460966810
856 162404056833
857 163351548503
858 164303457587
859 165259798848
860 166220588412
861 167185841400
862 168155573436
863 169129800000
864 170108537077
865 171091799641
866 172079604039
867 173071965606
868 174068900183
869 175070423466
870 176076551660
871 177087299952
872 178102684911
873 179122722087
874 180147427540
875 181176817184
876 182210907445
877 183249713724
878 184293252814
879 185341540482
880 186394593008
881 187452426525
882 188515057682
883 189582502096
884 190654776785
885 191731897734
886 192813881445
887 193900744272
888 194992503088
889 196089173727
890 197190773434
891 198297318414
892 199408825392
893 200525310944
894 201646792169
895 202773285120
896 203904807270
897 205041375045
898 206183005395
899 207329715120
900 208481521546
901 209638440946
902 210800491023
903 211967688426
904 213140050331
905 214317593763
906 215500336277
907 216688294368
908 217881485970
909 219079927956
910 220283637730
911 221492632544
912 222706930183
913 223926547365
914 225151502257
915 226381811958
916 227617494101
917 228858566166
918 230105046170
919 231356951056
920 232614299225
921 233877108003
922 235145395254
923 236419178688
924 237698476555
925 238983306024
926 240273685732
927 241569633234
928 242871166626
929 244178303849
930 245491063388
931 246809462640
932 248133520479
933 249463254690
934 250798683603
935 252139825392
936 253486698778
937 254839321387
938 256197712332
939 257561889630
940 258931871846
941 260307677388
942 261689325215
943 263076833184
944 264470220648
945 265869505857
946 267274707613
947 268685844560
948 270102935896
949 271525999710
950 272955055597
951 274390122042
952 275831218085
953 277278362607
954 278731575047
955 280190873728
956 281656278488
957 283127808048
958 284605481688
959 286089318528
960 287579338249
961 289075559409
962 290578002091
963 292086685254
964 293601628419
965 295122850946
966 296650372760
967 298184212656
968 299724390963
969 301270926879
970 302823840168
971 304383150432
972 305948877841
973 307521041428
974 309099661770
975 310684758306
976 312276351044
977 313874459829
978 315479105078
979 317090306064
980 318708083613
981 320332457406
982 321963447697
983 323601074576
984 325245358708
985 326896319607
986 328553978350
987 330218354862
988 331889469644
989 333567343032
990 335251995941
991 336943448128
992 338641720922
993 340346834493
994 342058809591
995 343777666800
996 345503427286
997 347236111050
998 348975739675
999 350722333578
1000 352475913759