0 1
1 1
2 3
3 7
4 18
5 36
6 82
7 153
8 300
9 520
10 915
11 1477
12 2437
13 3801
14 6027
15 9095
16 13824
17 20194
18 29734
19 42254
20 60348
21 83730
22 116565
23 158215
24 215375
25 286691
26 382461
27 500451
28 656130
29 846385
30 1094530
31 1395787
32 1784670
33 2254093
34 2853849
35 3573051
36 4482825
37 5565849
38 6922008
39 8525895
40 10516248
41 12857427
42 15741036
43 19115235
44 23241384
45 28046310
46 33879726
47 40638270
48 48788734
49 58187698
50 69454230
51 82394190
52 97816620
53 115457630
54 136367830
55 160188295
56 188277300
57 220162660
58 257580555
59 299908965
60 349354971
61 405096327
62 469924839
63 542781843
64 627167610
65 721719411
66 830805556
67 952670250
68 1092741720
69 1248801855
70 1427540940
71 1626159677
72 1852875761
73 2104175750
74 2390140854
75 2706428485
76 3065310984
77 3461426162
78 3909700360
79 4403546652
80 4961061216
81 5574209620
82 6264800526
83 7023081490
84 7875324575
85 8809666691
86 9857634366
87 11004924967
88 12289229370
89 13693324573
90 15262170370
91 16975007274
92 18885368400
93 20968407694
94 23287543566
95 25813071529
96 28620067700
97 31672992449
98 35060454870
99 38740203670
100 42816443586
101 47238990071
102 52130205590
103 57430563599
104 63283521432
105 69618847990
106 76604117535
107 84156711932
108 92472173114
109 101453238224
110 111327703650
111 121981723690
112 133679723430
113 146288627597
114 160115163626
115 175003703885
116 191309352126
117 208851039664
118 228038581005
119 248661488618
120 271192343324
121 295386408758
122 321787627896
123 350112707210
124 380985920136
125 414079715644
126 450110136720
127 488698570230
128 530665012500
129 575573745880
130 624361351260
131 676526985434
132 733139653740
133 793623672078
134 859197434952
135 929201700690
136 1005021646716
137 1085903211260
138 1173419974616
139 1266709425800
140 1367556774780
141 1474978638700
142 1590995610135
143 1714487683960
144 1847740170775
145 1989477966255
146 2142282630765
147 2304707089220
148 2479661529300
149 2665505402410
150 2865517257520
151 3077837650360
152 3306155708700
153 3548369985110
154 3808623223995
155 4084542807945
156 4380777762025
157 4694649815590
158 5031370215060
159 5387923537820
160 5770140183828
161 6174628337758
162 6607907460256
163 7066163542324
164 7556679077976
165 8075176188935
166 8629775412234
167 9215682990808
168 9841948740175
169 10503202149805
170 11209518604290
171 11954895355205
172 12750530737980
173 13589720806942
174 14484904980854
175 15428597898329
176 16434604644444
177 17494585952487
178 18623838734298
179 19813080314230
180 21079252088741
181 22412024054616
182 23830142416899
183 25322135201853
184 26908714751856
185 28577150555359
186 30350315897216
187 32214087013388
188 34193702013120
189 36273521179080
190 38481352577400
191 40799891155552
192 43259762804204
193 45841825122212
194 48579780907080
195 51452493870960
196 54497003238000
197 57689987583124
198 61072134667280
199 64617718254684
200 68371399887840
201 72304848513820
202 76467024766842
203 80826750755510
204 85437679365750
205 90265510596624
206 95368999585500
207 100710474299076
208 106354201513080
209 112258833664002
210 118494639650724
211 125016249622026
212 131900444178720
213 139097515906874
214 146691265327044
215 154627267117004
216 162996953085000
217 171740749006516
218 180958354201668
219 190584654397570
220 200728250196900
221 211318014749298
222 222472206644320
223 234113148606974
224 246369541685316
225 259156668970850
226 272614455516018
227 286650557964162
228 301417061911308
229 316813333783660
230 333004590471840
231 349881305460610
232 367622792485620
233 386109906547974
234 405537208093024
235 425775110310088
236 447034609691136
237 469174929655376
238 492424687502976
239 516631025461744
240 542041594104368
241 568490444850240
242 596245722352080
243 625127469067664
244 655425773620896
245 686945570206280
246 720000612349444
247 754379482862254
248 790421379485580
249 827897407731030
250 867173980707900
251 908003384776196
252 950781347611134
253 995239820601394
254 1041806011871454
255 1090190157378140
256 1140853092680388
257 1193481692541662
258 1248572963119696
259 1305788571707122
260 1365664322653620
261 1427834996815510
262 1492877802010044
263 1560398635527228
264 1631019184562600
265 1704314216178644
266 1780953064913106
267 1860477318032116
268 1943607097429620
269 2029848389791400
270 2119975816334988
271 2213457047302458
272 2311125021519900
273 2412406615462258
274 2518196862334104
275 2627878911411568
276 2742414338400300
277 2861139280157092
278 2985086436303528
279 3113541942676740
280 3247614155792304
281 3386535681249452
282 3531495863957424
283 3681669828380068
284 3838333379888934
285 4000600554555235
286 4169839027317315
287 4345097511699653
288 4527841926126910
289 4717050938816217
290 4914295253578305
291 5118479182511945
292 5331284669439960
293 5551536596022851
294 5781035720354324
295 6018521841695172
296 6265922316055146
297 6521886720253969
298 6788476693425066
299 7064245552102702
300 7351398223946847
301 7648385033029237
302 7957563419350011
303 8277274570465953
304 8610037545705624
305 8954077217760869
306 9312084945125374
307 9682161300250031
308 10067180869325010
309 10465112630464730
310 10879025160844500
311 11306747306176470
312 11751554237948702
313 12211125205042884
314 12688954889250408
315 13182564306473030
316 13695680363184336
317 14225655741885868
318 14776464425334954
319 15345279549008525
320 15936337364398056
321 16546621245434090
322 17180644688158359
323 17835189390062139
324 18515063567102375
325 19216834018517653
326 19945621527458046
327 20697765914482755
328 21478718098287450
329 22284576877607177
330 23121143819608618
331 23984261151700794
332 24880102021510260
333 25804237869148963
334 26763233991072459
335 27752374504283902
336 28778640844267050
337 29837011544056465
338 30934908672696549
339 32066988490555535
340 33241137753027792
341 34451671046190256
342 35706967804175840
343 37000979514981904
344 38342606861874672
345 39725418683458360
346 41158864968630864
347 42636109214132168
348 44167183328961444
349 45744820403171564
350 47379667505428560
351 49064004454138360
352 50809126148730960
353 52606832667890564
354 54469104694548432
355 56387233367598560
356 58373923775677440
357 60419931427921492
358 62538723740786664
359 64720489780984156
360 66979503351478200
361 69305353120877580
362 71713164095801940
363 74191893490168720
364 76757561443336080
365 79398457870665640
366 82131549077387560
367 84944418273023960
368 87855029815237440
369 90850224162778880
370 93949014541560960
371 97137457058337536
372 100435672765856576
373 103828887744575680
374 107338390835628288
375 110948536328815360
376 114681839544002880
377 118521734800453980
378 122492031891071984
379 126575192308781544
380 130796389452405312
381 135137063685487020
382 139623819661626384
383 144237020950817356
384 149004781739974000
385 153906327732729036
386 158971362205309008
387 164177917213760376
388 169557362953250160
389 175086473619165724
390 180798376307585040
391 186668516936981728
392 192731870857859160
393 198962491401365100
394 205397291537036052
395 212008858080206040
396 218836144857607400
397 225850191125084000
398 233092096299152400
399 240531278047825600
400 248211083797677120
401 256099224635835280
402 264241414246582750
403 272603564050803495
404 281233873848774600
405 290096370372256770
406 299241856745394975
407 308632377545722790
408 318321474458391725
409 328269103218918945
410 338531681076018270
411 349066977450534675
412 359934419061201840
413 371089477397843820
414 382594743067164830
415 394403267567794290
416 406580961712287600
417 419078345462759180
418 431964802553472675
419 445188193819748890
420 458821551921304070
421 472809939114496300
422 487230215086267980
423 502024516062380130
424 517273702657478940
425 532916839400841840
426 549038988140492010
427 565575982649385575
428 582617288576491140
429 600095363553691250
430 618104274730920495
431 636572937583762830
432 655600248337803795
433 675111399130810735
434 695210345342137650
435 715818390171072020
436 737044772574409440
437 758806717838367275
438 781219006683067590
439 804194580430805870
440 827854022450199540
441 852105801770697925
442 877076558762991885
443 902670075413610420
444 929019341528771100
445 956023218029760160
446 983821339584177720
447 1012307432170417800
448 1041628063170623640
449 1071671579873634446
450 1102591813135162980
451 1134271466207647950
452 1166871967472130360
453 1200270133694017722
454 1234635316120538220
455 1269838168926379284
456 1306056339867019800
457 1343154020173691788
458 1381317531409635276
459 1420404327402237630
460 1460609770724306916
461 1501784265414105776
462 1544132636599643112
463 1587497899087142602
464 1632094766039538816
465 1677758552742233360
466 1724714274222324048
467 1772789193377499200
468 1822219102040397680
469 1872822827563775600
470 1924847417758446720
471 1978102914057959800
472 2032848086031854340
473 2088883791080603300
474 2146481055008710180
475 2205431119257380570
476 2266017804654454200
477 2328022341563744756
478 2391741869406782436
479 2456947159041616776
480 2523949269092902476
481 2592508024494393292
482 2662949008147777014
483 2735020654051616292
484 2809063657264852008
485 2884814556325219526
486 2962629832472446976
487 3042233581668870120
488 3123998749893444360
489 3207636490088819740
490 3293536872249221640
491 3381397539386012272
492 3471626440773383963
493 3563907094794361077
494 3658666090229739330
495 3755572258913280435
496 3855071567639588142
497 3956817525369864911
498 4061276322340411720
499 4168085455215890201
500 4277732188563708210
501 4389837376701939505
502 4504910184596993199
503 4622554110894321315
504 4743301166198743050
505 4866736721312184999
506 4993416583784697243
507 5122907290698652154
508 5255789369370100680
509 5391609724445136010
510 5530974658930509908
511 5673410581259134672
512 5819550632059268160
513 5968899933527347495
514 6122119493698319874
515 6278692255661145285
516 6439308272949445075
517 6603427343993470529
518 6771769751845668108
519 6943771267203012165
520 7120183550833692780
521 7300417348502235013
522 7485257011353105810
523 7674087182028781094
524 7867726220771713548
525 8065531681508542885
526 8268357212212626144
527 8475532165385754224
528 8687946937426308048
529 8904901476964037440
530 9127324396431309600
531 9354485141553864480
532 9587351962725795600
533 9825162562275293288
534 10068926452774303664
535 10317848254182690536
536 10572980372498849712
537 10833493120962937352
538 11100483378774003024
539 11373085771999174000
540 11652443457461161432
541 11937653884192388456
542 12229908297636400272
543 12528265607479449728
544 12833966901746071104
545 13146031015981249344
546 13465750882793164416
547 13792103607370917888
548 14126435975613283200
549 14467681848754763840
550 14817243810939279000
551 15174010774321611848
552 15539443339995973424
553 15912383632311260936
554 16294352495619915696
555 16684143585784293480
556 17083340144419546368
557 17490685466511731424
558 17907827648265421760
559 18333457584589960344
560 18769290690169597872
561 19213963595279706960
562 19669261416826056504
563 20133764423167748640
564 20609330151585834000
565 21094480248212477808
566 21591147395321959104
567 22097792551111503312
568 22616426178390298860
569 23145446224096881753
570 23686943935090184940
571 24239251745214470157
572 24804544696009911000
573 25381087421706304470
574 25971141668913388854
575 26572901702026024329
576 27188719289626290900
577 27816715559879983275
578 28459335626194062870
579 29114624951568019500
580 29785125206275296480
581 30468803347853836560
582 31168301262284900664
583 31881504344768771940
584 32611158361252323900
585 33355064351474483730
586 34116075502545110733
587 34891905361892704905
588 35685518569787468715
589 36494537807644567413
590 37322043206661549810
591 38165563498699627620
592 39028298205797966430
593 39907678649742688995
594 40807028183824133670
595 41723676999023734245
596 42661076723573339556
597 43616453017338684810
598 44593390075801366800
599 45589005213530648460
600 46607020077240618840
601 47644439536187984340
602 48705127576339734360
603 49785972875335230261
604 50890986477009262584
605 52016936666354702525
606 53167986914568177596
607 54340780601774987989
608 55539638997562462350
609 56761076453544057060
610 58009577222845451700
611 59281522008279929269
612 60581563943781049654
613 61905945120310437091
614 63259493451265713519
615 64638307882230335130
616 66047396798259844692
617 67482710919831403392
618 68949445576328871256
619 70443397811055955595
620 71969956369347548910
621 73524759635228293750
622 75113396013868961985
623 76731339652402927493
624 78384385713649525100
625 80067838120666214237
626 81787705889107025262
627 83539117249185378459
628 85328301913256529750
629 87150206296209908976
630 89011288584486409268
631 90906306810548806752
632 92841955407308452800
633 94812798024311822112
634 96825772835942329536
635 98875242396294294132
636 100968397136620840725
637 103099391315156006570
638 105275676128311163259
639 107491190962411199380
640 109753655982649850592
641 112056788347620214172
642 114408586509291291080
643 116802537514160806007
644 119246927408850702012
645 121735005924629201335
646 124275355675281367617
647 126860981025726421492
648 129500771345508088070
649 132187477002596655406
650 134930304298040630400
651 137721741720946338780
652 140571322310657844420
653 143471263867500442267
654 146431437302409259028
655 149443780289381193517
656 152518512726447231978
657 155647283539712585450
658 158840672325716146962
659 162090029632665274728
660 165406306911253148097
661 168780546015234386821
662 172224082385209047312
663 175727639758339829508
664 179302949255477468232
665 182940405974064999624
666 186652149980500459598
667 190428236465257640507
668 194281227678044143140
669 198200828610814048285
670 202200036449882522130
671 206268194500974521078
672 210418749351895274779
673 214640670324663970555
674 218947867845079872951
675 223328926019262401110
676 227798233013204128098
677 232343975183784290974
678 236981034204479319960
679 241697185269537529958
680 246507819289192302528
681 251400288045074716150
682 256390506831816633732
683 261465390351849906212
684 266641395456845654875
685 271904985149647455606
686 277273174969415305902
687 282731962863861748278
688 288298939553059235010
689 293959623037737167223
690 299732197912167234806
691 305601686300787378958
692 311586885315977080320
693 317672306656850967248
694 323877377900312408256
695 330186084100793662336
696 336618503636832344575
697 343158077574080283606
698 349825555370841425403
699 356603818262487742975
700 363514306307748635862
701 370539323257483256621
702 377701021883424735144
703 384981109581946110595
704 392402473884724593024
705 399946208595331540795
706 407635957224124445796
707 415452180781106926172
708 423419302785919632652
709 431517130931966903980
710 439770892704806802375
711 448159723735596164005
712 456709678527797362620
713 465399199773484714682
714 474255195096527417964
715 483255391944576618381
716 492427577075142482688
717 501748742315737836633
718 511247578589385016218
719 520900319418507877737
720 530736588224539625432
721 540731835994027146472
722 550916646882283953672
723 561265667201312413656
724 571810469005642686054
725 582524869296023528091
726 593441458765860828834
727 604533198794669357458
728 615833729345418563610
729 627315132139781995135
730 639012125875470346530
731 650895885876745056205
732 663002242913473459270
733 675301437361635376695
734 687830445275753581620
735 700558546000263604420
736 713523892821558432516
737 726694775041069562686
738 740110559312155035690
739 753738513929492466515
740 767619254905013325612
741 781719001233815435455
742 796079652906463471164
743 810666348161871349848
744 825522310112947663300
745 840611562674845926325
746 855978691070776627806
747 871586574216148350610
748 887481196940025951360
749 903624259064859633120
750 920063187410194068160
751 936758466331585083200
752 953759006848174752630
753 971024044607436865014
754 988604015416387273779
755 1006456869283199805478
756 1024634612675679173675
757 1043093870568218145279
758 1061888265767133985701
759 1080973062212789744180
760 1100403542970816652278
761 1120133570958794879438
762 1140220139128495990680
763 1160615666733884209798
764 1181378906017141253232
765 1202460793596831167405
766 1223921888509343978310
767 1245711601461910446465
768 1267892351942632683947
769 1290411978611551859142
770 1313334814821934649730
771 1336607085014239319330
772 1360295087761227419130
773 1384343386469632377083
774 1408820302920906781696
775 1433668689593319833096
776 1458958949195148631944
777 1484632177661956802628
778 1510760914116132134067
779 1537284447334998864286
780 1564277515495029877017
781 1591677546277040835347
782 1619561539257035789802
783 1647865011707434743306
784 1676667284532826396482
785 1705901909896310993776
786 1735650597671600634822
787 1765844876634716301396
788 1796568912938655501000
789 1827752158690411594810
790 1859481301018551920640
791 1891683656273228715489
792 1924448505562230688800
793 1957700966537823299555
794 1991532986926117344726
795 2025867428132612182925
796 2060798974314336121296
797 2096248166825655769521
798 2132312505012269814692
799 2168910142232164203907
800 2206141471369058110272
801 2243922195653712598080
802 2282355676805714775840
803 2321355099064613080672
804 2361026877908417571825
805 2401281605266607652386
806 2442228834851232962934
807 2483776499232353446339
808 2526037371537973375050
809 2568916650685416112865
810 2612530420755287424276
811 2656781067937310942212
812 2701788078305972564550
813 2747450953001632445932
814 2793892667580112904772
815 2841009758022685481694
816 2888928787985313138175
817 2937543243038995843492
818 2986983373018148698899
819 3037139535104979007610
820 3088145759554084865142
821 3139889188807621345222
822 3192507739745435787390
823 3245885248200133268870
824 3300163623284152309008
825 3355223310178685854020
826 3411210311698608559224
827 3468001589338021146180
828 3525747353935059421503
829 3584320984331218005417
830 3643877013057713933865
831 3704285145763616610780
832 3765704345882244168750
833 3828000545671456414773
834 3891337262479416415266
835 3955576548617412952878
836 4020886597644366898122
837 4087125484432738600482
838 4154466196241667094716
839 4222762722644761189458
840 4292192976907623683751
841 4362606748620100470879
842 4434187008579797025153
843 4506779241454038271947
844 4580571601917322043256
845 4655405153646517049046
846 4731473377438206066738
847 4808612792597180048622
848 4887022347426117644550
849 4966533903950613884160
850 5047352013786059148480
851 5129303756834577608352
852 5212599440884895536086
853 5297061231025433983098
854 5382905343142270339962
855 5469948906078164708010
856 5558414189738878924884
857 5648113152490246029396
858 5739274282471745825940
859 5831704224945010843764
860 5925637849469917200192
861 6020876357669107575480
862 6117661157254057892376
863 6215787861955263798612
864 6315504593971582902450
865 6416601225888503389224
866 6519332769611096826666
867 6623483216311238582508
868 6729314635872925836480
869 6836604983082086374344
870 6945623575081304080272
871 7056142165668299814882
872 7168437507296512152720
873 7282275002107115231160
874 7397939018450419185312
875 7515188440395205382568
876 7634315455272844308225
877 7755072252348682796163
878 7877759039689581781956
879 8002121149981723093140
880 8128467005759345558196
881 8256534904494134752755
882 8386641701015129742420
883 8518518467919139091253
884 8652490708703631896232
885 8788282097467680163230
886 8926226994133485602748
887 9066041482638339878439
888 9208069012872230234340
889 9352017875144389125753
890 9498240841282235434890
891 9646438221693331723425
892 9796972332853808883900
893 9949535299690741912401
894 10104499233628948013562
895 10261547855924498423892
896 10421063321532334677432
897 10582720748266102952904
898 10746912573256718662020
899 10913305090461378196032
900 11082301287334573828560
901 11253558400078008862416
902 11427490232765810282880
903 11603744749679919575832
904 11782746827153750352024
905 11964134921317770939288
906 12148345267949065975296
907 12335006564402292258156
908 12524566691061343722240
909 12716644357006898306040
910 12911699360970518450040
911 13109340170676922360884
912 13310038810655016576144
913 13513393238812230518496
914 13719888010737614349504
915 13929110328674196317460
916 14141557572286467421728
917 14356805917098988036764
918 14575365895884093074544
919 14796802369984709704308
920 15021639351926048804256
921 15249430125603818374965
922 15480712496819326445469
923 15715027881836768142231
924 15952928231730536513925
925 16193942787428492125698
926 16438637994705225042831
927 16686530637341700266844
928 16938201991181287225500
929 17193156072306174393168
930 17451989363077695472836
931 17714192782641228786738
932 17980378393532819599260
933 18250023716405564556741
934 18523756752574219249734
935 18801041291974820371314
936 19082521677143492586900
937 19367647615130409427959
938 19657080189127759666365
939 19950254700717141764040
940 20247849357065733370608
941 20549284698972145653960
942 20855256487669681988700
943 21165170126610748849188
944 21479739357916166075892
945 21798354102742536188220
946 22121746493690382761736
947 22449290589765706505748
948 22781737373536186135476
949 23118444639347365986282
950 23460182675703273343320
951 23806292643556972986660
952 24157564574880354416280
953 24513322591273013098590
954 24874376958913700673660
955 25240034329955811872646
956 25611125691710003867856
957 25986939832854556443012
958 26368328929042324912986
959 26754563471771808611856
960 27146517348956598002592
961 27543442295486545200768
962 27946234431354820194144
963 28354126313906079858843
964 28768036793954597185032
965 29187178788075081737943
966 29612494437075964250796
967 30043176526172049929136
968 30480191040902761100250
969 30922710185613597358980
970 31371724322807579346195
971 31826384581410741583524
972 32287706297502584396316
973 32754819000887378329032
974 33228763593063939924489
975 33708647524841209350645
976 34195537830928740080742
977 34688519355291681510477
978 35188685902206105480864
979 35695099149931919141784
980 36208880303510631312018
981 36729067363365575856420
982 37256809540826286408312
983 37791120595279349646936
984 38333178422848627800000
985 38881971945671266570920
986 39438708417634535878680
987 40002351377237918048244
988 40574138081697453998160
989 41153006085127883264172
990 41740223371332951577992
991 42334700874212005853496
992 42937738021437028658280
993 43548218543964573378168
994 44167474001374629327576
995 44794360281123650269632
996 45430241845398271950900
997 46073946060265331765724
998 46726871054807950536024
999 47387815052388393205980
1000 48058210582073654541264