0 1
1 1
2 2
3 3
4 4
5 5
6 8
7 8
8 12
9 14
10 19
11 21
12 30
13 31
14 42
15 50
16 62
17 69
18 91
19 99
20 126
21 144
22 175
23 198
24 246
25 275
26 331
27 379
28 452
29 509
30 612
31 686
32 811
33 922
34 1076
35 1219
36 1428
37 1604
38 1863
39 2108
40 2434
41 2739
42 3162
43 3551
44 4075
45 4593
46 5240
47 5885
48 6721
49 7527
50 8556
51 9597
52 10870
53 12164
54 13766
55 15382
56 17352
57 19389
58 21813
59 24333
60 27358
61 30466
62 34158
63 38045
64 42568
65 47332
66 52908
67 58750
68 65548
69 72753
70 81032
71 89823
72 99949
73 110661
74 122931
75 136045
76 150914
77 166813
78 184875
79 204140
80 225951
81 249336
82 275622
83 303852
84 335601
85 369628
86 407765
87 448820
88 494618
89 543916
90 598921
91 658066
92 723885
93 794851
94 873523
95 958392
96 1052448
97 1153789
98 1265898
99 1386915
100 1520412
101 1664508
102 1823404
103 1994811
104 2183510
105 2387300
106 2611131
107 2852874
108 3118300
109 3404737
110 3718822
111 4058046
112 4429345
113 4830314
114 5268968
115 5742446
116 6259831
117 6818512
118 7428139
119 8086334
120 8804202
121 9578821
122 10422862
123 11333898
124 12325399
125 13395346
126 14559203
127 15814591
128 17179064
129 18650924
130 20249112
131 21972687
132 23843271
133 25859757
134 28046645
135 30404091
136 32958603
137 35711562
138 38693286
139 41905408
140 45382259
141 49127307
142 53178072
143 57540190
144 62256259
145 67332898
146 72818331
147 78722271
148 85097641
149 91957394
150 99361764
151 107325926
152 115917958
153 125157755
154 135120426
155 145831198
156 157375234
157 169781873
158 183147481
159 197508708
160 212972288
161 229582939
162 247461716
163 266660616
164 287316346
165 309492016
166 333339580
167 358934764
168 386449677
169 415971671
170 447695315
171 481724864
172 518277090
173 557475219
174 599564588
175 644687270
176 693120236
177 745030742
178 800728337
179 860408799
180 924422141
181 992993082
182 1066516880
183 1145255984
184 1229652512
185 1320011301
186 1416831987
187 1520463877
188 1631470767
189 1750257323
190 1877455354
191 2013532248
192 2159201404
193 2314996787
194 2481723112
195 2659995995
196 2850717656
197 3054595547
198 3272647961
199 3505681427
200 3754843850
201 4021060445
202 4305619300
203 4609579900
204 4934394448
205 5281268132
206 5651837197
207 6047479439
208 6470031229
209 6921064461
210 7402648502
211 7916568074
212 8465153082
213 9050437108
214 9675035295
215 10341261716
216 11052060492
217 11810053960
218 12618555061
219 13480543774
220 14399738087
221 15379519895
222 16424072116
223 17537221146
224 18723669858
225 19987755848
226 21334755780
227 22769582060
228 24298166054
229 25926056098
230 27659916574
231 29506024039
232 31471852734
233 33564496413
234 35792350053
235 38163414458
236 40687114018
237 43372481981
238 46230083496
239 49270109855
240 52504417594
241 55944483985
242 59603609560
243 63494730912
244 67632749239
245 72032235389
246 76709898274
247 81682125999
248 86967646876
249 92584902371
250 98554862652
251 104898267854
252 111638611947
253 118799191262
254 126406317927
255 134486170031
256 143068188739
257 152181773271
258 161859881215
259 172135495345
260 183045495922
261 194626894113
262 206920928101
263 219969109608
264 233817562398
265 248512803442
266 264106404340
267 280650498081
268 298202707721
269 316821432268
270 336571068960
271 357516985962
272 379731126933
273 403286663454
274 428263921944
275 454744774681
276 482818915768
277 512577889185
278 544121819163
279 577553062291
280 612983324712
281 650527006058
282 690308738597
283 732456306252
284 777108719932
285 824408702216
286 874511227416
287 927575644317
288 983774718887
289 1043286265433
290 1106302828863
291 1173022808040
292 1243660695210
293 1318437777631
294 1397592981156
295 1481373002796
296 1570043908725
297 1663880683535
298 1763179498282
299 1868246766643
300 1979412136230
301 2097016889244
302 2221427833317
303 2353025027307
304 2492216473320
305 2639425275614
306 2795105200634
307 2959727082836
308 3133795449386
309 3317834153948
310 3512403968168
311 3718087558519
312 3935508117419
313 4165313481755
314 4408196031931
315 4664875928815
316 4936122168662
317 5222735073431
318 5525568595927
319 5845511830911
320 6183512828258
321 6540559104271
322 6917702850216
323 7316040591320
324 7736739893397
325 8181017921208
326 8650169942910
327 9145546760454
328 9668584888487
329 10220783027471
330 10803734050390
331 11419100235643
332 12068647398091
333 12754218862132
334 13477771614071
335 14241349206022
336 15047120079018
337 15897349093356
338 16794438418777
339 17740897663733
340 18739387203043
341 19792687129540
342 20903743207408
343 22075634307007
344 23311621427891
345 24615113604432
346 25989719877269
347 27439213917462
348 28967589165232
349 30579021808902
350 32277929617002
351 34068933256506
352 35956918693726
353 37946997149015
354 40044571337507
355 42255293662700
356 44585136893160
357 47040350600314
358 49627536170068
359 52353601816582
360 55225842251574
361 58251891855624
362 61439809708676
363 64798030934652
364 68335456997796
365 72061405624813
366 75985706769265
367 80118650658576
368 84471090235395
369 89054387378511
370 93880521774384
371 98962035773863
372 104312150171759
373 109944707241579
374 115874294378311
375 122116185391576
376 128686471996347
377 135602003926549
378 142880528876316
379 150540630950072
380 158601880166878
381 167084769391497
382 176010873465778
383 185402785282767
384 195284285266371
385 205680276126361
386 216616964010047
387 228121792144170
388 240223633802883
389 252952725645006
390 266340873412174
391 280421384504743
392 295229287960624
393 310801266595244
394 327175891542364
395 344393554932218
396 362496720103147
397 381529854425545
398 401539697049962
399 422575192320416
400 444687775499159
401 467931307976288
402 492362382368931
403 518040259205418
404 545027193602903
405 573388374080721
406 603192271498655
407 634510581468052
408 667418597273382
409 701995155705956
410 738323036643974
411 776488913191558
412 816583778880299
413 858702903959198
414 902946292384768
415 949418644275431
416 998229845889797
417 1049494939479192
418 1103334647638213
419 1159875352827205
420 1219249658791124
421 1281596380070116
422 1347061144388809
423 1415796393810171
424 1487962029967136
425 1563725429738856
426 1643262136728177
427 1726755892159988
428 1814399377330194
429 1906394261974199
430 2002952000269266
431 2104293900261128
432 2210651977667403
433 2322269047646956
434 2439399642201033
435 2562310127273103
436 2691279687175527
437 2826600471576201
438 2968578652330912
439 3117534602364020
440 3273804031998040
441 3437738203723924
442 3609705152620935
443 3790089942754066
444 3979295978422932
445 4177745305245797
446 4385880020998252
447 4604162626634731
448 4833077542749196
449 5073131517831855
450 5324855258902354
451 5588803901377497
452 5865558764664208
453 6155727890589944
454 6459947931900785
455 6778884768498858
456 7113235539598372
457 7463729343963246
458 7831129429135838
459 8216233984737563
460 8619878499116658
461 9042936657497822
462 9486322879681396
463 9950993331549420
464 10437948660434796
465 10948235131875473
466 11482947576141540
467 12043230665195857
468 12630282087580641
469 13245353977181996
470 13889756337237612
471 14564858636333357
472 15272093498959215
473 16012958487833531
474 16789020082808116
475 17601915665074029
476 18453357810276740
477 19345136494674753
478 20279123725027908
479 21257275990971123
480 22281639259229648
481 23354351692958248
482 24477649042679878
483 25653867658526041
484 26885450306889525
485 28174949506536470
486 29525033805897703
487 30938491470418288
488 32418237261016129
489 33967316506197999
490 35588912419007002
491 37286350593281234
492 39063106903239234
493 40922812459880653
494 42869262144084815
495 44906420066305867
496 47038428780957849
497 49269615299593156
498 51604501042525754
499 54047808452435659
500 56604471747056647
501 59279644188728560
502 62078709699341600
503 65007290849648515
504 68071261407189486
505 71276755106480426
506 74630179210173820
507 78138224131288569
508 81807878085695745
509 85646437647600312
510 89661523582924725
511 93861092417104246
512 98253453550195318
513 102847281928194476
514 107651636539505999
515 112675974292949919
516 117930170008787779
517 123424531605522232
518 129169821712389733
519 135177274281453158
520 141458617948354590
521 148026094200797610
522 154892482630756118
523 162071120790629454
524 169575931496475611
525 177421444520623672
526 185622826107209850
527 194195902667543106
528 203157192688818624
529 212523932600731797
530 222314111278275130
531 232546498269083288
532 243240681094997225
533 254417096051117772
534 266097068534665055
535 278302846631311817
536 291057644724033735
537 304385680107899706
538 318312220138589859
539 332863622142840881
540 348067384395034676
541 363952189598645592
542 380547960008953348
543 397885904791822232
544 415998579621321955
545 434919938254221641
546 454685396966460735
547 475331890694122739
548 496897942708759728
549 519423725713604231
550 542951137173859863
551 567523865796014550
552 593187472971843810
553 619989465087077810
554 647979381582270330
555 677208873583351648
556 707731799105108687
557 739604308544416595
558 772884947604483580
559 807634750217206212
560 843917349820640549
561 881799080333918700
562 921349096451816738
563 962639483354886411
564 1005745386748937672
565 1050745132028566252
566 1097720364856466121
567 1146756180568278297
568 1197941276128870096
569 1251368090639695217
570 1307132969588010377
571 1365336317365563929
572 1426082774809087094
573 1489481384725281703
574 1555645783777448255
575 1624694382101962618
576 1696750570692591983
577 1771942916257218294
578 1850405385353364242
579 1932277555739801691
580 2017704858590947494
581 2106838807709833693
582 2199837261268428114
583 2296864670331722531
584 2398092361696642197
585 2503698807308015090
586 2613869929865806296
587 2728799394851763808
588 2848688940721673886
589 2973748695370268776
590 3104197532880867318
591 3240263416417660147
592 3382183783630384182
593 3530205918134384216
594 3684587365849744801
595 3845596337369891570
596 4013512157706833181
597 4188625702049096341
598 4371239881546365962
599 4561670115169339072
600 4760244854391293663
601 4967306094043261200
602 5183209938988356849
603 5408327157112805555
604 5643043791295310497
605 5887761757937343824
606 6142899507807493021
607 6408892673745222534
608 6686194784254854160
609 6975277964323253333
610 7276633705901629738
611 7590773626103040987
612 7918230299053166081
613 8259558076027864738
614 8615333983519517972
615 8986158610253652025
616 9372657076651507143
617 9775479994068547771
618 10195304511258791249
619 10632835351550929322
620 11088805942372185734
621 11563979536547276937
622 12059150431362662530
623 12575145180673731216
624 13112823910515560410
625 13673081629175732778
626 14256849646918455610
627 14865096991761303429
628 15498831941412791645
629 16159103553111744763
630 16847003316529048216
631 17563666806622960844
632 18310275466949734208
633 19088058395208102842
634 19898294267074903527
635 20742313264880336218
636 21621499152889384123
637 22537291360297719769
638 23491187219739806607
639 24484744216686121502
640 25519582403801142421
641 26597386829775103945
642 27719910143151362479
643 28888975214564296419
644 30106477944719814963
645 31374390095114395908
646 32694762315908346798
647 34069727201380132347
648 35501502554664055643
649 36992394685369647335
650 38544801929473521066
651 40161218207898553484
652 41844236821169146698
653 43596554289205598298
654 45420974441876600269
655 47320412561732982334
656 49297899793221610385
657 51356587611772049057
658 53499752576083854106
659 55730801148786761301
660 58053274818097928463
661 60470855297109707933
662 62987370043130681418
663 65606797864743789006
664 68333274869197918337
665 71171100508615447144
666 74124743988131461405
667 77198850784913202274
668 80398249552237486095
669 83727959147567443869
670 87193196070314486005
671 90799382037982187581
672 94552151998237652175
673 98457362294974064791
674 102521099298398687856
675 106749688206056594267
676 111149702337818197491
677 115727972620324028980
678 120491597597310892591
679 125447953649467302308
680 130604705774344065925
681 135969818597552165506
682 141551567980446477240
683 147358552882818413376
684 153399707860930722621
685 159684315846238316570
686 166222021601052974173
687 173022845482691478220
688 180097197928936953562
689 187455894282224952416
690 195110170382485210973
691 203071698531405749285
692 211352604276038619338
693 219965483599186822123
694 228923420983212422983
695 238240007919020727415
696 247929362346189034852
697 258006148579745836232
698 268485598229892674659
699 279383531653180211521
700 290716380462585988700
701 302501210617619387599
702 314755746643753168111
703 327498396484304262161
704 340748277557034378741
705 354525243499780558593
706 368849912201299663333
707 383743694582395406708
708 399228824748226105316
709 415328390956950356642
710 432066368051581347950
711 449467650779415318461
712 467558088672948851015
713 486364521895393503003
714 505914818752664904070
715 526237914252970933602
716 547363850445256423397
717 569323817894693920435
718 592150199057075104678
719 615876612886852877557
720 640537961472342962577
721 666170478008611823681
722 692811776934811583269
723 720500905521238420739
724 749278397767512776373
725 779186329871367354747
726 810268378165293038052
727 842569878753895151542
728 876137889786866665962
729 911021255572695004495
730 947270673507243321111
731 984938762994009764287
732 1024080137370838923979
733 1064751477990676375796
734 1107011611513812221643
735 1150921589528812115587
736 1196544771604054032923
737 1243946910856068875140
738 1293196243182685777986
739 1344363579215223205485
740 1397522400186118395892
741 1452748956733025297686
742 1510122371886220483149
743 1569724747226499901701
744 1631641273512710945405
745 1695960344731249432428
746 1762773676921586596843
747 1832176430693975581850
748 1904267338850674970942
749 1979148837990004949260
750 2056927205563989540358
751 2137712701231014412293
752 2221619714036641212715
753 2308766914224731385179
754 2399277411277099347673
755 2493278916943908893676
756 2590903914930589635815
757 2692289835962464397821
758 2797579239963798929194
759 2906920004029994421641
760 3020465518003657547683
761 3138374886290145079540
762 3260813137800206300793
763 3387951442611092530583
764 3519967337314494670270
765 3657044957596964859301
766 3799375280105466237256
767 3947156372097368328008
768 4100593651015135485032
769 4259900152437586743655
770 4425296808639969002396
771 4597012736165775283944
772 4775285534738625348489
773 4960361595867627489948
774 5152496423574462351618
775 5351954965545022289230
776 5559011957238792115498
777 5773952277206723137247
778 5997071316260431296412
779 6228675358690914278938
780 6469081978293734388118
781 6718620447345300608365
782 6977632161407062125315
783 7246471078047233124336
784 7525504172482152897495
785 7815111908171554607677
786 8115688725500334056638
787 8427643546524852980488
788 8751400299053455431266
789 9087398457981638478989
790 9436093607294914189004
791 9797958020602074446742
792 10173481263761305692571
793 10563170817403420721424
794 10967552723071650112799
795 11387172250722618986452
796 11822594591472210978704
797 12274405573271445018758
798 12743212403567378805296
799 13229644436574200200772
800 13734353969389573715910
801 14258017064520484883343
802 14801334403242126326406
803 15365032167293658548913
804 15949862953531101729850
805 16556606718980672923631
806 17186071761119623369223
807 17839095730766759919710
808 18516546682626293521558
809 19219324160807068570316
810 19948360324587029889549
811 20704621111685215155315
812 21489107444549010767306
813 22302856476859059443066
814 23146942886008829287103
815 24022480208702968618985
816 24930622225691998031511
817 25872564392730199684028
818 26849545324048313148173
819 27862848325371135862717
820 28913802983058977806982
821 30003786806348766814479
822 31134226929574301946113
823 32306601871288972096795
824 33522443357486679353928
825 34783338205793154962639
826 36090930278155154859252
827 37446922498852101683856
828 38853078945704912670626
829 40311227011261851096797
830 41823259642201644795790
831 43391137653691423777323
832 45016892127323362397735
833 46702626889330137301503
834 48450521078104946102360
835 50262831797693009599691
836 52141896866703432937010
837 54090137659279019927982
838 56110062048017288037619
839 58204267445457470639971
840 60375443954492566657207
841 62626377624304401828709
842 64959953822671401832341
843 67379160721235875188324
844 69887092905096067992079
845 72486955103307254126527
846 75182066052197938567811
847 77975862488091065092311
848 80871903281906158409993
849 83873873712245856482131
850 86985589890041889466638
851 90211003331388781117096
852 93554205692269245577640
853 97019433661835273745203
854 100611074028611805770670
855 104333668916333497907116
856 108191921204478845063143
857 112190700130273208573552
858 116335047087957545042996
859 120630181622169728155049
860 125081507632007696567818
861 129694619782711040109031
862 134475310142343260236837
863 139429575040519605448560
864 144563622167417294382690
865 149883877910239854520474
866 155396994946273845635173
867 161109860089855350477702
868 167029602413333806296496
869 173163601639519780782687
870 179519496826702754326757
871 186105195343918503311677
872 192928882158605802929720
873 199999029434549387816196
874 207324406463359038375325
875 214914089927628784483045
876 222777474520194493594263
877 230924283917911124010385
878 239364582135601308037595
879 248108785258904999507351
880 257167673582982034043984
881 266552404156143052702281
882 276274523756729857960244
883 286345982302704544123767
884 296779146723714381242034
885 307586815295515252114813
886 318782232468045552574282
887 330379104187503316714753
888 342391613745325307646077
889 354834438154938724943782
890 367722765090881679621846
891 381072310391730844441613
892 394899336163223442249404
893 409220669483637551935185
894 424053721749706123473852
895 439416508665814105457881
896 455327670916749420194007
897 471806495527505113595441
898 488872937952509713900148
899 506547644898602652505549
900 524851977926353573833482
901 543808037834936341747840
902 563438689877505147657411
903 583767589813255406181662
904 604819210845597068043335
905 626618871453683326611589
906 649192764169339847534832
907 672567985307789973698183
908 696772565706988756723526
909 721835502485210494130591
910 747786791874626642291427
911 774657463141876848943488
912 802479613656457268753615
913 831286445119400779857308
914 861112301016338684450709
915 891992705309010043984577
916 923964402432759351908695
917 957065398615813887012724
918 991335004591526848702538
919 1026813879721242876818764
920 1063544077602828851136612
921 1101569093184539347132233
922 1140933911463337189441183
923 1181685057789514997225375
924 1223870649861046999897609
925 1267540451431865478441752
926 1312745927822050979812874
927 1359540303256660425511019
928 1407978620126004708053773
929 1458117800196829859164666
930 1510016707872311277053535
931 1563736215533255603673308
932 1619339271063815939880481
933 1676890967597277767583228
934 1736458615590929921049669
935 1798111817268985033271940
936 1861922543548600616988510
937 1927965213491629539949527
938 1996316776403542530257428
939 2067056796626087636894077
940 2140267541151892736714148
941 2216034070111809740996574
942 2294444330270361114431368
943 2375589251584634828075234
944 2459562846969564760189307
945 2546462315329821898853794
946 2636388148009272738750841
947 2729444238723471323200405
948 2825737997134626864444224
949 2925380466140136422865554
950 3028486443043112150954799
951 3135174604682019716222613
952 3245567636697372692788826
953 3359792367019066099171318
954 3477979903762364924769248
955 3600265777623061546407314
956 3726790088970486576979029
957 3857697659736309155356603
958 3993138190309108704844633
959 4133266421540609135267098
960 4278242302085517734800800
961 4428231161189377953849043
962 4583403887159050212691382
963 4743937111639344691599713
964 4910013399943841516699785
965 5081821447573182407074635
966 5259556283183080830564890
967 5443419478145777384088798
968 5633619362982246755412244
969 5830371250820048765245283
970 6033897668170082416357489
971 6244428593189081854306239
972 6462201701738008393147535
973 6687462621415949959389518
974 6920465193897587186286119
975 7161471745767485347725909
976 7410753368198241333779908
977 7668590205680335917280813
978 7935271754170814821508935
979 8211097168884238376718133
980 8496375582114320857440024
981 8791426431326347215595390
982 9096579797931355458835403
983 9412176756999958779094326
984 9738569738350703925550006
985 10076122899289831905100661
986 10425212509462679618510585
987 10786227348113858613095038
988 11159569114243305370752853
989 11545652849976982193710263
990 11944907377667778491730445
991 12357775751068488503298142
992 12784715721122579454886228
993 13226200216739264972356868
994 13682717841130566693588427
995 14154773384103171431991855
996 14642888350916643618262918
997 15147601508128845022949532
998 15669469447076034786706197
999 16209067165438404378553562
1000 16766988667576585555391439