0 1
1 0
2 1
3 1
4 2
5 2
6 4
7 4
8 6
9 7
10 10
11 11
12 16
13 18
14 24
15 28
16 36
17 42
18 54
19 62
20 78
21 91
22 112
23 130
24 159
25 184
26 222
27 258
28 308
29 356
30 424
31 488
32 576
33 664
34 778
35 894
36 1044
37 1196
38 1389
39 1590
40 1838
41 2098
42 2419
43 2754
44 3162
45 3596
46 4114
47 4668
48 5328
49 6032
50 6864
51 7760
52 8806
53 9936
54 11252
55 12672
56 14316
57 16100
58 18148
59 20374
60 22925
61 25694
62 28854
63 32296
64 36200
65 40457
66 45276
67 50526
68 56450
69 62916
70 70182
71 78114
72 87014
73 96722
74 107586
75 119450
76 132684
77 147136
78 163234
79 180800
80 200328
81 221646
82 245288
83 271092
84 299672
85 330844
86 365312
87 402911
88 444406
89 489654
90 539536
91 593892
92 653732
93 718933
94 790600
95 868656
96 954366
97 1047658
98 1149978
99 1261320
100 1383282
101 1515936
102 1661112
103 1818920
104 1991448
105 2178926
106 2383668
107 2606046
108 2848704
109 3112110
110 3399284
111 3710890
112 4050296
113 4418400
114 4819046
115 5253330
116 5725632
117 6237376
118 6793464
119 7395701
120 8049680
121 8757558
122 9525710
123 10356816
124 11258032
125 12232650
126 13288823
127 14430446
128 15666804
129 17002616
130 18448334
131 20009630
132 21698410
133 23521328
134 25491930
135 27618156
136 29915274
137 32392704
138 35067820
139 37951602
140 41063810
141 44417384
142 48034632
143 51930750
144 56131098
145 60653304
146 65526180
147 70770332
148 76418304
149 82494110
150 89034720
151 96067858
152 103635498
153 111769828
154 120518272
155 129918120
156 140023185
157 150876364
158 162538690
159 175059698
160 188508352
161 202941744
162 218438054
163 235062738
164 252904373
165 272038212
166 292564304
167 314569032
168 338165688
169 363453010
170 390559230
171 419597422
172 450712362
173 484033382
174 519724234
175 557932360
176 598842886
177 642624120
178 689484928
179 739617216
180 793256964
181 850622400
182 911980014
183 977578190
184 1047717352
185 1122679942
186 1202804970
187 1288412908
188 1379886144
189 1477588496
190 1581950668
191 1693385332
192 1812377948
193 1939395770
194 2074985728
195 2219677056
196 2374085186
197 2538809088
198 2714541605
199 2901959612
200 3101842770
201 3314956104
202 3542176054
203 3784366678
204 4042513478
205 4317591140
206 4610707332
207 4922961549
208 5255597648
209 5609855112
210 5987130944
211 6388820918
212 6816493392
213 7271720032
214 7756260150
215 8271882432
216 8820560470
217 9404282790
218 10025262480
219 10685734900
220 11388179944
221 12135109056
222 12929300982
223 13773575028
224 14671043568
225 15624870898
226 16638540852
227 17715603098
228 18859956858
229 20075581176
230 21366838522
231 22738188212
232 24194508168
233 25740793536
234 27382497744
235 29125212480
236 30975032286
237 32938215012
238 35021568074
239 37232091622
240 39577387904
241 42065282752
242 44704262928
243 47503074932
244 50471188286
245 53618374225
246 56955196544
247 60492565324
248 64242260878
249 68216461338
250 72428297632
251 76891357686
252 81620274432
253 86630201200
254 91937439028
255 97558882013
256 103512681660
257 109817665344
258 116494040060
259 123562777912
260 131046366498
261 138968159976
262 147353173814
263 156227404926
264 165618673572
265 175555905906
266 186070031174
267 197193225156
268 208959860352
269 221405714184
270 234568975590
271 248489410528
272 263209434368
273 278773233038
274 295227898864
275 312622511832
276 331009342848
277 350442886974
278 370981144848
279 392684606078
280 415617606662
281 439847267470
282 465444932544
283 492485053724
284 521046722064
285 551212496848
286 583070028024
287 616710835308
288 652232027484
289 689735021804
290 729327374322
291 771121437690
292 815236300854
293 861796391746
294 910933533324
295 962785480686
296 1017498109638
297 1075223886491
298 1136124187944
299 1200367711020
300 1268132932836
301 1339606449284
302 1414985593478
303 1494476701632
304 1578297889608
305 1666677254790
306 1759855820992
307 1858085664310
308 1961633048115
309 2070776471634
310 2185809995606
311 2307041223744
312 2434794831630
313 2569410468444
314 2711246514240
315 2860677901438
316 3018100102294
317 3183926882298
318 3358594533130
319 3542559544850
320 3736303113816
321 3940328733916
322 4155166983260
323 4381373048904
324 4619531810936
325 4870255287592
326 5134188051006
327 5412004594470
328 5704415086144
329 6012162675756
330 6336029609254
331 6676834461944
332 7035438654456
333 7412743615968
334 7809697711040
335 8227293354080
336 8666574375056
337 9128633073152
338 9614618068930
339 10125731303424
340 10663236390832
341 11228455588698
342 11822778685772
343 12447659932786
344 13104627521676
345 13795280487104
346 14521298796600
347 15284440254528
348 16086551245862
349 16929563634626
350 17815506228288
351 18746501685612
352 19724778728780
353 20752669099828
354 21832620573161
355 22967193956852
356 24159076985232
357 25411081386848
358 26726157693722
359 28107392424594
360 29558023876306
361 31081439424206
362 32681192391344
363 34360999496704
364 36124758850918
365 37976547613312
366 39920641195093
367 41961511135504
368 44103845627520
369 46352547655440
370 48712756907696
371 51189848252040
372 53789455136262
373 56517468422650
374 59380061415382
375 62383689112206
376 65535114942906
377 68841410534160
378 72309984284432
379 75948581679024
380 79765315869852
381 83768668618418
382 87967522990576
383 92371165048322
384 96989318815534
385 101832148776568
386 106910297317494
387 112234888135488
388 117817566298072
389 123670502715720
390 129806437013932
391 136238683154184
392 142981175368558
393 150048475066624
394 157455820016182
395 165219132728976
396 173355073130304
397 181881048545028
398 190815270161472
399 200176764798468
400 209985435399540
401 220262074824562
402 231028430677624
403 242307221291780
404 254122205265066
405 266498199874944
406 279461155624064
407 293038177392778
408 307257604373652
409 322149034191428
410 337743408686976
411 354073041312048
412 371171709147748
413 389074683964086
414 407818830946442
415 427442643728480
416 447986350393707
417 469491952879962
418 492003340746058
419 515566335440896
420 540228812427432
421 566040750725844
422 593054364095016
423 621324156363232
424 650907062289014
425 681862509303084
426 714252568788502
427 748142024773184
428 783598536494656
429 820692714702793
430 859498296297418
431 900092229028800
432 942554859133524
433 986970025137236
434 1033425259559396
435 1082011892663680
436 1132825269227882
437 1185964863236590
438 1241534510872890
439 1299642537067752
440 1360402006040238
441 1423930860782808
442 1490352192407988
443 1559794393824204
444 1632391449334150
445 1708283103682382
446 1787615173549776
447 1870539733347890
448 1957215450194762
449 2047807788036978
450 2142489367912926
451 2241440191920188
452 2344848030806640
453 2452908669530194
454 2565826324172280
455 2683813911080954
456 2807093495361792
457 2935896585547408
458 3070464616198080
459 3211049270312064
460 3357912998542796
461 3511329371853636
462 3671583640167080
463 3838973117742012
464 4013807784398592
465 4196410706419704
466 4387118683496642
467 4586282708300928
468 4794268662663480
469 5011457818966960
470 5238247589462446
471 5475052073018682
472 5722302861518400
473 5980449635913024
474 6249961034078734
475 6531325300170544
476 6825051218785104
477 7131668822070736
478 7451730395131408
479 7785811245842700
480 8134510786956264
481 8498453373670784
482 8878289468455406
483 9274696551981247
484 9688380376832756
485 10120075957999344
486 10570548922273358
487 11040596584670866
488 11531049400987192
489 12042772137185600
490 12576665432815008
491 13133667071120954
492 13714753661787946
493 14320942019788448
494 14953290976720848
495 15612902877221906
496 16300925528510648
497 17018553824054131
498 17767031841842412
499 18547654605375274
500 19361770342170000
501 20210782393116092
502 21096151643191930
503 22019398591281696
504 22982105966181844
505 23985920969502358
506 25032558091224480
507 26123801539495704
508 27261508270646334
509 28447610620956696
510 29684119567378938
511 30973127577071618
512 32316812116503030
513 33717438735990788
514 35177364845724080
515 36699043054088064
516 38285025230765846
517 39937966118582640
518 41660627705583538
519 43455883131885208
520 45326721393758720
521 47276251568851458
522 49307707877275536
523 51424454249818114
524 53629989773142624
525 55927953627740144
526 58322130945822712
527 60816458148050698
528 63415029245094874
529 66122101603803894
530 68942102725974528
531 71879636477223180
532 74939490378398656
533 78126642333203130
534 81446268470598000
535 84903750409317128
536 88504683692734512
537 92254885631582014
538 96160404375169584
539 100227527377009458
540 104462791149831976
541 108872990401496216
542 113465188525041648
543 118246727456131824
544 123225238952455822
545 128408655228087498
546 133805221080878192
547 139423505362512426
548 145272414017161038
549 151361202450731012
550 157699489547930808
551 164297271009257920
552 171164934418902912
553 178313273622309156
554 185753504922981444
555 193497282579210499
556 201556716212731930
557 209944387509365904
558 218673368928904512
559 227757241699807676
560 237210115926573708
561 247046649975660388
562 257282072082703388
563 267932201234348246
564 279013470385523472
565 290542948948618200
566 302538367739401302
567 315018143193557648
568 328001404167469320
569 341508018011296296
570 355558619360400615
571 370174638202575352
572 385378330806116400
573 401192809929274630
574 417642078040463300
575 434751059829204144
576 452545637885621242
577 471052687682620706
578 490300115894288694
579 510316898031820872
580 531133119592209110
581 552780016544096640
582 575290019512357760
583 598696797323040642
584 623035304444641152
585 648341827816884354
586 674654037784055948
587 702011038449035976
588 730453422351386518
589 760023324604117406
590 790764481587752954
591 822722289146321910
592 855943865586609408
593 890478114230183838
594 926375791028164376
595 963689571785935214
596 1002474124726329724
597 1042786182726862536
598 1084684621186397460
599 1128230535639496570
600 1173487325307375980
601 1220520776478414528
602 1269399152151694128
603 1320193281600962020
604 1372976656546321264
605 1427825527349122804
606 1484819006178713694
607 1544039170315800300
608 1605571172814638738
609 1669503353426823576
610 1735927357292799912
611 1804938254034791370
612 1876634665049666116
613 1951118891356637824
614 2028497050104260646
615 2108879211800439792
616 2192379546687406756
617 2279116472026325016
618 2369212809040521540
619 2462795940972237468
620 2559997981343958912
621 2660955943555856308
622 2765811921265360636
623 2874713270348283648
624 2987812802253244224
625 3105268979204882294
626 3227246121450009816
627 3353914616643355650
628 3485451141963838456
629 3622038888689490870
630 3763867800230882496
631 3911134812969633454
632 4064044111329262661
633 4222807386027102424
634 4387644107377993798
635 4558781802189888826
636 4736456346579194520
637 4920912262823097778
638 5112403033054332528
639 5311191417474869584
640 5517549790389566394
641 5731760481283615440
642 5954116134755779776
643 6184920076062926898
644 6424486696621564160
645 6673141845734020954
646 6931223243438732966
647 7199080900251303834
648 7477077559266854861
649 7765589145872170080
650 8065005241134481950
651 8375729563575889454
652 8698180476018977020
653 9032791501658672906
654 9380011866684117974
655 9740307053032803080
656 10114159379267021190
657 10502068592558831076
658 10904552490464861590
659 11322147554865222768
660 11755409617461068496
661 12204914538572554912
662 12671258919376158912
663 13155060828665208180
664 13656960565044956138
665 14177621434970756142
666 14717730568337722682
667 15277999751332669888
668 15859166299088453760
669 16461993947126143074
670 17087273784988135988
671 17735825210303222592
672 18408496927577506870
673 19106167969183278096
674 19829748763769122488
675 20580182228764475840
676 21358444913166231362
677 22165548166460910000
678 23002539360865641152
679 23870503141895142208
680 24770562735476520406
681 25703881285740247136
682 26671663252786817790
683 27675155843655940992
684 28715650506910736012
685 29794484463133387448
686 30913042302905512750
687 32072757623604106508
688 33275114737790878400
689 34521650423535641638
690 35813955750695890914
691 37153677952471735332
692 38542522377555934554
693 39982254491138692452
694 41474701961433616256
695 43021756798898325114
696 44625377586207594348
697 46287591765032577468
698 48010498019134885044
699 49796268718668146428
700 51647152466701714558
701 53565476711669440704
702 55553650468314626140
703 57614167109608007296
704 59749607273832635328
705 61962641848042395310
706 64256035073772450752
707 66632647734907309536
708 69095440475326280742
709 71647477204891934400
710 74291928643216880946
711 77032075958387180352
712 79871314551962486060
713 82813157946010797478
714 85861241825447149855
715 89019328189971940592
716 92291309670910227854
717 95681213965735087824
718 99193208447686154080
719 102831604901718507582
720 106600864446375643566
721 110505602591229303552
722 114550594491755142300
723 118740780349640937272
724 123081271022759012998
725 127577353791116099712
726 132234498345457326432
727 137058362943106962448
728 142054800800271386280
729 147229866663599368372
730 152589823632872360734
731 158141150175792951895
732 163890547409484568476
733 169844946587793974400
734 176011516871866363514
735 182397673321147949638
736 189011085185253439644
737 195859684431875485632
738 202951674594246603456
739 210295539871300810796
740 217900054567249146888
741 225774292801623495742
742 233927638579831591298
743 242369796153142157906
744 251110800761591380376
745 260161029686540104232
746 269531213709967987008
747 279232448904978836278
748 289276208858339519772
749 299674357247227848330
750 310439160874883675940
751 321583303084984062276
752 333119897663473668608
753 345062503145248853640
754 357425137638623062090
755 370222294082505481038
756 383468956053571057088
757 397180614035830623722
758 411373282274415653684
759 426063516123393744528
760 441268430014146222224
761 457005715951487529672
762 473293662668949810600
763 490151175347718936282
764 507597796035747100800
765 525653724668764629888
766 544339840835022211528
767 563677726182680140230
768 583689687617181153664
769 604398781184661229948
770 625828836794477103674
771 648004483673972749810
772 670951176714537540592
773 694695223599106367208
774 719263812876355375638
775 744685042868717633664
776 770987951585941087464
777 798202547528218966616
778 826359841557346834044
779 855491879716806704832
780 885631777186223107440
781 916813753247911589926
782 949073167458258436134
783 982446556898407449164
784 1016971674704585579780
785 1052687529749269354332
786 1089634427681412332790
787 1127854013193617468302
788 1167389313732706845120
789 1208284784518195576208
790 1250586355093695050632
791 1294341477272354813952
792 1339599174710278610504
793 1386410093965590842132
794 1434826557286389671282
795 1484902616981779515108
796 1536694111628907846392
797 1590258723966707177794
798 1645656040739342056224
799 1702947614336546523072
800 1762197026504370636198
801 1823469953969967591191
802 1886834236264901550654
803 1952359945587061343562
804 2020119458997063979344
805 2090187532785679285016
806 2162641379320068805896
807 2237560746201794242740
808 2315027998056803585110
809 2395128200786802407280
810 2477949208615140643802
811 2563581753753088078054
812 2652119539033127244762
813 2743659333331602118008
814 2838301070141428306020
815 2936147949113722996622
816 3037306540943719449318
817 3141886895416384931788
818 3250002653002423863744
819 3361771159816673102605
820 3477313586345550859354
821 3596755049752242488184
822 3720224740182933171252
823 3847856050879522440106
824 3979786712539531265146
825 4116158931725451591552
826 4257119533782409766736
827 4402820110063339082922
828 4553417169939462858828
829 4709072297392347656286
830 4869952312685119165632
831 5036229438906273295432
832 5208081473904338721234
833 5385691967404179207024
834 5569250403844741433328
835 5758952390726565989378
836 5954999853031403863296
837 6157601233499950860186
838 6366971699353581911538
839 6583333355244040212960
840 6806915463041523720812
841 7037954668243307646562
842 7276695233639039089344
843 7523389280013262242830
844 7778297034548158203592
845 8041687086705805215744
846 8313836652280969134178
847 8595031845402801990624
848 8885567959205786297132
849 9185749754947698455180
850 9495891760325586558708
851 9816318576767356816176
852 10147365196481981809440
853 10489377329046172660160
854 10842711738344044446600
855 11207736589638295546314
856 11584831807624479975840
857 11974389445248116677680
858 12376814064172836871782
859 12792523126681088705150
860 13221947399933948185138
861 13665531372373892875584
862 14123733683237205711360
863 14597027564962892236032
864 15085901299506716026440
865 15590858688350966548546
866 16112419537262491804788
867 16651120155594062756032
868 17207513871227575402512
869 17782171560959475366662
870 18375682197474990631760
871 18988653412717763617348
872 19621712078851845549504
873 20275504906629766329102
874 20950699062416386579838
875 21647982803690444230504
876 22368066134328686728078
877 23111681479503811760964
878 23879584381558946944848
879 24672554216700352081062
880 25491394933931653324880
881 26336935816083086056824
882 27210032264422465114522
883 28111566606714532336884
884 29042448930281880285738
885 30003617939948708296258
886 30996041842490263968512
887 32020719257485471794362
888 33078680156268540945892
889 34170986828895002421058
890 35298734880894461666658
891 36463054259745238578672
892 37665110312923355488000
893 38906104877482774018399
894 40187277403103330260116
895 41509906108587088568098
896 42875309173827671503360
897 44284845967259287136616
898 45739918310902389862432
899 47241971783041144513062
900 48792497060746440726384
901 50393031302310630202458
902 52045159571909321202876
903 53750516306590076129316
904 55510786828009892660932
905 57327708899057961257688
906 59203074327897278586262
907 61138730619601365275776
908 63136582678036909430262
909 65198594558211594604696
910 67326791271860936933424
911 69523260646540001610366
912 71790155241122820833087
913 74129694318025764773076
914 76544165875193121350256
915 79035928738215469646688
916 81607414715761234163748
917 84261130818750686480382
918 86999661546601888901896
919 89825671241041085867890
920 92741906510963623412352
921 95751198728905924022736
922 98856466602778973374640
923 102060718823497104867904
924 105367056792325036766478
925 108778677428655700687590
926 112298876062223008505346
927 115931049410546619449676
928 119678698645803112431030
929 123545432552011440711232
930 127534970776926792286370
931 131651147179628155226314
932 135897913278403542079906
933 140279341800022538200318
934 144799630335220513078336
935 149463105101596069231488
936 154274224818977475605014
937 159237584698579496334128
938 164357920551249537329364
939 169640113016252693160928
940 175089191916150084116988
941 180710340739357264670558
942 186508901256205408210118
943 192490378270238738334538
944 198660444510852926031684
945 205024945669164596549682
946 211589905583513000216448
947 218361531576651446983104
948 225346219951340872152520
949 232550561646581930079168
950 239981348061525250822464
951 247645577049486989668800
952 255550459089453260921312
953 263703423637704176743704
954 272112125667302505357184
955 280784452398294789455964
956 289728530226749948196354
957 298952731855714567325932
958 308465683636609363812112
959 318276273124392702343176
960 328393656855435485172300
961 338827268351696079193056
962 349586826360581095103664
963 360682343334360437981970
964 372124134158986619676582
965 383922825136484709807594
966 396089363231250856260480
967 408635025584742873151386
968 421571429309414011705310
969 434910541566710718018414
970 448664689940525128639116
971 462846573111282026984502
972 477469271842618373605284
973 492546260286216812068110
974 508091417617348055017840
975 524119040007089207165126
976 540643852944400571732636
977 557681023914459283923120
978 575246175447092311748736
979 593355398542165450685506
980 612025266486465160683048
981 631272849069416597215802
982 651115727212904979059964
983 671572008023060732482128
984 692660340280043600125086
985 714399930374235225191168
986 736810558705683459984026
987 759912596555790679517432
988 783727023448939389892824
989 808275445013666110355454
990 833580111361970913639945
991 859663935997030150337294
992 886550515268840504472984
993 914264148388758334772496
994 942829858023452186329306
995 972273411479971326138922
996 1002621342503489335010368
997 1033900973700209251673100
998 1066140439608084878972160
999 1099368710428675538829096
1000 1133615616443941600533184