0 1
1 1
2 1
3 1
4 2
5 2
6 5
7 7
8 13
9 18
10 28
11 40
12 60
13 80
14 113
15 152
16 205
17 266
18 353
19 454
20 590
21 751
22 959
23 1210
24 1529
25 1905
26 2381
27 2953
28 3658
29 4501
30 5539
31 6772
32 8278
33 10065
34 12230
35 14801
36 17893
37 21544
38 25921
39 31089
40 37240
41 44478
42 53068
43 63150
44 75063
45 89018
46 105438
47 124632
48 147150
49 173390
50 204089
51 239802
52 281446
53 329784
54 386007
55 451121
56 526666
57 613990
58 715054
59 831652
60 966298
61 1121325
62 1299975
63 1505316
64 1741443
65 2012360
66 2323320
67 2679484
68 3087529
69 3554135
70 4087756
71 4696988
72 5392565
73 6185455
74 7089265
75 8118027
76 9288850
77 10619618
78 12131917
79 13848398
80 15796223
81 18004062
82 20505985
83 23338197
84 26543387
85 30167073
86 34262676
87 38887385
88 44107819
89 49995628
90 56633875
91 64112050
92 72533496
93 82009862
94 92669403
95 104651100
96 118113983
97 133230590
98 150197795
99 169229530
100 190568943
101 214480768
102 241265020
103 271248586
104 304801000
105 342325337
106 384275959
107 431149010
108 483502464
109 541945844
110 607163349
111 679902801
112 761001752
113 851376212
114 952050248
115 1064144029
116 1188907824
117 1327709648
118 1482073711
119 1653668231
120 1844349124
121 2056147594
122 2291320453
123 2552337780
124 2841940037
125 3163126885
126 3519222222
127 3913863814
128 4351078118
129 4835271373
130 5371314901
131 5964539000
132 6620830384
133 7346628996
134 8149040177
135 9035835556
136 10015581153
137 11097644482
138 12292341296
139 13610949355
140 15065877594
141 16670688656
142 18440292766
143 20390982201
144 22540653887
145 24908857422
146 27517052010
147 30388671387
148 33549418902
149 37027354601
150 40853234713
151 45060623971
152 49686287809
153 54770335705
154 60356672657
155 66493181469
156 73232243129
157 80630964128
158 88751778160
159 97662727911
160 107438158820
161 118159067762
162 129913903970
163 142798995251
164 156919474615
165 172389799571
166 189334821890
167 207890419411
168 228204732059
169 250438924402
170 274768616415
171 301384801328
172 330495498889
173 362326859167
174 397125074021
175 435157697096
176 476715856552
177 522115830445
178 571701604903
179 625846752366
180 684957390181
181 749474411000
182 819876907541
183 896684816740
184 980462879641
185 1071823773541
186 1171432691575
187 1280011041465
188 1398341744766
189 1527273598816
190 1667727403277
191 1820701099831
192 1987276855541
193 2168627104617
194 2366022740992
195 2580840212118
196 2814570986731
197 3068829877661
198 3345365982828
199 3646072431244
200 3972999028506
201 4328363657749
202 4714566885183
203 5134205287071
204 5590088316591
205 6085253858345
206 6622987707123
207 7206841705571
208 7840656225214
209 8528581301440
210 9275102574418
211 10085065884815
212 10963707204306
213 11916681235321
214 12950095924936
215 14070545698326
216 15285151247518
217 16601598106920
218 18028182515675
219 19573856160147
220 21248279008367
221 23061871172838
222 25025873759098
223 27152408924597
224 29454549940731
225 31946390695119
226 34643126321472
227 37561133581521
228 40718063626312
229 44132934883194
230 47826239744858
231 51820051837645
232 56138148669875
233 60806135437250
234 65851585969195
235 71304185513828
236 77195892662419
237 83561103924774
238 90436839667718
239 97862933702481
240 105882246721628
241 114540884551895
242 123888443076115
243 133978259343740
244 144867692495290
245 156618412526787
246 169296722390391
247 182973889852858
248 197726516680502
249 213636919819448
250 230793554363502
251 249291451167373
252 269232701251392
253 290726957914899
254 313891991305450
255 338854264247463
256 365749566869560
257 394723676654113
258 425933084408111
259 459545750447425
260 495741934759594
261 534715062907346
262 576672674945901
263 621837416508346
264 670448123058900
265 722760953689081
266 779050629560874
267 839611730365516
268 904760108315060
269 974834369943321
270 1050197489929812
271 1131238503937280
272 1218374349843006
273 1312051800814876
274 1412749565172106
275 1520980492849829
276 1637293969335821
277 1762278433055908
278 1896564103590222
279 2040825852573711
280 2195786311681148
281 2362219145336322
282 2540952590044308
283 2732873183546140
284 2938929793928159
285 3160137867147597
286 3397584011985368
287 3652430836069643
288 3925922161488010
289 4219388528585636
290 4534253126899425
291 4872038056470618
292 5234371069752204
293 5622992691949133
294 6039763882094042
295 6486674127077604
296 6965850144194345
297 7479565078509091
298 8030248384941540
299 8620496275463523
300 9253082936722098
301 9930972392401971
302 10657331232547307
303 11435542077820570
304 12269218019227929
305 13162217895056156
306 14118662665278455
307 15142952738855633
308 16239786535828101
309 17414180133145722
310 18671488299598789
311 20017426762575365
312 21458096037351310
313 23000006655485735
314 24650106150828887
315 26415807633564721
316 28305020340994387
317 30326181989841344
318 32488293351465033
319 34800954869439204
320 37274405776746449
321 39919565526998333
322 42748078035953036
323 45772358543576363
324 49005643635236208
325 52462044228826945
326 56156602112872589
327 60105349839664842
328 64325374609112846
329 68834885946072139
330 73653287861848626
331 78801255302664887
332 84300815636223390
333 90175434980547890
334 96450110192201023
335 103151466321733586
336 110307860425291031
337 117949491546112193
338 126108517833794575
339 134819180623299736
340 144117936527872046
341 154043597379574233
342 164637479165759245
343 175943559810420943
344 188008647052291167
345 200882556287681339
346 214618299743284474
347 229272286871215323
348 244904537455380578
349 261578907351142286
350 279363328483700312
351 298330063062756225
352 318555973788327226
353 340122810048575551
354 363117512048108127
355 387632532919027340
356 413766180933340477
357 441622981929356548
358 471314064268396886
359 502957566505998124
360 536679070310689224
361 572612058898035610
362 610898403751882150
363 651688879997205006
364 695143713458944083
365 741433159884079716
366 790738119649409349
367 843250788562526452
368 899175348396086373
369 958728697912336057
370 1022141228367343370
371 1089657644424397785
372 1161537834849960851
373 1238057794119123075
374 1319510599727471489
375 1406207446561482038
376 1498478743590579058
377 1596675274490754761
378 1701169427975811493
379 1812356499739470897
380 1930656072350463758
381 2056513475336631740
382 2190401332423763064
383 2332821198543890267
384 2484305294265416110
385 2645418340688761586
386 2816759503217940672
387 2998964447736450072
388 3192707518433530700
389 3398704041358158145
390 3617712763867602292
391 3850538434667427040
392 4098034535626592643
393 4361106170762281950
394 4640713124699621349
395 4937873096788189487
396 5253665124416972993
397 5589233202595402292
398 5945790114707872400
399 6324621482504292126
400 6727090051741039722
401 7154640222653940088
402 7608802843339877035
403 8091200276484463342
404 8603551759348652819
405 9147679068859115357
406 9725512513742019472
407 10339097267123944979
408 10990600063775924730
409 11682316277192315495
410 12416677403151188096
411 13196258966925433411
412 14023788883518845051
413 14902156290309946671
414 15834420884488185471
415 16823822787139233234
416 17873792969689873692
417 18987964267331662226
418 20170183018805931326
419 21424521360255633982
420 22755290216580022920
421 24167053021441361586
422 25664640213837712470
423 27253164546230419361
424 28938037257084795768
425 30724985147095048710
426 32620068617410229796
427 34629700713903573536
428 36760667241831524909
429 39020148000237257261
430 41415739207102355969
431 43955477170518114120
432 46647863284229265576
433 49501890409405148243
434 52527070729108238132
435 55733465144636284178
436 59131714309169616162
437 62733071376043076728
438 66549436566966294878
439 70593393646562133016
440 74878248419470883738
441 79418069346443399724
442 84227730407729497256
443 89322956321353643137
444 94720370257893469289
445 100437544171752845062
446 106493051905239116037
447 112906525199196100808
448 119698712782720203406
449 126891542690981415422
450 134508188001572921261
451 142573136155347401624
452 151112262071917311071
453 160152905244553712974
454 169723951046458038352
455 179855916453958264983
456 190581040442651928414
457 201933379285114685988
458 213948907032733066490
459 226665621435831342921
460 240123655613925189430
461 254365395758574197313
462 269435605212954991808
463 285381555241961983609
464 302253162872576633926
465 320103136152993287853
466 338987127249525429853
467 358963893768162873915
468 380095468763120595778
469 402447339861711472435
470 426088638015652410690
471 451092336355096097132
472 477535459708164112859
473 505499305314204626817
474 535069675351607259382
475 566337121865805596927
476 599397204782301850174
477 634350763653787025820
478 671304203896731804465
479 710369798236628235236
480 751666004194993122821
481 795317798414758229346
482 841457028742823646619
483 890222784951928085456
484 941761789114997695212
485 996228806608573408160
486 1053787078862455343659
487 1114608778936426481375
488 1178875491155735799772
489 1246778716001272916784
490 1318520401612270230340
491 1394313503224447814045
492 1474382572040363950237
493 1558964374994977803267
494 1648308547066172435852
495 1742678277747760978274
496 1842351033503159888542
497 1947619317987658061071
498 2058791472042884898625
499 2176192515439287458682
500 2300165032574323992083
501 2431070104309287324916
502 2569288288377098286319
503 2715220650772245310256
504 2869289850802400659080
505 3031941282464413129725
506 3203644275096202066993
507 3384893356244349841317
508 3576209579998154650643
509 3778141924035171534078
510 3991268758958164115267
511 4216199393504640095434
512 4453575699570940944328
513 4704073821002175838982
514 4968405970488126316688
515 5247322318923878790887
516 5541612982013113933042
517 5852110108921301657938
518 6179690078238084804896
519 6525275806549652785006
520 6889839175409542382537
521 7274403582551733374214
522 7680046623716094329420
523 8107902911527474121002
524 8559167038437716733005
525 9035096690829005912052
526 9537015921990240018378
527 10066318591787500103424
528 10624471981512075017567
529 11213020592521695108378
530 11833590138006300413206
531 12487891737367521800443
532 13177726323474524609095
533 13904989273245567331788
534 14671675272840783229249
535 15479883428970761065728
536 16331822638729701490570
537 17229817230617210717359
538 18176312890390861431792
539 19173882885687454480866
540 20225234604409151262973
541 21333216422211708567298
542 22500824915577356162192
543 23731212437346370135052
544 25027695072821279143115
545 26393760995005382964830
546 27833079238879849382361
547 29349508915133986371500
548 30947108885217475098534
549 32630147920163234057554
550 34403115367205050939810
551 36270732348871285125391
552 38237963520943177234191
553 40310029416409244583738
554 42492419404397720869214
555 44790905293907018005743
556 47211555614160398036945
557 49760750604354432753979
558 52445197947746313624009
559 55271949286085137712546
560 58248417552751868046596
561 61382395164161775315047
562 64682073111542943377000
563 68156060996536236168718
564 71813408056839596200113
565 75663625229609055440169
566 79716708303343130518129
567 83983162210640879998849
568 88474026517495817977769
569 93200902166643654184089
570 98175979536033971308896
571 103412067875563710988939
572 108922626189067392952529
573 114721795630860408654972
574 120824433490320564233604
575 127246148840551966558775
576 134003339931725153593943
577 141113233412529912742951
578 148593925468119890194007
579 156464424966082817444448
580 164744698707340387580626
581 173455718882380096091623
582 182619512839056823916260
583 192259215272078129522645
584 202399122950629095576541
585 213064752104884207156488
586 224282898599046831030979
587 236081701023305130942267
588 248490706844586261410203
589 261540941761240642262029
590 275264982414934173202959
591 289697032618827122971284
592 304873003269975366028093
593 320830596120295386607105
594 337609391590065169557232
595 355250940815002702554463
596 373798862128436852705701
597 393298942187883251153311
598 413799241966727832974292
599 435350207840317348266260
600 458004788008144308549881
601 481818554503286362919946
602 506849831053734861478078
603 533159827070679866275188
604 560812778053476538345617
605 589876092712502332460057
606 620420507127059714303541
607 652520246268116112053348
608 686253193233019826876660
609 721701066553229757375644
610 758949605954969709101880
611 798088766967999186002921
612 839212924798226411056947
613 882421087896683264550301
614 927817121679723721845920
615 975509982873756796921627
616 1025613964982134990449412
617 1078248955392080004470886
618 1133540704665979618902758
619 1191621108583631746906236
620 1252628503530795506436999
621 1316707975853817969916640
622 1384011685831426958554951
623 1454699206941558115137746
624 1528937881135168275059443
625 1606903190858354689124401
626 1688779148601189609512754
627 1774758704783877366654012
628 1865044174831202682772554
629 1959847686321528964665509
630 2059391647140527228525491
631 2163909235608484556358400
632 2273644913597837330077111
633 2388854963699932382731950
634 2509808051552031608078501
635 2636785814481962651215039
636 2770083477684418110391083
637 2910010499193691843298965
638 3056891244979232231858421
639 3211065695545980277244682
640 3372890185488482409680957
641 3542738177508596708703767
642 3721001072479541451504289
643 3908089057205582486664821
644 4104431991606013700452996
645 4310480337124871462072823
646 4526706128254173781040168
647 4753603989138067267822810
648 4991692197319220372386408
649 5241513796775816319679507
650 5503637762499727151302900
651 5778660218961559003719374
652 6067205714919484306339330
653 6369928557132709817138714
654 6687514205661440172549434
655 7020680733548749464949656
656 7370180353811425547657916
657 7736801016790889035128049
658 8121368081058512888502818
659 8524746061205131302390706
660 8947840456000332817669452
661 9391599660555044587637236
662 9857016966290401433255310
663 10345132652677367520052392
664 10857036174895938656579006
665 11393868451739000294448643
666 11956824258286445517625184
667 12547154728067493595497743
668 13166169969647255482976069
669 13815241802783448943201842
670 14495806619536377005375098
671 15209368375944215483237663
672 15957501720133631304226446
673 16741855262985451980942780
674 17564154997755650263617108
675 18426207875324210441990742
676 19329905542049511423194926
677 20277228247502764885896365
678 21270248929688765106873605
679 22311137485682880566291355
680 23402165235974892374949875
681 24545709591163085124242053
682 25744258930034131533258942
683 27000417698448800353549410
684 28316911738879831363620964
685 29696593860867277871600839
686 31142449663120060247015911
687 32657603618448918933400167
688 34245325433219728719768927
689 35909036693513349075720190
690 37652317810725762600760676
691 39478915279883795756618809
692 41392749264546866860888893
693 43397921522754943172588268
694 45498723689129703063644912
695 47699645928878027716134729
696 50005385980149860746057621
697 52420858601901549459653967
698 54951205445179608281714507
699 57601805366500810491214433
700 60378285202834474611024090
701 63286531028521032840980915
702 66332699915362724119976098
703 69523232218023552371147703
704 72864864407855341219965206
705 76364642479247406973527705
706 80029935953661656574118920
707 83868452507581852374817942
708 87888253251761884175125525
709 92097768690318501305948176
710 96505815389469697877045264
711 101121613386982294887574995
712 105954804374756131323434518
713 111015470688345108146845604
714 116314155138696524440179117
715 121861881722882938654955439
716 127670177252209281782735813
717 133751093937700984130076573
718 140117232974725477106755538
719 146781769170263852819568789
720 153758476658245881594401876
721 161061755750279477635529947
722 168706660971164630122434300
723 176708930330666271859876746
724 185085015885255746880621052
725 193852115645795752984184554
726 203028206889569986197646484
727 212632080937520072186585650
728 222683379460186024851572558
729 233202632378520643600870281
730 244211297428606706709920642
731 255731801462210865864996645
732 267787583558210323920370995
733 280403140023083872114268991
734 293604071362025285843557776
735 307417131305664218954011531
736 321870277981032622582588666
737 336992727319136467572134169
738 352815008795455957133210724
739 369369023603738655757453136
740 386688105367749941220646435
741 404807083500032850651729108
742 423762349321394151918923525
743 443591925059596733749009901
744 464335535850798483634133318
745 486034684872448271784321313
746 508732731741838107613597770
747 532474974320122372524702644
748 557308734067567635805389647
749 583283445101886813536234873
750 610450747117966916191766805
751 638864582333908382360552351
752 668581296635294279311388874
753 699659745096778286894317749
754 732161402067670820574400190
755 766150476015982127183452328
756 801694029333610862568745904
757 838862103313805798709294274
758 877727848520950325159237558
759 918367660781873199488129833
760 960861323037560814483867973
761 1005292153304074193879893792
762 1051747159001957690209583758
763 1100317197924192833923664619
764 1151097146124113726578722224
765 1204186073016375022219511852
766 1259687423996378387111223999
767 1317709210896221493178038399
768 1378364210608578997366593230
769 1441770172223648126550503943
770 1508050033038752490738306503
771 1577332143815074048889593784
772 1649750503671651735806598654
773 1725445005022910006140640368
774 1804561688982956164492939405
775 1887253011677361609828817124
776 1973678121921532286407944740
777 2064003150743712843868724369
778 2158401513250589964731355221
779 2257054223353982965849636731
780 2360150221898687182164772690
781 2467886718753771981901716358
782 2580469549453004933593915548
783 2698113546994164480174751054
784 2821042929432312216467196744
785 2949491703928193388274444937
786 3083704087940340693022759146
787 3223934948277725160271629436
788 3370450258759473520427108746
789 3523527577258789108163781733
790 3683456542940343404363079231
791 3850539394533563994343408413
792 4025091510519029370421425657
793 4207441972141088280734052442
794 4397934150197476827913754420
795 4596926316595586652827468754
796 4804792281705797515062554306
797 5021922058584382849328863801
798 5248722555182613689484382380
799 5485618295704258477069978593
800 5733052172321422504456906520
801 5991486228508002426815714031
802 6261402475301701333080503977
803 6543303741858946450905280026
804 6837714561722963378455088871
805 7145182096283051986707098080
806 7466277096963606051213798966
807 7801594907743960700948994908
808 8151756509675604512522468030
809 8517409609130970421571752021
810 8899229771588828461969912417
811 9297921602834531195851263135
812 9714219979529959777862762681
813 10148891331187245215547988269
814 10602734975663191221223588558
815 11076584510377034355391136462
816 11571309261543787320061387075
817 12087815793808125625662158065
818 12627049482760689878061739057
819 13189996152918959195978864384
820 13777683783859651786576210025
821 14391184287298069419105851281
822 15031615358023124634594087055
823 15700142401714084441377197389
824 16397980542787591098996816075
825 17126396715550358417594261339
826 17886711842065410771034744286
827 18680303100276877491522982422
828 19508606286081561360311431975
829 20373118273183778133458314500
830 21275399574724765449983354277
831 22217077010838260632179405582
832 23199846486451169343993145389
833 24225475883821531494697777159
834 25295808074486832813101040658
835 26412764055483014097178751917
836 27578346214889968804237165712
837 28794641731961759722351366198
838 30063826117310982372086470288
839 31388166898835484452139879956
840 32770027459303858556350792805
841 34211871031752548278772278584
842 35716264859093977687647307544
843 37285884524590579748861388697
844 38923518460115987806848667395
845 40632072639400673752129294445
846 42414575463747094337180786216
847 44274182847997609942310572704
848 46214183514849300594196187834
849 48238004505931946889525415090
850 50349216918401212177548473763
851 52551541876147039010384557064
852 54848856745079917639394812898
853 57245201602333536237114016869
854 59744785969613964515539253168
855 62351995821331449988466085770
856 65071400878573831543609951314
857 67907762200418949875852860571
858 70866040084540107092698337135
859 73951402289532005957331745344
860 77169232591877674590168537300
861 80525139690988018278755879217
862 84024966476277979232856328456
863 87674799670795146675673853592
864 91480979866491345649258752099
865 95450111966823518214883915517
866 99589076052990565170686653322
867 103905038690755971019484291479
868 108405464695475636367939367494
869 113098129373644577851404467423
870 117991131259998859170817952725
871 123092905369958432777075789923
872 128412236987976529870072684144
873 133958276013169939669531013178
874 139740551884446204479331404858
875 145768989108216487062234766704
876 152053923412691097170490149769
877 158606118553696417431847039831
878 165436783797931931934295214171
879 172557592110602218633091537672
880 179980699075416049556058356670
881 187718762576041099642814423512
882 195784963269243383580949574952
883 204193025881123335512830172586
884 212957241359090878236182728209
885 222092489913497780851227597139
886 231614264984172822820073003005
887 241538698168481624527315172107
888 251882585148964518765460478419
889 262663412660090356154504988819
890 273899386535208029575034555059
891 285609460876378579895067645640
892 297813368391435715163322525036
893 310531651944349233813920506530
894 323785697366761254448562960374
895 337597767580427105501057911000
896 351991038082228660789452112102
897 366989633845435601723754684482
898 382618667692977386826261186841
899 398904280200653395819254511540
900 415873681190459054784114359068
901 433555192876539531087229249049
902 451978294728708525214022995295
903 471173670120985588372050791564
904 491173254835220446432862084360
905 512010287492584845146484405861
906 533719361988531136324395153006
907 556336482009740068071399057554
908 579899117714618242279047910845
909 604446264662056374189988828296
910 630018505076433611630379747344
911 656658071540248718776792340307
912 684408913209287275550344068534
913 713316764648893234122621619234
914 743429217393715213042975611046
915 774795794337240928934816278378
916 807468027061529837515792396149
917 841499536221802614337232040938
918 876946115104959930393838351039
919 913865816485680423486405060197
920 952319042908502961911588241254
921 992368640529229737341624405349
922 1034079996654109332431762905265
923 1077521141120571341397403379953
924 1122762851668802145076610691194
925 1169878763459173895733432730911
926 1218945482896482311379736991782
927 1270042705928112564209840420273
928 1323253340989653981276400179179
929 1378663636778122744608506412924
930 1436363315039845896899358321386
931 1496445708567209282036578481141
932 1559007904605896258842021455808
933 1624150893881942976244820886585
934 1691979725465930503404211092988
935 1762603667699924360130192596563
936 1836136375421380008668856710853
937 1912696063727159213943851074124
938 1992405688530070149968413754864
939 2075393134169954709485716040418
940 2161791408351324312330912515708
941 2251738844689892053427982283094
942 2345379313161090374436414544807
943 2442862438754801545567295086141
944 2544343828652090726779455853677
945 2649985308251720770267133432541
946 2759955166386673475403099782618
947 2874428410083806869907819971596
948 2993587029233173241168779707935
949 3117620271547411926979127046442
950 3246724928206047105940972852696
951 3381105630594468612010288121042
952 3520975158562887897616477403723
953 3666554760646647127956344299346
954 3818074486705953843294627805190
955 3975773533460423034845675028563
956 4139900603411771887815710359057
957 4310714277666637214536144920467
958 4488483403190813123215639900435
959 4673487495046245204241629444241
960 4866017154182911354694265199542
961 5066374501379277964399166412587
962 5274873627947390097986152236727
963 5491841063841846500452896046599
964 5717616263835974099255567726763
965 5952552112453464578853008302803
966 6197015448369619941842104641901
967 6451387609023188709970129903789
968 6716064996207615136996693067293
969 6991459663439386169435859771885
970 7277999925931103886207676498399
971 7576130994027952290703815090142
972 7886315630998429231248733029383
973 8209034836103596418058528748255
974 8544788553903729460741526707665
975 8894096410797147287955714747995
976 9257498479823236816318777813318
977 9635556074800288403768986027143
978 10028852574908795418824727334635
979 10437994280872373856676062872619
980 10863611303931504965592652837760
981 11306358488849924787366667758263
982 11766916372239763961801564982868
983 12245992177539511607834487445902
984 12744320848028628464246059620539
985 13262666119314202551196742814836
986 13801821632778520931079437712378
987 14362612091531863067120268395049
988 14945894460472306341153073884833
989 15552559212113915719970799351705
990 16183531619906475296861224617830
991 16839773100833956878604913208244
992 17522282609145324707635966069788
993 18232098083140097717852712338862
994 18970297947002453464660671148735
995 19738002669751617842096992225176
996 20536376383452971700767593586759
997 21366628562913781584556907787456
998 22230015769169865076825741898281
999 23127843459154899464880444624974
1000 24061467864032622473692149720708