3 1
4 1
5 2
6 6
7 7
8 11
9 16
10 31
11 36
12 55
13 71
14 101
15 147
16 188
17 245
18 327
19 421
20 540
21 732
22 899
23 1154
24 1445
25 1831
26 2253
27 2846
28 3545
29 4352
30 5352
31 6576
32 7993
33 9778
34 11826
35 14314
36 17430
37 20866
38 25076
39 30043
40 35974
41 42776
42 51053
43 60463
44 71772
45 85094
46 100370
47 118155
48 139331
49 163440
50 191757
51 224547
52 262589
53 306290
54 357351
55 416257
56 483594
57 561755
58 651164
59 754112
60 872458
61 1008062
62 1162657
63 1340926
64 1543266
65 1775316
66 2040534
67 2341785
68 2684470
69 3076243
70 3519803
71 4024656
72 4597330
73 5247243
74 5981961
75 6817067
76 7758407
77 8824729
78 10031305
79 11389852
80 12923176
81 14654432
82 16602186
83 18795315
84 21265379
85 24039562
86 27158456
87 30661527
88 34591733
89 38997743
90 43944499
91 49481592
92 55678741
93 62618024
94 70378204
95 79048451
96 88743784
97 99560114
98 111637742
99 125108205
100 140127765
101 156856755
102 175505202
103 196249411
104 219339322
105 245028071
106 273575510
107 305291584
108 340534919
109 379645267
110 423051536
111 471204158
112 524582041
113 583738207
114 649285674
115 721855362
116 802176536
117 891069356
118 989361519
119 1098037699
120 1218166820
121 1350839042
122 1497351604
123 1659116597
124 1837583032
125 2034462721
126 2251569129
127 2490864161
128 2754527792
129 3045009398
130 3364806051
131 3716854598
132 4104246177
133 4530377536
134 4998933217
135 5514108174
136 6080185362
137 6702068070
138 7385076961
139 8134935124
140 8957918021
141 9860995338
142 10851472100
143 11937626599
144 13128340859
145 14433219918
146 15862791090
147 17428671239
148 19143162602
149 21019924813
150 23073842154
151 25320824740
152 27778444684
153 30465862117
154 33403416361
155 36613793459
156 40121469424
157 43952700461
158 48136394395
159 52703936668
160 57689035826
161 63128528152
162 69062598641
163 75534209090
164 82590601896
165 90282761312
166 98665725562
167 107799344410
168 117748985160
169 128584162593
170 140381575270
171 153223696160
172 167199352147
173 182405342889
174 198946741971
175 216935918787
176 236495916460
177 257759095092
178 280868432581
179 305978792721
180 333258353216
181 362886903440
182 395060771298
183 429991388076
184 467906400502
185 509052543109
186 553696706140
187 602125151979
188 654648937285
189 711603163804
190 773348603253
191 840274926814
192 912804024284
193 991387863274
194 1076516494689
195 1168717823230
196 1268559188032
197 1376653746887
198 1493662944435
199 1620296569758
200 1757321934605
201 1905565497015
202 2065914535714
203 2239327440666
204 2426835546560
205 2629546951714
206 2848655865392
207 3085449054673
208 3341306035851
209 3617715846974
210 3916278915743
211 4238712807990
212 4586868214630
213 4962736255801
214 5368450421956
215 5806310802352
216 6278786651474
217 6788529025205
218 7338387985737
219 7931428037576
220 8570932027033
221 9260433707176
222 10003724561354
223 10804871668918
224 11668243649762
225 12598533303760
226 13600764877846
227 14680340333207
228 15843051939220
229 17095108059534
230 18443172334847
231 19894394094334
232 21456424191945
233 23137482787142
234 24946373999740
235 26892529266011
236 28986061439332
237 31237812852575
238 33659382448340
239 36263212444423
240 39062625802302
241 42071882359938
242 45306261923170
243 48782128309780
244 52516981770487
245 56529575798629
246 60839977855036
247 65469649529729
248 70441573620017
249 75780339155108
250 81512234798906
251 87665396245055
252 94269920555740
253 101357971677543
254 108963961334846
255 117124685339157
256 125879455862366
257 135270316624550
258 145342208973964
259 156143127573443
260 167724392131626
261 180140827292678
262 193450982457066
263 207717419254038
264 223006969766085
265 239390967359077
266 256945624921630
267 275752306639038
268 295897857361274
269 317475003305196
270 340582735842029
271 365326648060090
272 391819479035937
273 420181515651757
274 450541061028705
275 483035021629674
276 517809456738002
277 555020072980074
278 594833014350639
279 637425418183874
280 682986136482038
281 731716537412068
282 783831321380778
283 839559254320263
284 899144251154396
285 962846233622887
286 1030942136792700
287 1103727075386902
288 1181515504296858
289 1264642300717286
290 1353464286554301
291 1448361478701482
292 1549738538425144
293 1658026444735552
294 1773684121826311
295 1897200067417388
296 2029094438363016
297 2169920921976461
298 2320268764805470
299 2480765184001081
300 2652077677226578
301 2834916366582886
302 3030036973935110
303 3238243483724050
304 3460391045905615
305 3697389412322593
306 3950206197627978
307 4219870319443563
308 4507476090176005
309 4814187103420321
310 5141240358450030
311 5489951111995914
312 5861717506243537
313 6258025527859098
314 6680454709815701
315 7130683738696675
316 7610496254531650
317 8121787738663334
318 8666572071073520
319 9246988586708350
320 9865310091683509
321 10523950801108210
322 11225474628721150
323 11972604824367563
324 12768233253001114
325 13615430459797484
326 14517456789197783
327 15477773831678730
328 16500055944639493
329 17588203868833256
330 18746357816753897
331 19978911709451676
332 21290528773421032
333 22686157566433479
334 24171048379539115
335 25750772234921314
336 27431239285429484
337 29218718923781331
338 31119861556678606
339 33141721155696656
340 35291778355026807
341 37577966857709708
342 40008699481407355
343 42592896255121565
344 45340014850219548
345 48260082134248896
346 51363726696801234
347 54662215551311453
348 58167490705165933
349 61892208322885025
350 65849781378713566
351 70054423533503753
352 74521194770721138
353 79266052400710702
354 84305902130773020
355 89658652852078287
356 95343275769574750
357 101379865644349578
358 107789704665881344
359 114595332860761096
360 121820619641773741
361 129490839734141756
362 137632755601431957
363 146274702323530945
364 155446676637377113
365 165180434314135657
366 175509589774729434
367 186469721538835738
368 198098486251543683
369 210435736373324316
370 223523644099540258
371 237406835604670454
372 252132529438594149
373 267750682414683048
374 284314147356973428
375 301878835913233259
376 320503890109491556
377 340251867583169049
378 361188933156030038
379 383385060123519178
380 406914248385483334
381 431854748486982752
382 458289299435294772
383 486305383130925404
384 515995488972611032
385 547457391612570007
386 580794450728515506
387 616115920147882422
388 653537275469437802
389 693180563390079441
390 735174766592444730
391 779656185499243806
392 826768850224762072
393 876664945437417127
394 929505260880381697
395 985459670740264516
396 1044707634362674898
397 1107438721126552500
398 1173853174579559680
399 1244162495582181232
400 1318590060343732637
401 1397371776590270964
402 1480756770013517699
403 1569008103797795270
404 1662403549472029109
405 1761236386387225983
406 1865816246920948924
407 1976470013416964097
408 2093542757479438098
409 2217398723358841463
410 2348422380665104642
411 2487019516555736532
412 2633618390602906222
413 2788670958470062460
414 2952654152694698700
415 3126071226688968346
416 3309453187377354812
417 3503360286040554493
418 3708383591821767224
419 3925146657937444604
420 4154307266590567654
421 4396559259476303110
422 4652634485865601680
423 4923304832577888742
424 5209384363683260935
425 5511731586224617148
426 5831251820827371071
427 6168899691840427940
428 6525681770740421899
429 6902659334261375296
430 7300951269979841693
431 7721737149259324868
432 8166260444649625827
433 8635831908902261214
434 9131833155608018256
435 9655720400809093754
436 10209028398593698402
437 10793374605712074144
438 11410463535616817025
439 12062091336987427280
440 12750150636033780984
441 13476635601359243642
442 14243647267528619578
443 15053399164258843820
444 15908223202759616203
445 16810575866757318584
446 17763044748281485126
447 18768355392340155895
448 19829378484849358983
449 20949137448666349190
450 22130816387329823908
451 23377768438499035619
452 24693524585264679166
453 26081802886557782712
454 27546518164907322148
455 29091792240177067718
456 30721964629850454680
457 32441603802982612284
458 34255519036480435345
459 36168772839701613844
460 38186693993970978980
461 40314891311789682120
462 42559268029641719868
463 44926036937589064971
464 47421736311249804186
465 50053246608308780059
466 52827807982224527308
467 55753038759206055284
468 58836954758715067842
469 62087989604143076123
470 65515016092712483510
471 69127368592853695674
472 72934866538230889785
473 76947839186919206785
474 81177151521863116088
475 85634231467304879124
476 90331098509043035717
477 95280393691803899792
478 100495411075966078310
479 105990130868017306959
480 111779254085557833632
481 117878238964769783254
482 124303339233161849920
483 131071644215361683067
484 138201120889203692063
485 145710658148232081034
486 153620113115557023270
487 161950359775036844021
488 170723340068780166934
489 179962117435033151987
490 189690932943547216174
491 199935264334638829168
492 210721887809803453605
493 222078942880830651561
494 234036000482791982596
495 246624134335601091289
496 259875995752585887048
497 273825892272733245460
498 288509869967942023347
499 303965799780373001190
500 320233468194260919048
501 337354672192961968796
502 355373318810403599711
503 374335529696331931411
504 394289750581338959227
505 415286866063187156074
506 437380320107343090124
507 460626242230403217694
508 485083579764271429368
509 510814236708695857024
510 537883219097154703929
511 566358787369019959668
512 596312616291810657729
513 627819962378889368292
514 660959839357037956667
515 695815202283804238372
516 732473140299091086924
517 771025078605898320761
518 811566990385000756675
519 854199618608029814675
520 899028708482594325246
521 946165251237045657578
522 995725739333697045690
523 1047832433820854066349
524 1102613644743022607919
525 1160204024612905459025
526 1220744875869750858148
527 1284384473235875988898
528 1351278401137951934518
529 1421589907079817558463
530 1495490272188830473381
531 1573159198913883728520
532 1654785217167127126895
533 1740566109955450450296
534 1830709358869851811310
535 1925432610527512686795
536 2024964165498358673692
537 2129543489830443492905
538 2239421750758767604478
539 2354862377947097266126
540 2476141650846164647866
541 2603549313516674360062
542 2737389218911780960713
543 2877980002819740363801
544 3025655789520865204888
545 3180766930859917888888
546 3343680779571210024168
547 3514782498617552554822
548 3694475909023679416324
549 3883184376625012452499
550 4081351740339906415880
551 4289443284102528977106
552 4507946753697563574833
553 4737373420710795487792
554 4978259196754934009621
555 5231165798682879616636
556 5496681968058107033682
557 5775424747668038246036
558 6068040816765093835102
559 6375207887890491242909
560 6697636169298327420027
561 7036069894050460195338
562 7391288919964581343546
563 7764110403998655653321
564 8155390553271984701661
565 8566026456603133391796
566 8996958001407644625030
567 9449169877791453517368
568 9923693674958700158581
569 10421610074626310060324
570 10944051144464235179875
571 11492202736471417506368
572 12067306996475962056397
573 12670664987389852977796
574 13303639432658987295556
575 13967657586047430571318
576 14664214231632402134342
577 15394874820584022454706
578 16161278752324731072543
579 16965142803950584360838
580 17808264715969494183771
581 18692526942294148720672
582 19619900569690199816942
583 20592449415153894807186
584 21612334310733921976702
585 22681817581347949701184
586 23803267725631252129464
587 24979164310161498622736
588 26212103083850276234780
589 27504801323522012716222
590 28860103422703681890338
591 30280986731156238099574
592 31770567657923541607802
593 33332108051174656989050
594 34969021863828771615378
595 36684882119238526470173
596 38483428191905494524738
597 40368573413840495665150
598 42344413022343377039758
599 44415232466546010321350
600 46585516084449690632643
601 48859956168854145037697
602 51243462441201804596171
603 53741171947440903154538
604 56358459396022940956118
605 59100947960316995556254
606 61974520560742599106254
607 64985331650471475703256
608 68139819528536139253885
609 71444719199379523856006
610 74907075804363946343037
611 78534258653606723265194
612 82333975878475696326822
613 86314289735176663306823
614 90483632589755070852533
615 94850823609750222605754
616 99425086194745414462454
617 104216066182394902247686
618 109233850856382647401046
619 114488988795308630705294
620 119992510601066313944090
621 125755950539879658388804
622 131791369137190951693447
623 138111376772874160738852
624 144729158311527454248432
625 151658498817806327956414
626 158913810405622069596687
627 166510160264858814608142
628 174463299917857207863311
629 182789695765115606802134
630 191506560965675219501305
631 200631888715566315875654
632 210184486987098593400756
633 220184014785159078135967
634 230651019987861086054131
635 241606978846716292587919
636 253074337205847027884104
637 265076553521099113052153
638 277638143758790321716193
639 290784728247243822986979
640 304543080567020867127355
641 318941178575127305047670
642 334008257641396709098060
643 349774866199040582316754
644 366272923711729448888642
645 383535781151509507799140
646 401598284097360419766700
647 420496838575343751791472
648 440269479741907786594098
649 460955943540036571338648
650 482597741459015203217239
651 505238238518867848176480
652 528922734620373373350385
653 553698549413433487976984
654 579615110816168471393978
655 606724047348943587641790
656 635079284450180637627376
657 664737144929963528877146
658 695756453741026797634580
659 728198647260780271152261
660 762127887256059301649358
661 797611179738396268587040
662 834718498923199793461507
663 873522916492408982833327
664 914100736390220227253229
665 956531635397196069277540
666 1000898809704309709501118
667 1047289127750648710179882
668 1095793289596557643359223
669 1146505993087617759174301
670 1199526107103153584836552
671 1254956852198586749896960
672 1312905988928637845360948
673 1373486014184315830994898
674 1436814365890518614256658
675 1503013636391000956755590
676 1572211794894279665183658
677 1644542419372813743214413
678 1720144938284000482739631
679 1799164882534977946274616
680 1881754148132574691834760
681 1968071269935475850184348
682 2058281706984919511330999
683 2152558139909317756096743
684 2251080780876771504545617
685 2354037696629551096867142
686 2461625145161144262118618
687 2574047926568918930197236
688 2691519748687199572377077
689 2814263608127903780267142
690 2942512187336202917977283
691 3076508268336520822918556
692 3216505163881577527877470
693 3362767166683253723487019
694 3515570017493861444607339
695 3675201392831242936509480
696 3841961413123751500830654
697 4016163172130529406428435
698 4198133288540311753216994
699 4388212480613754325000740
700 4586756164844660944759454
701 4794135079642236002920727
702 5010735935026591448345538
703 5236962089418069443725854
704 5473234254665280539740976
705 5719991230414078682598869
706 5977690669050341933928202
707 6246809872487247622344184
708 6527846622057849976140923
709 6821320042881857567343174
710 7127771504154532624867263
711 7447765556759016418096498
712 7781890909764103064007280
713 8130761447411620946524946
714 8495017288197903423867711
715 8875325887780674433165506
716 9272383187540222671005652
717 9686914810577804713285723
718 10119677307123094981254276
719 10571459451380181862096135
720 11043083591848583958806104
721 11535407057306942857000988
722 12049323620770048205378898
723 12585765023682160730431738
724 13145702562836793757400841
725 13730148742587497458694821
726 14340158994929554919942604
727 14976833470219204818012481
728 15641318901443256790990548
729 16334810544910943619534901
730 17058554200509437347496618
731 17813848314760203779523562
732 18602046169944730209072007
733 19424558162790892160941464
734 20282854176392550651823974
735 21178466049002991787362710
736 22112990143659815870895930
737 23088090022728763817172998
738 24105499231497534637101771
739 25167024195226292662902905
740 26274547234282663980612241
741 27430029701966163413589270
742 28635515250010193203476520
743 29893133226915341114391596
744 31205102214330761396606648
745 32573733707044608195519185
746 34001435942402418906866024
747 35490717884984105906296477
748 37044193372812235718706282
749 38664585431588065662418711
750 40354730763540207006094608
751 42117584417889981969524600
752 43956224650256904167451953
753 45873857978366167183427908
754 47873824441948928273721785
755 49959603075018241317452975
756 52134817598818723513549300
757 54403242344272848279508627
758 56768808413125540657321858
759 59235610087080426175488433
760 61807911494845983298700458
761 64490153547385086365061094
762 67286961151823219753358031
763 70203150715114291043053979
764 73243737949023214045632244
765 76413945988142947363971954
766 79719213833399501981637604
767 83165205133993422691124054
768 86757817320931371857330687
769 90503191106101075374814397
770 94407720361403024270105039
771 98478062392693223913597614
772 102721148624174002224324208
773 107144195709495874176099785
774 111754717086110721302569858
775 116560534990409143592097602
776 121569792951842474589523170
777 126790968784600141100391438
778 132232888096451399989852062
779 137904738335172478275051796
780 143816083393340747280160756
781 149976878793494866409661326
782 156397487476492812160487385
783 163088696216396799589056491
784 170061732686479474511512048
785 177328283201960542398986708
786 184900511165563026495508410
787 192791076243483979654004326
788 201013154300383402497166721
789 209580458122688896811762580
790 218507258961031082192211066
791 227808408923902310416937638
792 237499364255276134229282205
793 247596209530755920528081832
794 258115682808079743691705062
795 269075201768735391720732461
796 280492890889268118861458776
797 292387609682474334925533198
798 304778982049515961732913316
799 317687426786240026158019938
800 331134189288548348935941226
801 345141374502870391807421407
802 359731981170033240346729103
803 374929937412816447916106535
804 390760137718597063798405074
805 407248481371238210372614359
806 424421912388307791869573834
807 442308461021303983819612460
808 460937286879278137654602386
809 480338723738733568519338525
810 500544326104150812099037597
811 521586917586829457237906422
812 543500641172168254960459099
813 566321011447530544621884394
814 590084968866177954521640756
815 614830936125841523410877492
816 640598876742406128544085044
817 667430355903283063897697309
818 695368603688049984455051610
819 724458580746562042125780554
820 754747046528809478857022715
821 786282630164608165208766916
822 819115904093727094693293296
823 853299460552000775239462719
824 888887991022786736590417613
825 925938368766422077732900531
826 964509734545354142809308350
827 1004663585667333433724890944
828 1046463868472300178405137602
829 1089977074394640643202511802
830 1135272339737241232669316726
831 1182421549297941506003149546
832 1231499443995178901228953032
833 1282583732645402523495026223
834 1335755208049053346017402792
835 1391097867549253106166982763
836 1448699038233284988488477702
837 1508649506952227735236575853
838 1571043655341709964879848491
839 1635979600033894723266601164
840 1703559338256237380925561829
841 1773888899021473669828866250
842 1847078500120767160587154872
843 1923242711138537156977588745
844 2002500622716896135914185944
845 2084976022306405492357631136
846 2170797576646812938385955402
847 2260099021232316452304512726
848 2353019357025202403653265865
849 2449703054689999738496929410
850 2550300266631884378002419426
851 2654967047133854158723886248
852 2763865580896123909919338130
853 2877164420294374818728444266
854 2995038731685173873046201802
855 3117670551097219213619781837
856 3245249049661370763950857612
857 3377970809145713330659203222
858 3516040107973226384679798547
859 3659669218115732682805986128
860 3809078713272356023819494009
861 3964497788753616544093463092
862 4126164593509972691889867088
863 4294326574759924826443199718
864 4469240835687172834298030342
865 4651174506695969597641199416
866 4840405130731894204942158472
867 5037221063191434372332345825
868 5241921886965483960283984976
869 5454818843181984993864088389
870 5676235278231097897859890158
871 5906507107680225259335832334
872 6145983297708762283523198577
873 6395026364712550156320996672
874 6654012893754787525542091118
875 6923334076564933828774356909
876 7203396269809954890130012221
877 7494621574391579503965254948
878 7797448436551151371113984566
879 8112332271588773830464995005
880 8439746111036379922416190399
881 8780181274154859579880480996
882 9134148064654070730562816583
883 9502176493570344434937279343
884 9884817029270743827298102465
885 10282641375584621163972400690
886 10696243279103458785887007214
887 11126239366727653634024023096
888 11573270014574713688644655065
889 12038000249407223968246656126
890 12521120683781776957729757616
891 13023348486158995552640866662
892 13545428387264519222864669376
893 14088133724037188478217331439
894 14652267522545447199013799622
895 15238663621306684905491842781
896 15848187836497182298744529038
897 16481739170588824526462376407
898 17140251066009733792309328708
899 17824692705483196204664831059
900 18536070360755023392198938603
901 19275428791485277205582495650
902 20043852696145712503926482145
903 20842468216824485355220649219
904 21672444499914575908223617816
905 22534995314732962147191438182
906 23431380732186753991820830384
907 24362908865683370091382511924
908 25330937676562293875315256190
909 26336876846400907691680484389
910 27382189718638662931218834113
911 28468395312050825293332338868
912 29597070408689015105355154382
913 30769851719004784960356485264
914 31988438126971697447098768763
915 33254593018114400250056712847
916 34570146693465555522296092928
917 35936998872578887476520781698
918 37357121288832922036503771470
919 38832560380381625076009565854
920 40365440080230173871556564350
921 41957964709029495760807475902
922 43612421974320906897606736389
923 45331186080094431787917372201
924 47116720950655986371233425022
925 48971583572947861169773915372
926 50898427461616860390517335308
927 52900006251267635837543469716
928 54979177420507155808978827673
929 57138906152549372954750360554
930 59382269337311627634521900166
931 61712459720117413991283145130
932 64132790202304452592492947117
933 66646698299214196590461637199
934 69257750761245046439689023038
935 71969648363852455164672086781
936 74786230872579470961136572018
937 77711482189426126315343052592
938 80749535687092085606239851672
939 83904679737846387006641986612
940 87181363444030206316329450056
941 90584202577445880771637114778
942 94117985735132505413842743844
943 97787680719304069052297600078
944 101598441149503499810857726590
945 105555613315297292670122831362
946 109664743278143410159632988286
947 113931584231369750796063559566
948 118362104127504479705707099428
949 122962493582537650794141379933
950 127739174067033863052960704402
951 132698806394350351236616091540
952 137848299516591916336040117528
953 143194819639308300013400485078
954 148745799666313859139893611970
955 154508948986423876829186262807
956 160492263614318774687728000346
957 166704036698160706218799895838
958 173152869407047440057236678007
959 179847682211848476194877695357
960 186797726573428498342090623405
961 194012597052770962793336737292
962 201502243858025737616594248534
963 209276985844013567633024490306
964 217347523980283101841016731602
965 225724955304381077244614760106
966 234420787377561507207262677914
967 243446953260781681739510001883
968 252815827029458617114913541290
969 262540239846086184602383262764
970 272633496610501024216975596624
971 283109393208278217657520168508
972 293982234378432200173082680174
973 305266852222359332682260214933
974 316978625376725019001562815808
975 329133498873768846163260352636
976 341748004713341343608710520903
977 354839283171835988375471085990
978 368425104874031963983845302475
979 382523893654794304153550693603
980 397154750238516238258894316504
981 412337476765135085405431654926
982 428092602192579613610559918000
983 444441408606547813950889002759
984 461405958469559262343405422462
985 479009122842364800192799651882
986 497274610611943722705587958208
987 516226998761481121178977834333
988 535891763718971055129994476244
989 556295313822366443744054023252
990 577465022940477655193061800629
991 599429265290212875446670893396
992 622217451492157425456797354362
993 645860065907914067098358344889
994 670388705304156858342596024569
995 695836118889911088865994885006
996 722236249775141381465381339770
997 749624277900429537967099186625
998 778036664489239786458534172470
999 807511198076015587438090188681
1000 838087042165220095120468331327