0 0
1 1
2 1716
3 54573
4 492724
5 2467137
6 8786436
7 25066621
8 61189668
9 133071009
10 264735892
11 490704621
12 858686676
13 1432583713
14 2295801444
15 3554870397
16 5343375556
17 7826194881
18 11204046708
19 15718346029
20 21656369652
21 29356730241
22 39215159236
23 51690598653
24 67311601764
25 86683042657
26 110493134676
27 139520757741
28 174643094548
29 216843575649
30 267220133412
31 326993764861
32 397517403396
33 480285099393
34 576941509684
35 689291695917
36 819311231796
37 969156619201
38 1141176013188
39 1337920255869
40 1562154219172
41 1816868456481
42 2105291163156
43 2430900445933
44 2797436901204
45 3208916502177
46 3669643794916
47 4184225403261
48 4757583842628
49 5394971642689
50 6101985778932
51 6884582413101
52 7749091942516
53 8702234358273
54 9751134912324
55 10903340093437
56 12166833912036
57 13550054493921
58 15061910982868
59 16711800752109
60 18509626924692
61 20465816202721
62 22591337005476
63 24897717916413
64 27397066439044
65 30102088061697
66 33026105631156
67 36183079035181
68 39587625193908
69 43255038360129
70 47201310728452
71 51443153353341
72 55998017376036
73 60884115560353
74 66120444137364
75 71726804958957
76 77723827960276
77 84132993931041
78 90976657595748
79 98278071002749
80 106061407222212
81 114351784352961
82 123175289838196
83 132559005090093
84 142531030423284
85 153120510297217
86 164357658867396
87 176273785845501
88 188901322668388
89 202273848975969
90 216426119397972
91 231394090649581
92 247214948935956
93 263927137665633
94 281570385472804
95 300185734548477
96 319815569280516
97 340503645202561
98 362295118251828
99 385236574335789
100 409376059207732
101 434763108651201
102 461448778973316
103 489485677806973
104 518927995221924
105 549831535144737
106 582253747087636
107 616253758186221
108 651892405546068
109 689232268898209
110 728337703563492
111 769274873725821
112 812111786014276
113 856918323394113
114 903766279366644
115 952729392477997
116 1003883381136756
117 1057305978740481
118 1113076969111108
119 1171278222239229
120 1231993730337252
121 1295309644201441
122 1361314309882836
123 1430098305667053
124 1501754479362964
125 1576377985900257
126 1654066325235876
127 1734919380569341
128 1819039456866948
129 1906531319694849
130 1997502234361012
131 2092062005366061
132 2190323016162996
133 2292400269225793
134 2398411426426884
135 2508476849723517
136 2622719642152996
137 2741265689136801
138 2864243700093588
139 2991785250361069
140 3124024823426772
141 3261099853467681
142 3403150768198756
143 3550321032030333
144 3702757189534404
145 3860608909219777
146 4024029027616116
147 4193173593666861
148 4368201913431028
149 4549276595093889
150 4736563594286532
151 4930232259714301
152 5130455379094116
153 5337409225400673
154 5551273603421524
155 5772231896621037
156 6000471114313236
157 6236181939143521
158 6479558774879268
159 6730799794509309
160 6990106988652292
161 7257686214273921
162 7533747243713076
163 7818503814016813
164 8112173676584244
165 8414978647119297
166 8727144655892356
167 9048901798310781
168 9380484385798308
169 9722130996983329
170 10074084529196052
171 10436592250274541
172 10809905850679636
173 11194281495918753
174 11589979879278564
175 11997266274866557
176 12416410590961476
177 12847687423672641
178 13291376110908148
179 13747760786651949
180 14217130435549812
181 14699778947804161
182 15196005174377796
183 15706112982506493
184 16230411311520484
185 16769214228974817
186 17322840987088596
187 17891616079493101
188 18475869298288788
189 19075935791411169
190 19692156120305572
191 20324876317910781
192 20974447946951556
193 21641228158540033
194 22325579751086004
195 23027871229516077
196 23748476864801716
197 24487776753796161
198 25246156879380228
199 26024009170916989
200 26821731565015332
201 27639728066602401
202 28478408810304916
203 29338190122139373
204 30219494581511124
205 31122751083522337
206 32048394901588836
207 32996867750365821
208 33968617848982468
209 34964099984585409
210 35983775576191092
211 37028112738847021
212 38097586348101876
213 39192678104784513
214 40313876600091844
215 41461677380985597
216 42636583015897956
217 43839103160746081
218 45069754625255508
219 46329061439592429
220 47617554921304852
221 48935773742572641
222 50284263997766436
223 51663579271315453
224 53074280705884164
225 54516937070857857
226 55992124831137076
227 57500428216240941
228 59042439289719348
229 60618758018874049
230 62229992344788612
231 63876758252667261
232 65559679842482596
233 67279389399932193
234 69036527467704084
235 70831742917051117
236 72665693019674196
237 74539043519914401
238 76452468707253988
239 78406651489126269
240 80402283464034372
241 82440064994978881
242 84520705283194356
243 86644922442194733
244 88813443572127604
245 91027004834437377
246 93286351526837316
247 95592238158590461
248 97945428526099428
249 100346695788805089
250 102796822545394132
251 105296600910315501
252 107846832590605716
253 110448328963023073
254 113101911151490724
255 115808410104848637
256 118568666674914436
257 121383531694853121
258 124253866057855668
259 127180540796126509
260 130164437160179892
261 133206446698445121
262 136307471337180676
263 139468423460697213
264 142690225991889444
265 145973812473076897
266 149320127147153556
267 152730125039046381
268 156204772037482708
269 159745044977066529
270 163351931720663652
271 167026431242095741
272 170769553709143236
273 174582320566857153
274 178465764621179764
275 182420930122874157
276 186448872851762676
277 190550660201274241
278 194727371263300548
279 198980096913361149
280 203309939896077412
281 207718014910955361
282 212205448698477396
283 216773380126502893
284 221422960276977684
285 226155352532952417
286 230971732665909796
287 235873288923400701
288 240861222116989188
289 245936745710506369
290 251101085908613172
291 256355481745671981
292 261701185174927156
293 267139461157994433
294 272671587754659204
295 278298856212983677
296 284022571059722916
297 289844050191049761
298 295764624963588628
299 301785640285758189
300 307908454709422932
301 314134440521853601
302 320464983837996516
303 326901484693051773
304 333445357135360324
305 340098029319599937
306 346860943600290036
307 353735556625605421
308 360723339431498868
309 367825777536132609
310 375044371034618692
311 382380634694068221
312 389836098048949476
313 397412305496754913
314 405110816393977044
315 412933205152393197
316 420881061335659156
317 428955989756211681
318 437159610572479908
319 445493559386405629
320 453959487341272452
321 462559061219843841
322 471293963542810036
323 480165892667543853
324 489176562887165364
325 498327704529915457
326 507621064058838276
327 517058404171772541
328 526641503901651748
329 536372158717113249
330 546252180623416212
331 556283398263668461
332 566467657020362196
333 576806819117218593
334 587302763721341284
335 597957387045678717
336 608772602451795396
337 619750340552952001
338 630892549317494388
339 642201194172551469
340 653678258108041972
341 665325741780990081
342 677145663620149956
343 689140059930939133
344 701310985000680804
345 713660511204154977
346 726190729109458516
347 738903747584174061
348 751801693901847828
349 764886713848776289
350 778160971831101732
351 791626650982216701
352 805285953270477316
353 819141099607225473
354 833194329955119924
355 847447903436776237
356 861904098443715636
357 876565212745622721
358 891433563599912068
359 906511487861603709
360 921801342093507492
361 937305502676716321
362 953026365921408276
363 968966348177957613
364 985127885948354644
365 1001513435997934497
366 1018125475467414756
367 1034966501985241981
368 1052039033780247108
369 1069345609794609729
370 1086888789797131252
371 1104671154496816941
372 1122695305656766836
373 1140963866208375553
374 1159479480365840964
375 1178244813740981757
376 1197262553458363876
377 1216535408270735841
378 1236066108674772948
379 1255857407027130349
380 1275912077660805012
381 1296232917001806561
382 1316822743686136996
383 1337684398677079293
384 1358820745382794884
385 1380234669774230017
386 1401929080503330996
387 1423906909021568301
388 1446171109698769588
389 1468724659942261569
390 1491570560316320772
391 1514711834661933181
392 1538151530216862756
393 1561892717736028833
394 1585938491612192404
395 1610291969996951277
396 1634956294922044116
397 1659934632420963361
398 1685230172650877028
399 1710846130014859389
400 1736785743284430532
401 1763052275722404801
402 1789649015206048116
403 1816579274350544173
404 1843846390632769524
405 1871453726515377537
406 1899404669571191236
407 1927702632607905021
408 1956351053793095268
409 1985353396779539809
410 2014713150830846292
411 2044433830947389421
412 2074518977992557076
413 2104972158819305313
414 2135796966397022244
415 2166997019938700797
416 2198575965028420356
417 2230537473749137281
418 2262885244810784308
419 2295623003678678829
420 2328754502702240052
421 2362283521244015041
422 2396213865809013636
423 2430549370174352253
424 2465293895519206564
425 2500451330555073057
426 2536025591656339476
427 2572020622991164141
428 2608440396652664148
429 2645288912790412449
430 2682570199742243812
431 2720288314166369661
432 2758447341173801796
433 2797051394461084993
434 2836104616443338484
435 2875611178387606317
436 2915575280546516596
437 2956001152292249601
438 2996893052250814788
439 3038255268436636669
440 3080092118387449572
441 3122407949299501281
442 3165207138163065556
443 3208494091898263533
444 3252273247491194004
445 3296549072130372577
446 3341326063343479716
447 3386608749134417661
448 3432401688120676228
449 3478709469671007489
450 3525536714043409332
451 3572888072523417901
452 3620768227562708916
453 3669181892918007873
454 3718133813790309124
455 3767628766964403837
456 3817671560948716836
457 3868267036115452321
458 3919420064841048468
459 3971135551646940909
460 4023418433340635092
461 4076273679157087521
462 4129706290900395876
463 4183721303085798013
464 4238323783081979844
465 4293518831253692097
466 4349311581104675956
467 4405707199420897581
468 4462710886414091508
469 4520327875865612929
470 4578563435270598852
471 4637422865982438141
472 4696911503357550436
473 4757034716900473953
474 4817797910409262164
475 4879206522121189357
476 4941266024858765076
477 5003981926176057441
478 5067359768505325348
479 5131405129303959549
480 5196123621201732612
481 5261520892148357761
482 5327602625561356596
483 5394374540474235693
484 5461842391684972084
485 5530011969904807617
486 5598889101907352196
487 5668479650677995901
488 5738789515563629988
489 5809824632422676769
490 5881590973775428372
491 5954094548954694381
492 6027341404256758356
493 6101337623092643233
494 6176089326139685604
495 6251602671493418877
496 6327883854819765316
497 6404939109507536961
498 6482774706821245428
499 6561396956054220589
500 6640812204682038132
501 6721026838516256001
502 6802047281858459716
503 6883879997654616573
504 6966531487649738724
505 7050008292542855137
506 7134316992142292436
507 7219464205521264621
508 7305456591173771668
509 7392300847170807009
510 7480003711316873892
511 7568571961306810621
512 7658012414882924676
513 7748331929992435713
514 7839537404945227444
515 7931635778571908397
516 8024634030382181556
517 8118539180723522881
518 8213358290940168708
519 8309098463532412029
520 8405766842316207652
521 8503370612583086241
522 8601917001260377236
523 8701413277071740653
524 8801866750698007764
525 8903284774938330657
526 9005674744871640676
527 9109044098018415741
528 9213400314502756548
529 9318750917214771649
530 9425103471973271412
531 9532465587688770861
532 9640844916526801396
533 9750249154071531393
534 9860686039489695684
535 9972163355694833917
536 10084688929511837796
537 10198270631841807201
538 10312916377827215188
539 10428634127017381869
540 10545431883534257172
541 10663317696238512481
542 10782299658895941156
543 10902385910344167933
544 11023584634659667204
545 11145904061325090177
546 11269352465396900916
547 11393938167673321261
548 11519669534862584628
549 11646554979751498689
550 11774602961374316932
551 11903821985181919101
552 12034220603211300516
553 12165807414255370273
554 12298591064033058324
555 12432580245359731437
556 12567783698317918036
557 12704210210428341921
558 12841868616821264868
559 12980767800408138109
560 13120916692053562692
561 13262324270747558721
562 13404999563778143476
563 13548951646904218413
564 13694189644528765044
565 13840722729872349697
566 13988560125146937156
567 14137711101730013181
568 14288184980339015908
569 14439991131206076129
570 14593138974253066452
571 14747637979266959341
572 14903497666075494036
573 15060727604723152353
574 15219337415647443364
575 15379336769855496957
576 15540735389100966276
577 15703543046061239041
578 15867769564514957748
579 16033424819519848749
580 16200518737590860212
581 16369061296878608961
582 16539062527348136196
583 16710532510957972093
584 16883481381839509284
585 17057919326476685217
586 17233856583885973396
587 17411303445796683501
588 17590270256831570388
589 17770767414687751969
590 17952805370317935972
591 18136394628111955581
592 18321545746078613956
593 18508269336027837633
594 18696576063753138804
595 18886476649214386477
596 19077981866720886516
597 19271102545114770561
598 19465849567954693828
599 19662233873699841789
600 19860266455894245732
601 20059958363351407201
602 20261320700339231316
603 20464364626765268973
604 20669101358362267924
605 20875542166874032737
606 21083698380241593636
607 21293581382789684221
608 21505202615413528068
609 21718573575765934209
610 21933705818444701492
611 22150610955180331821
612 22369300655024052276
613 22589786644536146113
614 22812080707974592644
615 23036194687484015997
616 23262140483284942756
617 23489930053863368481
618 23719575416160633108
619 23951088645763605229
620 24184481877095175252
621 24419767303605057441
622 24656957177960900836
623 24896063812239709053
624 25137099578119568964
625 25380076907071688257
626 25625008290552741876
627 25871906280197527341
628 26120783488011928948
629 26371652586566190849
630 26624526309188499012
631 26879417450158872061
632 27136338864903360996
633 27395303470188557793
634 27656324244316412884
635 27919414227319361517
636 28184586521155758996
637 28451854289905624801
638 28721230759966695588
639 28992729220250787069
640 29266363022380464772
641 29542145580886023681
642 29820090373402776756
643 30100210940868652333
644 30382520887722100404
645 30667033882100307777
646 30953763656037722116
647 31242724005664884861
648 31533928791407573028
649 31827391938186249889
650 32123127435615824532
651 32421149338205720301
652 32721471765560252116
653 33024108902579312673
654 33329074999659367524
655 33636384372894759037
656 33946051404279319236
657 34258090541908291521
658 34572516300180561268
659 34889343260001195309
660 35208586068984290292
661 35530259441656129921
662 35854378159658651076
663 36180957071953218813
664 36510011095024710244
665 36841555213085907297
666 37175604478282198356
667 37512174010896588781
668 37851278999555020308
669 38192934701431999329
670 38537156442456534052
671 38883959617518380541
672 39233359690674597636
673 39585372195356410753
674 39940012734576384564
675 40297296981135904557
676 40657240677832967476
677 41019859637670280641
678 41385169744063670148
679 41753186951050797949
680 42123927283500187812
681 42497406837320560161
682 42873641779670475796
683 43252648349168288493
684 43634442856102406484
685 44019041682641862817
686 44406461283047194596
687 44796718183881631101
688 45189828984222590788
689 45585810355873487169
690 45984679043575843572
691 46386451865221716781
692 46791145712066429556
693 47198777548941612033
694 47609364414468552004
695 48022923421271854077
696 48439471756193407716
697 48859026680506664161
698 49281605530131222228
699 49707225715847722989
700 50135904723513053332
701 50567660114275858401
702 51002509524792362916
703 51440470667442501373
704 51881561330546357124
705 52325799378580910337
706 52773202752397094836
707 53223789469437163821
708 53677577623952364468
709 54134585387220921409
710 54594831007766329092
711 55058332811575953021
712 55525109202319939876
713 55995178661570436513
714 56468559749021117844
715 56945271102707023597
716 57425331439224703956
717 57908759553952674081
718 58395574321272177508
719 58885794694788258429
720 59379439707551142852
721 59876528472277928641
722 60377080181574584436
723 60881114108158257453
724 61388649605079890164
725 61899706105947145857
726 62414303125147643076
727 62932460258072498941
728 63454197181340181348
729 63979533653020670049
730 64508489512859926612
731 65041084682504673261
732 65577339165727480596
733 66117273048652164193
734 66660906499979490084
735 67208259771213189117
736 67759353196886280196
737 68314207194787702401
738 68872842266189255988
739 69435278996072852269
740 70001538053358072372
741 70571640191130034881
742 71145606246867572356
743 71723457142671716733
744 72305213885494493604
745 72890897567368025377
746 73480529365633943316
747 74074130543173108461
748 74671722448635641428
749 75273326516671261089
750 75878964268159932132
751 76488657310442821501
752 77102427337553563716
753 77720296130449835073
754 78342285557245236724
755 78968417573441486637
756 79598714222160920436
757 80233197634379301121
758 80871890029158937668
759 81514813713882112509
760 82161991084484817892
761 82813444625690801121
762 83469196911245918676
763 84129270604152799213
764 84793688456905815444
765 85462473311726364897
766 86135648100798459556
767 86813235846504624381
768 87495259661662104708
769 88181742749759382529
770 88872708405193001652
771 89568180013504701741
772 90268181051618861236
773 90972735088080249153
774 91681865783292085764
775 92395596889754412157
776 93113952252302768676
777 93836955808347182241
778 94564631588111462548
779 95297003714872807149
780 96034096405201715412
781 96775933969202211361
782 97522540810752375396
783 98273941427745184893
784 99030160412329663684
785 99791222451152340417
786 100557152325599015796
787 101327974912036838701
788 102103715182056691188
789 102884398202715882369
790 103670049136781151172
791 104460693242971977981
792 105256355876204205156
793 106057062487833966433
794 106862838625901925204
795 107673709935377821677
796 108489702158405328916
797 109310841134547217761
798 110137152801030830628
799 110968663192993864189
800 111805398443730460932
801 112647384784937609601
802 113494648546961854516
803 114347216159046313773
804 115205114149578006324
805 116068369146335487937
806 116937007876736796036
807 117811057168087703421
808 118690543947830280868
809 119575495243791768609
810 120465938184433756692
811 121361899999101674221
812 122263408018274587476
813 123170489673815306913
814 124083172499220803044
815 125001484129872931197
816 125925452303289465156
817 126855104859375439681
818 127790469740674801908
819 128731574992622371629
820 129678448763796110452
821 130631119306169699841
822 131589614975365428036
823 132553964230907385853
824 133524195636474971364
825 134500337860156703457
826 135482419674704344276
827 136470469957787330541
828 137464517692247513748
829 138464591966354209249
830 139470721974059554212
831 140482937015254174461
832 141501266496023160196
833 142525739928902350593
834 143556386933134927284
835 144593237234928316717
836 145636320667711401396
837 146685667172392040001
838 147741306797614896388
839 148803269700019577469
840 149871586144499079972
841 150946286504458546081
842 152027401262074327956
843 153114961008553361133
844 154208996444392846804
845 155309538379640242977
846 156416617734153564516
847 157530265537861992061
848 158650512931026789828
849 159777391164502532289
850 160910931599998639732
851 162051165710341222701
852 163198125079735235316
853 164351841404026937473
854 165512346490966665924
855 166679672260471914237
856 167853850744890721636
857 169034914089265370721
858 170222894551596394068
859 171417824503106889709
860 172619736428507145492
861 173828662926259572321
862 175044636708843946276
863 176267690603022959613
864 177497857550108080644
865 178735170606225722497
866 179979662942583720756
867 181231367845738119981
868 182490318717860269108
869 183756549077004225729
870 185030092557374469252
871 186310982909593922941
872 187599254000972284836
873 188894939815774667553
874 190198074455490546964
875 191508692139103019757
876 192826827203358369876
877 194152514103035943841
878 195485787411218334948
879 196826681819561876349
880 198175232138567443012
881 199531473297851562561
882 200895440346417834996
883 202267168452928661293
884 203646692905977280884
885 205034049114360118017
886 206429272607349436996
887 207832399034966306301
888 209243464168253871588
889 210662503899550937569
890 212089554242765858772
891 213524651333650739181
892 214967831430075940756
893 216419130912304900833
894 217878586283269258404
895 219346234168844289277
896 220822111318124650116
897 222306254603700431361
898 223798701021933519028
899 225299487693234265389
900 226808651862338468532
901 228326230898584660801
902 229852262296191706116
903 231386783674536706173
904 232929832778433215524
905 234481447478409765537
906 236041665770988697236
907 237610525778965303021
908 239188065751687277268
909 240774324065334475809
910 242369339223198984292
911 243973149855965495421
912 245585794721991995076
913 247207312707590757313
914 248837742827309648244
915 250477124224213738797
916 252125496170167226356
917 253782898066115665281
918 255449369442368506308
919 257124949958881944829
920 258809679405542078052
921 260503597702448371041
922 262206744900197431636
923 263919161180167094253
924 265640886854800812564
925 267371962367892361057
926 269112428294870845476
927 270862325343086022141
928 272621694352093926148
929 274390576293942808449
930 276169012273459381812
931 277957043528535375661
932 279754711430414399796
933 281562057483979116993
934 283379123328038724484
935 285205950735616744317
936 287042581614239122596
937 288889058006222637601
938 290745422088963616788
939 292611716175226962669
940 294487982713435487572
941 296374264287959557281
942 298270603619407043556
943 300177043564913585533
944 302093627118433160004
945 304020397411028960577
946 305957397711164585716
947 307904671424995535661
948 309862262096661018228
949 311830213408576063489
950 313808569181723947332
951 315797373375948923901
952 317796670090249266916
953 319806503563070619873
954 321826918172599655124
955 323857958437058041837
956 325899669014996722836
957 327952094705590500321
958 330015280448932930468
959 332089271326331526909
960 334174112560603273092
961 336269849516370443521
962 338376527700356733876
963 340494192761683700013
964 342622890492167505844
965 344762666826615980097
966 346913567843125981956
967 349075639763381075581
968 351248928952949513508
969 353433481921582528929
970 355629345323512936852
971 357836565957754044141
972 360055190768398868436
973 362285266844919665953
974 364526841422467768164
975 366779961882173727357
976 369044675751447771076
977 371321030704280565441
978 373609074561544287348
979 375908855291294005549
980 378220421009069370612
981 380543819978196613761
982 382879100610090854596
983 385226311464558717693
984 387585501250101258084
985 389956718824217195617
986 392340013193706458196
987 394735433514974033901
988 397143029094334131988
989 399562849388314652769
990 401994944003961966372
991 404439362699146000381
992 406896155382865636356
993 409365372115554415233
994 411847063109386551604
995 414341278728583256877
996 416848069489719371316
997 419367486062030304961
998 421899579267719287428
999 424444400082264926589
1000 427001999634729076132