0 1
1 1
2 1
3 1
4 2
5 3
6 4
7 5
8 7
9 10
10 12
11 15
12 20
13 26
14 32
15 39
16 50
17 63
18 76
19 92
20 114
21 140
22 168
23 201
24 244
25 295
26 350
27 415
28 496
29 591
30 696
31 818
32 967
33 1140
34 1332
35 1554
36 1820
37 2126
38 2468
39 2861
40 3324
41 3855
42 4448
43 5126
44 5916
45 6816
46 7824
47 8970
48 10292
49 11793
50 13471
51 15372
52 17548
53 20007
54 22756
55 25857
56 29384
57 33356
58 37788
59 42771
60 48408
61 54734
62 61784
63 69683
64 78578
65 88530
66 99600
67 111968
68 125838
69 141312
70 158496
71 177642
72 199036
73 222842
74 249230
75 278557
76 311224
77 347484
78 387608
79 432095
80 481506
81 536230
82 596676
83 663549
84 737632
85 819504
86 909788
87 1009464
88 1119624
89 1241127
90 1374888
91 1522282
92 1684824
93 1863764
94 2060448
95 2276781
96 2514868
97 2776514
98 3063657
99 3378948
100 3725294
101 4105275
102 4521672
103 4978142
104 5478698
105 6027000
106 6626988
107 7283709
108 8002676
109 8789042
110 9648360
111 10587557
112 11614192
113 12735471
114 13959152
115 15294726
116 16752522
117 18342548
118 20075592
119 21964599
120 24023640
121 26266549
122 28708214
123 31366254
124 34259776
125 37407786
126 40830752
127 44552549
128 48599047
129 52996244
130 57772104
131 62958909
132 68591568
133 74705464
134 81338660
135 88534632
136 96340356
137 104803791
138 113976480
139 123916832
140 134687856
141 146354280
142 158985648
143 172660152
144 187462076
145 203478444
146 220802690
147 239539215
148 259800412
149 281702847
150 305371612
151 330945665
152 358574468
153 388413612
154 420629952
155 455407944
156 492945784
157 533450438
158 577143752
159 624269862
160 675090876
161 729881232
162 788934892
163 852574142
164 921144678
165 995009256
166 1074556248
167 1160209929
168 1252425056
169 1351679727
170 1458485460
171 1573399406
172 1697018248
173 1829970267
174 1972927320
175 2126619134
176 2291826684
177 2469373356
178 2660139108
179 2865077415
180 3085207944
181 3321606890
182 3575423776
183 3847901360
184 4140367824
185 4454226186
186 4790974208
187 5152227966
188 5539713456
189 5955255212
190 6400799952
191 6878444343
192 7390426292
193 7939112786
194 8527027946
195 9156885936
196 9831581970
197 10554179571
198 11327943984
199 12156381011
200 13043228161
201 13992441524
202 15008235468
203 16095128772
204 17257936104
205 18501754896
206 19832012720
207 21254521845
208 22775471788
209 24401416620
210 26139331392
211 27996677072
212 29981394594
213 32101893360
214 34367118696
215 36786628860
216 39370591828
217 42129775768
218 45075629630
219 48220374962
220 51577006320
221 55159285086
222 58981835960
223 63060256220
224 67411121672
225 72051985222
226 77001492468
227 82279512195
228 87907149616
229 93906751922
230 100302046992
231 107118299127
232 114382332492
233 122122546191
234 130369080776
235 139154004666
236 148511350860
237 158477145044
238 169089605856
239 180389367912
240 192419536344
241 205225732202
242 218856333325
243 233362741915
244 248799461932
245 265224167379
246 282697992552
247 301285852873
248 321056552288
249 342082881276
250 364441966584
251 388215656919
252 413490668320
253 440358720768
254 468916960232
255 499268422107
256 531522225650
257 565793759847
258 602205192848
259 640886029948
260 681973369644
261 725612152632
262 771955777272
263 821166771327
264 873417126480
265 928888627068
266 987773593888
267 1050275694024
268 1116610373464
269 1187005286763
270 1261701196536
271 1340952949784
272 1425030034014
273 1514217133480
274 1608815217156
275 1709142717021
276 1815536237856
277 1928351272154
278 2047963516748
279 2174770294811
280 2309191457568
281 2451670296999
282 2602675139136
283 2762701061606
284 2932271032968
285 3111937071576
286 3302282174448
287 3503922391446
288 3717508259644
289 3943726267267
290 4183301188476
291 4436998589804
292 4705626628084
293 4990037892087
294 5291132229156
295 5609859773301
296 5947223192258
297 6304279994772
298 6682145952108
299 7081998757710
300 7505080825676
301 7952702171848
302 8426244555248
303 8927165899995
304 9457003771768
305 10017378963402
306 10610000506584
307 11236671015464
308 11899290992928
309 12599863280612
310 13340499122688
311 14123424621513
312 14950986059960
313 15825655409090
314 16750037662550
315 17726878635342
316 18759071526112
317 19849663717539
318 21001865645304
319 22219060216167
320 23504810883234
321 24862870023084
322 26297189655936
323 27811932817482
324 29411483475260
325 31100456826614
326 32883712252148
327 34766367040766
328 36753808545876
329 38851706819208
330 41066030255328
331 43403062152668
332 45869415587940
333 48472048887500
334 51218284514160
335 54115829040660
336 57172791321952
337 60397701407594
338 63799533331167
339 67387729190934
340 71172221314680
341 75163455341220
342 79372417705424
343 83810664655843
344 88490349251036
345 93424249484352
346 98625801414012
347 104109134114847
348 109889102510904
349 115981321595486
350 122402206344320
351 129169013792237
352 136299882911496
353 143813876188407
354 151731027680592
355 160072393646322
356 168860100915990
357 178117397339256
358 187868709615384
359 198139704178986
360 208957345802184
361 220349958725181
362 232347296204822
363 244980613695955
364 258282739761056
365 272288150055402
366 287033050919000
367 302555467284062
368 318895328380056
369 336094557169116
370 354197170754088
371 373249385916642
372 393299722586752
373 414399111831638
374 436601016389016
375 459961557294030
376 484539638663328
377 510397077940914
378 537598750498400
379 566212741476248
380 596310496113144
381 627966976669148
382 661260835789440
383 696274598467074
384 733094842966708
385 771812389691856
386 812522508900290
387 855325138632278
388 900325102238020
389 947632335464823
390 997362135172176
391 1049635420169832
392 1104578992507071
393 1162325810246772
394 1223015285080332
395 1286793594332574
396 1353813994521840
397 1424237148703118
398 1498231482368816
399 1575973556420824
400 1657648443119678
401 1743450118550391
402 1833581887947824
403 1928256831272458
404 2027698253560146
405 2132140155044808
406 2241827739124896
407 2357017944337263
408 2477979983368872
409 2604995905708034
410 2738361203916516
411 2878385448358374
412 3025392931780144
413 3179723342127828
414 3341732485686240
415 3511793043929628
416 3690295343714282
417 3877648161157916
418 4074279583619424
419 4280637911604447
420 4497192578300736
421 4724435109268346
422 4962880149261812
423 5213066536312701
424 5475558398701212
425 5750946299739537
426 6039848460180960
427 6342912036552472
428 6660814428781308
429 6994264644703704
430 7344004754395824
431 7710811410644550
432 8095497406499732
433 8498913300432794
434 8921949145499488
435 9365536296695574
436 9830649264813004
437 10318307650584288
438 10829578199327720
439 11365576947985793
440 11927471430039624
441 12516482975685834
442 13133889151707960
443 13781026310476731
444 14459292210507160
445 15170148749958984
446 15915124862171240
447 16695819540023124
448 17513904948285424
449 18371129669763975
450 19269322139481940
451 20210394230877258
452 21196344949662318
453 22229264286058460
454 23311337285347512
455 24444848297705259
456 25632185359220912
457 26875844760240482
458 28178435867285798
459 29542686156319248
460 30971446405243488
461 32467696107812799
462 34034549182181760
463 35675259928467101
464 37393229178956730
465 39192010709823240
466 41075317995300036
467 43047031255115445
468 45111204734282152
469 47272074291537448
470 49534065385949088
471 51901801408706498
472 54380112294411048
473 56974043496404532
474 59688865425143360
475 62530083292688456
476 65503447292558736
477 68614963208670744
478 71870903562891936
479 75277819240148364
480 78842551515032280
481 82572244583825644
482 86474358723147386
483 90556684009893924
484 94827354520847066
485 99294863127232722
486 103968077018399428
487 108856253884873403
488 113969058673389722
489 119316581041817612
490 124909353662556780
491 130758371300164197
492 136875110569805832
493 143271550518559416
494 149960194194151960
495 156954091122325233
496 164266860593278912
497 171912715914920544
498 179906489815325424
499 188263660911041366
500 197000381135391924
501 206133504302063208
502 215680616006199624
503 225660064775138307
504 236090994356604704
505 246993377339229372
506 258388050329708256
507 270296750594386191
508 282742154046739840
509 295747914797528511
510 309338706516554736
511 323540265509701687
512 338379435386512135
513 353884213559550764
514 370083799851971412
515 387008647113226992
516 404690513712170320
517 423162518176211760
518 442459196283624256
519 462616560505712931
520 483672161662480104
521 505665153091139463
522 528636357668848776
523 552628337583878984
524 577685466713741460
525 603854005944063572
526 631182181807901616
527 659720268338114781
528 689520671987005776
529 720638019985614361
530 753129252565248780
531 787053718933488786
532 822473276855518784
533 859452396256553406
534 898058267315966376
535 938360912946444126
536 980433305507034164
537 1024351488214543332
538 1070194701777745212
539 1118045516150689065
540 1167989967253629528
541 1220117699180832626
542 1274522112480098648
543 1331300518405553711
544 1390554298994035140
545 1452389073545946138
546 1516914872163225664
547 1584246316254079766
548 1654502805859192518
549 1727808714449730860
550 1804293591925943832
551 1884092375737510149
552 1967345609988023328
553 2054199673252136536
554 2144807015919808118
555 2239326407004470196
556 2337923190289088968
557 2440769550626883519
558 2548044791307484160
559 2659935622445981545
560 2776636460285255280
561 2898349738327886472
562 3025286231316927972
563 3157665392049598335
564 3295715700936438336
565 3439675029334691160
566 3589791017797409660
567 3746321469256052093
568 3909534757078249584
569 4079710249156526271
570 4257138749307316512
571 4442122956040208234
572 4634977938676469160
573 4836031632116321856
574 5045625351689817696
575 5264114328203380005
576 5491868263208376380
577 5729271905953683146
578 5976725653632696571
579 6234646175100839006
580 6503467058148864744
581 6783639481977951252
582 7075632916685394056
583 7379935850014824042
584 7697056541529101846
585 8027523806060241456
586 8371887828469457484
587 8730721010065504641
588 9104618846928579252
589 9494200842230337352
590 9900111454836777864
591 10323021084655572432
592 10763627095083499516
593 11222654874912280503
594 11700858942266671248
595 12199024091172292182
596 12717966581239729794
597 13258535373126992180
598 13821613412679251808
599 14408118964505482482
600 15019006995635889004
601 15655270612266893642
602 16317942552860930656
603 17008096738553447534
604 17726849881699198672
605 18475363155955998207
606 19254843931590635064
607 20066547577187790728
608 20911779328818384836
609 21791896230509973624
610 22708309150177315080
611 23662484872463947134
612 24655948269817496184
613 25690284556146414758
614 26767141627753289684
615 27888232493313782325
616 29055337794539230656
617 30270308422444557735
618 31535068234526140640
619 32851616874992948750
620 34222032700061070144
621 35648475813885889920
622 37133191221128517072
623 38678512098738893967
624 40286863189403899960
625 41960764322976780301
626 43702834072670379050
627 45515793549110936682
628 47402470335215401324
629 49365802569052791090
630 51408843182364838848
631 53534764298443930616
632 55746861792934652432
633 58048560025679890052
634 60443416752301251420
635 62935128219913612512
636 65527534451245917528
637 68224624726382217114
638 71030543271965861832
639 73949595163084445346
640 76986252442932063420
641 80145160470706864767
642 83431144508897889936
643 86849216556130525814
644 90404582431628318016
645 94102649123165362536
646 97949032411154141232
647 101949564776144150421
648 106110303596908242076
649 110437539652603216296
650 114937805943345241154
651 119617886837759318014
652 124484827555980753304
653 129545944003431187923
654 134808832971638668952
655 140281382716149438549
656 145971783921520189302
657 151888541070803983940
658 158040484237993919232
659 164436781315196110065
660 171086950686272648544
661 178000874366748809534
662 185188811630945620460
663 192661413140103797331
664 200429735585269198200
665 208505256867445744488
666 216899891838818502056
667 225626008621118215122
668 234696445517245689960
669 244124528541750591980
670 253924089597201101712
671 264109485315177786585
672 274695616580724708704
673 285697948769370028346
674 297132532727432956730
675 309016026517421927599
676 321365717950491871422
677 334199547939079562091
678 347536134704622683208
679 361394798865708372802
680 375795589432236357348
681 390759310743278970876
682 406307550388311335424
683 422462708141236421301
684 439248025936959995920
685 456687618933395213280
686 474806507703996485056
687 493630651594942467596
688 513186983281526667208
689 533503444572554514930
690 554609023514022737088
691 576533792831601540362
692 599308949752006800666
693 622966857258802062000
694 647541086840935470984
695 673066462779740029596
696 699579108020843464056
697 727116491694203506692
698 755717478348573829526
699 785422378953260219340
700 816273003720921980560
701 848312716823374828311
702 881586493075804860248
703 916140976650439778479
704 952024541881827207036
705 989287356245627577744
706 1027981445596691709588
707 1068160761736861901484
708 1109881252384282188816
709 1153200933637454212898
710 1198179965031597779760
711 1244880727268524914308
712 1293367902702866851572
713 1343708558690786037456
714 1395972233912145546432
715 1450231027759687291344
716 1506559692890730936132
717 1565035731062203188288
718 1625739492375229743216
719 1688754278036978203662
720 1754166446749784226120
721 1822065524865073797016
722 1892544320445672824085
723 1965699041360376343658
724 2041629417537437593660
725 2120438827533496139853
726 2202234429581280464308
727 2287127297258475142586
728 2375232559923444853168
729 2466669548095957672786
730 2561561943968697750456
731 2660037937213135623840
732 2762230386247220200888
733 2868276985167632277338
734 2978320436557923314408
735 3092508630360316629954
736 3210994829003529212112
737 3333937859017329677556
738 3461502309374187017400
739 3593858736773448170570
740 3731183878088852697468
741 3873660870241913343784
742 4021479477774519232032
743 4174836328367790449448
744 4333935156560491589504
745 4498987055965703602164
746 4670210740296621688190
747 4847832813484571426844
748 5032088049179658052368
749 5223219679973866355892
750 5421479696700107773488
751 5627129158131458530463
752 5840438511413354497968
753 6061687923615293653668
754 6291167624803979863464
755 6529178263009090549686
756 6776031271462747557472
757 7032049248552348549890
758 7297566350943719881964
759 7572928700299291170399
760 7858494804027464634768
761 8154635990563173107127
762 8461736859699090843776
763 8780195748453192356734
764 9110425212971631401664
765 9452852527035472597296
766 9807920197761721582848
767 10176086499053838899811
768 10557826023372264036020
769 10953630252471321748610
770 11364008147773552469952
771 11789486761015790599386
772 12230611865819014836868
773 12687948610916728832703
774 13162082195804408662448
775 13653618569534434322297
776 14163185153401317923246
777 14691431588352327468712
778 15239030507989890495756
779 15806678337992722694172
780 16395096122806097685648
781 17005030380550246423968
782 17637253987131115850736
783 18292567090497068925231
784 18971798056012087768770
785 19675804444023708896370
786 20405474020743623790384
787 21161725803517168874168
788 21945511141588907234226
789 22757814833589161952648
790 23599656283011099430848
791 24472090692905378107884
792 25376210301054911875440
793 26313145657020933448396
794 27284066942501961122726
795 28290185336404051442694
796 29332754426061439983472
797 30413071666187381519427
798 31532479887191825446528
799 32692368854458995040557
800 33894176880224559898369
801 35139392489846082850884
802 36429556144324474450740
803 37766262020890630672236
804 39151159853524760172400
805 40585956835444523646336
806 42072419585670311139184
807 43612376181732866254446
808 45207718260649424100924
809 46860403190479254385407
810 48572456314850899300200
811 50345973272811236380580
812 52183122396416118228912
813 54086147188684821023996
814 56057368884632301712944
815 58099189098052677649317
816 60214092556806802377000
817 62404649929588871122408
818 64673520747250452976754
819 67023456421722063700900
820 69457303365663017876184
821 71978006216213965145283
822 74588611166343166591464
823 77292269407242447679043
824 80092240685332055278760
825 82991896977701165380332
826 85994726289942310643904
827 89104336580307050541027
828 92324459814227859645024
829 95658956153545079103986
830 99111818284926065008920
831 102687175891938075072683
832 106389300275370366636844
833 110222609126723970949071
834 114191671459954799647760
835 118301212706536877369508
836 122556119979064868444688
837 126961447508970263088308
838 131522422264114086127416
839 136244449752008458520886
840 141133120014592603136832
841 146194213820879714528335
842 151433709064003625913446
843 156857787369193855970652
844 162472840919404524066616
845 168285479505752893752333
846 174302537810162882304192
847 180531082927620847497278
848 186978422135674627324434
849 193652110919280761134028
850 200559961259374896858924
851 207710050193567157027624
852 215110728657618169711968
853 222770630616873825009182
854 230698682497141255062592
855 238904112924532942103967
856 247396462784094022406856
857 256185595607603862078519
858 265281708301286128516704
859 274695342224226893975546
860 284437394628627164558664
861 294519130473651741275928
862 304952194625023069640352
863 315748624452598701398943
864 326920862838541575333652
865 338481771609393857885220
866 350444645405800941126962
867 362823226003751110198651
868 375631717101616371069440
869 388884799588054746306468
870 402597647306325499777488
871 416785943330721523136764
872 431465896771298879234954
873 446654260123939688174996
874 462368347183337954324928
875 478626051536690169698742
876 495445865656411266813832
877 512846900611143080807582
878 530848906414945979061344
879 549472293034802416020459
880 568738152077170983521904
881 588668279175376566037911
882 609285197100324595211436
883 630612179617318649233742
884 652673276112450644276436
885 675493337013191574912216
886 699098040028601921134536
887 723513917234933539312242
888 748768383033175303862744
889 774889763006377655766280
890 801907323705482266009476
891 829851303392806604754030
892 858752943773215642524352
893 888644522744433937281720
894 919559388198954790771320
895 951531992910508340753442
896 984597930539047857592328
897 1018793972789788249602816
898 1054158107762960617910868
899 1090729579531545649913070
900 1128548928985375601299460
901 1167658035981740439696792
902 1208100162843905720022648
903 1249919999249656270549705
904 1293163708553252696192196
905 1337878975586124006758418
906 1384115055983051529267488
907 1431922827081428965433174
908 1481354840442620787098484
909 1532465376046589589361656
910 1585310498212574588779200
911 1639948113299574050339283
912 1696438029242006882763184
913 1754842016978313354311112
914 1815223873832068463794562
915 1877649488906313021402156
916 1942186910553638347091164
917 2008906415987208467999820
918 2077880583099944316562056
919 2149184364560409522878309
920 2222895164256002786754384
921 2299092916157003161267364
922 2377860165677310318991932
923 2459282153609246129675082
924 2543446902712113158087040
925 2630445307037474034412130
926 2720371224076698008928248
927 2813321569818083330433365
928 2909396416803490207013388
929 3008699095278051987039879
930 3111336297529436515554816
931 3217418185515162643514760
932 3327058501879436804136870
933 3440374684465013906283912
934 3557487984428852696864088
935 3678523588072676263912470
936 3803610742502883603597800
937 3932882885238750770876642
938 4066477777891532056723168
939 4204537644039761146309268
940 4347209311429809328097472
941 4494644358635755951040343
942 4646999266316754083345624
943 4804435573213159589758875
944 4967120037026923037469996
945 5135224800337305860789304
946 5308927561707621640261536
947 5488411752142237036042935
948 5673866717057830731930304
949 5865487903939099836010084
950 6063477055854316847117564
951 6268042411010181697154253
952 6479398908530775459997920
953 6697768400652315250854423
954 6923379871531267849410408
955 7156469662867995424836948
956 7397281706554140656387568
957 7646067764559634588291368
958 7903087676281791447253440
959 8168609613584219996382213
960 8442910343760069201045720
961 8726275500662675877913065
962 9018999864254073732629668
963 9321387648827822429663106
964 9633752800170250199398948
965 9956419301933728557838710
966 10289721491503898793232128
967 10634004385649597853331496
968 10989624016252816268317435
969 11356947776426634113992056
970 11736354777338401730928024
971 12128236216063195196423529
972 12532995754802227573861844
973 12951049911812724942573304
974 13382828464406240006613344
975 13828774864381194336707360
976 14289346666266287119422028
977 14765015968764591883590759
978 15256269869799907727641520
979 15763610935576939152081330
980 16287557684079066479256834
981 16828645083442165481305700
982 17387425065656115761150568
983 17964467056056985110858606
984 18560358519086568604626120
985 19175705520812346591188748
986 19811133308715715530838980
987 20467286909269202548269444
988 21144831743838751708259408
989 21844454263465440355207008
990 22566862603097575990865568
991 23312787255858680034867137
992 24082981767954131124471584
993 24878223454839614802575564
994 25699314139293137341474944
995 26547080912048828939428356
996 27422376915670144727228976
997 28326082152362794422534230
998 29259104316448603118993396
999 30222379652240123166996308
1000 31216873838077571868019032