3 0
4 1
5 24
6 200
7 1053
8 3932
9 11988
10 31298
11 73046
12 155880
13 310046
14 581414
15 1038634
16 1779531
17 2942114
18 4714412
19 7350595
20 11184786
21 16654116
22 24317554
23 34886940
24 49252544
25 68523846
26 94062350
27 127534794
28 170954603
29 226748678
30 297809946
31 387580007
32 500113190
33 640178710
34 813337956
35 1026067304
36 1285851950
37 1601332168
38 1982413872
39 2440443048
40 2988335113
41 3640778556
42 4414387370
43 5327937201
44 6402540704
45 7661922114
46 9132617936
47 10844290754
48 12829960602
49 15126361820
50 17774204516
51 20818581676
52 24309263469
53 28301155100
54 32854630484
55 38036045161
56 43918108200
57 50580458784
58 58110079438
59 66601936338
60 76159441676
61 86895162522
62 98931330530
63 112400629470
64 127446755711
65 144225283934
66 162904287600
67 183665288183
68 206703933062
69 232231040008
70 260473336278
71 291674597216
72 326096457260
73 364019648506
74 405744880194
75 451594190694
76 501911899591
77 557066071194
78 617449551542
79 683481549795
80 755608755746
81 834307054386
82 920082728384
83 1013474303060
84 1115053847874
85 1225428958676
86 1345244152700
87 1475183005324
88 1615969643373
89 1768371032648
90 1933198585406
91 2111310606037
92 2303614006020
93 2511066927030
94 2734680568516
95 2975521983414
96 3234716036150
97 3513448378848
98 3812967531752
99 4134588061368
100 4479692788793
101 4849736163776
102 5246246620800
103 5670830157461
104 6125172828884
105 6611044554124
106 7130301754746
107 7684891381934
108 8276853721232
109 8908326649270
110 9581548593726
111 10298863045746
112 11062721681299
113 11875689120570
114 12740446234964
115 13659795162891
116 14636662789850
117 15674106049164
118 16775315581658
119 17943621311108
120 19182496310136
121 20495562660302
122 21886595509910
123 23359529249890
124 24918461770371
125 26567660940494
126 28311569092850
127 30154809817663
128 32102192658942
129 34158720256878
130 36329593262908
131 38620217816736
132 41036210711990
133 43583407218816
134 46267866482024
135 49095879725904
136 52073975892401
137 55208930212724
138 58507770119922
139 61977784198745
140 65626528352456
141 69461835170506
142 73491820357464
143 77724892501130
144 82169759800754
145 86835440247556
146 91731268629900
147 96866907168804
148 102252352808293
149 107897948286468
150 113814389751116
151 120012738278817
152 126504427791200
153 133301277067800
154 140415497971526
155 147859707933674
156 155646938531700
157 163790648459378
158 172304732429882
159 181203534680038
160 190501858207623
161 200214978785846
162 210358654581080
163 220949140691071
164 232003199113614
165 243538113860784
166 255571701287806
167 268122325757064
168 281208910376612
169 294850953227970
170 309068538482186
171 323882353247166
172 339313699070879
173 355384509379490
174 372117361420494
175 389535494306171
176 407662821361850
177 426523948833994
178 446144188653528
179 466549577777228
180 487766891422346
181 509823663056332
182 532748198065140
183 556569594454260
184 581317756960981
185 607023418432704
186 633718154442950
187 661434405362493
188 690205491438572
189 720065635625598
190 751049979138188
191 783194605004606
192 816536554157070
193 851113849723976
194 886965513613904
195 924131591617264
196 962653170494961
197 1002572403849704
198 1043932529786552
199 1086777897570445
200 1131153985811916
201 1177107429985476
202 1224686041151794
203 1273938834294150
204 1324916047648184
205 1377669171873486
206 1432250969940950
207 1488715507218234
208 1547118171926363
209 1607515706093138
210 1669966226654076
211 1734529257291347
212 1801265750125730
213 1870238118524020
214 1941510259393986
215 2015147586911084
216 2091217055495600
217 2169787194476758
218 2250928131695262
219 2334711629192058
220 2421211107448603
221 2510501682047766
222 2602660188635210
223 2697765220571031
224 2795897154551894
225 2897138189345094
226 3001572372084116
227 3109285638029144
228 3220365837623742
229 3334902777300920
230 3452988247236896
231 3574716063298936
232 3700182095509209
233 3829484311074860
234 3962722803654074
235 4099999837488001
236 4241419877401200
237 4387089634136274
238 4537118095102048
239 4691616570847698
240 4850698726655306
241 5014480630173612
242 5183080783783220
243 5356620173495580
244 5535222302104541
245 5719013239283564
246 5908121655624900
247 6102678873955673
248 6302818904188952
249 6508678495969168
250 6720397174349118
251 6938117293693826
252 7161984074289500
253 7392145657526986
254 7628753143362834
255 7871960646897774
256 8121925336704271
257 8378807492725134
258 8642770545578432
259 8913981135797895
260 9192609154031126
261 9478827801742296
262 9772813632318374
263 10074746613155120
264 10384810167787164
265 10703191239379466
266 11030080333792850
267 11365671584606614
268 11710162797134583
269 12063755514895658
270 12426655064701286
271 12799070624596627
272 13181215269926610
273 13573306042878690
274 13975563999542896
275 14388214280968644
276 14811486161344850
277 15245613120593988
278 15690832893574892
279 16147387544350428
280 16615523516428733
281 17095491708612536
282 17587547526410190
283 18091950959490341
284 18608966634160724
285 19138863892570054
286 19681916846270676
287 20238404457071174
288 20808610591819622
289 21392824104931120
290 21991338894284856
291 22604453985574056
292 23232473589333289
293 23875707187009680
294 24534469589262704
295 25209081023781381
296 25899867194744900
297 26607159372539004
298 27331294454394218
299 28072615055895518
300 28831469572946016
301 29608212275095142
302 30403203368711150
303 31216809092286850
304 32049401780838051
305 32901359963076074
306 33773068427185700
307 34664918319890203
308 35577307213487082
309 36510639206970588
310 37465324994342698
311 38441781967677396
312 39440434286866280
313 40461712984650846
314 41506056037675814
315 42573908473660434
316 43665722443777331
317 44781957331842014
318 45923079828182562
319 47089564040874095
320 48281891570967086
321 49500551625943966
322 50746041096324204
323 52018864671217040
324 53319534916474694
325 54648572392368496
326 56006505733152600
327 57393871767046944
328 58811215597229953
329 60259090723997028
330 61738059127359746
331 63248691391407657
332 64791566788370840
333 66367273405374810
334 67976408229985256
335 69619577279219354
336 71297395686756450
337 73010487834234068
338 74759487439975772
339 76545037692768148
340 78367791342125013
341 80228410834403156
342 82127568404793020
343 84065946215802001
344 86044236450817104
345 88063141455158664
346 90123373831234486
347 92225656582016154
348 94370723207981252
349 96559317853041570
350 98792195403113066
351 101070121634705526
352 103393873315140119
353 105764238353646950
354 108182015903433384
355 110648016515319311
356 113163062241489950
357 115727986791885184
358 118343635639657038
359 121010866180153688
360 123730547838291476
361 126503562230163922
362 129330803272155930
363 132213177345401070
364 135151603406658511
365 138147013155453234
366 141200351146932350
367 144312574961719083
368 147484655320569962
369 150717576257172858
370 154012335234625928
371 157369943321008316
372 160791425307904410
373 164277819888778556
374 167830179779359844
375 171449571899058244
376 175137077493231141
377 178893792317463344
378 182720826761945942
379 186619306038652045
380 190590370307636796
381 194635174867353486
382 198754890282896284
383 202950702579272910
384 207223813371827774
385 211575440062503576
386 216006815972247200
387 220519190540512224
388 225113829459669473
389 229792014877560248
390 234555045534156456
391 239404236967197437
392 244340921650895420
393 249366449204915380
394 254482186535148066
395 259689518045836214
396 264989845782667400
397 270384589648079998
398 275875187546464902
399 281463095602918218
400 287149788310574443
401 292936758752602626
402 298825518751930700
403 304817599096519011
404 310914549691258034
405 317117939786793924
406 323429358133622546
407 329850413214257084
408 336382733399785632
409 343027967185415270
410 349787783349268526
411 356663871191586346
412 363657940695786699
413 370771722771109670
414 378006969416213114
415 385365453965294791
416 392848971253993350
417 400459337869277814
418 408198392317677508
419 416067995278715208
420 424070029775748686
421 432206401432982952
422 440479038648684560
423 448889892856071240
424 457440938698922921
425 466134174296118044
426 474971621419931850
427 483955325764255313
428 493087357125334592
429 502369809673978978
430 511804802138765808
431 521394478081999586
432 531141006085680890
433 541046580031253116
434 551113419288081924
435 561343768997304204
436 571739900262842701
437 582304110439112124
438 593038723324875572
439 603946089454844745
440 615028586296117256
441 626288618543993856
442 637728618321021614
443 649351045476775730
444 661158387789823404
445 673153161271507706
446 685337910370563650
447 697715208281235454
448 710287657150570143
449 723057888390608318
450 736028562888678416
451 749202371323698967
452 762582034379197350
453 776170303064063400
454 789969958928318326
455 803983814388052224
456 818214712944274700
457 832665529512074778
458 847339170642269282
459 862238574855133638
460 877366712864874023
461 892726587917653946
462 908321236019230230
463 924153726277314371
464 940227161132080514
465 956544676703218834
466 973109443023341856
467 989924664389446964
468 1006993579599569762
469 1024319462308695220
470 1041905621268358236
471 1059755400687369516
472 1077872180474390029
473 1096259376603180840
474 1114920441358508894
475 1133858863705960821
476 1153078169540872100
477 1172581922063079894
478 1192373722028902628
479 1212457208130533078
480 1232836057251434646
481 1253513984850415232
482 1274494745220124040
483 1295782131876190360
484 1317379977818848281
485 1339292155926833504
486 1361522579222511200
487 1384075201270571893
488 1406954016446337972
489 1430163060339651948
490 1453706410026389338
491 1477588184477224206
492 1501812544832732720
493 1526383694817077526
494 1551305881016369054
495 1576583393297671314
496 1602220565090649011
497 1628221773811571354
498 1654591441148638452
499 1681334033491025195
500 1708454062217545466
501 1735956084131148076
502 1763844701750947194
503 1792124563751838500
504 1820800365260298584
505 1849876848299163886
506 1879358802086848950
507 1909251063487709634
508 1939558517314708963
509 1970286096785024238
510 2001438783826572626
511 2033021609538905247
512 2065039654503233630
513 2097498049249041870
514 2130401974567643036
515 2163756661984160384
516 2197567394075035350
517 2231839504945421408
518 2266578380550275912
519 2301789459177607408
520 2337478231773180753
521 2373650242429260116
522 2410311088713358610
523 2447466422162521081
524 2485121948615741544
525 2523283428714236394
526 2561956678237559416
527 2601147568609498794
528 2640862027238330642
529 2681106038028384420
530 2721885641724049196
531 2763206936427468036
532 2805076077946327109
533 2847499280317303460
534 2890482816158087724
535 2934033017196630401
536 2978156274627003200
537 3022859039644914424
538 3068147823807439398
539 3114029199574420298
540 3160509800672526356
541 3207596322642583762
542 3255295523207561370
543 3303614222826311430
544 3352559305065511591
545 3402137717159422614
546 3452356470386257400
547 3503222640634001823
548 3554743368780797102
549 3606925861267314768
550 3659777390481183518
551 3713305295335515176
552 3767516981657856900
553 3822419922774914786
554 3878021659905608234
555 3934329802752492574
556 3991352029898947071
557 4049096089406884034
558 4107569799218561582
559 4166781047760626395
560 4226737794350118426
561 4287448069805359146
562 4348919976856180024
563 4411161690761234220
564 4474181459722950314
565 4537987605511315116
566 4602588523883110100
567 4667992685212687764
568 4734208634915522933
569 4801244994085551008
570 4869110459923546086
571 4937813806381069277
572 5007363884593221260
573 5077769623529733790
574 5149040030432129196
575 5221184191471513694
576 5294211272190666350
577 5368130518168582888
578 5442951255467031792
579 5518682891302392528
580 5595334914496711633
581 5672916896156384136
582 5751438490128242840
583 5830909433685132141
584 5911339547986558124
585 5992738738771709604
586 6075116996824702226
587 6158484398674585574
588 6242851107065725272
589 6328227371664845870
590 6414623529536068406
591 6502050005855554906
592 6590517314391234939
593 6680036058224580530
594 6770616930235576604
595 6862270713831676531
596 6955008283437523650
597 7048840605231664404
598 7143778737641054818
599 7239833832085049868
600 7337017133475260816
601 7435339980966871542
602 7534813808463343550
603 7635450145375647450
604 7737260617131849851
605 7840256945943768374
606 7944450951322017450
607 8049854550850138103
608 8156479760704588982
609 8264338696436950438
610 8373443573498895348
611 8483806708031965496
612 8595440517398110430
613 8708357520977087896
614 8822570340702046464
615 8938091701865160984
616 9054934433658293881
617 9173111469986353164
618 9292635850013631962
619 9413520718984941345
620 9535779328777093136
621 9659425038728430066
622 9784471316195487104
623 9910931737390395890
624 10038819987943335594
625 10168149863747864396
626 10298935271528614100
627 10431190229695182844
628 10564928868915109053
629 10700165432975791628
630 10836914279363365796
631 10975189880132704057
632 11115006822491637240
633 11256379809679682160
634 11399323661557643806
635 11543853315494525154
636 11689983826963144700
637 11837730370435282218
638 11987108239982743922
639 12138132850181401998
640 12290819736717743663
641 12445184557301249006
642 12601243092277069920
643 12759011245546800551
644 12918505045186707254
645 13079740644377561464
646 13242734322028457286
647 13407502483715140304
648 13574061662310070652
649 13742428518929302570
650 13912619843568202866
651 14084652556057563126
652 14258543706705010519
653 14434310477259775050
654 14611970181560462534
655 14791540266508532211
656 14973038312721830450
657 15156482035517472834
658 15341889285571175888
659 15529278049908954788
660 15718666452572935026
661 15910072755621921572
662 16103515359803077580
663 16299012805562071420
664 16496583773720660061
665 16696247086495813784
666 16898021708183898350
667 17101926746188833733
668 17307981451712250612
669 17516205220791401958
670 17726617594995331828
671 17939238262471928166
672 18154087058650810310
673 18371183967299579856
674 18590549121232790744
675 18812202803378129544
676 19036165447491506441
677 19262457639232541744
678 19491100116886496592
679 19722113772449123045
680 19955519652354786596
681 20191338958571423836
682 20429593049334895434
683 20670303440253416510
684 20913491805048871424
685 21159179976670774726
686 21407389948043887950
687 21658143873192467874
688 21911464067994224323
689 22167373011314209098
690 22425893345765858756
691 22687047878854582587
692 22950859583745218570
693 23217351600416089980
694 23486547236432913866
695 23758469968112667764
696 24033143441304707400
697 24310591472564502398
698 24590838049941279302
699 24873907334162408818
700 25159823659427613843
701 25448611534603337726
702 25740295644024286850
703 26034900848697839311
704 26332452187112225934
705 26632974876451774974
706 26936494313411771596
707 27243036075423855984
708 27552625921478343782
709 27865289793359837520
710 28181053816476299576
711 28499944301105685696
712 28821987743231810849
713 29147210825801310020
714 29475640419567092514
715 29807303584355690441
716 30142227569917580600
717 30480439817205742714
718 30821967959232889608
719 31166839822360528058
720 31515083427163905986
721 31866726989731636852
722 32221798922537630460
723 32580327835752116340
724 32942342538120599221
725 33307872038285561844
726 33676945545673267100
727 34049592471826201713
728 34425842431296978992
729 34805725242992372328
730 35189270931074359958
731 35576509726315016186
732 35967472067005533540
733 36362188600322033666
734 36760690183241808074
735 37163007883920911254
736 37569172982617661751
737 37979216973081272774
738 38393171563483462472
739 38811068677818184495
740 39232940456840575806
741 39658819259478663456
742 40088737663779692014
743 40522728468333049080
744 40960824693224834804
745 41403059581472069106
746 41849466599984718650
747 42300079441012075854
748 42754932023112285743
749 43214058492610126418
750 43677493224574911966
751 44145270824289737867
752 44617426128236962250
753 45093994205579820250
754 45575010359155526376
755 46060510126968474524
756 46550529283191851450
757 47045103839672486428
758 47544270046940164932
759 48048064395725045988
760 48556523617974719173
761 49069684688383393296
762 49587584825417600630
763 50110261492857221421
764 50637752400829011164
765 51170095507360393134
766 51707329019420852156
767 52249491394487685614
768 52796621341596181662
769 53348757822917393720
770 53905940054816265536
771 54468207509442375616
772 55035599915796052929
773 55608157261331268440
774 56185919793030673544
775 56768928019020704221
776 57357222709654691100
777 57950844899141137044
778 58549835886634942978
779 59154237237878022678
780 59764090786299590696
781 60379438634669180382
782 61000323156205129190
783 61626786996240975210
784 62258873073342184331
785 62896624580985075554
786 63540084988682750700
787 64189298043676615043
788 64844307772070631122
789 65505158480536424548
790 66171894757455906738
791 66844561474639102556
792 67523203788476117120
793 68207867141667752326
794 68898597264385925454
795 69595440176018079114
796 70298442186336096811
797 71007649897253629254
798 71723110204004496602
799 72444870296912998695
800 73172977662580897766
801 73907480085671731926
802 74648425650106423844
803 75395862740860706600
804 76149840045170362734
805 76910406554341830536
806 77677611564966153200
807 78451504680743799784
808 79232135813707370313
809 80019555186059726588
810 80813813331406472426
811 81614961096607462897
812 82423049643018125280
813 83238130448355395970
814 84060255307947928336
815 84889476336615538434
816 85725845969929333850
817 86569416966104737308
818 87420242407270587812
819 88278375701376806508
820 89143870583472516653
821 90016781117627418716
822 90897161698219978260
823 91785067051872579881
824 92680552238748819944
825 93583672654503518944
826 94494484031589165966
827 95413042441219842194
828 96339404294687881292
829 97273626345341774170
830 98215765689912067746
831 99165879770504345886
832 100124026375934413759
833 101090263643735393310
834 102064650061503272624
835 103047244468918186551
836 104038106059099338950
837 105037294380641578824
838 106044869338979742998
839 107060891198439551648
840 108085420583612466156
841 109118518481420975162
842 110160246242502960770
843 111210665583292501030
844 112269838587413792391
845 113337827707776477914
846 114414695767980236150
847 115500505964424706723
848 116595321867723724002
849 117699207424830981618
850 118812226960463959168
851 119934445179244320276
852 121065927167132658050
853 122206738393583698836
854 123356944712990829884
855 124516612366857266124
856 125685807985250408621
857 126864598588987954184
858 128053051591103225982
859 129251234799046298645
860 130459216416159249476
861 131677065043893472246
862 132904849683294897924
863 134142639737236462070
864 135390505011914452214
865 136648515719096202016
866 137916742477626498600
867 139195256315691692664
868 140484128672336215033
869 141783431399742052608
870 143093236764756547136
871 144413617451187310677
872 145744646561340224660
873 147086397618331000140
874 148438944567633426746
875 149802361779406512494
876 151176724050054171600
877 152562106604568018038
878 153958585098097394942
879 155366235618309043378
880 156785134686967523283
881 158215359262310676986
882 159656986740641646740
883 161110094958720207691
884 162574762195365269274
885 164051067173863315404
886 165539089063581440026
887 167038907482391798724
888 168550602498296399672
889 170074254631867641870
890 171609944857883733206
891 173157754607786569506
892 174717765771327830339
893 176290060699043087630
894 177874722203909816754
895 179471833563837810431
896 181081478523337961150
897 182703741296030251054
898 184338706566323356668
899 185986459491939087968
900 187647085705604069366
901 189320671317590704192
902 191007302917419772200
903 192707067576419206800
904 194420052849437660401
905 196146346777419951924
906 197886037889132870450
907 199639215203757369753
908 201405968232625434632
909 203186386981830326538
910 204980561953974564248
911 206788584150797062346
912 208610545074933513330
913 210446536732560496196
914 212296651635167068364
915 214160982802217165284
916 216039623762932454181
917 217932668558971850564
918 219840211746226937612
919 221762348397518677345
920 223699174104404187936
921 225650784979891987416
922 227617277660260181254
923 229598749307789048490
924 231595297612591960244
925 233607020795365386546
926 235634017609231321850
927 237676387342506067494
928 239734229820554216903
929 241807645408575007478
930 243896735013469203096
931 246001600086643094207
932 248122342625887037390
933 250259065178198475760
934 252411870841672188606
935 254580863268341109704
936 256766146666079641700
937 258967825801462351618
938 261186006001679093322
939 263420793157412969598
940 265672293724767316063
941 267940614728161691106
942 270225863762272093070
943 272528148994945057851
944 274847579169149836154
945 277184263605912005514
946 279538312206277661336
947 281909835454265288204
948 284298944418843353802
949 286705750756900519820
950 289130366715235348916
951 291572905133546279476
952 294033479446433499669
953 296512203686407414400
954 299009192485904092934
955 301524561080312308861
956 304058425310001254700
957 306610901623367596734
958 309182107078875510988
959 311772159348122464638
960 314381176717892997326
961 317009278093243310472
962 319656582999567470480
963 322323211585702265520
964 325009284626005885361
965 327714923523481740584
966 330440250311871060600
967 333185387658795757133
968 335950458867863600012
969 338735587881831602308
970 341540899284723828978
971 344366518305013981766
972 347212570817757299960
973 350079183347792427406
974 352966483071886047894
975 355874597821955529594
976 358803656087226350491
977 361753787017474181394
978 364725120425196578492
979 367717786788874587795
980 370731917255157330146
981 373767643642144640436
982 376825098441584600834
983 379904414822175858860
984 383005726631779603824
985 386129168400741647126
986 389274875344117449950
987 392442983365015497274
988 395633629056835432923
989 398846949706631354198
990 402083083297364567306
991 405342168511286886487
992 408624344732206600470
993 411929752048893325830
994 415258531257357240916
995 418610823864274103064
996 421986772089279281150
997 425386518868413021048
998 428810207856427849952
999 432257983430255658168
1000 435729990691328531993