0 1
1 2
2 1
3 4
4 8
5 6
6 10
7 16
8 18
9 26
10 33
11 40
12 58
13 74
14 82
15 112
16 147
17 166
18 212
19 268
20 316
21 392
22 476
23 560
24 695
25 838
26 967
27 1184
28 1430
29 1648
30 1970
31 2352
32 2731
33 3236
34 3803
35 4404
36 5206
37 6080
38 6984
39 8192
40 9553
41 10942
42 12709
43 14736
44 16886
45 19506
46 22448
47 25648
48 29552
49 33874
50 38514
51 44180
52 50530
53 57306
54 65380
55 74496
56 84385
57 95936
58 108834
59 122976
60 139484
61 157774
62 177706
63 200944
64 226824
65 254922
66 287268
67 323404
68 362906
69 407902
70 457866
71 512736
72 575173
73 644180
74 719693
75 805496
76 900516
77 1004224
78 1121228
79 1250928
80 1392907
81 1552122
82 1727941
83 1920784
84 2136766
85 2374552
86 2634754
87 2925776
88 3246357
89 3596510
90 3986421
91 4415968
92 4885650
93 5406678
94 5979234
95 6605664
96 7299777
97 8060928
98 8892301
99 9812364
100 10821150
101 11921442
102 13135608
103 14466384
104 15918186
105 17516172
106 19264493
107 21171776
108 23268884
109 25559670
110 28055514
111 30796768
112 33789912
113 37047240
114 40617639
115 44514016
116 48753428
117 53391858
118 58446904
119 63945200
120 69955299
121 76497170
122 83605169
123 91367392
124 99811726
125 108977984
126 118972978
127 129839696
128 141630703
129 154470158
130 168414290
131 183537480
132 199991456
133 217843182
134 237187216
135 258215680
136 281017018
137 305703936
138 332509426
139 361557000
140 392991384
141 427086558
142 464000404
143 503926864
144 547200125
145 594011288
146 644603987
147 699396480
148 758633866
149 822609976
150 891831960
151 966624880
152 1047359508
153 1134636996
154 1228866382
155 1330528256
156 1440354202
157 1558841792
158 1686588914
159 1824502416
160 1973208925
161 2133432610
162 2306271850
163 2492532348
164 2693116330
165 2909332418
166 3142182840
167 3392811104
168 3662805827
169 3953386304
170 4265963426
171 4602490784
172 4964483990
173 5353652690
174 5772359102
175 6222512192
176 6706221268
177 7226308480
178 7785126479
179 8385306724
180 9030265344
181 9722858690
182 10466310558
183 11264793360
184 12121822678
185 13041298724
186 14028255424
187 15087056352
188 16222475310
189 17440532096
190 18746563534
191 20146454960
192 21647470901
193 23256070750
194 24979419513
195 26826337956
196 28804712938
197 30923190208
198 33192384030
199 35621976352
200 38222478954
201 41006580560
202 43986045319
203 47173713352
204 50584847932
205 54233637216
206 58135626478
207 62309252160
208 66771722761
209 71541737558
210 76641417816
211 82091707060
212 87915208908
213 94138335232
214 100786388900
215 107886774160
216 115471158217
217 123569944686
218 132216145020
219 141447831040
220 151301667418
221 161817230406
222 173040063608
223 185014476144
224 197788063651
225 211415102746
226 225948854635
227 241446664064
228 257973394348
229 275592807330
230 294373666150
231 314393620224
232 335729175053
233 358462487654
234 382686161107
235 408492106688
236 435978676364
237 465255983488
238 496434006098
239 529630608544
240 564976957173
241 602604238460
242 642653194427
243 685280231580
244 730642047318
245 778906231550
246 830258739504
247 884886865456
248 942990400345
249 1004789917686
250 1070508599019
251 1140384752992
252 1214680295628
253 1293660523778
254 1377608903570
255 1466836613904
256 1561659251127
257 1662413248320
258 1769467455184
259 1883197406100
260 2004002646078
261 2132319563840
262 2268593947714
263 2413300384976
264 2566955470110
265 2730087354732
266 2903258532370
267 3087080675576
268 3282179728644
269 3489221178344
270 3708927921056
271 3942041804800
272 4189350367818
273 4451706632642
274 4729988132927
275 5025126799804
276 5338129448870
277 5670032456576
278 6021936678952
279 6395030429744
280 6790537754741
281 7209757126730
282 7654088923044
283 8124978590912
284 8623957701816
285 9152674392122
286 9712832891548
287 10306239343488
288 10934833492010
289 11600621992196
290 12305731690881
291 13052445127336
292 13843124748542
293 14680271917304
294 15566569090298
295 16504796776560
296 17497896323770
297 18549016653248
298 19661426050622
299 20838582161584
300 22084180920448
301 23402059576320
302 24796277732048
303 26271172118880
304 27831246859347
305 29481263185228
306 31226304127010
307 33071654621056
308 35022897254888
309 37085983979798
310 39267109018676
311 41572815513664
312 44010071046205
313 46586128376982
314 49308648435584
315 52185784826976
316 55226026896658
317 58438335879166
318 61832244154086
319 65417684331360
320 69205134998413
321 73205730828942
322 77431081869962
323 81893435796468
324 86605794549046
325 91581717029814
326 96835505560086
327 102382336376096
328 108238038224263
329 114419298795520
330 120943817229969
331 127830063847072
332 135097501846622
333 142766756645184
334 150859362658530
335 159398010042688
336 168406725132719
337 177910595083264
338 187936050523237
339 198511067457840
340 209664859632746
341 221428191591670
342 233833613552934
343 246915128932000
344 260708531679045
345 275251667362880
346 290584084243680
347 306747408704544
348 323785625077956
349 341744697971730
350 360673001148772
351 380621630740384
352 401643985313120
353 423796241159410
354 447137715161072
355 471730413185724
356 497639544000146
357 524933923119936
358 553685501472454
359 583969937464944
360 615867032296330
361 649460222657706
362 684837232648555
363 722090561270464
364 761316921393342
365 802617962784710
366 846100834786278
367 891877586693200
368 940065952274836
369 990789976823694
370 1044179396013496
371 1100370509562284
372 1159506860827806
373 1221738573071280
374 1287223342954594
375 1356127202061440
376 1428623787576355
377 1504895445184448
378 1585134105124282
379 1669540509075904
380 1758325411045970
381 1851710554947706
382 1949927882234208
383 2053220870007040
384 2161845595987834
385 2276069900066182
386 2396174903173258
387 2522456201428992
388 2655222952471938
389 2794799563359360
390 2941527060261624
391 3095762131144752
392 3257878969968673
393 3428270807103656
394 3607348943891588
395 3795544809013112
396 3993311633664930
397 4201123444716608
398 4419477395231978
399 4648895644083056
400 4889924271775274
401 5143135873199380
402 5409131707922107
403 5688540584759108
404 5982021704052270
405 6290267063207334
406 6614000361848216
407 6953980173515248
408 7311002590119294
409 7685900107825374
410 8079545216819364
411 8492853370337568
412 8926781808611186
413 9382333557075418
414 9860560815076674
415 10362563785685648
416 10889495072539351
417 11442563474935954
418 12023032899769037
419 12632227271841560
420 13271534721856600
421 13942406535225106
422 14646362703297550
423 15384996627918496
424 16159974059260483
425 16973039285474388
426 17826020491166175
427 18720828784856704
428 19659465025689346
429 20644025830137424
430 21676702802185496
431 22759790163124464
432 23895691402118943
433 25086918662106688
434 26336101357002454
435 27645993645800684
436 29019473925580736
437 30459554449615104
438 31969389824665936
439 33552276761546448
440 35211664711335894
441 36951165397839390
442 38774552994806005
443 40685776021794496
444 42688967928061718
445 44788447655821312
446 46988733064027190
447 49294552826478992
448 51710847341308127
449 54242783727751206
450 56895769330639983
451 59675453202809232
452 62587742728322406
453 65638818780793694
454 68835138033433672
455 72183451562419648
456 75690821716210012
457 79364625234953792
458 83212574227027729
459 87242735136263360
460 91463532658184968
461 95883773193020016
462 100512666341242498
463 105359829960514912
464 110435316215058044
465 115749635712975872
466 121313764090150036
467 127139171177242852
468 133237847911456194
469 139622314480703774
470 146305653187769376
471 153301538709917600
472 160624247851610555
473 168288696311977338
474 176310472930462031
475 184705851572715360
476 193491832038045520
477 202686178521842880
478 212307434223683236
479 222374967167818384
480 232909013148412140
481 243930693196055578
482 255462065171153436
483 267526172046989092
484 280147062402126656
485 293349848169235048
486 307160759207979210
487 321607167627491984
488 336717652126873816
489 352522059290462708
490 369051532642858488
491 386338584734215872
492 404417165652553802
493 423322697137725664
494 443092153694629676
495 463764139604537504
496 485378928483670495
497 507978554102806656
498 531606897325528993
499 556309732348593280
500 582134827998099238
501 609132045366651434
502 637353392123167914
503 666853136014614528
504 697687914080061635
505 729916795691916458
506 763601410187802101
507 798806069592951584
508 835597841160926104
509 874046690302463228
510 914225618968036302
511 956210749596378880
512 1000081484660241097
513 1045920662042042462
514 1093814652529321405
515 1143853538581536796
516 1196131288208669504
517 1250745867249303320
518 1307799440257870788
519 1367398565807913744
520 1429654324971413806
521 1494682546288435840
522 1562604025750600483
523 1633544674430097616
524 1707635769745076342
525 1785014202370478522
526 1865822646319559018
527 1950209840441871056
528 2038330864798948698
529 2130347335392498598
530 2226427720278797666
531 2326747649843178204
532 2431490138676288460
533 2540845939547436352
534 2655013892518608608
535 2774201178527972576
536 2898623714871921681
537 3028506546878875712
538 3164084138303570147
539 3305600814286886400
540 3453311199779730944
541 3607480550515647888
542 3768385250095361814
543 3936313301905976144
544 4111564704945406689
545 4294452010317590064
546 4485300874162600807
547 4684450485383297024
548 4892254187489581144
549 5109080098610839154
550 5335311599011135588
551 5571348027352514384
552 5817605374613772750
553 6074516837708677266
554 6342533600267472517
555 6622125610740355152
556 6913782209253767534
557 7218013001431059392
558 7535348732130803804
559 7866341996438071856
560 8211568216080831615
561 8571626618596522902
562 8947141044637809672
563 9338761040786391996
564 9747162955135141436
565 10173050851299081454
566 10617157732991629036
567 11080246771699457424
568 11563112339103965465
569 12066581377026753238
570 12591514774656906697
571 13138808536206931744
572 13709395311465235874
573 14304245938219650398
574 14924370763937098862
575 15570821357941341488
576 16244692236555367533
577 16947122355657399296
578 17679297027876698117
579 18442449854374588720
580 19237864407213740650
581 20066876373125373578
582 20930875718559010074
583 21831308587801240560
584 22769679697418444763
585 23747554759356924774
586 24766562623753791149
587 25828397956069584640
588 26934823945956699520
589 28087674721775245926
590 29288858346034516426
591 30540359846518134240
592 31844243932794239572
593 33202658343866335944
594 34617837242160986995
595 36092104271943010416
596 37627876297041170966
597 39227667196671882880
598 40894091310260222510
599 42629867613988268496
600 44437823961988888845
601 46320900960447387264
602 48282156637186660382
603 50324771183854689376
604 52452051307293853702
605 54667435445151120034
606 56974499070929870502
607 59376959583912854128
608 61878682129914776575
609 64483685530099179648
610 67196147777733953366
611 70020412538257595272
612 72960995769806321464
613 76022591894284892712
614 79210081059196569896
615 82528536534583355120
616 85983231633819109918
617 89579647819561181106
618 93323482971270099778
619 97220659149617922048
620 101277331638346797548
621 105499898176987272116
622 109895007673403538482
623 114469570294285692208
624 119230767768512157470
625 124186063153275515414
626 129343212098453245602
627 134710274349418579328
628 140295624684402042328
629 146107965480092746752
630 152156339557012071384
631 158450142431606288512
632 164999136324863765468
633 171813464496492390442
634 178903664971353952467
635 186280686162175958432
636 193955902855335506858
637 201941131575339083328
638 210248648011601290574
639 218891204851377126944
640 227882048964710144252
641 237234940831279133794
642 246964174437616895000
643 257084596501266147396
644 267611628115698277222
645 278561286936765238442
646 289950208689174466852
647 301795671288679329360
648 314115619567937702795
649 326928689318003232642
650 340254234175446417516
651 354112353183921504472
652 368523917651929051706
653 383510601105205633088
654 399094910012823071234
655 415300213793779377744
656 432150778168403650722
657 449671799393467901248
658 467889437786926348771
659 486830854870307584132
660 506524251495590900404
661 526998905276140577982
662 548285211954833894726
663 570414727870765169184
664 593420211727795691343
665 617335670646753527356
666 642196407468895371371
667 668039067366307363776
668 694901689087047645360
669 722823757620719445824
670 751846256210265581344
671 782011723381600956336
672 813364311554492881710
673 845949845048811393978
674 879815883554351639725
675 915011787363102338176
676 951588782028621044140
677 989600028972805586944
678 1029100698088886511664
679 1070148039816384220496
680 1112801463657756393717
681 1157122618950198535820
682 1203175475201626114464
683 1251026409408005553216
684 1300744295879155905268
685 1352400595738174477842
686 1406069454026247623332
687 1461827799600269494000
688 1519755444796984064184
689 1579935193380620473274
690 1642452951639697780261
691 1707397839365643800484
692 1774862309813011083154
693 1844942273203412793358
694 1917737220292564593828
695 1993350355681519602128
696 2071888735066416987911
697 2153463402761483529920
698 2238189539843009819874
699 2326186616673601852032
700 2417578545897089639784
701 2512493847008167023808
702 2611065815843276918614
703 2713432694776487132352
704 2819737855479013026632
705 2930129987198641098854
706 3044763286070979640248
707 3163797658075198698240
708 3287398928119472631198
709 3415739050532054713722
710 3548996334432938585640
711 3687355675915804837632
712 3831008792005413235544
713 3980154470841529211500
714 4134998829491098764962
715 4295755573965116031976
716 4462646276866822233382
717 4635900663572857599568
718 4815756901178665369202
719 5002461906611357445088
720 5196271664210251054405
721 5397451546706068625728
722 5606276657115834168831
723 5823032181146362682500
724 6048013743643640387778
725 6281527787863233924650
726 6523891966481412925404
727 6775435537393291463328
728 7036499784332665190523
729 7307438450594569196292
730 7588618178470393069411
731 7880418975693353456288
732 8183234696409927257110
733 8497473528906740917156
734 8823558512827617001712
735 9161928072498535243776
736 9513036558093343625074
737 9877354818994488350656
738 10255370795110949270168
739 10647590117268441617480
740 11054536742650382726990
741 11476753610239092622336
742 11914803306822763094452
743 12369268771178465388528
744 12840754020409766033841
745 13329884888525250402754
746 13837309806719805900868
747 14363700608201181805248
748 14909753347024426416212
749 15476189162478685298686
750 16063755170785311943786
751 16673225372795874390400
752 17305401611326805632315
753 17961114558859325028074
754 18641224723604684951168
755 19346623509677236748032
756 20078234310876769388742
757 20837013625479749034368
758 21623952230165505921476
759 22440076391146250043696
760 23286449099121247441024
761 24164171368856773183330
762 25074383580093457508972
763 26018266845436081405152
764 26997044448720092018622
765 28011983329255503962520
766 29064395596745167090850
767 30155640123086553703056
768 31287124184912517708182
769 32460305140920500666578
770 33676692193265084807740
771 34937848205069434704572
772 36245391557136853503692
773 37600998096571936214390
774 39006403147648444832238
775 40463403566807560223648
776 41973859897958622958315
777 43539698596783939799296
778 45162914304868376056446
779 46845572233323391472232
780 48589810622669386433498
781 50397843258873152703278
782 52271962109150533600026
783 54214540042045619530768
784 56228033610487900636539
785 58314985965843563861696
786 60478029865321789421889
787 62719890749960370086272
788 65043389965656868868216
789 67451448087559679636312
790 69947088323735653904284
791 72533440075083654572576
792 75213742609389369176784
793 77991348824305538433024
794 80869729181288987322242
795 83852475765582926971712
796 86943306445563689018522
797 90146069219132963006848
798 93464746699565556725992
799 96903460712322147242496
800 100466477096224527832406
801 104158210658856034887974
802 107983230256100706224711
803 111946264095014108293280
804 116052205206883533147042
805 120306117059016500980864
806 124713239410951042034954
807 129278994358464502362064
808 134008992532139715625707
809 138909039563424110530658
810 143985142758239961631432
811 149243517942704691053008
812 154690596601238073109416
813 160333033243962284301952
814 166177712966024311221282
815 172231759326574397978672
816 178502542480594263747782
817 184997687524555725551916
818 191725083191989834587671
819 198692890827866315930816
820 205909553600623003618820
821 213383806097207638986530
822 221124684225944551304292
823 229141535383416226427344
824 237444029040149398823378
825 246042167666043135899122
826 254946297949422822956500
827 264167122474103830702720
828 273715711770845229837416
829 283603516695128281345600
830 293842381306360240005422
831 304444556159619045738960
832 315422711959330652401727
833 326789953761877618387898
834 338559835633254488563868
835 350746375708005884368556
836 363364071848553408673890
837 376427917806299638508800
838 389953419828027411765664
839 403956613919046655596688
840 418454083658923174290884
841 433462978511045940523330
842 449001032851248556572251
843 465086585604909059222280
844 481738600430811032403830
845 498976686692237094275894
846 516821121098650288341830
847 535292869952539536024768
848 554413612257455102162897
849 574205763564874255434554
850 594692500491327645261560
851 615897786177705911189504
852 637846396561675371357682
853 660563947392073108190930
854 684076922274885024273734
855 708412701613994309376800
856 733599592372163416230795
857 759666858961422884576896
858 786644755118757183387297
859 814564556688273291046816
860 843458595639020225941338
861 873360295167513590664386
862 904304205802595754473730
863 936326042862272427312768
864 969462725103551550449065
865 1003752414480115340440878
866 1039234557380202835625383
867 1075949927176470502648284
868 1113940667998863412858350
869 1153250340127996617772778
870 1193923966832137876259324
871 1236008082554003313553248
872 1279550782870587715871689
873 1324601776041050964430272
874 1371212436044985743135918
875 1419435857560680670702592
876 1469326912688915361779696
877 1520942309321705766863488
878 1574340651634872593721606
879 1629582502499027348973920
880 1686730447704323560539154
881 1745849162510126588351214
882 1807005480304023114611852
883 1870268463260259741292172
884 1935709475541886889212542
885 2003402258821660215246344
886 2073423010007746432176742
887 2145850461752569598970608
888 2220765965508816740714317
889 2298253577015884800798144
890 2378400144832798540028900
891 2461295401668876886508128
892 2547032058391326977201464
893 2635705901367322695877062
894 2727415892880126436050772
895 2822264274492972842177936
896 2920356674060976438264011
897 3021802216119978008375232
898 3126713635522178043059009
899 3235207395062829979591220
900 3347403806814329693922274
901 3463427157035354759390506
902 3583405835447951425441670
903 3707472468584350203216720
904 3835764057067458846746223
905 3968422117671427806358336
906 4105592829850883892748279
907 4247427186597554361182976
908 4394081150525815901189746
909 4545715814864025316294656
910 4702497569207218988959622
911 4864598270989669662319808
912 5032195422340203112779005
913 5205472352174936533781560
914 5384618404548752457041230
915 5569829132912204295873604
916 5761306500125927241016330
917 5959259085322897456041600
918 6163902297250877962448588
919 6375458593942876898667872
920 6594157709877274074348164
921 6820236890247554727329346
922 7053941132187994246817128
923 7295523434190779387713024
924 7545245053319617298853988
925 7803375770067624426758106
926 8070194162176297283268872
927 8345987887003216840935088
928 8631053972285958217909795
929 8925699116708241908050378
930 9230239999841087860475550
931 9545003601304383005404620
932 9870327530647302171500678
933 10206560367508119879141816
934 10554062011900440383017298
935 10913204046220173855908848
936 11284370108518850185497572
937 11667956276895820246352384
938 12064371466709130865555007
939 12474037840132997735130496
940 12897391227918164278158528
941 13334881565170521654977152
942 13786973340661670108964182
943 14254146059529732134661376
944 14736894721305772487473385
945 15235730312768910496290884
946 15751180315495372318049981
947 16283789230161635253454592
948 16834119117091286454973378
949 17402750152923012327923416
950 17990281205596934225372596
951 18597330427132624830798016
952 19224535864086745945994723
953 19872556088037584004786030
954 20542070845558221072100067
955 21233781727575294250681920
956 21948412860616755039365536
957 22686711619403784729330688
958 23449449360699429180403976
959 24237422181080152500841632
960 25051451698076033074380654
961 25892385854614814764719872
962 26761099749614567813761321
963 27658496494158511845319928
964 28585508093208612392021896
965 29543096355897984113677118
966 30532253833829935513516758
967 31554004787360642657574912
968 32609406183109157679223782
969 33699548722123784516174250
970 34825557898711081802174238
971 35988595093384050380965400
972 37189858699357179723006220
973 38430585282633395589429200
974 39712050779372646482768520
975 41035571729966109518328448
976 42402506549899379271215592
977 43814256841349142024031936
978 45272268744942526884766414
979 46778034331800729637839100
980 48333093040077764427328154
981 49939033155438307072264152
982 51597493335646498993420170
983 53310164183755574428994288
984 55078789869355233216798886
985 56905169798111796348627098
986 58791160334396307370737156
987 60738676576469030867667424
988 62749694184519486003952226
989 64826251266690427022130830
990 66970450322578066599292580
991 69184460244573297547161904
992 71470518382521557155390227
993 73830932671230722474272970
994 76268083821273761124120815
995 78784427578930449705688812
996 81382497054834262551150822
997 84064905121870665107719104
998 86834346888571910723470038
999 89693602247611409364149488
1000 92645538500046641424011286