1 0
2 1
3 10
4 44
5 130
6 313
7 640
8 1192
9 2044
10 3305
11 5078
12 7524
13 10750
14 14993
15 20388
16 27128
17 35448
18 45665
19 57922
20 72636
21 89970
22 110297
23 133976
24 161440
25 192860
26 228857
27 269758
28 316012
29 367974
30 426417
31 491468
32 564120
33 644640
34 733633
35 831674
36 939292
37 1056962
38 1186057
39 1326880
40 1479968
41 1645820
42 1825945
43 2020350
44 2230660
45 2457046
46 2700305
47 2961708
48 3242368
49 3542232
50 3863217
51 4205666
52 4570916
53 4959610
54 5373625
55 5812864
56 6278952
57 6772644
58 7295673
59 7849198
60 8434804
61 9051886
62 9703825
63 10391076
64 11114080
65 11874480
66 12674097
67 13513370
68 14395772
69 15320962
70 16290841
71 17305744
72 18369232
73 19480628
74 20644265
75 21860334
76 23129396
77 24453494
78 25834497
79 27273084
80 28773384
81 30334424
82 31959633
83 33650834
84 35410996
85 37238026
86 39136537
87 41108472
88 43155216
89 45277100
90 47479241
91 49759526
92 52122972
93 54571182
94 57106481
95 59731268
96 62446440
97 65252248
98 68155521
99 71155218
100 74253628
101 77452234
102 80757641
103 84167824
104 87689288
105 91320036
106 95062233
107 98920998
108 102900572
109 106997766
110 111221073
111 115567996
112 120043216
113 124647008
114 129387665
115 134262402
116 139276300
117 144430898
118 149727961
119 155172208
120 160765488
121 166505980
122 172405177
123 178463998
124 184684644
125 191067630
126 197617633
127 204332740
128 211224480
129 218290528
130 225535825
131 232959626
132 240571532
133 248366690
134 256353929
135 264536232
136 272913192
137 281489732
138 290274985
139 299264254
140 308468188
141 317880398
142 327510913
143 337363332
144 347439688
145 357737208
146 368267969
147 379035266
148 390039300
149 401283402
150 412777897
151 424514304
152 436508288
153 448755220
154 461259721
155 474024102
156 487057404
157 500356814
158 513937953
159 527800220
160 541945632
161 556371696
162 571089681
163 586098506
164 601412924
165 617028738
166 632945705
167 649174816
168 665723336
169 682580244
170 699765849
171 717274982
172 735115204
173 753291022
174 771814689
175 790678044
176 809887920
177 829445848
178 849364289
179 869645882
180 890299948
181 911311738
182 932708057
183 954481184
184 976640848
185 999186588
186 1022127673
187 1045463014
188 1069202644
189 1093349334
190 1117903233
191 1142870316
192 1168268600
193 1194085696
194 1220345057
195 1247043362
196 1274177052
197 1301751770
198 1329788217
199 1358271128
200 1387227000
201 1416642020
202 1446532313
203 1476903518
204 1507759020
205 1539091214
206 1570917969
207 1603244148
208 1636070720
209 1669397816
210 1703241425
211 1737589770
212 1772477884
213 1807898154
214 1843858473
215 1880363392
216 1917415208
217 1955006268
218 1993158665
219 2031878358
220 2071167724
221 2111019902
222 2151455137
223 2192470620
224 2234089552
225 2276295568
226 2319098833
227 2362517026
228 2406564540
229 2451219594
230 2496516217
231 2542438464
232 2588992104
233 2636185652
234 2684046777
235 2732553302
236 2781728500
237 2831573742
238 2882097185
239 2933295172
240 2985193352
241 3037765488
242 3091055569
243 3145052874
244 3199764188
245 3255195802
246 3311351817
247 3368234560
248 3425861072
249 3484228764
250 3543351865
251 3603226142
252 3663878636
253 3725281654
254 3787471985
255 3850454780
256 3914221216
257 3978785624
258 4044173905
259 4110366842
260 4177385484
261 4245213890
262 4313876793
263 4383388000
264 4453763752
265 4524972140
266 4597050265
267 4669989230
268 4743811180
269 4818513726
270 4894121057
271 4970602996
272 5048007000
273 5126315112
274 5205532129
275 5285683226
276 5366768252
277 5448779562
278 5531760377
279 5615705720
280 5700610632
281 5786462708
282 5873317081
283 5961150126
284 6049996604
285 6139842038
286 6230682497
287 6322529692
288 6415407072
289 6509293400
290 6604240785
291 6700230386
292 6797285844
293 6895405410
294 6994618489
295 7094890520
296 7196257656
297 7298713260
298 7402264329
299 7506933510
300 7612728956
301 7719622646
302 7827666113
303 7936863420
304 8047220792
305 8158727232
306 8271409841
307 8385251914
308 8500304372
309 8616532482
310 8733972969
311 8852616200
312 8972501640
313 9093590764
314 9215943641
315 9339552766
316 9464390724
317 9590493294
318 9717891393
319 9846557948
320 9976520056
321 10107756376
322 10240306785
323 10374160234
324 10509351228
325 10645850882
326 10783695465
327 10922903744
328 11063482912
329 11205424404
330 11348757369
331 11493441238
332 11639555436
333 11787076374
334 11936008657
335 12086375380
336 12238179968
337 12391385768
338 12546073505
339 12702221386
340 12859847228
341 13018927770
342 13179509897
343 13341568624
344 13505150544
345 13670246468
346 13836858777
347 14005021534
348 14174761140
349 14346031214
350 14518894481
351 14693307508
352 14869298936
353 15046872184
354 15226088417
355 15406910482
356 15589370660
357 15773466850
358 15959192105
359 16146581576
360 16335661888
361 16526363332
362 16718781449
363 16912908662
364 17108738636
365 17306258294
366 17505518641
367 17706504308
368 17909275568
369 18113783976
370 18320057793
371 18528095418
372 18737932060
373 18949538442
374 19162990041
375 19378245056
376 19595315760
377 19814216332
378 20034984521
379 20257578198
380 20482085708
381 20708456894
382 20936737409
383 21166940724
384 21399095920
385 21633144064
386 21869116337
387 22107054938
388 22346952260
389 22588818138
390 22832703865
391 23078530768
392 23326376952
393 23576215836
394 23828096873
395 24082027798
396 24338018076
397 24596017830
398 24856127729
399 25118335540
400 25382614616
401 25648961368
402 25917469761
403 26188092210
404 26460873604
405 26735801450
406 27012865161
407 27292089400
408 27573518984
409 27857100036
410 28142945385
411 28430996862
412 28721298532
413 29013842782
414 29308655521
415 29605696396
416 29905032320
417 30206631840
418 30510544337
419 30816757322
420 31125339036
421 31436186450
422 31749439945
423 32065078144
424 32383096376
425 32703498276
426 33026295065
427 33351490926
428 33679125780
429 34009196166
430 34341694433
431 34676634372
432 35014090032
433 35353977360
434 35696415201
435 36041350290
436 36388789124
437 36738765850
438 37091315433
439 37446404256
440 37804111544
441 38164352324
442 38527176281
443 38892603206
444 39260715332
445 39631431478
446 40004823553
447 40380900228
448 40759664464
449 41141074136
450 41525242065
451 41912063306
452 42301640364
453 42693963922
454 43089058729
455 43486938184
456 43887567584
457 44290933676
458 44697165017
459 45106230854
460 45518110252
461 45932791830
462 46350390353
463 46770800052
464 47194158712
465 47620401408
466 48049537569
467 48481623698
468 48916711148
469 49354688770
470 49795660265
471 50239601568
472 50686557000
473 51136515884
474 51589519977
475 52045539262
476 52504605860
477 52966695102
478 53431865217
479 53900146596
480 54371585200
481 54846058152
482 55323698865
483 55804514586
484 56288479228
485 56775598834
486 57265938505
487 57759451896
488 58256254016
489 58756274052
490 59259559641
491 59766059750
492 60275897068
493 60788974758
494 61305388273
495 61825100788
496 62348099416
497 62874436304
498 63404172401
499 63937269250
500 64473834932
501 65013767594
502 65557148201
503 66103987928
504 66654337304
505 67208051436
506 67765275161
507 68325983822
508 68890205236
509 69457958654
510 70029320849
511 70604163092
512 71182606216
513 71764627528
514 72350234913
515 72939492530
516 73532411580
517 74128926826
518 74729131801
519 75332995848
520 75940570088
521 76551782628
522 77166790969
523 77785489078
524 78408010220
525 79034304902
526 79664318705
527 80298157436
528 80935843032
529 81577276752
530 82222629105
531 82871826498
532 83524914068
533 84181852554
534 84842756313
535 85507571920
536 86176366512
537 86849108020
538 87525855753
539 88206616214
540 88891379212
541 89580052158
542 90272853521
543 90969742396
544 91670724704
545 92375746248
546 93084897969
547 93798078730
548 94515477276
549 95237032626
550 95962757001
551 96692613168
552 97426703088
553 98164942444
554 98907463529
555 99654269774
556 100405314204
557 101160652414
558 101920362145
559 102684330572
560 103452667440
561 104225256872
562 105002202945
563 105783579410
564 106569449092
565 107359682378
566 108154385705
567 108953570552
568 109757186024
569 110565268124
570 111377934873
571 112195021534
572 113016729148
573 113842936966
574 114673739617
575 115509104260
576 116349085904
577 117193607104
578 118042868369
579 118896806370
580 119755451740
581 120618727370
582 121486761449
583 122359499048
584 123237023576
585 124119290212
586 125006266569
587 125898072782
588 126794791716
589 127696234806
590 128602577153
591 129513764444
592 130429870800
593 131350845680
594 132276834433
595 133207670882
596 134143444068
597 135084202410
598 136029983545
599 136980760144
600 137936657928
601 138897477036
602 139863472361
603 140834535654
604 141810709724
605 142792022782
606 143778468033
607 144770040884
608 145766885688
609 146768878856
610 147776047169
611 148788416146
612 149806081076
613 150828914210
614 151857139705
615 152890713080
616 153929570560
617 154973683796
618 156023265721
619 157078200358
620 158138631908
621 159204408334
622 160275602545
623 161352292668
624 162434495456
625 163522071664
626 164615200241
627 165713893810
628 166818109708
629 167927893922
630 169043324041
631 170164206160
632 171290845008
633 172423125084
634 173561119561
635 174704846270
636 175854312836
637 177009426142
638 178170282033
639 179336871244
640 180509245872
641 181687334544
642 182871356385
643 184061182562
644 185256971236
645 186458556066
646 187666002473
647 188879337920
648 190098711872
649 191323922852
650 192555189161
651 193792399798
652 195035599804
653 196284861078
654 197540309601
655 198801804460
656 200069438400
657 201343157608
658 202623007873
659 203908981690
660 205201239028
661 206499517218
662 207804139001
663 209115047704
664 210432177504
665 211755574364
666 213085240889
667 214421163270
668 215763491788
669 217112197822
670 218467321697
671 219828807724
672 221196766648
673 222571012472
674 223951850865
675 225339225706
676 226733045228
677 228133359730
678 229540353001
679 230953872104
680 232374037104
681 233800690964
682 235234026761
683 236673984174
684 238120745756
685 239574066510
686 241034150417
687 242500959236
688 243974572280
689 245454921256
690 246942125377
691 248436019058
692 249936886148
693 251444623114
694 252959149017
695 254480624120
696 256009072176
697 257544353572
698 259086674857
699 260636027414
700 262192417892
701 263755693094
702 265326144945
703 266903568084
704 268488174504
705 270079837528
706 271678615681
707 273284631306
708 274897906228
709 276518305818
710 278146083737
711 279781077176
712 281423348592
713 283072903596
714 284729836105
715 286393966158
716 288065430828
717 289744292990
718 291430614097
719 293124418436
720 294825783856
721 296534401752
722 298250590913
723 299974321634
724 301705642500
725 303444535018
726 305191016697
727 306945004272
728 308706756944
729 310476033012
730 312252994937
731 314037621278
732 315830053652
733 317630138350
734 319438126481
735 321253953476
736 323077469704
737 324908750128
738 326747981089
739 328595001242
740 330450078420
741 332312995722
742 334183839769
743 336062624216
744 337949570512
745 339844401092
746 341747346025
747 343658413222
748 345577573372
749 347504752438
750 349440142337
751 351383554532
752 353335296976
753 355295203096
754 357263394321
755 359239803330
756 361224538692
757 363217385050
758 365218715769
759 367228467776
760 369246541696
761 371272892316
762 373307829881
763 375351174814
764 377403058572
765 379463436342
766 381532205937
767 383609589116
768 385695599240
769 387790054256
770 389893285857
771 392004982418
772 394125401204
773 396254509538
774 398392479193
775 400539073768
776 402694424240
777 404858527020
778 407031364281
779 409213071030
780 411403700508
781 413602963350
782 415811225153
783 418028395476
784 420254519864
785 422489526568
786 424733627473
787 426986723466
788 429249050196
789 431520461234
790 433801032697
791 436090673272
792 438389517840
793 440697315964
794 443014408969
795 445340793406
796 447676374060
797 450021224294
798 452375522673
799 454738960340
800 457111849904
801 459493962400
802 461885492017
803 464286513050
804 466697079196
805 469117005570
806 471546381865
807 473985256920
808 476433757872
809 478891798036
810 481359602393
811 483836830510
812 486323878292
813 488820510134
814 491326898561
815 493842986764
816 496368891776
817 498904384040
818 501449788289
819 504005104458
820 506570166452
821 509145022530
822 511729980201
823 514324827584
824 516929821552
825 519544789804
826 522169631977
827 524804482166
828 527449582636
829 530104582318
830 532769885937
831 535445280468
832 538130898640
833 540826614936
834 543532579265
835 546248730666
836 548975235804
837 551711928018
838 554458925689
839 557216346888
840 559984320224
841 562762367692
842 565551043241
843 568350277198
844 571160065892
845 573980370118
846 576811231137
847 579652536332
848 582504452608
849 585366930896
850 588240131377
851 591123895730
852 594018468724
853 596923648746
854 599839782969
855 602766643176
856 605704180696
857 608652531764
858 611611950313
859 614582063814
860 617563285388
861 620555339982
862 623558324065
863 626572382892
864 629597656616
865 632633763040
866 635681044705
867 638739517962
868 641809130836
869 644889790026
870 647981747353
871 651084727912
872 654199075248
873 657324679524
874 660461611513
875 663609853398
876 666769423932
877 669940266422
878 673122738609
879 676316727876
880 679522246528
881 682739033416
882 685967542097
883 689207407834
884 692459081108
885 695722268098
886 698997032105
887 702283575368
888 705582005936
889 708891986740
890 712213814505
891 715547371774
892 718892652460
893 722249791286
894 725618901793
895 728999835060
896 732392764776
897 735797481680
898 739214123281
899 742642834466
900 746083719876
901 749536354530
902 753001238233
903 756478247112
904 759967376008
905 763468679540
906 766982327273
907 770508162790
908 774046500196
909 777597138638
910 781160112609
911 784735200372
912 788322907072
913 791922802832
914 795535279217
915 799160322066
916 802797796028
917 806447803346
918 810110476313
919 813785544144
920 817473448784
921 821173804292
922 824886911497
923 828612796790
924 832351541476
925 836102727558
926 839866735569
927 843643672060
928 847433483520
929 851236111584
930 855051891825
931 858880397066
932 862721924036
933 866576477370
934 870444153641
935 874324974280
936 878218824152
937 882125503356
938 886045574137
939 889978810166
940 893925359268
941 897885016094
942 901858179825
943 905844574348
944 909844428952
945 913857568816
946 917883864161
947 921923562778
948 925976975340
949 930043726682
950 934124142249
951 938217969056
952 942325467016
953 946446382708
954 950581194329
955 954729543334
956 958891714788
957 963067642550
958 967257271729
959 971460801516
960 975678237384
961 979909178600
962 984154249553
963 988413207578
964 992686153908
965 996973104010
966 1001274160377
967 1005589023864
968 1009918217592
969 1014261396468
970 1018618668137
971 1022990061022
972 1027375904892
973 1031775770158
974 1036190037841
975 1040618696532
976 1045061515064
977 1049518627328
978 1053990393761
979 1058476496938
980 1062977177668
981 1067492066290
982 1072021509817
983 1076565587480
984 1081124475392
985 1085697720812
986 1090285700617
987 1094888300598
988 1099505515340
989 1104137310798
990 1108784034481
991 1113445217020
992 1118121518976
993 1122812639376
994 1127518768929
995 1132239808330
996 1136975939764
997 1141726929802
998 1146493216825
999 1151274671424
1000 1156071168968