7 7
8 0
9 8
10 8
11 17
12 17
13 36
14 43
15 74
16 85
17 136
18 167
19 254
20 308
21 437
22 550
23 754
24 944
25 1270
26 1581
27 2088
28 2588
29 3356
30 4160
31 5326
32 6568
33 8306
34 10217
35 12776
36 15634
37 19413
38 23644
39 29134
40 35360
41 43250
42 52285
43 63599
44 76547
45 92608
46 111079
47 133705
48 159774
49 191477
50 228012
51 272104
52 322985
53 383912
54 454277
55 538082
56 634735
57 749295
58 881403
59 1037165
60 1216663
61 1427470
62 1670104
63 1953989
64 2280413
65 2660908
66 3097987
67 3605902
68 4188452
69 4863492
70 5636870
71 6530380
72 7552761
73 8731077
74 10077420
75 11625461
76 13391962
77 15418448
78 17727928
79 20371854
80 23380781
81 26818722
82 30726385
83 35182538
84 40241080
85 45999587
86 52527965
87 59947274
88 68348042
89 77879637
90 88659084
91 100870843
92 114664323
93 130267757
94 147871715
95 167757088
96 190166107
97 215445275
98 243900022
99 275957503
100 312002372
101 352559494
102 398112252
103 449305579
104 506743273
105 571217988
106 643482719
107 724508588
108 815232766
109 916845089
110 1030507033
111 1157675118
112 1299786567
113 1458620520
114 1635952165
115 1833953293
116 2054809016
117 2301168868
118 2575718488
119 2881683250
120 3222358516
121 3601668060
122 4023644821
123 4493057233
124 5014833540
125 5594759313
126 6238847443
127 6954111017
128 7747870018
129 8628617601
130 9605252867
131 10688044751
132 11887796670
133 13216913488
134 14688485856
135 16317483164
136 18119746466
137 20113315466
138 22317334044
139 24753519847
140 27444970617
141 30417805773
142 33699859253
143 37322503486
144 41319237790
145 45727707984
146 50588173583
147 55945762244
148 61848801092
149 68351323438
150 75511273477
151 83393283347
152 92066737775
153 101608871983
154 112102678158
155 123640349529
156 136321045266
157 150254709988
158 165559678654
159 182366939064
160 200817562802
161 221067447845
162 243284597529
163 267654384290
164 294376665620
165 323671659566
166 355776881903
167 390953690016
168 429484077770
169 471677950930
170 517869770846
171 568426681887
172 623745002397
173 684259286780
174 750438715763
175 822797185785
176 901889606868
177 988323186965
178 1082753644523
179 1185897810851
180 1298529845108
181 1421495291821
182 1555707327622
183 1702162501260
184 1861937055087
185 2036204531391
186 2226232295203
187 2433401212364
188 2659202449605
189 2905259543495
190 3173325563110
191 3465307839241
192 3783265698577
193 4129438155942
194 4506242360150
195 4916304695962
196 5362460113974
197 5847787045505
198 6375607926284
199 6949528374847
200 7573439170578
201 8251560327594
202 8988444823313
203 9789028159060
204 10658634330582
205 11603031544297
206 12628440856890
207 13741598949101
208 14949769941004
209 16260816102092
210 17683213582296
211 19226132044197
212 20899455026952
213 22713869789928
214 24680893122659
215 26812972695453
216 29123519455121
217 31627021946062
218 34339086415668
219 37276565961749
220 40457609656382
221 43901808427780
222 47630254919679
223 51665708259840
224 56032666435541
225 60757552628097
226 65868802128348
227 71397073048122
228 77375350375728
229 83839184239263
230 90826813832221
231 98379437096241
232 106541357658802
233 115360290060373
234 124887533586823
235 135178317701297
236 146292006954256
237 158292492226781
238 171248431473588
239 185233692823008
240 200327636966670
241 216615618945955
242 234189318489369
243 253147308593882
244 273595441010108
245 295647490458392
246 319425603861594
247 345061030183892
248 372694642869723
249 402477767048376
250 434572785921565
251 469154078217513
252 506408721265140
253 546537553255329
254 589755987045882
255 636295214209539
256 686403145546537
257 740345775671461
258 798408268924964
259 860896505668992
260 928138334382522
261 1000485324188601
262 1078314206687703
263 1162028861905951
264 1252061977272051
265 1348877297687843
266 1452971532146578
267 1564876903294755
268 1685163336280258
269 1814441347153205
270 1953364553863078
271 2102632947882754
272 2262995771980240
273 2435255225969669
274 2620269761716668
275 2818958279782160
276 3032303899669138
277 3261358711372773
278 3507248085731082
279 3771176054000925
280 4054430231671379
281 4358387907741058
282 4684521665877771
283 5034406275424694
284 5409725103899744
285 5812277914530248
286 6243988176159347
287 6706911884507336
288 7203245890432189
289 7735337876886008
290 8305695841046355
291 8916999376800697
292 9572110463632206
293 10274086222323911
294 11026191184271918
295 11831911709096863
296 12694969929140309
297 13619340042727070
298 14609264153193248
299 15669270677094050
300 16804192326435603
301 18019186900873570
302 19319757691898207
303 20711776963136449
304 22201509090247210
305 23795637069872055
306 25501288749972855
307 27326066750018298
308 29278078179477027
309 31365968400900921
310 33598954683653462
311 35986864293196267
312 38540172584686785
313 41270045961025608
314 44188384971756406
315 47307872751011007
316 50642023756856836
317 54205238373282930
318 58012858005465315
319 62081226613171024
320 66427752963466669
321 71070979958626527
322 76030654945612701
323 81327807804319192
324 86984830325475382
325 93025564141744393
326 99475390306575955
327 106361328284040807
328 113712136998379152
329 121558426242620715
330 129932770624939171
331 138869834919161435
332 148406502503755339
333 158582016362858073
334 169438123805243814
335 181019235026135539
336 193372586111190103
337 206548417296732902
338 220600156500776619
339 235584619676902853
340 251562217381474174
341 268597179897550906
342 286757789649459570
343 306116634089315569
344 326750867100566546
345 348742492996743179
346 372178660426634762
347 397151981225855059
348 423760860754971511
349 452109855783153988
350 482310045649499974
351 514479433851875521
352 548743364936419981
353 585234975006902804
354 624095659825961595
355 665475580067462464
356 709534186749219225
357 756440787732686750
358 806375137318542679
359 859528071248024245
360 916102168091412079
361 976312460843732644
362 1040387178615192517
363 1108568543853393919
364 1181113603827035352
365 1258295123541710821
366 1340402517607557455
367 1427742850070829967
368 1520641878468386993
369 1619445173089067742
370 1724519286369854782
371 1836253005525642404
372 1955058661953036226
373 2081373532755075632
374 2215661306485503966
375 2358413650867886754
376 2510151853070569105
377 2671428572876214605
378 2842829677749577946
379 3024976202891703276
380 3218526403650408804
381 3424177946321636673
382 3642670202997882768
383 3874786699660327182
384 4121357681396560535
385 4383262847308801622
386 4661434217164068015
387 4956859185963160141
388 5270583726568086462
389 5603715800442658212
390 5957428934675433634
391 6332966029475612668
392 6731643352288910482
393 7154854787161179312
394 7604076293395992219
395 8080870646900900882
396 8586892416116411522
397 9123893251012058014
398 9693727434849685929
399 10298357782663257048
400 10939861833891597880
401 11620438428987740952
402 12342414615140968240
403 13108252977215317847
404 13920559336717515242
405 14782090921645731638
406 15695764947657352215
407 16664667720666257820
408 17692064198921825729
409 18781408132450065363
410 19936352715531148881
411 21160761878449707648
412 22458722151794283864
413 23834555238537833290
414 25292831224807625857
415 26838382574218013699
416 28476318834362878288
417 30212042210718651255
418 32051263934273493286
419 34000021589315512729
420 36064697325506715251
421 38252037132675633462
422 40569171100395691833
423 43023634853710730764
424 45623392085122617807
425 48376858388144501786
426 51292926310767305168
427 54380991849125848672
428 57650982298180273839
429 61113385695856026384
430 64779281776147066237
431 68660374685065761336
432 72769027373951990243
433 77118297942790365066
434 81721977847443762449
435 86594632263708391412
436 91751642521879182061
437 97209250926615207189
438 102984607876083295235
439 109095821618748556244
440 115562010562682059826
441 122403358501230403159
442 129641172671426967026
443 137297945036539190423
444 145397416711417070968
445 153964645951755958781
446 163026079629126658534
447 172609628645027590710
448 182744747209942508855
449 193462516475446702270
450 204795732450621303058
451 216778998728392187165
452 229448823959645915449
453 242843724641412460955
454 257004333164953231593
455 271973511734105686837
456 287796472109363644946
457 304520901835687456546
458 322197096921047312193
459 340878101675314690672
460 360619855690040735413
461 381481348724702867079
462 403524783495842924357
463 426815747195259488195
464 451423391752218087463
465 477420623731535347532
466 504884303903894527399
467 533895457451529531781
468 564539494870319170870
469 596906444608663709482
470 631091197532569693661
471 667193764341134776744
472 705319546054236633606
473 745579618787631108779
474 788091032974202943624
475 832977128345281628868
476 880367864872810644209
477 930400171093481616044
478 983218310063195561246
479 1038974264479441761221
480 1097828141273797028041
481 1159948597338565095831
482 1225513286750588910344
483 1294709331293652686782
484 1367733814710924453276
485 1444794302638235270216
486 1526109388726610670465
487 1611909269067113439660
488 1702436345512881753175
489 1797945860187863326441
490 1898706561873933688294
491 2005001406757832605431
492 2117128294337995741633
493 2235400841181337468101
494 2360149193451299302692
495 2491720881124190112645
496 2630481714950361159057
497 2776816729324254300051
498 2931131172270712091849
499 3093851545980234223076
500 3265426699268697782819
501 3446328975686627286260
502 3637055418840498577090
503 3838129038969512785187
504 4050100142548246679709
505 4273547729305014621594
506 4509080958657416863166
507 4757340690332083883671
508 5019001101426404317973
509 5294771385090027896468
510 5585397533368244966675
511 5891664209832194233621
512 6214396714853192680884
513 6554463049633174791282
514 6912776082197418650923
515 7290295821992123943916
516 7688031806679181882668
517 8107045608348458928171
518 8548453463167145092705
519 9013429032315925419053
520 9503206298703535608263
521 10019082607995312729766
522 10562421858968777994029
523 11134657852478901511025
524 11737297804621959920480
525 12371926034194647090351
526 13040207830672597130761
527 13743893513692090219251
528 14484822690959788544296
529 15264928726540716042057
530 16086243427221898097107
531 16950901959955101253467
532 17861148008927116898910
533 18819339186408951977318
534 19827952706869734464597
535 20889591339757456413547
536 22006989651464460807584
537 23183020553242976532132
538 24420702166724101564651
539 25723205025291371623295
540 27093859624211426415487
541 28536164339391989385630
542 30053793729043338049723
543 31650607239878151193400
544 33330658333635496784845
545 35098204057487310044815
546 36957715075771886468398
547 38913886188708778027690
548 40971647357361767423521
549 43136175262788808228625
550 45412905420646024821092
551 47807544881674662533083
552 50326085541533936903434
553 52974818093122059710382
554 55760346647258133714892
555 58689604057824418463640
556 61769867979884715803341
557 65008777700101409774688
558 68414351770865492081728
559 71995006490974132363777
560 75759575267448153341521
561 79717328905151290996466
562 83877996862286376319579
563 88251789522601258186222
564 92849421526195842090156
565 97682136214307617768019
566 102761731234147714673886
567 108100585364116864344053
568 113711686610051282293240
569 119608661638223770811161
570 125805806600762417429278
571 132318119425090803837897
572 139161333628538884605332
573 146351953736133238813428
574 153907292368719713883129
575 161845509086405061365785
576 170185651061039350771390
577 178947695670326802015840
578 188152595094472185386633
579 197822323016230487087967
580 207979923513124173945706
581 218649562251715164209088
582 229856580081286482311397
583 241627549146643973312008
584 253990331626783817167197
585 266974141229835066341027
586 280609607561285205775570
587 294928843507549914447248
588 309965515763108128286712
589 325754918655951687270204
590 342334051411820464588235
591 359741699025788536053357
592 378018516895050896131404
593 397207119396520234037787
594 417352172577692727091437
595 438500491160770797796524
596 460701140044452535757979
597 484005540521206606737676
598 508467581411853071188953
599 534143735354679895493646
600 561093180469917347747953
601 589377927657928268970968
602 619062953772671156270403
603 650216340951790637430467
604 682909422367512698523508
605 717216934704727769360963
606 753217177655113328312898
607 790992180760915592025408
608 830627877924152291939889
609 872214289944493945216196
610 915845715430928208184101
611 961620930482713367511292
612 1009643397516716005733726
613 1060021483671723895308640
614 1112868689201701019811596
615 1168303886326744568712552
616 1226451568991715847320561
617 1287442114042825418797697
618 1351412054313558762574099
619 1418504364175383689740878
620 1488868758089748550364568
621 1562662002765930058249873
622 1640048243510393583501503
623 1721199345425641382487509
624 1806295250097749741420822
625 1895524348488655508242456
626 1989083870730698075567454
627 2087180293602634450260954
628 2190029766448118524007569
629 2297858556384528703375509
630 2410903513632251488369828
631 2529412557886952886043223
632 2653645186640182165293377
633 2783873006451983930275232
634 2920380288162748406726392
635 3063464547136174188277379
636 3213437149609683600804782
637 3370623946340019586704848
638 3535365934717323709680791
639 3708019950639591948090249
640 3888959391426290823954685
641 4078574971176222424196460
642 4277275509963162520119721
643 4485488758397344227224131
644 4703662259071107993153849
645 4932264246550402668443639
646 5171784587566170150756856
647 5422735763212444627988609
648 5685653894952762587912374
649 5961099816399372963709563
650 6249660192827273669224615
651 6551948690558798756733019
652 6868607198355175085328248
653 7200307103136736299690783
654 7547750622357760843959888
655 7911672195559558865280497
656 8292839937633768973832989
657 8692057156538753658955937
658 9110163938224890300049626
659 9548038801749702199260451
660 10006600427581821141477560
661 10486809462333155815576310
662 10989670403182452656341963
663 11516233565510147007439596
664 12067597137294661073580701
665 12644909324094524303005366
666 13249370588478144823974185
667 13882235988056049779990421
668 14544817616315883429583977
669 15238487150773569907007411
670 15964678513008431960796807
671 16724890645484769613446323
672 17520690410126681487643689
673 18353715613970788927008119
674 19225678167296773399481117
675 20138367380018370411256002
676 21093653402204855276024297
677 22093490815012467804613672
678 23139922378406036477687396
679 24235082942489108400847286
680 25381203529376528069579656
681 26580615593012192998378120
682 27835755464466696236676565
683 29149168990751360926910543
684 30523516375335160769332992
685 31961577229088261559025157
686 33466255840545731067001270
687 35040586674960275646707450
688 36687740111804468621024126
689 38411028430999146130750405
690 40213912058360196082738148
691 42100006081416113427277149
692 44073087046990533573638861
693 46137100052651311910547615
694 48296166144398388040539585
695 50554590033720766403631418
696 52916868147455216597701012
697 55387697024691915921427341
698 57971982075309147134897014
699 60674846715590391497865936
700 63501641896751937421459661
701 66457956043143361570401006
702 69549625417299466293946079
703 72782744930024232334802205
704 76163679414148891186620164
705 79699075381681029423937682
706 83395873284572695382350543
707 87261320300488612534992682
708 91302983665520730893404742
709 95528764577032711719852866
710 99946912690442090407419062
711 104566041235075816409531031
712 109395142774923405076783857
713 114443605641537337597905504
714 119721231067089089199822801
715 125238251047119386777576311
716 131005346963356571758003910
717 137033668998619926557075988
718 143334856376743471364573187
719 149921058462220043918508812
720 156804956755274917956443124
721 163999787819973052475598596
722 171519367184072353897042238
723 179378114251370618436362036
724 187591078268509669956859373
725 196173965390386633752705920
726 205143166889655132345028636
727 214515788558148253768796416
728 224309681349515220270686093
729 234543473314887775819150823
730 245236602884990686825466544
731 256409353554823217662578661
732 268082890028787101238789252
733 280279295887051730446819882
734 293021612835859220606226638
735 306333881607605406390690414
736 320241184578622059994197296
737 334769690175953909259050173
738 349946699146705743852623794
739 365800692767156003341356324
740 382361383071323877926730580
741 399659765182570189306005727
742 417728171834529648259218239
743 436600330171858267696434417
744 456311420924242945304203123
745 476898140051621752099515161
746 498398762961793392622860515
747 520853211406435282886124238
748 544303123165068767729076019
749 568791924631716421671244063
750 594364906422828869901337918
751 621069302130658387914963135
752 648954370350428691180861352
753 678071480115673653532571037
754 708474199880657840215509776
755 740218390195271004319385171
756 773362300222727450799534985
757 807966668257371263864592794
758 844094826405258841000488963
759 881812809597688668134225699
760 921189469113686116626980883
761 962296590795518398368173823
762 1005209018147658621785307747
763 1050004780518297648923667036
764 1096765226569393872233461794
765 1145575163250590061302391484
766 1196523000499810398483646901
767 1249700901903399602872934436
768 1305204941556791070859690115
769 1363135267377503795908024066
770 1423596271131086291196197847
771 1486696765442261084440362371
772 1552550168073091733213987138
773 1621274693762515105139072747
774 1692993553931960914051299888
775 1767835164575254460865763720
776 1845933362662254415442156089
777 1927427631400177473172880775
778 2012463334708765164856404464
779 2101191961281052587881176951
780 2193771378614726319195030399
781 2290366097415852145615955577
782 2391147546791087296148845252
783 2496294360662564941969931586
784 2605992675855168268422706658
785 2720436442325361959532389192
786 2839827746017569850671047879
787 2964377144855020638310157149
788 3094304018390199218002766003
789 3229836931662570083231381630
790 3371214013830961073224056776
791 3518683352172242087945125015
792 3672503402059281491328190226
793 3832943413557257655546849133
794 4000283875300506871424273477
795 4174816976340172842644357763
796 4356847086677921837106313970
797 4546691257231212373088737328
798 4744679740002652466394661511
799 4951156529258506055497636480
800 5166479924550661508252332107
801 5391023116451382791843186416
802 5625174795901796601869719266
803 5869339788112744083722321210
804 6123939711990827644994038953
805 6389413666103029113411708932
806 6666218942230248707904272384
807 6954831767603748521763101124
808 7255748076958446458729882242
809 7569484315583963790778662422
810 7896578274597515162491958000
811 8237589959713262221428884460
812 8593102494829413496548820367
813 8963723061808731732823230974
814 9350083877878518744096669382
815 9752843212134664182935074735
816 10172686442688793270197011614
817 10610327156060515975134812186
818 11066508290475583287579661100
819 11542003324798511667230891949
820 12037617514891733045629107483
821 12554189179266233376957489723
822 13092591035957196563507410583
823 13653731592636615636523286320
824 14238556592048836562054200305
825 14848050514939402932292679899
826 15483238142727444757728803605
827 16145186182262665036656518305
828 16835004955094177970584641036
829 17553850153776154002352667808
830 18302924667828240430339720163
831 19083480482073837872615860483
832 19896820650179664783396032321
833 20744301346333122107242904239
834 21627333998102225029274436805
835 22547387503644516704216567728
836 23505990536548143855279030913
837 24504733941719134439518931445
838 25545273225854845543695506245
839 26629331146184314684680141810
840 27758700401292040524465563623
841 28935246427993132431608514617
842 30160910308374180686217138611
843 31437711791277059903870162928
844 32767752432660721321779117793
845 34153218859451195999402844496
846 35596386161660176691731777906
847 37099621417740940007481465329
848 38665387358333756021765717492
849 40296246173755543905047003952
850 41994863470786164688063612894
851 43764012384521634622283364819
852 45606577851277504466571284512
853 47525561048759965251904686199
854 49524084009951695297436103619
855 51605394417411427637247412813
856 53772870584933413111641700393
857 56030026633783884759688986606
858 58380517870997909554655743351
859 60828146377511323719086351787
860 63376866814189254767641009809
861 66030792454125941391419372458
862 68794201449899444788573974373
863 71671543344801580507109547157
864 74667445837396021790151761158
865 77786721809119537805022612095
866 81034376624999478548487241256
867 84415615717949785481775698511
868 87935852467493400885857979431
869 91600716384177286876698358197
870 95416061611361365219843679718
871 99387975756512361211864964365
872 103522789064580354144566556465
873 107827083946519165141068668608
874 112307704876492627120030839109
875 116971768671828258020003207931
876 121826675170297417584297822646
877 126880118319859326502442840582
878 132140097696563269089860620713
879 137614930466903290641780788801
880 143313263811518965097794717443
881 149244087827780568869432549273
882 155416748929441737723489545836
883 161840963762235517216274123358
884 168526833654983320330461972225
885 175484859626530756674440576564
886 182725957969570396035647264388
887 190261476433211398568440199577
888 198103211026958436318023353349
889 206263423469621696958299331753
890 214754859307542830481035850589
891 223590766727444936535128940333
892 232784916090142825806386947335
893 242351620212341588163852374958
894 252305755424749517206478515218
895 262662783435796834098110328005
896 273438774031324717608214453325
897 284650428641753530418429564130
898 296315104809392784170942625631
899 308450841589784545282241980529
900 321076385922212168000523931674
901 334211220005826381789930160662
902 347875589719173851514133177911
903 362090534122331103330556610536
904 376877916082279544171088600701
905 392260454063679843873020943309
906 408261755128743859071186225583
907 424906349191537232815532075862
908 442219724573700650747742060679
909 460228364910333300837455052108
910 478959787456560296772234004826
911 498442582847190790176128023784
912 518706456363784113782306871714
913 539782270765465080762162501205
914 561702090741882275405787957035
915 584499229048875866957164762521
916 608208294389626668078741819839
917 632865241106390589568186301204
918 658507420750291446054187317088
919 685173635599148826469939357552
920 712904194195862093548158473833
921 741740968982559090366288436123
922 771727456108450820068967746619
923 802908837492217948354116475052
924 835332045222689711545640986855
925 869045828384671732690428958794
926 904100822399930716050108568575
927 940549620976666531436784889679
928 978446850764186142986020755155
929 1017849248813059375518519966153
930 1058815742944669795790450450449
931 1101407535137900065010362630842
932 1145688188044591814596507592548
933 1191723714749525509095690126826
934 1239582671894853226625508163818
935 1289336256293322161550980313931
936 1341058405159121630590882018741
937 1394825900089912260374907905782
938 1450718474938420737021668782344
939 1508818927717053508771779235142
940 1569213236684161057277442943355
941 1631990680766023206871916891219
942 1697243964474183174606958771120
943 1765069347483592243040791657688
944 1835566779042990476456774261116
945 1908840037395206763464491775690
946 1984996874391460544692419483236
947 2064149165490459493752426854006
948 2146413065339953335327832621109
949 2231909169145602451003223344698
950 2320762680039386197656098688610
951 2413103582667495693257379379378
952 2509066823225558346001200728139
953 2608792496177319857863644693420
954 2712426037901386625125065716299
955 2820118427519508426832202476331
956 2932026395168974289249794175450
957 3048312637991212593269146813559
958 3169146044118439329485865119758
959 3294701924950403496642872037436
960 3425162256023738454138536149299
961 3560715926787368956139449575511
962 3701558999608640840706576938754
963 3847894978346569439055849970841
964 3999935086840631446785596453896
965 4157898557676098287843096502220
966 4322012931599806901953397554761
967 4492514367973741321581103685598
968 4669647966667627375190328976408
969 4853668101806188583171032269649
970 5044838767801537536536349363873
971 5243433938116659709072722767926
972 5449737937221840947347746445945
973 5664045826222482909130388827835
974 5886663802653788856175414707463
975 6117909614955584162704980464008
976 6358112992158798945298834053902
977 6607616089334195150747191519543
978 6866773949373495119945142106411
979 7135954981693486457501004582869
980 7415541458474657134276538103442
981 7705930029067791610038998322124
982 8007532253224441521783721686949
983 8320775153830623251978258600208
984 8646101789847187265597755586761
985 8983971850185414793801808575143
986 9334862269272213373533553976502
987 9699267865086183015154637099136
988 10077702000473485489729117792503
989 10470697268581264883611676743940
990 10878806203276002938583386722134
991 11302602015445058288146041475512
992 11742679356111387594451664593088
993 12199655107324505982969657040111
994 12674169201824755085615489212757
995 13166885472513354017798169734510
996 13678492532797140327066052254078
997 14209704688914827046357475941750
998 14761262885390624259077431969939
999 15333935684801680580219297509997
1000 15928520283087594289977539796313