1 0
2 1
3 126
4 1168
5 7334
6 35749
7 137970
8 438984
9 1208246
10 2969389
11 6662480
12 13873100
13 27144408
14 50389581
15 89424014
16 152638280
17 251834530
18 403250693
19 628798516
20 957543164
21 1427453780
22 2087456085
23 2999819778
24 4242915176
25 5914375214
26 8134700605
27 11051347640
28 14843339788
29 19726445936
30 25958969789
31 33848196630
32 43757545320
33 56114475098
34 71419198421
35 90254252764
36 113294985980
37 141321011500
38 175228691333
39 216044706506
40 264940776264
41 323249589030
42 392482009805
43 474345630368
44 570764730316
45 683901718664
46 816180127405
47 970309230110
48 1149310360328
49 1356545006226
50 1595744759589
51 1871043198980
52 2187009788540
53 2548685875588
54 2961622871861
55 3431922704914
56 3966280627880
57 4572030477470
58 5257192471773
59 6030523641096
60 6901570986764
61 7880727464480
62 8979290890525
63 10209525870758
64 11584728854056
65 13119296413514
66 14828796860405
67 16730045297580
68 18841182220668
69 21181755777116
70 23772807794789
71 26636963693530
72 29798526394760
73 33283574345878
74 37120063777901
75 41337935316464
76 45969225067980
77 51048180304440
78 56611379872013
79 62697859450286
80 69349241790664
81 76609872064130
82 84526958450245
83 93150718100948
84 102534528614396
85 112735085155764
86 123812563363605
87 135830788182050
88 148857408760808
89 162964079566606
90 178226647851389
91 194725347624280
92 212545000275980
93 231775222005968
94 252510638204541
95 274851104943414
96 298901937730280
97 324774147684410
98 352584685292053
99 382456691902076
100 414519759123964
101 448910196291980
102 485771306160965
103 525253669000938
104 567515435259336
105 612722626961414
106 661049448021005
107 712678603635520
108 767801628940748
109 826619227102696
110 889341617025389
111 956188890855230
112 1027391381464200
113 1103190040095858
114 1183836824359781
115 1269595096761764
116 1360740033958780
117 1457559046929380
118 1560352212251893
119 1669432714684466
120 1785127301242664
121 1907776746972030
122 2037736332614685
123 2175376334370728
124 2321082525956876
125 2475256693166464
126 2638317161136605
127 2810699334529990
128 2992856250840488
129 3185259147033386
130 3388398039732789
131 3602782319170380
132 3828941357111420
133 4067425128975548
134 4318804850371621
135 4583673628267514
136 4862647127017480
137 5156364249471350
138 5465487833391533
139 5790705363405456
140 6132729698722764
141 6492299816848280
142 6870181573523405
143 7267168479130318
144 7684082491795016
145 8121774827426914
146 8581126786934405
147 9063050600857460
148 9568490291660028
149 10098422553926676
150 10653857652709589
151 11235840340273730
152 11845450791489640
153 12483805558125038
154 13152058542288061
155 13851401989276664
156 14583067500090380
157 15348327063862320
158 16148494110470973
159 16984924583593046
160 17859018034460264
161 18772218736584730
162 19726016821719125
163 20721949437319708
164 21761601925781756
165 22846609025718764
166 23978656095558405
167 25159480359729930
168 26390872177719368
169 27674676336270566
170 29012793365011789
171 30407180875789280
172 31859854925990860
173 33372891406144328
174 34948427452077101
175 36588662881925214
176 38295861658281480
177 40072353375774290
178 41920534774370213
179 43842871278695236
180 45841898563671164
181 47920224146765380
182 50080529007153845
183 52325569232098898
184 54658177690845096
185 57081265736338014
186 59597824935072605
187 62210928825379400
188 64923734704458508
189 67739485444473056
190 70661511338015389
191 73693231973261030
192 76838158139127080
193 80099893760753418
194 83482137865626741
195 86988686580669164
196 90623435160614780
197 94390380047999260
198 98293620965089253
199 102337363038080026
200 106525918953891464
201 110863711149894230
202 115355274036899565
203 120005256255747888
204 124818422967833036
205 129799658179900664
206 134953967103461005
207 140286478549157870
208 145802447356437448
209 151507256858862146
210 157406421385416389
211 163505588798152980
212 169810543066530300
213 176327206878792308
214 183061644290744981
215 190020063412284514
216 197208819132034280
217 204634415880449230
218 212303510431748093
219 220222914745035416
220 228399598844977164
221 236840693742395280
222 245553494395148285
223 254545462709666678
224 263824230583513576
225 273397602989342714
226 283273561100627605
227 293460265459537340
228 303966059187336188
229 314799471237685836
230 325969219693230789
231 337484215105849130
232 349353563880952520
233 361586571706220998
234 374192747025159821
235 387181804555867264
236 400563668855403980
237 414348477930156200
238 428546586892586733
239 443168571664769406
240 458225232729104264
241 473727598926612530
242 489686931303212005
243 506114727004375268
244 523022723218574716
245 540422901169920164
246 558327490160396405
247 576748971662109810
248 595700083459954728
249 615193823845112126
250 635243455859794589
251 655862511593653480
252 677064796532265740
253 698864393958119488
254 721275669404519261
255 744313275162833414
256 767992154843507880
257 792327547991272170
258 817334994754965173
259 843030340612409996
260 869429741150768764
261 896549666902809980
262 924406908239522725
263 953018580319513658
264 982402128095624456
265 1012575331379209014
266 1043556309962511405
267 1075363528799587280
268 1108015803246213068
269 1141532304359229016
270 1175932564255763789
271 1211236481532790030
272 1247464326747461960
273 1284636747958687778
274 1322774776330391301
275 1361899831796918964
276 1402033728791049980
277 1443198682035069140
278 1485417312395363413
279 1528712652801005186
280 1573108154226786664
281 1618627691741171630
282 1665295570619632445
283 1713136532523841848
284 1762175761747190796
285 1812438891527105264
286 1863952010424636605
287 1916741668771801750
288 1970834885187151208
289 2026259153160044506
290 2083042447704114389
291 2141213232080402780
292 2200800464590653180
293 2261833605441245868
294 2324342623678263941
295 2388358004194179914
296 2453910754806654280
297 2521032413409939110
298 2589755055199381453
299 2660111299969522976
300 2732134319486293964
301 2805857844933801480
302 2881316174436213165
303 2958544180655239838
304 3037577318463721736
305 3118451632695824914
306 3201203765974356005
307 3285870966615705220
308 3372491096612929148
309 3461102639697486596
310 3551744709480142389
311 3644457057671555730
312 3739280082383071400
313 3836254836508233758
314 3935423036185545181
315 4036827069342992264
316 4140510004324864780
317 4246515598601394080
318 4354888307561739293
319 4465673293390851366
320 4578916434030746664
321 4694664332226723530
322 4812964324659056885
323 4933864491160707628
324 5057413664021585276
325 5183661437379903964
326 5312658176701173605
327 5444455028345369690
328 5579103929222826888
329 5716657616539403286
330 5857169637631463789
331 6000694359891232880
332 6147286980783068620
333 6297003537951211448
334 6449900919419563021
335 6606036873884052014
336 6765470021098145480
337 6928259862352066050
338 7094466791046276933
339 7264152103359798356
340 7437378009013920764
341 7614207642131881780
342 7794705072195075605
343 7978935315096365218
344 8166964344291069416
345 8358859102046198414
346 8554687510788513405
347 8754518484551987160
348 8958421940525244428
349 9166468810699562576
350 9378731053618014589
351 9595281666226338230
352 9816194695826116840
353 10041545252130858938
354 10271409519425565461
355 10505864768830375164
356 10744989370668880380
357 10988862806941707020
358 11237565683905954373
359 11491179744761091946
360 11749787882441912264
361 12013474152519140230
362 12282323786208301325
363 12556423203487452608
364 12835860026324382156
365 13120723092013884264
366 13411102466625719405
367 13707089458563869630
368 14008776632237701768
369 14316257821845652466
370 14629628145272050789
371 14948984018097695780
372 15274423167724808060
373 15606044647616976228
374 15943948851654720501
375 16288237528607297714
376 16639013796721373480
377 16996382158427188990
378 17360448515162851613
379 17731320182317380136
380 18109105904293137164
381 18493915869688282880
382 18885861726599886045
383 19285056598048329798
384 19691615097523651496
385 20105653344654457514
386 20527288981000055605
387 20956641185966449100
388 21393830692846838908
389 21838979804987280956
390 22292212412078148389
391 22753654006572049530
392 23223431700228854280
393 23701674240788483318
394 24188512028772116141
395 24684077134412475664
396 25188503314713848780
397 25701926030642503960
398 26224482464448168653
399 26756311537117230926
400 27297553925958331464
401 27848352082321013730
402 28408850249448101765
403 28979194480462476788
404 29559532656488925436
405 30150014504911734164
406 30750791617768706005
407 31362017470282277570
408 31983847439528415848
409 32616438823243976046
410 33259950858773203389
411 33914544742154063480
412 34580383647345087500
413 35257632745593420208
414 35946459224944760381
415 36647032309895885014
416 37359523281190450280
417 38084105495758763930
418 38820954406802225493
419 39570247584023132316
420 40332164734000551164
421 41106887720712956780
422 41894600586208340485
423 42695489571422493578
424 43509743137146171976
425 44337551985141850214
426 45179109079410774605
427 46034609667611027040
428 46904251302627312588
429 47788233864293185736
430 48686759581266431789
431 49600033053058321630
432 50528261272217459720
433 51471653646668946898
434 52430422022209581221
435 53404780705159821764
436 54394946485173241980
437 55401138658204200900
438 56423579049634462133
439 57462492037559492306
440 58518104576235172264
441 59590646219685656030
442 60680349145473114205
443 61787448178630100168
444 62912180815755279116
445 64054787249273261664
446 65215510391859285405
447 66394595901029489510
448 67592292203897529128
449 68808850522098278026
450 70044524896879369589
451 71299572214361327980
452 72574252230967042940
453 73868827599021343388
454 75183563892521426661
455 76518729633078901914
456 77874596316034207880
457 79251438436744166870
458 80649533517043438573
459 82069162131880638896
460 83510607936129890764
461 84974157691578575480
462 86460101294092054925
463 87968731800956136558
464 89500345458398054856
465 91055241729286744514
466 92633723321013182405
467 94236096213551576980
468 95862669687702185468
469 97513756353516540916
470 99189672178905872789
471 100890736518433506530
472 102617272142292029160
473 104369605265466009678
474 106148065577081064701
475 107952986269940061464
476 109784704070247251980
477 111643559267521133840
478 113529895744696834813
479 115444061008418820086
480 117386406219524722664
481 119357286223721099130
482 121357059582451914645
483 123386088603960562748
484 125444739374546227196
485 127533381790015394764
486 129652389587329329605
487 131802140376448321450
488 133983015672373521608
489 136195400927387182406
490 138439685563492117389
491 140716263005051201280
492 143025530711627730380
493 145367890211027465768
494 147743747132543183341
495 150153511240402556414
496 152597596467420198280
497 155076420948854693810
498 157590407056471450853
499 160139981432812203876
500 162725575025672003964
501 165347623122784530980
502 168006565386716565365
503 170702845889972458738
504 173436913150309444136
505 176209220166264628414
506 179020224452894511005
507 181870388077727874920
508 184760177696932897548
509 187690064591699330496
510 190660524704836599389
511 193672038677588676230
512 196725091886666578600
513 199820174481499351658
514 202957781421704390581
515 206138412514777962764
516 209362572454006790780
517 212630770856601558780
518 215943522302053206693
519 219301346370712878266
520 222704767682596390664
521 226154315936414095030
522 229650525948826999085
523 233193937693930024528
524 236785096342963273676
525 240424552304252181464
526 244112861263377430605
527 247850584223575509390
528 251638287546370793288
529 255476542992440033186
530 259365927762710134789
531 263307024539690115380
532 267300421529038125820
533 271346712501364427348
534 275446496834271214421
535 279600379554630176514
536 283808971381098693480
537 288072888766875560750
538 292392753942697142333
539 296769194960074851256
540 301202845734774858764
541 305694346090540935280
542 310244341803061327805
543 314853484644180580118
544 319522432426357203816
545 324251849047368109914
546 329042404535260712405
547 333894775093553616860
548 338809643146686808828
549 343787697385722258476
550 348829632814295859589
551 353936150794821622730
552 359107959094949044040
553 364345771934274572838
554 369650310031308102861
555 375022300650695413664
556 380462477650697490380
557 385971581530927651720
558 391550359480347417773
559 397199565425522050846
560 402919960079136704264
561 408712310988774115730
562 414577392585954783525
563 420515986235440565508
564 426528880284802642556
565 432616870114254789764
566 438780758186752900405
567 445021354098361709330
568 451339474628889664168
569 457735943792792894366
570 464211592890349229789
571 470767260559103222280
572 477403792825583125260
573 484122043157290788128
574 490922872514965423901
575 497807149405122210214
576 504775749932866685480
577 511829557854985903690
578 518969464633317313013
579 526196369488396325036
580 533511179453383543164
581 540914809428272620380
582 548408182234379718245
583 555992228669115540698
584 563667887561040917896
585 571436105825206917014
586 579297838518780458605
587 587254048896956418800
588 595305708469157199308
589 603453797055520748856
590 611699302843678021389
591 620043222445820858030
592 628486560956061281480
593 637030332008083193218
594 645675557833087465541
595 654423269318031422164
596 663274506064163702780
597 672230316445855508660
598 681291757669729228053
599 690459895834085441826
600 699735805988629311464
601 709120572194497353230
602 718615287584585603965
603 728221054424180185688
604 737938984171891277836
605 747770197540891507664
606 757715824560459771005
607 767777004637831497270
608 777954886620356374248
609 788250628857964549946
610 798665399265942330389
611 809200375388018393980
612 819856744459761544700
613 830635703472291028108
614 841538459236300435781
615 852566228446396225514
616 863720237745751886280
617 875001723791078778630
618 886411933317914682893
619 897952123206231089216
620 909623560546360265164
621 921427522705243138280
622 933365297392999032685
623 945438182729818300478
624 957647487313178890376
625 969994530285387897714
626 982480641401449141605
627 995107161097257816740
628 1007875440558123268988
629 1020786841787620945636
630 1033842737676774572789
631 1047044512073569614130
632 1060393559852799066920
633 1073891286986242652798
634 1087539110613180462621
635 1101338459111242116264
636 1115290772167592499980
637 1129397500850455145600
638 1143660107680974317533
639 1158080066705416875206
640 1172658863567714980264
641 1187397995582350719530
642 1202298971807583716405
643 1217363313119022805068
644 1232592552283542843516
645 1247988234033547743164
646 1263551915141580794405
647 1279285164495283369210
648 1295189563172703083528
649 1311266704517952503926
650 1327518194217219484589
651 1343945650375130222480
652 1360550703591466120140
653 1377334997038235547288
654 1394300186537101594061
655 1411447940637166910414
656 1428779940693116727880
657 1446297880943721161570
658 1464003468590697891973
659 1481898423877936327796
660 1499984480171084352764
661 1518263384037498760980
662 1536736895326560487125
663 1555406787250355739458
664 1574274846464724145256
665 1593342873150675020014
666 1612612681096172873405
667 1632086097778293266680
668 1651764964445750137868
669 1671651136201795712816
670 1691746482087494121789
671 1712052885165369843030
672 1732572242603432096360
673 1753306465759576311578
674 1774257480266363798101
675 1795427226116180743964
676 1816817657746777673980
677 1838430744127190498540
678 1860268468844044286213
679 1882332830188240894986
680 1904625841242031598664
681 1927149529966475846630
682 1949905939289287296845
683 1972897127193068263648
684 1996125166803933723596
685 2019592146480526024264
686 2043300169903421442605
687 2067251356164929741150
688 2091447839859287872008
689 2115891771173248980306
690 2140585315977067860389
691 2165530655915884019780
692 2190729988501503507580
693 2216185527204580665668
694 2241899501547200962741
695 2267874157195866072914
696 2294111756054882362280
697 2320614576360153948510
698 2347384912773381500253
699 2374425076476667944776
700 2401737395267532253964
701 2429324213654332480480
702 2457187892952099217565
703 2485330811378780657638
704 2513755364151900426536
705 2542463963585629371914
706 2571459039188272486005
707 2600743037760172144620
708 2630318423492028845948
709 2660187678063640634396
710 2690353300743062396389
711 2720817808486186216730
712 2751583736036743985800
713 2782653636026733449558
714 2814030079077268895981
715 2845715653899857673264
716 2877712967398103736780
717 2910024644769839423480
718 2942653329609686654093
719 2975601684012048765166
720 3008872388674534174664
721 3042468143001813086530
722 3076391665209908441285
723 3110645692430922321428
724 3145232980818199022076
725 3180156305651925998964
726 3215418461445173907605
727 3251022262050376949090
728 3286970540766254739688
729 3323266150445176923086
730 3359911963600971745789
731 3396910872517179817880
732 3434265789355754283020
733 3471979646266208623248
734 3510055395495213325821
735 3548496009496642641014
736 3587304481042072661480
737 3626483823331731955450
738 3666037070105905987733
739 3705967275756796564156
740 3746277515440837536764
741 3786970885191468008780
742 3828050502032364280005
743 3869519504091131775018
744 3911381050713458198216
745 3953638322577729161414
746 3996294521810107531405
747 4039352872100077746560
748 4082816618816456353228
749 4126689029123870014376
750 4170973392099702244589
751 4215673018851510127230
752 4260791242634912271240
753 4306331418971949266738
754 4352296925769917900261
755 4398691163440680392164
756 4445517555020449920380
757 4492779546290053696420
758 4540480605895674861173
759 4588624225470074469746
760 4637213919754294836264
761 4686253226719845511230
762 4735745707691373165725
763 4785694947469816658408
764 4836104554456048562956
765 4886978160775004435264
766 4938319422400301101405
767 4990132019279345249030
768 5042419655458933606568
769 5095186059211345996266
770 5148434983160932548789
771 5202170204411196368780
772 5256395524672372942460
773 5311114770389507580028
774 5366331792871032187301
775 5422050468417842662714
776 5478274698452878217480
777 5535008409651203918390
778 5592255554070597754413
779 5650020109282643529936
780 5708306078504330889164
781 5767117490730163777880
782 5826458400864778650445
783 5886332889856073731598
784 5946745064828850644296
785 6007699059218969716514
786 6069199032908020281605
787 6131249172358507288500
788 6193853690749555539708
789 6257016828113132876756
790 6320742851470793634389
791 6385036054970943686530
792 6449900760026628408680
793 6515341315453844883118
794 6581362097610379674941
795 6647967510535173508664
796 6715161986088214176780
797 6782949984090959013360
798 6851335992467288267453
799 6920324527384990712726
800 6989920133397782831464
801 7060127383587862912730
802 7130950879709001406165
803 7202395252330168874588
804 7274465160979702890236
805 7347165294290015221164
806 7420500370142840656005
807 7494475135815028816970
808 7569094368124880312648
809 7644362873579028583846
810 7720285488519868797389
811 7796867079273535144480
812 7874112542298427901900
813 7952026804334291616008
814 8030614822551845771181
815 8109881584702969306014
816 8189832109271440342280
817 8270471445624232493330
818 8351804674163369120293
819 8433836906478336906116
820 8516573285499060119164
821 8600018985649436939780
822 8684179213001439224885
823 8769059205429777087378
824 8854664232767129668776
825 8940999596959943485214
826 9028070632224799728605
827 9115882705205351906440
828 9204441215129835205388
829 9293751593969148965536
830 9383819306595513653789
831 9474649850941703726630
832 9566248758160857774120
833 9658621592786867338698
834 9751773952895345804021
835 9845711470265178750764
836 9940439810540657177980
837 10035964673394194990300
838 10132291792689632152933
839 10229426936646124918106
840 10327375908002624528264
841 10426144544182945803030
842 10525738717461427018605
843 10626164335129182489968
844 10727427339660949267916
845 10829533708882529364664
846 10932489456138828923405
847 11036300630462495748910
848 11140973316743156617928
849 11246513635897255789826
850 11352927745038496139589
851 11460221837648884336980
852 11568402143750381497340
853 11677474930077160731188
854 11787446500248473021461
855 11898323194942122858914
856 12010111392068555067880
857 12122817506945554256270
858 12236447992473558325373
859 12351009339311587476696
860 12466508076053790154764
861 12582950769406607366480
862 12700344024366556819325
863 12818694484398638322358
864 12938008831615361895656
865 13058293786956400035514
866 13179556110368865584405
867 13301802600988216656380
868 13425040097319790070268
869 13549275477420964744716
870 13674515659083956510789
871 13800767600019245799530
872 13928038298039639663560
873 14056334791244969593478
874 14185664158207426591501
875 14316033518157534966464
876 14447450031170766315980
877 14579920898354795163240
878 14713453362037397717613
879 14848054705954995229886
880 14983732255441843414664
881 15120493377619869414130
882 15258345481589157779045
883 15397296018619086944548
884 15537352482340117679996
885 15678522408936234993764
886 15820813377338044975605
887 15964233009416528060850
888 16108788970177450202408
889 16254488967956433438206
890 16401340754614687343389
891 16549352125735402858280
892 16698530920820809984780
893 16848885023489900845568
894 17000422361676819602141
895 17153150907829920729414
896 17307078679111497146280
897 17462213737598179703210
898 17618564190482009529653
899 17776138190272184745676
900 17934943934997483043964
901 18094989668409361649980
902 18256283680185736169765
903 18418834306135439836538
904 18582649928403364668936
905 18747738975676286055414
906 18914109923389372281005
907 19081771293933380514320
908 19250731656862540774348
909 19420999629103129398296
910 19592583875162733533389
911 19765493107340208177230
912 19939736085936327293000
913 20115321619465130527458
914 20292258564865967061381
915 20470555827716238123764
916 20650222362444839702780
917 20831267172546306988180
918 21013699310795662081493
919 21197527879463966512066
920 21382762030534580098664
921 21569410965920127698030
922 21757483937680175383485
923 21946990248239617598328
924 22137939250607776830476
925 22330340348598217356464
926 22524202997049274604605
927 22719536702045301688790
928 22916351021138634666088
929 23114655563572278072986
930 23314459990503312296789
931 23515774015227024340380
932 23718607403401763540220
933 23922969973274523799148
934 24128871595907253897221
935 24336322195403897445514
936 24545331749138164049480
937 24755910287982033250150
938 24968067896534992813133
939 25181814713354012937056
940 25397160931184257954764
941 25614116797190537102280
942 25832692613189495932205
943 26052898735882549949918
944 26274745577089562052616
945 26498243603983265352914
946 26723403339324432970405
947 26950235361697796376260
948 27178750305748713877628
949 27408958862420590830276
950 27640871779193053169589
951 27874499860320875851730
952 28109853967073667798440
953 28346945017976314940638
954 28585783989050182957661
955 28826381914055081310664
956 29068749884731990170380
957 29312899051046551841120
958 29558840621433328284573
959 29806585863040826348646
960 30056146101977292308264
961 30307532723557277326730
962 30560757172548975447925
963 30815830953422335731308
964 31072765630597950143356
965 31331572828696718820764
966 31592264232790294322405
967 31854851588652306488730
968 32119346703010369528968
969 32385761443798872958166
970 32654107740412558007789
971 32924397583960881135280
972 33196643027523166259660
973 33470856186404547351928
974 33747049238392703010701
975 34025234424015384655214
976 34305424046798739969480
977 34587630473526433233090
978 34871866134499564175813
979 35158143523797386994836
980 35446475199538831175164
981 35736873784144825755380
982 36029351964601428682645
983 36323922492723762902498
984 36620598185420760830696
985 36919391924960718856014
986 37220316659237663524605
987 37523385402038531058200
988 37828611233311161860108
989 38136007299433111664656
990 38445586813481280987389
991 38757363055502364535030
992 39071349372784122235880
993 39387559180127473553018
994 39706005960119416744341
995 40026703263406774735164
996 40349664708970769270780
997 40674903984402425018060
998 41002434846178805286853
999 41332271119940081043626
1000 41664426700767434891464