7 1
8 0
9 1
10 1
11 2
12 2
13 4
14 6
15 9
16 10
17 16
18 20
19 29
20 36
21 53
22 66
23 91
24 112
25 152
26 190
27 251
28 315
29 409
30 510
31 655
32 809
33 1029
34 1271
35 1602
36 1967
37 2457
38 3009
39 3729
40 4543
41 5595
42 6801
43 8321
44 10069
45 12258
46 14783
47 17906
48 21511
49 25947
50 31073
51 37315
52 44542
53 53285
54 63415
55 75587
56 89687
57 106543
58 126068
59 149284
60 176156
61 207979
62 244789
63 288200
64 338349
65 397289
66 465328
67 544997
68 636860
69 744108
70 867643
71 1011420
72 1176815
73 1368835
74 1589458
75 1844927
76 2138078
77 2476767
78 2864915
79 3312345
80 3824456
81 4413588
82 5087049
83 5860239
84 6742997
85 7754613
86 8908148
87 10227718
88 11730530
89 13446805
90 15399058
91 17625004
92 20153946
93 23033044
94 26300235
95 30014280
96 34224076
97 39002960
98 44413631
99 50547318
100 57484173
101 65337792
102 74210140
103 84242356
104 95563778
105 108349782
106 122763820
107 139023323
108 157334409
109 177966529
110 201178736
111 227304405
112 256668346
113 289682728
114 326753718
115 368390114
116 415098658
117 467506941
118 526245694
119 592087846
120 665816812
121 748383699
122 840759548
123 944112905
124 1059645141
125 1188790600
126 1333032677
127 1494129510
128 1673909483
129 1874525556
130 2098227239
131 2347647352
132 2625549102
133 2935148800
134 3279834858
135 3663531392
136 4090387227
137 4565184879
138 5092996315
139 5679643065
140 6331316676
141 7055095834
142 7858527756
143 8750209647
144 9739328517
145 10836314802
146 12052336250
147 13400032851
148 14892962453
149 16546426593
150 18376863459
151 20402775946
152 22644069656
153 25123095663
154 27863928712
155 30893539105
156 34241009483
157 37938851321
158 42022155369
159 46530071846
160 51504892900
161 56993716397
162 63047456484
163 69722714729
164 77080718544
165 85189425015
166 94122384697
167 103961108365
168 114793857734
169 126718308114
170 139840265517
171 154276664108
172 170154214177
173 187612776999
174 206803946842
175 227894852937
176 251066684632
177 276518976181
178 304468083285
179 335152014220
180 368828875221
181 405782319100
182 446319975672
183 490779601153
184 539527520664
185 592965571130
186 651529584047
187 715697229720
188 785986582203
189 862964985537
190 947247746281
191 1039508161826
192 1140476403617
193 1250950864452
194 1371797302504
195 1503961690000
196 1648469710371
197 1806441313276
198 1979090669769
199 2167742671265
200 2373833474968
201 2598929216687
202 2844727297895
203 3113077622089
204 3405984813761
205 3725632330280
206 4074385829392
207 4454820562483
208 4869726157673
209 5322137755551
210 5815342514305
211 6352915018788
212 6938725880099
213 7576982023009
214 8272237806914
215 9029440888037
216 9853946376564
217 10751569066496
218 11728601220507
219 12791872080671
220 13948769987603
221 15207310210947
222 16576162217883
223 18064727019269
224 19683170550595
225 21442511899282
226 23354663909081
227 25432533855618
228 27690072583328
229 30142389419255
230 32805811349879
231 35698014228597
232 38838093759943
233 42246715347578
234 45946198923176
235 49960690125571
236 54316261353622
237 59041107352212
238 64165665226525
239 69722837959520
240 75748136576564
241 82279935621324
242 89359641135484
243 97031982708403
244 105345211528284
245 114351434273815
246 124106846129677
247 134672112554220
248 146112642922507
249 158499027060660
250 171907356021818
251 186419721269986
252 202124590105424
253 219117376497651
254 237500879783347
255 257385937442378
256 278891937008424
257 302147562534581
258 327291391116571
259 354472746469540
260 383852393181111
261 415603512714531
262 449912510417478
263 486980131436691
264 527022397749839
265 570271883932959
266 616978803972550
267 667412469644625
268 721862549776523
269 780640737174962
270 844082206258746
271 912547518119017
272 986424306217895
273 1066129453283735
274 1152111039001671
275 1244850827152129
276 1344866514116288
277 1452714569987989
278 1568992832205929
279 1694343750451320
280 1829457376047404
281 1975075067323180
282 2131992932541459
283 2301066060243021
284 2483212481635647
285 2679417999296701
286 2890740744159361
287 3118316686031370
288 3363364870864509
289 3627193707954880
290 3911206985055961
291 4216911040094260
292 4545921665273411
293 4899972285798221
294 5280921879425387
295 5690764301344430
296 6131637363095895
297 6605833461588686
298 7115809980996765
299 7664201405248114
300 8253831228953160
301 8887725756838601
302 9569127735045969
303 10301512068355345
304 11088601411963545
305 11934384068245368
306 12843131811564359
307 13819420261332265
308 14868149249240158
309 15994566004916141
310 17204288416502876
311 18503331409946370
312 19898133500965093
313 21395586799504118
314 23003067304246163
315 24728469020867590
316 26580238510419642
317 28567413674437972
318 30699663136343577
319 32987330319243508
320 35441478316245977
321 38073939968882159
322 40897368968700325
323 43925296736900505
324 47172190597353006
325 50653518362497706
326 54385814528029421
327 58386753587976258
328 62675225325680846
329 67271418013731258
330 72196904015908044
331 77474734177339104
332 83129535110116079
333 89187616247610680
334 95677080364323462
335 102627944958211247
336 110072267755901620
337 118044284300630534
338 126580550419559850
339 135720098135610761
340 145504597327841303
341 155978532356183397
342 167189385431693314
343 179187836647852521
344 192027971899335686
345 205767509356071351
346 220468035130893381
347 236195259617735026
348 253019284515534366
349 271014892884798256
350 290261851592303534
351 310845239426781129
352 332855789543022437
353 356390260523829424
354 381551823979342324
355 408450484056175978
356 437203515996344484
357 467935940283513028
358 500781018693773607
359 535880790042423374
360 573386631076227936
361 613459861651993125
362 656272378736803708
363 702007339823419839
364 750859879333945121
365 803037880169038806
366 858762782964149282
367 918270456894086781
368 981812113524872577
369 1049655289367780712
370 1122084877519911457
371 1199404236000122187
372 1281936351996885534
373 1370025091741935862
374 1464036514004594633
375 1564360279189534422
376 1671411130756469668
377 1785630483390146219
378 1907488093307886942
379 2037483847770240074
380 2176149647795784793
381 2324051423989698283
382 2481791258046488763
383 2650009652905013666
384 2829387922621905402
385 3020650748252522587
386 3224568869259274073
387 3441961960310761593
388 3673701661395183464
389 3920714814970588246
390 4183986876432060932
391 4464565555786868424
392 4763564655130833326
393 5082168164320431379
394 5421634577708455956
395 5783301499205334968
396 6168590496775667474
397 6579012278894236278
398 7016172152287273222
399 7481775839174686596
400 7977635611538047041
401 8505676826787206019
402 9067944820542817417
403 9666612247571566994
404 10303986824789287582
405 10982519574583131942
406 11704813520585814034
407 12473632941966946006
408 13291913136628919004
409 14162770807837715505
410 15089515022986916521
411 16075658868200875177
412 17124931745864781227
413 18241292448735800600
414 19428942956217711438
415 20692343097243946494
416 22036226023981132466
417 23465614652506346088
418 24985839013469493653
419 26602554681603665119
420 28321762226103123853
421 30149827864532560278
422 32093505261549732923
423 34159958670097635199
424 36356787355915702084
425 38692051519318539360
426 41174299655022673948
427 43812597581682306426
428 46616559082274726502
429 49596378406259252413
430 52762864575514516483
431 56127477765935900744
432 59702367708150299399
433 63500414402039392969
434 67535271090664640095
435 71821409813120226510
436 76374169484833563538
437 81209806851888831420
438 86345550271731215263
439 91799656696300021898
440 97591471814833227847
441 103741493764515354146
442 110271440372295560885
443 117204320371074676198
444 124564508561042521928
445 132377825397568175286
446 140671620985441059296
447 149474864002550642755
448 158818235543594920496
449 168734228452402699628
450 179257252146268501007
451 190423743550560575519
452 202272284162093371887
453 214843723913778466870
454 228181311876721404918
455 242330834531551904322
456 257340761665748549268
457 273262400693521013959
458 290150059478895367441
459 308061218529376941998
460 327056712668426155784
461 347200923131551749166
462 368561980226015743669
463 391211977583646801259
464 415227198183198756460
465 440688353264409965898
466 467680834351899726902
467 496294979612460699367
468 526626354811477156433
469 558776050203026186733
470 592850993673588306253
471 628964281595457324459
472 667235527771361460655
473 707791232059481098349
474 750765169130224468820
475 796298799089739219485
476 844541700500603025798
477 895652027694404148220
478 949796992996045565954
479 1007153375929527462191
480 1067908060125933166309
481 1132258600195229960958
482 1200413819396325010518
483 1272594440577313567121
484 1349033751348362100331
485 1429978306189773664511
486 1515688666601591338171
487 1606440182250181655976
488 1702523814379772914406
489 1804247004721763633589
490 1911934591351089055511
491 2025929775026729534251
492 2146595137668854362055
493 2274313716843498840356
494 2409490138134799343041
495 2552551809641963008922
496 2703950180735540967219
497 2864162069712127461300
498 3033691062766584464789
499 3213068989362051281495
500 3402857476734638504763
501 3603649589097262627268
502 3816071554634217278631
503 4040784586382449964968
504 4278486800486738582163
505 4529915238508234796804
506 4795847997714491197405
507 5077106476671061951598
508 5374557740553919034300
509 5689117014206158940129
510 6021750307904955821246
511 6373477184634584122002
512 6745373674439707005547
513 7138575345502870352424
514 7554280538196715532891
515 7993753772686217740581
516 8458329337083076935867
517 8949415067750394902703
518 9468496329594636273609
519 10017140209066319064478
520 10596999928633328602953
521 11209819496682000108576
522 11857438602638449660107
523 12541797772620267556983
524 13264943796551970293337
525 14029035443542503606806
526 14836349477723160119706
527 15689286992978709261718
528 16590380080172023052981
529 17542298847090217510186
530 18547858806265669452394
531 19610028652871674364043
532 20731938449565963821978
533 21916888242647456439090
534 23168357128303300537461
535 24490012795690090983131
536 25885721567733052615331
537 27359558968999365045148
538 28915820843859854015179
539 30559035057164223855665
540 32293973803221061788991
541 34125666558458635077274
542 36059413706406439389891
543 38100800873833804716876
544 40255714009833605050903
545 42530355250487356053290
546 44931259604377574212989
547 47465312505756545698910
548 50139768274478317994186
549 52962269534085206570482
550 55940867631396346213380
551 59084044114020922980929
552 62400733313824378179241
553 65900346098294520677211
554 69592794843000868856171
555 73488519693159404216950
556 77598516173193904536315
557 81934364218964821039252
558 86508258697840832985011
559 91333041498594022039340
560 96422235263222379539245
561 101790078850704945076655
562 107451564612430678965181
563 113422477578114353280664
564 119719436640357196180652
565 126359937846333057771167
566 133362399894030975733075
567 140746211952145030457622
568 148531783911256766855879
569 156740599197044894805764
570 165395270264416143893290
571 174519596916069270645604
572 184138627576770794760944
573 194278723680874466553960
574 204967627317995566341135
575 216234532309754421643005
576 228110158877503049286864
577 240626832090825083615674
578 253818564273230199970494
579 267721141573345826865862
580 282372214896186216298982
581 297811395423108193186960
582 314080354935005208517891
583 331222931189621357494108
584 349285238589497746147479
585 368315784415859171081885
586 388365590889096794041428
587 409488323357940967846847
588 431740424904517459110484
589 455181257696752618534168
590 479873251404484412539194
591 505882059042948012971241
592 533276720592036443626747
593 562129834790309579874682
594 592517739487353352623769
595 624520700992163548290036
596 658223112839819273054924
597 693713704456540751520506
598 731085760187854404116085
599 770437349216452254937105
600 811871566881085288893424
601 855496787974028188629249
602 901426932579628931718126
603 949781745087311013925128
604 1000687086997708611056052
605 1054275244216474016206583
606 1110685249516074117289860
607 1170063220927132319854869
608 1232562716807260000067849
609 1298345108422347597592487
610 1367579970862447584392529
611 1440445493207632111253047
612 1517128908847329688074582
613 1597826946956593569672855
614 1682746306122043483273027
615 1772104151217379610870648
616 1866128634619057438696475
617 1965059442967630687252903
618 2069148370672621303145701
619 2178659921482052381522445
620 2293871939432085892729015
621 2415076270624487547809658
622 2542579457276227550336563
623 2676703465627507695743831
624 2817786449293735680602773
625 2966183549799404887012788
626 3122267736034117084697479
627 3286430684534694583699774
628 3459083702503106375551282
629 3640658695645796292897690
630 3831609182929777919420190
631 4032411360539833935897876
632 4243565217335487538967995
633 4465595704309529482915718
634 4699053960569382134516448
635 4944518598580959380167407
636 5202597051440027515792977
637 5473926985170922036952775
638 5759177779084422930093024
639 6059052077479224058567517
640 6374287416010813565043674
641 6705657926323417780788169
642 7053976122588395378353967
643 7420094773885043720219061
644 7804908866416881096218262
645 8209357659871448140882075
646 8634426842299259974802693
647 9081150788226727838886310
648 9550614924797177105425701
649 10043958211099436858066679
650 10562375735935862770982090
651 11107121439675280873566059
652 11679510965943300252562624
653 12280924649326639421503854
654 12912810645391290880164144
655 13576688209771600997757031
656 14274151133228550732547899
657 15006871340068524477829231
658 15776602657475079743257750
659 16585184763837900388589064
660 17434547324346542850495037
661 18326714322690087075804500
662 19263808597911830188287051
663 20248056596086925334387442
664 21281793346726126040517199
665 22367467674476541261805749
666 23507647656955683063066064
667 24705026340275845363754601
668 25962427724114513786133872
669 27282813028964645515911558
670 28669287258534074747422652
671 30125106071103559679461478
672 31653682974028960903513143
673 33258596856480561749931629
674 34943599875933236636824000
675 36712625714901527017333055
676 38569798224883660995439131
677 40519440475537782050057345
678 42566084227637900037752709
679 44714479849501736303893476
680 46969606697166613650616782
681 49336683979826737154600657
682 51821182132694893892796237
683 54428834720789039643674325
684 57165650897866155758892527
685 60037928446171804172328576
686 63052267423475094654663182
687 66215584445422495163180380
688 69535127632132373502972748
689 73018492249643381576429691
690 76673637077813943753439827
691 80508901538099506834118918
692 84533023615723359413208998
693 88755158612735966565955181
694 93184898769662078722571250
695 97832293795576302426081154
696 102707872347778389780711371
697 107822664504556833581505467
698 113188225275998287362795874
699 118816659200308323859732854
700 124720646074729550374377939
701 130913467872857770058360970
702 137409036901943365336286028
703 144221925256703793803217931
704 151367395628141270924851601
705 158861433529041308521672903
706 166720780999994792951055905
707 174962971863231192839526114
708 183606368593935009936649430
709 192670200882447962831377230
710 202174605963381782217893019
711 212140670791706375822777410
712 222590476148760556418984735
713 233547142765507974029212036
714 245034879553527539837251053
715 257079034038966913411353496
716 269706145098164802754101160
717 282943998098781603944549183
718 296821682554094279498550649
719 311369652403672891329494197
720 326619789037842979070307830
721 342605467189363284262275666
722 359361623820339471401378573
723 376924830138922696110754413
724 395333366885374373052317643
725 414627303034151979938907053
726 434848578064184826267525739
727 456041087957173453604489768
728 478250775089785796315281751
729 501525722193929068945375249
730 525916250565888803902607789
731 551475022714127443321450789
732 578257149642772142246321738
733 606320302977576157625674733
734 635724832149056578968948086
735 666533886858083136182838310
736 698813545057853580238359435
737 732632946697649242269378724
738 768064433483234103972958799
739 805183694921179609150570060
740 844069920924748520554047033
741 884805961272431738425533676
742 927478492221543082019046218
743 972178190593867085254807402
744 1018999915662711433008784374
745 1068042899186530234043964435
746 1119410943947779265987866102
747 1173212631172806470874351715
748 1229561537223315175373128347
749 1288576459968518914897646463
750 1350381655263189780543381159
751 1415107083976943914516392786
752 1482888670037658680152389635
753 1553868569973749207763440288
754 1628195454459180017534107497
755 1706024802388754197594543145
756 1787519208032108035189598015
757 1872848701840493385369690495
758 1962191085503205233139809850
759 2055732281878320766035047580
760 2153666700447246547263071217
761 2256197618972714499706761961
762 2363537582066932243707671266
763 2475908817409268564591468333
764 2593543670382348922405047364
765 2716685057930854428416162639
766 2845586942479452460320965898
767 2980514826784678702388515003
768 3121746270630595004856859728
769 3269571430319661107326903698
770 3424293621948381425870708056
771 3586229909502393407310634008
772 3755711718847175393682516885
773 3933085478739440897097946678
774 4118713290029478446320648761
775 4312973624277684998089976410
776 4516262053057731214680794330
777 4728992009276228044228008137
778 4951595581892296354845239857
779 5184524345482685596355868365
780 5428250226156334685529981272
781 5683266405389727082605378479
782 5950088263417758390873352248
783 6229254363887942779758011715
784 6521327481554708188208270984
785 6826895674869757976178412102
786 7146573405399432500873112755
787 7481002706085860921580126888
788 7830854400450196087055445914
789 8196829374929262671496242334
790 8579659906625555597521338118
791 8980111048851340366660703339
792 9398982076943922212642297340
793 9837107996938388742506456494
794 10295361119788808879020904542
795 10774652703947230839156175752
796 11275934669223571766179127993
797 11800201384977730149474516827
798 12348491535818841564336296141
799 12921890068125533878944432451
800 13521530220835298478228259433
801 14148595644101612382956734966
802 14804322609563277940792855131
803 15490002316133505971043369289
804 16206983295374646343956459272
805 16956673920701106636126762376
806 17740545024824979382299929969
807 18560132630050233894734072317
808 19417040796208052877549264144
809 20312944591233141237319460356
810 21249593189583539911258174369
811 22228813103930948350963586444
812 23252511555768584490967472230
813 24322679990826724374221693751
814 25441397745424857239780628269
815 26610835870152682205132409626
816 27833261117531302382940585907
817 29111040100591098910242224432
818 30446643629583929350782156842
819 31842651234356052108422385949
820 33301755880213207887244888054
821 34826768885443616905934847379
822 36420625048995532659524298817
823 38086387997167988556070377178
824 39827255758532256016094597471
825 41646566576693463407824096303
826 43547804970891030366516938818
827 45534608054860889095316641792
828 47610772124804504399264624288
829 49780259527769056833318287888
830 52047205822200745049486550014
831 54415927242930415092544020335
832 56890928483346805107707446264
833 59476910808050939299848117032
834 62178780509822950730332969198
835 65001657725315195951180540157
836 67950885624468368907833244296
837 71032039989277856842956751321
838 74250939198169235900283263315
839 77613654632924196127489198936
840 81126521525782663310298844076
841 84796150265085352659085316405
842 88629438178562626409826329824
843 92633581814174628479000691719
844 96816089739211152313319294225
845 101184795879224356431680457115
846 105747873419237835711998001258
847 110513849290611090775562794296
848 115491619267881214468216353667
849 120690463700915769469094324569
850 126120063908731903629108944671
851 131790519262431730003241076348
852 137712364985809755044896954048
853 143896590703372644846624117214
854 150354659766708960532307070390
855 157098529391427762368256417904
856 164140671638181362188926114359
857 171494095272673347690670935389
858 179172368540956472070092265246
859 187189642897823858311475493743
860 195560677727616222415980597724
861 204300866098388795863999849562
862 213426261592026057655246003996
863 222953606254645315468485114625
864 232900359713409920116349706444
865 243284729507768394514860120008
866 254125702685061765559618170983
867 265443078712490909760058089442
868 277257503759519813086869904862
869 289590506407006559890985945355
870 302464534841608798021394742731
871 315902995596406080248829542716
872 329930293901121031304899845239
873 344571875707911084775107096680
874 359854271461341567910121831798
875 375805141683950391956555811853
876 392453324451669170679389938056
877 409828884836391524743343230990
878 427963166396066743592175084471
879 446888844795967461709568475387
880 466639983648118956899635835454
881 487252092659412235562128388664
882 508762188182533722406716652469
883 531208856267664061406372664075
884 554632318316802645986698986634
885 579074499446702035384478640468
886 604579099670617456987829313656
887 631191668013536486903962974330
888 658959679680117297817896030288
889 687932616399382537982754386930
890 718162050075148771071744528347
891 749701729876377366700283812907
892 782607672906964628962564063530
893 816938258600112933357554888914
894 852754326988187348058854098846
895 890119281005037366657318544471
896 929099192983991162436518596567
897 969762915521291832324553570190
898 1012182196881474913921949689575
899 1056431801128273956549426883867
900 1102589633171912622925586738074
901 1150736868931296276883562813441
902 1200958090817472553053804953444
903 1253341428752996647379432285444
904 1307978706950324773725221898611
905 1364965596681285512363238932244
906 1424401775278847584483703435818
907 1486391091622040937390759289744
908 1551041738364791764653371692951
909 1618466431179838586118013382730
910 1688782595299593205205792268222
911 1762112559647045450192301095333
912 1838583758861362787515613028159
913 1918328943534964704127667198761
914 2001486398991326822521427279392
915 2088200172945862423765735452000
916 2178620312405699635150414331553
917 2272903110178304775085674669968
918 2371211361373446706727227376941
919 2473714630298250288150908537239
920 2580589528160789470515712429992
921 2692020002014132609779206992136
922 2808197635389703980788657175195
923 2929321961086590834248645564673
924 3055600786601723600651487844418
925 3187250532705027393600054990001
926 3324496585683393511070207338568
927 3467573663798005092514750478802
928 3616726198520867498066190205179
929 3772208731138712513699249728955
930 3934286325335450093260488909505
931 4103234996388420226774673101711
932 4279342157638522089092982749633
933 4462907084920273891111678051730
934 4654241399664643275070499727489
935 4853669571415509330586519848387
936 5061529440529518386335920056975
937 5278172761859320838319573433500
938 5503965770251356551370768660276
939 5739289768721956435618827720532
940 5984541740209164434053611406010
941 6240134983832843375599514965616
942 6506499776631911880237066921619
943 6784084061785476164936918377925
944 7073354164363756771986465869121
945 7374795535695597799232597952653
946 7688913527481555875014976156579
947 8016234196825654330692381535520
948 8357305143404409118760120845929
949 8712696380039269176890302895119
950 9083001237987702571305961141475
951 9468837308319409991228722394211
952 9870847420797078975780790964435
953 10289700661736342994894097071415
954 10726093432376681132298125508366
955 11180750549354553572139643370994
956 11654426388931598754557214643986
957 12147906076694917875942980018800
958 12662006724512805606407501528539
959 13197578716598482897846579081585
960 13755507046605893077853441728338
961 14336712707756200527425061925264
962 14942154138070706331288660865675
963 15572828722866267510838088470226
964 16229774356752379105687762104373
965 16914071067455689008668158428783
966 17626842703887245883831196750881
967 18369258690961107473237570682955
968 19142535853769419824595016969983
969 19947940313819635336079356404830
970 20786789460143506004896762465899
971 21660453998195828895433876041590
972 22570360079572947280766260739944
973 23517991515697729402631374908977
974 24504892078738447083044672111846
975 25532667893154712197783641772583
976 26602989921393665498976748656303
977 27717596547395052921938369609603
978 28878296261703909406492198609309
979 30086970452135455108077548054848
980 31345576304087708014128981419605
981 32656149814754440933058025168025
982 34020808925653647612660934256614
983 35441756778055900420144857978028
984 36921285096072041707013573939817
985 38461777702341881130463706926232
986 40065714171454105479284116319144
987 41735673626423837805370775475174
988 43474338683757314557413708099780
989 45284499552844441381442041469127
990 47169058295638617429273689487872
991 49131033252810712756583948122684
992 51173563642799491802574579371656
993 53299914340425699828720679239613
994 55513480841990487158586835542459
995 57817794424042517073267590888544
996 60216527503270975942345107587731
997 62713499205265538655680136053187
998 65312681150178096993767724525474
999 68018203463626578486985919099842
1000 70834361021497396201563378192174