1 0
2 0
3 24
4 126
5 387
6 915
7 1845
8 3339
9 5586
10 8802
11 13230
12 19140
13 26829
14 36621
15 48867
16 63945
17 82260
18 104244
19 130356
20 161082
21 196935
22 238455
23 286209
24 340791
25 402822
26 472950
27 551850
28 640224
29 738801
30 848337
31 969615
32 1103445
33 1250664
34 1412136
35 1588752
36 1781430
37 1991115
38 2218779
39 2465421
40 2732067
41 3019770
42 3329610
43 3662694
44 4020156
45 4403157
46 4812885
47 5250555
48 5717409
49 6214716
50 6743772
51 7305900
52 7902450
53 8534799
54 9204351
55 9912537
56 10660815
57 11450670
58 12283614
59 13161186
60 14084952
61 15056505
62 16077465
63 17149479
64 18274221
65 19453392
66 20688720
67 21981960
68 23334894
69 24749331
70 26227107
71 27770085
72 29380155
73 31059234
74 32809266
75 34632222
76 36530100
77 38504925
78 40558749
79 42693651
80 44911737
81 47215140
82 49606020
83 52086564
84 54658986
85 57325527
86 60088455
87 62950065
88 65912679
89 68978646
90 72150342
91 75430170
92 78820560
93 82323969
94 85942881
95 89679807
96 93537285
97 97517880
98 101624184
99 105858816
100 110224422
101 114723675
102 119359275
103 124133949
104 129050451
105 134111562
106 139320090
107 144678870
108 150190764
109 155858661
110 161685477
111 167674155
112 173827665
113 180149004
114 186641196
115 193307292
116 200150370
117 207173535
118 214379919
119 221772681
120 229355007
121 237130110
122 245101230
123 253271634
124 261644616
125 270223497
126 279011625
127 288012375
128 297229149
129 306665376
130 316324512
131 326210040
132 336325470
133 346674339
134 357260211
135 368086677
136 379157355
137 390475890
138 402045954
139 413871246
140 425955492
141 438302445
142 450915885
143 463799619
144 476957481
145 490393332
146 504111060
147 518114580
148 532407834
149 546994791
150 561879447
151 577065825
152 592557975
153 608359974
154 624475926
155 640909962
156 657666240
157 674748945
158 692162289
159 709910511
160 727997877
161 746428680
162 765207240
163 784337904
164 803825046
165 823673067
166 843886395
167 864469485
168 885426819
169 906762906
170 928482282
171 950589510
172 973089180
173 995985909
174 1019284341
175 1042989147
176 1067105025
177 1091636700
178 1116588924
179 1141966476
180 1167774162
181 1194016815
182 1220699295
183 1247826489
184 1275403311
185 1303434702
186 1331925630
187 1360881090
188 1390306104
189 1420205721
190 1450585017
191 1481449095
192 1512803085
193 1544652144
194 1577001456
195 1609856232
196 1643221710
197 1677103155
198 1711505859
199 1746435141
200 1781896347
201 1817894850
202 1854436050
203 1891525374
204 1929168276
205 1967370237
206 2006136765
207 2045473395
208 2085385689
209 2125879236
210 2166959652
211 2208632580
212 2250903690
213 2293778679
214 2337263271
215 2381363217
216 2426084295
217 2471432310
218 2517413094
219 2564032506
220 2611296432
221 2659210785
222 2707781505
223 2757014559
224 2806915941
225 2857491672
226 2908747800
227 2960690400
228 3013325574
229 3066659451
230 3120698187
231 3175447965
232 3230914995
233 3287105514
234 3344025786
235 3401682102
236 3460080780
237 3519228165
238 3579130629
239 3639794571
240 3701226417
241 3763432620
242 3826419660
243 3890194044
244 3954762306
245 4020131007
246 4086306735
247 4153296105
248 4221105759
249 4289742366
250 4359212622
251 4429523250
252 4500681000
253 4572692649
254 4645565001
255 4719304887
256 4793919165
257 4869414720
258 4945798464
259 5023077336
260 5101258302
261 5180348355
262 5260354515
263 5341283829
264 5423143371
265 5505940242
266 5589681570
267 5674374510
268 5760026244
269 5846643981
270 5934234957
271 6022806435
272 6112365705
273 6202920084
274 6294476916
275 6387043572
276 6480627450
277 6575235975
278 6670876599
279 6767556801
280 6865284087
281 6964065990
282 7063910070
283 7164823914
284 7266815136
285 7369891377
286 7474060305
287 7579329615
288 7685707029
289 7793200296
290 7901817192
291 8011565520
292 8122453110
293 8234487819
294 8347677531
295 8462030157
296 8577553635
297 8694255930
298 8812145034
299 8931228966
300 9051515772
301 9173013525
302 9295730325
303 9419674299
304 9544853601
305 9671276412
306 9798950940
307 9927885420
308 10058088114
309 10189567311
310 10322331327
311 10456388505
312 10591747215
313 10728415854
314 10866402846
315 11005716642
316 11146365720
317 11288358585
318 11431703769
319 11576409831
320 11722485357
321 11869938960
322 12018779280
323 12169014984
324 12320654766
325 12473707347
326 12628181475
327 12784085925
328 12941429499
329 13100221026
330 13260469362
331 13422183390
332 13585372020
333 13750044189
334 13916208861
335 14083875027
336 14253051705
337 14423747940
338 14595972804
339 14769735396
340 14945044842
341 15121910295
342 15300340935
343 15480345969
344 15661934631
345 15845116182
346 16029899910
347 16216295130
348 16404311184
349 16593957441
350 16785243297
351 16978178175
352 17172771525
353 17369032824
354 17566971576
355 17766597312
356 17967919590
357 18170947995
358 18375692139
359 18582161661
360 18790366227
361 19000315530
362 19212019290
363 19425487254
364 19640729196
365 19857754917
366 20076574245
367 20297197035
368 20519633169
369 20743892556
370 20969985132
371 21197920860
372 21427709730
373 21659361759
374 21892886991
375 22128295497
376 22365597375
377 22604802750
378 22845921774
379 23088964626
380 23333941512
381 23580862665
382 23829738345
383 24080578839
384 24333394461
385 24588195552
386 24844992480
387 25103795640
388 25364615454
389 25627462371
390 25892346867
391 26159279445
392 26428270635
393 26699330994
394 26972471106
395 27247701582
396 27525033060
397 27804476205
398 28086041709
399 28369740291
400 28655582697
401 28943579700
402 29233742100
403 29526080724
404 29820606426
405 30117330087
406 30416262615
407 30717414945
408 31020798039
409 31326422886
410 31634300502
411 31944441930
412 32256858240
413 32571560529
414 32888559921
415 33207867567
416 33529494645
417 33853452360
418 34179751944
419 34508404656
420 34839421782
421 35172814635
422 35508594555
423 35846772909
424 36187361091
425 36530370522
426 36875812650
427 37223698950
428 37574040924
429 37926850101
430 38282138037
431 38639916315
432 39000196545
433 39362990364
434 39728309436
435 40096165452
436 40466570130
437 40839535215
438 41215072479
439 41593193721
440 41973910767
441 42357235470
442 42743179710
443 43131755394
444 43522974456
445 43916848857
446 44313390585
447 44712611655
448 45114524109
449 45519140016
450 45926471472
451 46336530600
452 46749329550
453 47164880499
454 47583195651
455 48004287237
456 48428167515
457 48854848770
458 49284343314
459 49716663486
460 50151821652
461 50589830205
462 51030701565
463 51474448179
464 51921082521
465 52370617092
466 52823064420
467 53278437060
468 53736747594
469 54198008631
470 54662232807
471 55129432785
472 55599621255
473 56072810934
474 56549014566
475 57028244922
476 57510514800
477 57995837025
478 58484224449
479 58975689951
480 59470246437
481 59967906840
482 60468684120
483 60972591264
484 61479641286
485 61989847227
486 62503222155
487 63019779165
488 63539531379
489 64062491946
490 64588674042
491 65118090870
492 65650755660
493 66186681669
494 66725882181
495 67268370507
496 67814159985
497 68363263980
498 68915695884
499 69471469116
500 70030597122
501 70593093375
502 71158971375
503 71728244649
504 72300926751
505 72877031262
506 73456571790
507 74039561970
508 74626015464
509 75215945961
510 75809367177
511 76406292855
512 77006736765
513 77610712704
514 78218234496
515 78829315992
516 79443971070
517 80062213635
518 80684057619
519 81309516981
520 81938605707
521 82571337810
522 83207727330
523 83847788334
524 84491534916
525 85138981197
526 85790141325
527 86445029475
528 87103659849
529 87766046676
530 88432204212
531 89102146740
532 89775888570
533 90453444039
534 91134827511
535 91820053377
536 92509136055
537 93202089990
538 93898929654
539 94599669546
540 95304324192
541 96012908145
542 96725435985
543 97441922319
544 98162381781
545 98886829032
546 99615278760
547 100347745680
548 101084244534
549 101824790091
550 102569397147
551 103318080525
552 104070855075
553 104827735674
554 105588737226
555 106353874662
556 107123162940
557 107896617045
558 108674251989
559 109456082811
560 110242124577
561 111032392380
562 111826901340
563 112625666604
564 113428703346
565 114236026767
566 115047652095
567 115863594585
568 116683869519
569 117508492206
570 118337477982
571 119170842210
572 120008600280
573 120850767609
574 121697359641
575 122548391847
576 123403879725
577 124263838800
578 125128284624
579 125997232776
580 126870698862
581 127748698515
582 128631247395
583 129518361189
584 130410055611
585 131306346402
586 132207249330
587 133112780190
588 134022954804
589 134937789021
590 135857298717
591 136781499795
592 137710408185
593 138644039844
594 139582410756
595 140525536932
596 141473434410
597 142426119255
598 143383607559
599 144345915441
600 145313059047
601 146285054550
602 147261918150
603 148243666074
604 149230314576
605 150221879937
606 151218378465
607 152219826495
608 153226240389
609 154237636536
610 155254031352
611 156275441280
612 157301882790
613 158333372379
614 159369926571
615 160411561917
616 161458294995
617 162510142410
618 163567120794
619 164629246806
620 165696537132
621 166769008485
622 167846677605
623 168929561259
624 170017676241
625 171111039372
626 172209667500
627 173313577500
628 174422786274
629 175537310751
630 176657167887
631 177782374665
632 178912948095
633 180048905214
634 181190263086
635 182337038802
636 183489249480
637 184646912265
638 185810044329
639 186978662871
640 188152785117
641 189332428320
642 190517609760
643 191708346744
644 192904656606
645 194106556707
646 195314064435
647 196527197205
648 197745972459
649 198970407666
650 200200520322
651 201436327950
652 202677848100
653 203925098349
654 205178096301
655 206436859587
656 207701405865
657 208971752820
658 210247918164
659 211529919636
660 212817775002
661 214111502055
662 215411118615
663 216716642529
664 218028091671
665 219345483942
666 220668837270
667 221998169610
668 223333498944
669 224674843281
670 226022220657
671 227375649135
672 228735146805
673 230100731784
674 231472422216
675 232850236272
676 234234192150
677 235624308075
678 237020602299
679 238423093101
680 239831798787
681 241246737690
682 242667928170
683 244095388614
684 245529137436
685 246969193077
686 248415574005
687 249868298715
688 251327385729
689 252792853596
690 254264720892
691 255743006220
692 257227728210
693 258718905519
694 260216556831
695 261720700857
696 263231356335
697 264748542030
698 266272276734
699 267802579266
700 269339468472
701 270882963225
702 272433082425
703 273989844999
704 275553269901
705 277123376112
706 278700182640
707 280283708520
708 281873972814
709 283470994611
710 285074793027
711 286685387205
712 288302796315
713 289927039554
714 291558136146
715 293196105342
716 294840966420
717 296492738685
718 298151441469
719 299817094131
720 301489716057
721 303169326660
722 304855945380
723 306549591684
724 308250285066
725 309958045047
726 311672891175
727 313394843025
728 315123920199
729 316860142326
730 318603529062
731 320354100090
732 322111875120
733 323876873889
734 325649116161
735 327428621727
736 329215410405
737 331009502040
738 332810916504
739 334619673696
740 336435793542
741 338259295995
742 340090201035
743 341928528669
744 343774298931
745 345627531882
746 347488247610
747 349356466230
748 351232207884
749 353115492741
750 355006340997
751 356904772875
752 358810808625
753 360724468524
754 362645772876
755 364574742012
756 366511396290
757 368455756095
758 370407841839
759 372367673961
760 374335272927
761 376310659230
762 378293853390
763 380284875954
764 382283747496
765 384290488617
766 386305119945
767 388327662135
768 390358135869
769 392396561856
770 394442960832
771 396497353560
772 398559760830
773 400630203459
774 402708702291
775 404795278197
776 406889952075
777 408992744850
778 411103677474
779 413222770926
780 415350046212
781 417485524365
782 419629226445
783 421781173539
784 423941386761
785 426109887252
786 428286696180
787 430471834740
788 432665324154
789 434867185671
790 437077440567
791 439296110145
792 441523215735
793 443758778694
794 446002820406
795 448255362282
796 450516425760
797 452786032305
798 455064203409
799 457350960591
800 459646325397
801 461950319400
802 464262964200
803 466584281424
804 468914292726
805 471253019787
806 473600484315
807 475956708045
808 478321712739
809 480695520186
810 483078152202
811 485469630630
812 487869977340
813 490279214229
814 492697363221
815 495124446267
816 497560485345
817 500005502460
818 502459519644
819 504922558956
820 507394642482
821 509875792335
822 512366030655
823 514865379609
824 517373861391
825 519891498222
826 522418312350
827 524954326050
828 527499561624
829 530054041401
830 532617787737
831 535190823015
832 537773169645
833 540364850064
834 542965886736
835 545576302152
836 548196118830
837 550825359315
838 553464046179
839 556112202021
840 558769849467
841 561437011170
842 564113709810
843 566799968094
844 569495808756
845 572201254557
846 574916328285
847 577641052755
848 580375450809
849 583119545316
850 585873359172
851 588636915300
852 591410236650
853 594193346199
854 596986266951
855 599789021937
856 602601634215
857 605424126870
858 608256523014
859 611098845786
860 613951118352
861 616813363905
862 619685605665
863 622567866879
864 625460170821
865 628362540792
866 631275000120
867 634197572160
868 637130280294
869 640073147931
870 643026198507
871 645989455485
872 648962942355
873 651946682634
874 654940699866
875 657945017622
876 660959659500
877 663984649125
878 667020010149
879 670065766251
880 673121941137
881 676188558540
882 679265642220
883 682353215964
884 685451303586
885 688559928927
886 691679115855
887 694808888265
888 697949270079
889 701100285246
890 704261957742
891 707434311570
892 710617370760
893 713811159369
894 717015701481
895 720231021207
896 723457142685
897 726694090080
898 729941887584
899 733200559416
900 736470129822
901 739750623075
902 743042063475
903 746344475349
904 749657883051
905 752982310962
906 756317783490
907 759664325070
908 763021960164
909 766390713261
910 769770608877
911 773161671555
912 776563925865
913 779977396404
914 783402107796
915 786838084692
916 790285351770
917 793743933735
918 797213855319
919 800695141281
920 804187816407
921 807691905510
922 811207433430
923 814734425034
924 818272905216
925 821822898897
926 825384431025
927 828957526575
928 832542210549
929 836138507976
930 839746443912
931 843366043440
932 846997331670
933 850640333739
934 854295074811
935 857961580077
936 861639874755
937 865329984090
938 869031933354
939 872745747846
940 876471452892
941 880209073845
942 883958636085
943 887720165019
944 891493686081
945 895279224732
946 899076806460
947 902886456780
948 906708201234
949 910542065391
950 914388074847
951 918246255225
952 922116632175
953 925999231374
954 929894078526
955 933801199362
956 937720619640
957 941652365145
958 945596461689
959 949552935111
960 953521811277
961 957503116080
962 961496875440
963 965503115304
964 969521861646
965 973553140467
966 977596977795
967 981653399685
968 985722432219
969 989804101506
970 993898433682
971 998005454910
972 1002125191380
973 1006257669309
974 1010402914941
975 1014560954547
976 1018731814425
977 1022915520900
978 1027112100324
979 1031321579076
980 1035543983562
981 1039779340215
982 1044027675495
983 1048289015889
984 1052563387911
985 1056850818102
986 1061151333030
987 1065464959290
988 1069791723504
989 1074131652321
990 1078484772417
991 1082851110495
992 1087230693285
993 1091623547544
994 1096029700056
995 1100449177632
996 1104882007110
997 1109328215355
998 1113787829259
999 1118260875741
1000 1122747381747