1 0
2 9
3 116
4 670
5 2580
6 7735
7 19544
8 43596
9 88440
10 166485
11 295020
12 497354
13 804076
14 1254435
15 1897840
16 2795480
17 4022064
18 5667681
19 7839780
20 10665270
21 14292740
22 18894799
23 24670536
24 31848100
25 40687400
26 51482925
27 64566684
28 80311266
29 99133020
30 121495355
31 147912160
32 178951344
33 215238496
34 257460665
35 306370260
36 362789070
37 427612404
38 501813351
39 586447160
40 682655740
41 791672280
42 914825989
43 1053546956
44 1209371130
45 1383945420
46 1579032915
47 1796518224
48 2038412936
49 2306861200
50 2604145425
51 2932692100
52 3295077734
53 3694034916
54 4132458495
55 4613411880
56 5140133460
57 5716043144
58 6344749021
59 7030054140
60 7775963410
61 8586690620
62 9466665579
63 10420541376
64 11453201760
65 12569768640
66 13775609705
67 15076346164
68 16477860606
69 17986304980
70 19608108695
71 21349986840
72 23218948524
73 25222305336
74 27367679925
75 29663014700
76 32116580650
77 34736986284
78 37533186691
79 40514492720
80 43690580280
81 47071499760
82 50667685569
83 54489965796
84 58549571990
85 62858149060
86 67427765295
87 72270922504
88 77400566276
89 82830096360
90 88573377165
91 94644748380
92 101059035714
93 107831561756
94 114978156955
95 122515170720
96 130459482640
97 138828513824
98 147640238361
99 156913194900
100 166666498350
101 176919851700
102 187693557959
103 199008532216
104 210886313820
105 223349078680
106 236419651685
107 250121519244
108 264478841946
109 279516467340
110 295259942835
111 311735528720
112 328970211304
113 346991716176
114 365828521585
115 385509871940
116 406065791430
117 427527097764
118 449925416031
119 473293192680
120 497663709620
121 523071098440
122 549550354749
123 577137352636
124 605868859250
125 635782549500
126 666917020875
127 699311808384
128 733007399616
129 768045249920
130 804467797705
131 842318479860
132 881641747294
133 922483080596
134 964889005815
135 1008907110360
136 1054586059020
137 1101975610104
138 1151126631701
139 1202091118060
140 1254922206090
141 1309674191980
142 1366402547939
143 1425163939056
144 1486016240280
145 1549018553520
146 1614231224865
147 1681715861924
148 1751535351286
149 1823753876100
150 1898436933775
151 1975651353800
152 2055465315684
153 2137948367016
154 2223171441645
155 2311206877980
156 2402128437410
157 2496011322844
158 2592932197371
159 2692969203040
160 2796201979760
161 2902711684320
162 3012581009529
163 3125894203476
164 3242737088910
165 3363197082740
166 3487363215655
167 3615326151864
168 3747178208956
169 3883013377880
170 4022927343045
171 4167017502540
172 4315382988474
173 4468124687436
174 4625345261075
175 4787149166800
176 4953642678600
177 5124933907984
178 5301132825041
179 5482351279620
180 5668703022630
181 5860303727460
182 6057271011519
183 6259724457896
184 6467785637140
185 6681578129160
186 6901227545245
187 7126861550204
188 7358609884626
189 7596604387260
190 7840979017515
191 8091869878080
192 8349415237664
193 8613755553856
194 8885033496105
195 9163393968820
196 9448984134590
197 9741953437524
198 10042453626711
199 10350638779800
200 10666665326700
201 10990692073400
202 11322880225909
203 11663393414316
204 12012397716970
205 12370061684780
206 12736556365635
207 13112055328944
208 13496734690296
209 13890773136240
210 14294351949185
211 14707655032420
212 15130868935254
213 15564182878276
214 16007788778735
215 16461881276040
216 16926657757380
217 17402318383464
218 17889066114381
219 18387106735580
220 18896648883970
221 19417904074140
222 19951086724699
223 20496414184736
224 21054106760400
225 21624387741600
226 22207483428825
227 22803623160084
228 23413039337966
229 24035967456820
230 24672646130055
231 25323317117560
232 25988225353244
233 26667618972696
234 27361749340965
235 28070871080460
236 28795242098970
237 29535123617804
238 30290780200051
239 31062479778960
240 31850493686440
241 32655096681680
242 33476566979889
243 34315186281156
244 35171239799430
245 36045016291620
246 36936808086815
247 37846911115624
248 38775624939636
249 39723252781000
250 40690101552125
251 41676481885500
252 42682708163634
253 43709098549116
254 44755975014795
255 45823663374080
256 46912493311360
257 48022798412544
258 49154916195721
259 50309188141940
260 51485959726110
261 52685580448020
262 53908403863479
263 55154787615576
264 56425093466060
265 57719687326840
266 59038939291605
267 60383223667564
268 61752919007306
269 63148408140780
270 64570078207395
271 66018320688240
272 67493531438424
273 68996110719536
274 70526463232225
275 72084998148900
276 73672129146550
277 75288274439684
278 76933856813391
279 78609303656520
280 80315046994980
281 82051523525160
282 83819174647469
283 85618446499996
284 87449789992290
285 89313660839260
286 91210519595195
287 93140831687904
288 95105067452976
289 97103702168160
290 99137216087865
291 101206094477780
292 103310827649614
293 105451910995956
294 107629845025255
295 109845135396920
296 112098292956540
297 114389833771224
298 116720279165061
299 119090155754700
300 121499995485050
301 123950335665100
302 126441719003859
303 128974693646416
304 131549813210120
305 134167636820880
306 136828729149585
307 139533660448644
308 142283006588646
309 145077349095140
310 147917275185535
311 150803377806120
312 153736255669204
313 156716513290376
314 159744761025885
315 162821615110140
316 165947697693330
317 169123636879164
318 172350066762731
319 175627627468480
320 178956965188320
321 182338732219840
322 185773587004649
323 189262194166836
324 192805224551550
325 196403355263700
326 200057269706775
327 203767657621784
328 207535215126316
329 211360644753720
330 215244655492405
331 219187962825260
332 223191288769194
333 227255361914796
334 231380917466115
335 235568697280560
336 239819449908920
337 244133930635504
338 248512901518401
339 252957131429860
340 257467396096790
341 262044478141380
342 266689167121839
343 271402259573256
344 276184559048580
345 281036876159720
346 285960028618765
347 290954841279324
348 296022146177986
349 301162782575900
350 306377597000475
351 311667443287200
352 317033182621584
353 322475683581216
354 327995822177945
355 333594481900180
356 339272553755310
357 345030936312244
358 350870535744071
359 356792265870840
360 362797048202460
361 368885811981720
362 375059494227429
363 381319039777676
364 387665401333210
365 394099539500940
366 400622422837555
367 407235027893264
368 413938339255656
369 420733349593680
370 427621059701745
371 434602478543940
372 441678623298374
373 448850519401636
374 456119200593375
375 463485708961000
376 470951094984500
377 478516417581384
378 486182744151741
379 493951150623420
380 501822721497330
381 509798549892860
382 517879737593419
383 526067395092096
384 534362641637440
385 542766605279360
386 551280422915145
387 559905240335604
388 568642212271326
389 577492502439060
390 586457283588215
391 595537737547480
392 604735055271564
393 614050436888056
394 623485091744405
395 633040238455020
396 642717104948490
397 652516928514924
398 662440955853411
399 672490443119600
400 682666655973400
401 692970869626800
402 703404368891809
403 713968448228516
404 724664411793270
405 735493573486980
406 746457257003535
407 757556795878344
408 768793533536996
409 780168823344040
410 791684028651885
411 803340522849820
412 815139689413154
413 827082921952476
414 839171624263035
415 851407210374240
416 863791104599280
417 876324741584864
418 889009566361081
419 901847034391380
420 914838611622670
421 927985774535540
422 941290010194599
423 954752816298936
424 968375701232700
425 982160184115800
426 996107794854725
427 1010220074193484
428 1024498573764666
429 1038944856140620
430 1053560494884755
431 1068347074602960
432 1083306190995144
433 1098439450906896
434 1113748472381265
435 1129234884710660
436 1144900328488870
437 1160746455663204
438 1176774929586751
439 1192987425070760
440 1209385628437140
441 1225971237571080
442 1242745961973789
443 1259711522815356
444 1276869652987730
445 1294222097157820
446 1311770611820715
447 1329516965353024
448 1347462938066336
449 1365610322260800
450 1383960922278825
451 1402516554558900
452 1421279047689534
453 1440250242463316
454 1459431991931095
455 1478826161456280
456 1498434628769260
457 1518259284021944
458 1538302029842421
459 1558564781389740
460 1579049466408810
461 1599758025285420
462 1620692411101379
463 1641854589689776
464 1663246539690360
465 1684870252605040
466 1706727732853505
467 1728820997828964
468 1751152077954006
469 1773723016736580
470 1796535870826095
471 1819592710069640
472 1842895617568324
473 1866446689733736
474 1890248036344525
475 1914301780603100
476 1938610059192450
477 1963175022333084
478 1987998833840091
479 2013083671180320
480 2038431725529680
481 2064045201830560
482 2089926318849369
483 2116077309234196
484 2142500419572590
485 2169197910449460
486 2196172056505095
487 2223425146493304
488 2250959483339676
489 2278777384199960
490 2306881180518565
491 2335273218087180
492 2363955857103514
493 2392931472230156
494 2422202452653555
495 2451771202143120
496 2481640139110440
497 2511811696668624
498 2542288322691761
499 2573072479874500
500 2604166645791750
501 2635573312958500
502 2667294988889759
503 2699334196160616
504 2731693472466420
505 2764375370683080
506 2797382458927485
507 2830717320618044
508 2864382554535346
509 2898380774882940
510 2932714611348235
511 2967386709163520
512 3002399729167104
513 3037756347864576
514 3073459257490185
515 3109511166068340
516 3145914797475230
517 3182672891500564
518 3219788203909431
519 3257263506504280
520 3295101587187020
521 3333305250021240
522 3371877315294549
523 3410820619581036
524 3450138015803850
525 3489832373297900
526 3529906577872675
527 3570363531875184
528 3611206154253016
529 3652437380617520
530 3694060163307105
531 3736077471450660
532 3778492291031094
533 3821307624948996
534 3864526493086415
535 3908151932370760
536 3952186996838820
537 3996634757700904
538 4041498303405101
539 4086780739701660
540 4132485189707490
541 4178614793970780
542 4225172710535739
543 4272162115007456
544 4319586200616880
545 4367448178285920
546 4415751276692665
547 4464498742336724
548 4513693839604686
549 4563339850835700
550 4613440076387175
551 4663997834700600
552 4715016462367484
553 4766499314195416
554 4818449763274245
555 4870871201042380
556 4923767037353210
557 4977140700541644
558 5030995637490771
559 5085335313698640
560 5140163213345160
561 5195482839359120
562 5251297713485329
563 5307611376351876
564 5364427387537510
565 5421749325639140
566 5479580788339455
567 5537925392474664
568 5596786774102356
569 5656168588569480
570 5716074510580445
571 5776508234265340
572 5837473473248274
573 5898973960715836
574 5961013449485675
575 6023595712075200
576 6086724540770400
577 6150403747694784
578 6214637164878441
579 6279428644327220
580 6344782058092030
581 6410701298338260
582 6477190277415319
583 6544252927926296
584 6611893202797740
585 6680115075349560
586 6748922539365045
587 6818319609161004
588 6888310319658026
589 6958898726450860
590 7030088905878915
591 7101884955096880
592 7174290992145464
593 7247311156022256
594 7320949606752705
595 7395210525461220
596 7470098114442390
597 7545616597232324
598 7621770218680111
599 7698563245019400
600 7775999963940100
601 7854084684660200
602 7932821737997709
603 8012215476442716
604 8092270274229570
605 8172990527409180
606 8254380653921435
607 8336445093667744
608 8419188308583696
609 8502614782711840
610 8586729022274585
611 8671535555747220
612 8757038933931054
613 8843243730026676
614 8930154539707335
615 9017775981192440
616 9106112695321180
617 9195169345626264
618 9284950618407781
619 9375461222807180
620 9466705890881370
621 9558689377676940
622 9651416461304499
623 9744891943013136
624 9839120647265000
625 9934107421810000
626 10029857137760625
627 10126374689666884
628 10223664995591366
629 10321732997184420
630 10420583659759455
631 10520221972368360
632 10620652947877044
633 10721881623041096
634 10823913058581565
635 10926752339260860
636 11030404573958770
637 11134874895748604
638 11240168461973451
639 11346290454322560
640 11453246078907840
641 11561040566340480
642 11669679171807689
643 11779167175149556
644 11889509880936030
645 12000712618544020
646 12112780742234615
647 12225719631230424
648 12339534689793036
649 12454231347300600
650 12569815058325525
651 12686291302712300
652 12803665585655434
653 12921943437777516
654 13041130415207395
655 13161232099658480
656 13282254098507160
657 13404202044871344
658 13527081597689121
659 13650898441797540
660 13775658288011510
661 13901366873202820
662 14028029960379279
663 14155653338763976
664 14284242823874660
665 14413804257603240
666 14544343508295405
667 14675866470830364
668 14808379066700706
669 14941887244092380
670 15076396977964795
671 15211914270131040
672 15348445149338224
673 15485995671347936
674 15624571919016825
675 15764180002377300
676 15904826058718350
677 16046516252666484
678 16189256776266791
679 16333053849064120
680 16477913718184380
681 16623842658415960
682 16770846972291269
683 16918932990168396
684 17068107070312890
685 17218375598979660
686 17369744990494995
687 17522221687338704
688 17675812160226376
689 17830522908191760
690 17986360458669265
691 18143331367576580
692 18301442219397414
693 18460699627264356
694 18621110233041855
695 18782680707409320
696 18945417749944340
697 19109328089206024
698 19274418482818461
699 19440695717554300
700 19608166609418450
701 19776838003731900
702 19946716775215659
703 20117809828074816
704 20290124096082720
705 20463666542665280
706 20638444160985385
707 20814463974027444
708 20991733034682046
709 21170258425830740
710 21350047260430935
711 21531106681600920
712 21713443862705004
713 21897066007438776
714 22081980349914485
715 22268194154746540
716 22455714717137130
717 22644549362961964
718 22834705448856131
719 23026190362300080
720 23219011521705720
721 23413176376502640
722 23608692407224449
723 23805567125595236
724 24003808074616150
725 24203422828652100
726 24404418993518575
727 24606804206568584
728 24810586136779716
729 25015772484841320
730 25222370983241805
731 25430389396356060
732 25639835520532994
733 25850717184183196
734 26063042247866715
735 26276818604380960
736 26492054178848720
737 26708756928806304
738 26926934844291801
739 27146595947933460
740 27367748295038190
741 27590399973680180
742 27814559104789639
743 28040233842241656
744 28267432372945180
745 28496162916932120
746 28726433727446565
747 28958253091034124
748 29191629327631386
749 29426570790655500
750 29663085867093875
751 29901182977594000
752 30140870576553384
753 30382157152209616
754 30625051226730545
755 30869561356304580
756 31115696131231110
757 31363464176011044
758 31612874149437471
759 31863934744686440
760 32116654689407860
761 32371042745816520
762 32627107710783229
763 32884858415926076
764 33144303727701810
765 33405452547497340
766 33668313811721355
767 33932896491896064
768 34199209594749056
769 34467262162305280
770 34737063271979145
771 35008622036666740
772 35281947604838174
773 35557049160630036
774 35833935923937975
775 36112617150509400
776 36393102132036300
777 36675400196248184
778 36959520707005141
779 37245473064391020
780 37533266704806730
781 37822911101063660
782 38114415762477219
783 38407790234960496
784 38703044101118040
785 39000186980339760
786 39299228528894945
787 39600178440026404
788 39903046444044726
789 40207842308422660
790 40514575837889615
791 40823256874526280
792 41133895297859364
793 41446501024956456
794 41761084010521005
795 42077654246987420
796 42396221764616290
797 42716796631589724
798 43039388954106811
799 43364008876479200
800 43690666581226800
801 44019372289173600
802 44350136259543609
803 44682968790056916
804 45017880217025870
805 45354880915451380
806 45693981299119335
807 46035191820697144
808 46378522971830396
809 46723985283239640
810 47071589324817285
811 47421345705724620
812 47773265074488954
813 48127358119100876
814 48483635567111635
815 48842108185730640
816 49202786781923080
817 49565682202507664
818 49930805334254481
819 50298167103982980
820 50667778478660070
821 51039650465498340
822 51413794112054399
823 51790220506327336
824 52168940776857300
825 52549966092824200
826 52933307664146525
827 53318976741580284
828 53706984616818066
829 54097342622588220
830 54490062132754155
831 54885154562413760
832 55282631367998944
833 55682504047375296
834 56084784139941865
835 56489483226731060
836 56896612930508670
837 57306184915874004
838 57718210889360151
839 58132702599534360
840 58549671837098540
841 58969130434989880
842 59391090268481589
843 59815563255283756
844 60242561355644330
845 60672096572450220
846 61104180951328515
847 61538826580747824
848 61976045592119736
849 62415850159900400
850 62858252501692225
851 63303264878345700
852 63750899594061334
853 64201168996491716
854 64654085476843695
855 65109661469980680
856 65567909454525060
857 66028841952960744
858 66492471531735821
859 66958810801365340
860 67427872416534210
861 67899669076200220
862 68374213523697179
863 68851518546838176
864 69331596978018960
865 69814461694321440
866 70300125617617305
867 70788601714671764
868 71279902997247406
869 71774042522208180
870 72271033391623495
871 72770888752872440
872 73273621798748124
873 73779245767562136
874 74287773943249125
875 74799219655471500
876 75313596279724250
877 75830917237439884
878 76351195996093491
879 76874446069307920
880 77400681016959080
881 77929914445281360
882 78462160006973169
883 78997431401302596
884 79535742374213190
885 80077106718429860
886 80621538273564895
887 81169050926224104
888 81719658610113076
889 82273375306143560
890 82830215042539965
891 83390191894945980
892 83953319986531314
893 84519613488098556
894 85089086618190155
895 85661753643195520
896 86237628877458240
897 86816726683383424
898 87399061471545161
899 87984647700794100
900 88573499878365150
901 89165632559985300
902 89761060349981559
903 90359797901389016
904 90961859916059020
905 91567261144767480
906 92176016387323285
907 92788140492676844
908 93403648359028746
909 94022554933938540
910 94644875214433635
911 95270624247118320
912 95899817128282904
913 96532469004012976
914 97168595070298785
915 97808210573144740
916 98451330808679030
917 99097971123263364
918 99748146913602831
919 100401873626855880
920 101059166760744420
921 101720041863664040
922 102384514534794349
923 103052600424209436
924 103724315232988450
925 104399674713326300
926 105078694668644475
927 105761390953701984
928 106447779474706416
929 107137876189425120
930 107831697107296505
931 108529258289541460
932 109230575849274894
933 109935665951617396
934 110644544813807015
935 111357228705311160
936 112073733947938620
937 112794076915951704
938 113518274036178501
939 114246341788125260
940 114978296704088890
941 115714155369269580
942 116453934421883539
943 117197650553275856
944 117945320508033480
945 118696961084098320
946 119452589132880465
947 120212221559371524
948 120975875322258086
949 121743567434035300
950 122515314961120575
951 123291135023967400
952 124071044797179284
953 124855061509623816
954 125643202444546845
955 126435484939686780
956 127231926387389010
957 128032544234720444
958 128837355983584171
959 129646379190834240
960 130459631468390560
961 131277130483353920
962 132098893958121129
963 132924939670500276
964 133755285453826110
965 134589949197075540
966 135428948844983255
967 136272302398157464
968 137120027913195756
969 137972143502801080
970 138828667335897845
971 139689617637748140
972 140555012690068074
973 141424870831144236
974 142299210455950275
975 143178050016263600
976 144061408020782200
977 144949303035241584
978 145841753682531841
979 146738778642814820
980 147640396653641430
981 148546626510069060
982 149457487064779119
983 150372997228194696
984 151293175968598340
985 152218042312249960
986 153147615343504845
987 154081914204931804
988 155020958097431426
989 155964766280354460
990 156913358071620315
991 157866752847835680
992 158824970044413264
993 159788029155690656
994 160755949735049305
995 161728751395033620
996 162706453807470190
997 163689076703587124
998 164676639874133511
999 165669163169499000
1000 166666666499833500