1 1
2 1
3 1
4 3
5 3
6 7
7 7
8 13
9 16
10 24
11 30
12 46
13 55
14 79
15 100
16 136
17 169
18 229
19 282
20 374
21 462
22 598
23 737
24 947
25 1158
26 1466
27 1794
28 2246
29 2733
30 3399
31 4116
32 5076
33 6133
34 7503
35 9033
36 10993
37 13177
38 15943
39 19061
40 22939
41 27327
42 32749
43 38883
44 46395
45 54938
46 65278
47 77070
48 91270
49 107439
50 126795
51 148889
52 175141
53 205125
54 240607
55 281092
56 328788
57 383240
58 447064
59 519926
60 605052
61 702105
62 815117
63 943957
64 1093413
65 1263694
66 1460706
67 1684907
68 1943617
69 2237849
70 2576403
71 2961125
72 3402841
73 3904193
74 4478571
75 5129988
76 5874588
77 6718257
78 7680843
79 8770272
80 10011008
81 11413949
82 13008775
83 14810363
84 16855113
85 19162433
86 21777109
87 24724801
88 28059919
89 31816149
90 36060197
91 40835217
92 46223053
93 52279321
94 59103601
95 66767327
96 75392291
97 85068766
98 95945888
99 108138109
100 121826833
101 137156714
102 154349262
103 173585450
104 195135738
105 219226789
106 246187341
107 276300667
108 309967165
109 347538200
110 389501470
111 436292979
112 488504551
113 546676096
114 611526720
115 683721557
116 764133925
117 853582926
118 953126318
119 1063771055
120 1186798883
121 1323442729
122 1475254983
123 1643744425
124 1830786851
125 2038225608
126 2268327568
127 2523338009
128 2805994445
129 3119029418
130 3465742756
131 3849455290
132 4274143612
133 4743833562
134 5263313742
135 5837460408
136 6472030680
137 7172922934
138 7947055876
139 8801549935
140 9744712935
141 10785132384
142 11932770498
143 13197971623
144 14592674763
145 16129319219
146 17822201463
147 19686266020
148 21738611068
149 23997170292
150 26482379524
151 29215728006
152 32221620334
153 35525782128
154 39157325138
155 43147013943
156 47529550799
157 52341678519
158 57624729785
159 63422547489
160 69784310889
161 76762282601
162 84414935903
163 92804498214
164 102000436730
165 112076778137
166 123115972371
167 135206000162
168 148444648534
169 162936372421
170 178797057685
171 196150613008
172 215134250222
173 235894824197
174 258594678805
175 283407696696
176 310525809036
177 340154731973
178 372521186321
179 407868344964
180 446463830824
181 488594836211
182 534577030033
183 584749326439
184 639483769385
185 699179989603
186 764276164547
187 835243125374
188 912596565560
189 996890783507
190 1088732243359
191 1188773010722
192 1297725805148
193 1416357100631
194 1545503903733
195 1686066518687
196 1839027202985
197 2005442689186
198 2186464919498
199 2383333313417
200 2597397897835
201 2830111351111
202 3083054755551
203 3357929558891
204 3656586237301
205 3981016204334
206 4333383818378
207 4716018319252
208 5131449513396
209 5582399960557
210 6071824755329
211 6602904058125
212 7179087570545
213 7804087579756
214 8481928620426
215 9216941376049
216 10013818130099
217 10877607734726
218 11813777684112
219 12828210456783
220 13927272935075
221 15117814655311
222 16407245449627
223 17803535994887
224 19315304841089
225 20951821792173
226 22723105386191
227 24639929926462
228 26713934682176
229 28957635254999
230 31384546145365
231 34009197330490
232 36847271756982
233 39915628386859
234 43232456461409
235 46817306150377
236 50691261915193
237 54876982176153
238 59398894064253
239 64283244011137
240 69558316568383
241 75254497753990
242 81404521257626
243 88043546766116
244 95209436899242
245 102942853401142
246 111287568700916
247 120290582854086
248 130002474464874
249 140477541828171
250 151774198103835
251 163955140990245
252 177087797803495
253 191244528156922
254 206503125732570
255 222947059241340
256 240666038010682
257 259756297708959
258 280321237957699
259 302471759649959
260 326326984321569
261 352014651056843
262 379671927992675
263 409445878446197
264 441494376446611
265 475986652420570
266 513104326734056
267 553042046924588
268 596008654316618
269 642227927069269
270 691939897095837
271 745401714399556
272 802889134379468
273 864697521322021
274 931143527935599
275 1002566259012087
276 1079329168093045
277 1161821404314289
278 1250459955055435
279 1345691202394531
280 1447993343335689
281 1557878186707489
282 1675893886919911
283 1802627015277041
284 1938705648672693
285 2084801754208493
286 2241634678442043
287 2409973890340863
288 2590642922868573
289 2784522524155665
290 2992555110823275
291 3215748384265478
292 3455180361405922
293 3712003521627047
294 3987450489425467
295 4282838784818392
296 4599577242971474
297 4939171450960140
298 5303230998792030
299 5693475697507111
300 6111743768438605
301 6559998948516109
302 7040339739458641
303 7555007520439822
304 8106396992590726
305 8697065436246014
306 9329744503746624
307 10007350774447526
308 10732999069582134
309 11510014478581803
310 12341947389683451
311 13232587185067177
312 14185979205777503
313 15206440336482253
314 16298578152395595
315 17467308643340990
316 18717877819092948
317 20055881856153600
318 21487291473109858
319 23018474817168286
320 24656224961898558
321 26407785891516737
322 28280883514633179
323 30283755151628276
324 32425184507595678
325 34714535116526155
326 37161789773767395
327 39777588448540962
328 42573272735096174
329 45560928811612436
330 48753437539032778
331 52164523113454405
332 55808809521554151
333 59701875615130027
334 63860318715694617
335 68301816933067591
336 73045200809749223
337 78110523803692210
338 83519142974862346
339 89293798666977374
340 95458705357042644
341 102039641701458072
342 109064052806813184
343 116561151944765335
344 124562035658468367
345 133099798611611123
346 142209663111823775
347 151929108741799706
348 162298018073404616
349 173358822924898975
350 185156668257220873
351 197739577126669706
352 211158634989457882
353 225468175674060320
354 240725988588853072
355 256993528313844857
356 274336147509412485
357 292823333042036603
358 312528967720934023
359 333531596227395486
360 355914719180635962
361 379767092526361359
362 405183057854765727
363 432262879342863769
364 461113114706864453
365 491846994286580424
366 524584837535438054
367 559454479374338859
368 596591737707751959
369 636140892785020487
370 678255211871016297
371 723097488038218822
372 770840628843693636
373 821668261726187283
374 875775394352140483
375 933369094639513552
376 994669231325005868
377 1059909237586002477
378 1129336941383375515
379 1203215422695957606
380 1281823944315014998
381 1365458913879628467
382 1454434927032173823
383 1549085846756235614
384 1649765972188218924
385 1756851249204859609
386 1870740579735034435
387 1991857179166570894
388 2120650042708119362
389 2257595466997815571
390 2403198691977725965
391 2557995606084981592
392 2722554584236194136
393 2897478398220240086
394 3083406273744365526
395 3281016030145330813
396 3491026382083451693
397 3714199335444863712
398 3951342762207145892
399 4203313082487240733
400 4471018144344569807
401 4755420225363857313
402 5057539252783826081
403 5378456161797122459
404 5719316495426779143
405 6081334160960184152
406 6465795453451509294
407 6874063256421111253
408 7307581537832679279
409 7767880046398816130
410 8256579334412273436
411 8775396006805959082
412 9326148331329202386
413 9910762103970017240
414 10531276913775820448
415 11189852695385534844
416 11888776723362757846
417 12630470930535131609
418 13417499715074055427
419 14252578112172971210
420 15138580506416524316
421 16078549754096036099
422 17075706903750569289
423 18133461377279807839
424 19255421812969651831
425 20445407425623495533
426 21707460099089776739
427 23045857058966496072
428 24465124355748331286
429 25970050998473645231
430 27565703985196536457
431 29257444062381772134
432 31050942476715946792
433 32952198543226378343
434 34967558311641366465
435 37103734146377704802
436 39367825521878710564
437 41767340839975644783
438 44310220592172798447
439 47004861664604236846
440 49860143131323493322
441 52885453324487622162
442 56090718551541842220
443 59486433238630804581
444 63083691896529527233
445 66894222678842237192
446 70930422956927343640
447 75205396671632514624
448 79732993916572158368
449 84527852503321178820
450 89605441995724217884
451 94982109953960183617
452 100675130910508333105
453 106702757808865269381
454 113084276464755413953
455 119840062771013592622
456 126991643246247941774
457 134561758638956242435
458 142574431230688415501
459 151055035540573883911
460 160030373121630803299
461 169528751142195512369
462 179580065493220583435
463 190215888106252014341
464 201469559277101377755
465 213376284671963665508
466 225973237869486891186
467 239299668108235842261
468 253397014156001123129
469 268309023963964901040
470 284081881090102177978
471 300764337549333676526
472 318407854148093903148
473 337066747956634504862
474 356798348055684635628
475 377663159208083040713
476 399725034677289557235
477 423051357842297388595
478 447713233922954856629
479 473785691466204644993
480 501347895006595559193
481 530483368554923659128
482 561280231435763210834
483 593831446133665459536
484 628235079784886328524
485 664594578983520736972
486 703019059664279559498
487 743623611743470868920
488 786529620416089718276
489 831865103807181412843
490 879765069022172833709
491 930371886315646138439
492 983835683581939612385
493 1040314760913640298059
494 1099976027603222721749
495 1162995461366276381545
496 1229558592347707403447
497 1299861011728548297097
498 1374108907696191591181
499 1452519628642487795501
500 1535322276570869096081
501 1622758330632103981794
502 1715082304006515922724
503 1812562434117132446406
504 1915481409647977791904
505 2024137134427642223332
506 2138843531930475405656
507 2259931390543071826313
508 2387749253650126359529
509 2522664354788481570916
510 2665063602250604707586
511 2815354613502606995884
512 2973966804153234510518
513 3141352531971867249206
514 3317988301077580717360
515 3504376026949154696690
516 3701044367796568793686
517 3908550123116708377500
518 4127479705428483096178
519 4358450686205986457521
520 4602113422498874421229
521 4859152765480564438908
522 5130289857949923807376
523 5416284022277883677942
524 5717934746407896614624
525 6036083769684222507157
526 6371617276751056408883
527 6725468201614678487414
528 7098618650800802570294
529 7492102448056905087808
530 7907007810281377409286
531 8344480157530174105246
532 8805725067598303868894
533 9292011378476171401144
534 9804674450065006483544
535 10345119588954203164291
536 10914825648610063593417
537 11515348809340316057117
538 12148326551434479897393
539 12815481826471479793140
540 13518627441337767286138
541 14259670660646587592704
542 15040618043346422090200
543 15863580519987745323181
544 16730778727791546536377
545 17644548610855368341414
546 18607347304115929938492
547 19621759309367742089083
548 20690502983564165581723
549 21816437348770466468130
550 23002569245746269111320
551 24252060841715177897602
552 25568237516205988206940
553 26954596136841380634316
554 28414813751036523257656
555 29952756706944093798977
556 31572490231872496429889
557 33278288483132046750388
558 35074645102002941773788
559 36966284287571333165769
560 38958172423816303668689
561 41055530278675602557640
562 43263845811403847291766
563 45588887609142376847752
564 48036718992208641762480
565 50613712811446057903255
566 53326566980624508188461
567 56182320769906675460103
568 59188371907166797674249
569 62352494516129656965546
570 65682857942254745053136
571 69188046498591536644896
572 72877080187043211362046
573 76759436430857521678849
574 80845072878702355913447
575 85144451320105840421361
576 89668562777982814039227
577 94428953822392643370224
578 99437754177100042835994
579 104707705667891318783610
580 110252192590596925974946
581 116085273553066506303208
582 122221714876003101797928
583 128677025612729390085427
584 135467494280378602581053
585 142610227368992906696141
586 150123189729294935907153
587 158025246912665695043611
588 166336209573115941264063
589 175076880012536196565200
590 184269100988851525743770
591 193935806876885543810482
592 204101077312290207132726
593 214790193417707025009675
594 226029696753217694200379
595 237847451100532410927883
596 250272707235735756335655
597 263336170811328589877656
598 277070073516303759422886
599 291508247647388593135596
600 306686204275369224679474
601 322641215153232307153983
602 339412398566591197688999
603 357040809288055144221213
604 375569532854059109477421
605 395043784342181771657344
606 415511011887152281436736
607 437021005131523295571014
608 459626008870675237536738
609 483380842107806522351630
610 508343022801980547695694
611 534572898546451571586785
612 562133783485860917460569
613 591092101733158504835103
614 621517537622668848208491
615 653483193086045034546594
616 687065752517871463530578
617 722345655446014072051547
618 759407277406558539065439
619 798339119369484582467829
620 839234006150982573552337
621 882189294192550955981935
622 927307089182099603932823
623 974694473934402094849670
624 1024463747048983714174300
625 1076732672803501528698793
626 1131624742847427340370337
627 1189269450198631982144195
628 1249802576158612814021945
629 1313366490697686852634607
630 1380110466981403299134471
631 1450191010642785157489780
632 1523772204532158034196638
633 1601026069607440413659708
634 1682132942762594700017682
635 1767281872320811233904429
636 1856671032061984721196145
637 1950508154580679521062438
638 2049010984922452038758916
639 2152407755370812463029768
640 2260937682418024103661594
641 2374851486875158158903880
642 2494411938247574479605388
643 2619894424422067999821214
644 2751587547893147352019370
645 2889793749673884430919148
646 3034829962229157906008718
647 3187028292685063914566955
648 3346736737772533447697697
649 3514319931877220191820504
650 3690159929784650597787716
651 3874657025621837561458436
652 4068230609726985123255568
653 4271320065089446373381537
654 4484385705246909164585063
655 4707909755435812868651215
656 4942397379051154267187039
657 5188377751379554735650248
658 5446405182845984165563908
659 5717060293921166065223646
660 6000951244130671606411468
661 6298715017512522749481027
662 6611018767182742959144751
663 6938561221573591191902878
664 7282074155241729927939416
665 7642323927048711631378765
666 8020113088869924113546199
667 8416282067893509061190691
668 8831710925947212433986655
669 9267321199197189464500036
670 9724077821963474655835770
671 10202991138304097658652078
672 10705119005446415757153266
673 11231568993053296024632693
674 11783500682766058815881665
675 12362128072377597691233958
676 12968722089472978482039926
677 13604613219289500748728668
678 14271194252063752877983374
679 14969923155051877039580206
680 15702326074958678314916050
681 16470000476434815796268845
682 17274618422886977790135275
683 18117930005775492703023343
684 19001766929198279128408999
685 19928046256496681379316103
686 20898774326284714411453553
687 21916050845248241968654364
688 22982073165771060941658048
689 24099140756399633439727023
690 25269659873916282538434833
691 26496148445756772956047489
692 27781241172317296534759401
693 29127694858675047781697543
694 30538393986110355455892119
695 32016356533812476491695529
696 33564740062073541618193779
697 35186848068286376107228474
698 36886136628047130144336730
699 38666221333694304994733254
700 40530884543668349691059928
701 42484082956128643912533440
702 44529955521389528723157962
703 46672831707814513386307458
704 48917240137010151119137540
705 51267917604266474293677956
706 53729818501476429196602330
707 56308124659903504530236876
708 59008255631541565080302314
709 61835879427982780116098971
710 64796923737180180013446791
711 67897587638702495960981744
712 71144353839652474479323728
713 74544001453674754030779704
714 78103619347163411597052862
715 81830620077082929256486376
716 85732754446619021703920894
717 89818126705233583847389765
718 94095210421628200848038045
719 98572865058538615630820707
720 103260353280349707215915707
721 108167359025005146695933284
722 113304006373900259536415534
723 118680879254005015331273045
724 124309042008836656499607563
725 130200060875541445185627565
726 136366026407887683635911717
727 142819576885702231649222212
728 149573922754008297408599264
729 156642872135951735843520007
730 164040857466525307967794277
731 171782963295039358753360087
732 179884955307421094812962925
733 188363310620484283790636228
734 197235249403672433436256584
735 206518767884970858354428959
736 216232672801289051791807257
737 226396617354953020541833241
738 237031138741816603931828447
739 248157697317999303775340703
740 259798717476410915516837347
741 271977630305897657233648833
742 284718918110302275966093703
743 298048160866597966628914170
744 311992084706042020543203692
745 326578612504373996973587668
746 341836916672222710276063306
747 357797474239196907218059905
748 374492124330654516857572419
749 391954128138709627712571279
750 410218231494966043862594891
751 429320730155308158334665632
752 449299537913450754685296258
753 470194257663094833854802303
754 492046255535382573650233919
755 514898738241821887103218423
756 538796833760208784091970877
757 563787675504915711748581985
758 589920490130822997366919981
759 617246689124406467541585673
760 645819964343997064165927765
761 675696387675896478630126568
762 706934514982175264319824884
763 739595494521119742719589399
764 773743180031125669222163923
765 809444248674490880659206698
766 846768324048133427343253358
767 885788104474476779028278910
768 926579496797118176472905150
769 969221755912722519525238055
770 1013797630282820986324611439
771 1060393513676685777341868614
772 1109099603409618512955410208
773 1160010065349207204785879184
774 1213223205976274415813729622
775 1268841651796246151375197910
776 1326972536411918209433614604
777 1387727695578462908079354456
778 1451223870577929851140739718
779 1517582920261295473039209725
780 1586932042123781022824262531
781 1659404002790976610172336984
782 1735137378312325799726091308
783 1814276804671448895163807151
784 1896973238943257322963503931
785 1983384231541937138944881352
786 2073674210025925042022713176
787 2168014774941432157424422572
788 2266585008209809954648618926
789 2369571794580903736264792590
790 2477170156700104269053093934
791 2589583604355200732294074035
792 2707024498496671940266086355
793 2829714430645119419489748540
794 2957884618329202193031949466
795 3091776317219317144865473224
796 3231641250654213524373068156
797 3377742057281586812175608778
798 3530352757568109144354229276
799 3689759239960350831443254206
800 3856259767515119711263504236
801 4030165505846064866915561489
802 4211801073273331745673571299
803 4401505114093894681207480450
804 4599630895933225933320949562
805 4806546932172531336687653549
806 5022637630492150285711486835
807 5248303968608250916300557057
808 5483964198329914376638709189
809 5730054579103446323880675511
810 5987030142264593418141700987
811 6255365487262567172463029460
812 6535555611177797005819077870
813 6828116772902330295256418290
814 7133587393414323542954372956
815 7452528993629150751513901224
816 7785527171377040695262517612
817 8133192619112662937214735007
818 8496162184034707333730094625
819 8875099972353803667893451708
820 9270698499525401952195787826
821 9683679888329726834019556815
822 10114797116765284027232637505
823 10564835317793509849490928609
824 11034613133063086099783072287
825 11524984122819639615989419847
826 12036838234304556872350429471
827 12571103331030425995853683992
828 13128746785426262538834606660
829 13710777137436583413384311849
830 14318245821772266479046550361
831 14952248966609751721228782677
832 15613929266657884767178783333
833 16304477933618663385568965696
834 17025136727200456596896379764
835 17777200069958248814065678127
836 18562017249378080906156948433
837 19380994710748601362761227391
838 20235598444516375002531103445
839 21127356471957890616920372048
840 22057861433166924594579056732
841 23028773281503621445211797559
842 24041822088830283058901957279
843 25098810966018897450468455422
844 26201619103407990194977691976
845 27352204936059754156551463312
846 28552609438875971186453094698
847 29804959556819022760948706350
848 31111471775708018278196589964
849 32474455839263426274868599138
850 33896318618314757670451044624
851 35379568138306034014921235999
852 36926817771493725197703649771
853 38540790600470205124592111499
854 40224323959925973295420054067
855 41980374163821893527036701896
856 43812021425444721472989213146
857 45722474978098408913008309633
858 47715078404509208359827657407
859 49793315183324728056941881492
860 51960814461437963015446088108
861 54221357061194194418990335827
862 56578881731916830681767723931
863 59037491655541843456897606951
864 61601461216558054663077318461
865 64275243046832951285094183738
866 67063475356343008544180673310
867 69970989561241056523233472902
868 73002818221166684639229114190
869 76164203298152838542977308257
870 79460604749992021425632417265
871 82897709471408941885698052400
872 86481440596936351441445199914
873 90217967179913386091613639790
874 94113714262618334360902678806
875 98175373353112560864175571731
876 102409913325010927551189043079
877 106824591757004430724962261840
878 111426966729648940635375062208
879 116224909097593467719711286060
880 121226615256162925860434288362
881 126440620421922931567199507140
882 131875812447653215673591222948
883 137541446192925992848702688547
884 143447158472346591259818126231
885 149602983604345103925948452640
886 156019369584335465457454128426
887 162707194906956344062888578003
888 169677786063107694727086463457
889 176942935738466541441912560747
890 184514921741242345713521673843
891 192406526687979385360557843487
892 200631058477373629752557226553
893 209202371583202049141780861963
894 218134889198712021435261569309
895 227443626266038839211979304034
896 237144213425565585420506102274
897 247252921921456874832238508099
898 257786689501048162237484318919
899 268763147347193973383230249760
900 280200648084240515964935143120
901 292118294899822322786783762289
902 304535971826365140281180629971
903 317474375227832742820211195295
904 330955046539067584750616972039
905 345000406306861340653755715542
906 359633789583843193334949724094
907 374879482728200653984797399950
908 390762761664349741496846365098
909 407309931661749943757141550511
910 424548368691323120596130206383
911 442506562421177486989696864887
912 461214160915775571493231919889
913 480702017105103008505991645271
914 501002237093020053419125017959
915 522148230376585215258806205653
916 544174762050966958916911934807
917 567118007077371061299644646850
918 591015606694454615474999286964
919 615906727056729124609411125750
920 641832120186731867306704894820
921 668834187331012853847637427074
922 696957044813512478547391749700
923 726246592483427951044669708838
924 756750584858464466189686733986
925 788518705068164408581513428522
926 821602641706096329624028576918
927 856056168703778120060851031398
928 891935228343609815826046738996
929 929298017532502079476554935744
930 968205077462623642791256053706
931 1008719386790443788334604524873
932 1050906458470344844693297683587
933 1094834440384200741643407853249
934 1140574219913805547498544317711
935 1188199532608553312109875765593
936 1237787075106676759602119225785
937 1289416622474296259653426522849
938 1343171150132886628110272794225
939 1399136960552172088139482939899
940 1457403814892299655702191963037
941 1518065069786037727240452171826
942 1581217819459106824924766510904
943 1646963043394177145166533116085
944 1715405759751987124250036820859
945 1786655184771036339918591644331
946 1860824898375827083011514646463
947 1938033016232242693664398670270
948 2018402368497818399007505098226
949 2102060685523935268993468455630
950 2189140790776830710223410505308
951 2279780801254304839603767906557
952 2374124335685612176548855419151
953 2472320730812778693586355608902
954 2574525266062997650579886383806
955 2680899396933330541065075845791
956 2791610997421216293313666853007
957 2906834611846748974448962975005
958 3026751716425889077336445910489
959 3151550990967181269743152598280
960 3281428601078753694772974558636
961 3416588491286803823892857454671
962 3557242689482049933837428763659
963 3703611623126156007965570221180
964 3855924447666563770047643284916
965 4014419387624875481968581330134
966 4179344090841594752638151523374
967 4350955996378012186563361086771
968 4529522716595016219705940427563
969 4715322433947953721206282511872
970 4908644313057087340575887251352
971 5109788928634007457852933629609
972 5319068709866314130985225738909
973 5536808401885271470765807386674
974 5763345544964743604689263908200
975 5999030972123802155596708406002
976 6244229325830773515124683364246
977 6499319594532394900373990380515
978 6764695669759029564079140233209
979 7040766924584747668120081687951
980 7327958814250404771221294511821
981 7626713499787806882167867489975
982 7937490495514571884206527180057
983 8260767341301511090959070677780
984 8597040300548233383721594890794
985 8946825084837312816421946997352
986 9310657606273771389281599687162
987 9689094758553871397280806072324
988 10082715227846341713508069551662
989 10492120334609202273824312777124
990 10917934907507400776341192608436
991 11360808190639519742960488896713
992 11821414785326996907893943257711
993 12300455627765572393106088164173
994 12798659003887226971873302754557
995 13316781602830610908775948517080
996 13855609610470127483346690987752
997 14415959844507290876207493729479
998 14998680932684022256643733020381
999 15604654535734998166952519788086
1000 16234796616756374065311804866454