0 1
1 1
2 0
3 1
4 5
5 5
6 1
7 5
8 20
9 20
10 6
11 20
12 65
13 65
14 25
15 66
16 185
17 185
18 85
19 190
20 481
21 482
22 250
23 501
24 1165
25 1170
26 666
27 1230
28 2666
29 2685
30 1646
31 2850
32 5827
33 5887
34 3830
35 6303
36 12251
37 12415
38 8487
39 13395
40 24912
41 25323
42 18052
43 27507
44 49215
45 50176
46 37072
47 54832
48 94781
49 96905
50 73852
51 106465
52 178437
53 182929
54 143245
55 201930
56 329161
57 338310
58 271322
59 375030
60 596115
61 614155
62 503102
63 683383
64 1061600
65 1096196
66 915144
67 1223857
68 1861729
69 1926465
70 1635838
71 2157265
72 3219029
73 3337541
74 2877790
75 3747398
76 5493467
77 5706227
78 4988920
79 6422260
80 9261636
81 9636897
82 8532369
83 10869269
84 15438550
85 16089847
86 14410430
87 18181911
88 25463695
89 26577555
90 24055069
91 30084101
92 41583201
93 43462505
94 39718630
95 49270867
96 67274768
97 70406052
98 64914264
99 79921905
100 107883650
101 113040710
102 105078451
103 128470936
104 171568735
105 179970709
106 168561238
107 204751033
108 270701558
109 284252420
110 268097268
111 323689301
112 423923898
113 445572774
114 422977975
115 507800657
116 659158024
117 693437434
118 662241367
119 790837655
120 1017988076
121 1071813025
122 1029331238
123 1223104411
124 1562006600
125 1645853840
126 1588867662
127 1879155767
128 2381964972
129 2511603010
130 2436437626
131 2868899552
132 3610907077
133 3809920510
134 3712686935
135 4353533000
136 5442939822
137 5746393558
138 5623511389
139 6568319325
140 8159948871
141 8619679996
142 8468862502
143 9855003779
144 12169470545
145 12861694663
146 12683672751
147 14707761778
148 18058173027
149 19094367400
150 18895766111
151 21838075748
152 26667100205
153 28209506276
154 28007487790
155 32265994411
156 39197153345
157 41480766575
158 41310340468
159 47448036495
160 57356450346
161 60720085579
162 60645393553
163 69455826456
164 83565497565
165 88495502937
166 88626963303
167 101224738576
168 121241925391
169 128433463505
170 128953472728
171 146898848850
172 175194397701
173 185637041523
174 186838063410
175 212307978250
176 252165889084
177 267262758671
178 269603212653
179 305625374900
180 361580744004
181 383313765035
182 387499312829
183 438271723229
184 516568997620
185 547727384443
186 554828227147
187 626154134786
188 735366927417
189 779862072905
190 791481011697
191 891359460392
192 1043226807481
193 1106524921453
194 1125036595155
195 1264462172757
196 1475014101865
197 1564728854104
198 1593618271768
199 1787661493305
200 2078730441344
201 2205432430689
202 2249771381607
203 2519034661561
204 2920280379975
205 3098599651540
206 3165713725588
207 3538288895010
208 4089905267851
209 4340028869075
210 4440426890325
211 4954521003071
212 5710846581215
213 6060547299914
214 6209210614495
215 6916660325907
216 7950984119037
217 8438361723212
218 8656525129669
219 9627490081535
220 11038435115079
221 11715611028807
222 12033213018851
223 13362430433445
224 15282415997500
225 16220500853311
226 16679541970153
227 18494644456568
228 21101081889804
229 22396838588275
230 23055967943082
231 25528522648426
232 29058599237721
233 30843359488491
234 31784117126825
235 35144247518077
236 39914411837512
237 42365981331749
238 43701266481269
239 48256981894185
240 54688578575367
241 58047097460640
242 59932620413587
243 66095320635526
244 74748254784695
245 79337282057064
246 81987004438762
247 90305069547220
248 101921938339348
249 108176421849935
250 111883314327463
251 123086262531627
252 138650109075103
253 147153413702886
254 152317285023235
255 167373720120336
256 188183487253700
257 199716316517707
258 206881023117886
259 227074545304515
260 254843491356150
261 270448396029839
262 280351465998612
263 307379944815887
264 344363801714580
265 365430078770966
266 379068727266511
267 415173909343060
268 464337507343194
269 492712725098775
270 511431464122479
271 559567907606146
272 624801476067863
273 662937707658071
274 688544343008430
275 752599257399521
276 838998784084377
277 890144007224117
278 925062873815020
279 1010141753312785
280 1124371830643994
281 1192820004154181
282 1240293950925180
283 1353091117531013
284 1503853856639325
285 1595271100348181
286 1659627167704767
287 1808905734883473
288 2007545881316694
289 2129395202691705
290 2216393355024930
291 2413605996484568
292 2674890705681612
293 2836984133893067
294 2954274092183785
295 3214364747686638
296 3557487039335733
297 3772702224849108
298 3930420738788812
299 4272858506230415
300 4722726799452756
301 5007935594021943
302 5219485841807717
303 5669596416610502
304 6258489486516995
305 6635759339058926
306 6918826106047431
307 7509504019920614
308 8279192130088737
309 8777338080049905
310 9155207652851340
311 9929115218628257
312 10933575224972201
313 11590161805046417
314 12093435019021820
315 13105822540930326
316 14414708870475891
317 15278628549529334
318 15947440271825094
319 17269758276974180
320 18972834659158279
321 20107624076494531
322 20994514012782834
323 22719033933089546
324 24931824846958335
325 26419923907487801
326 27593543772801969
327 29839261073085944
328 32710249871106414
329 34658464163323380
330 36208357197221371
331 39128523420898297
332 42848309486263881
333 45394806424041991
334 47437559770141130
335 51229281119565575
336 56042215548861836
337 59365472839840976
338 62052624973250385
339 66969079542747160
340 73188033115340106
341 77518269262155718
342 81046457846185070
343 87412427313729157
344 95437512614489450
345 101071268946588805
346 105695234747072475
347 113926826455461578
348 124269106274620866
349 131587825697543185
350 137637052365622088
351 148266713292058598
352 161578190145411456
353 171071858354313088
354 178971834597463775
355 192680040898639197
356 209791550463207554
357 222088741955917557
358 232388092558148330
359 250043451042889830
360 272012491292126831
361 287918508994630443
362 301323567645851603
363 324033505834010013
364 352204543224629120
365 372749774108679578
366 390168580631322451
367 419343351248989965
368 455423779599804113
369 481924930653499065
370 504523148557013952
371 541956558659749680
372 588112275170841834
373 622249830892692825
374 651521723788733470
375 699492850644725392
376 758468393584474029
377 802384480495771677
378 840242889438517711
379 901644104894200730
380 976913514118912854
381 1033335410039573433
382 1082225677541446705
383 1160723619225108056
384 1256679689651840820
385 1329075525578771043
386 1392119564424752778
387 1492357326680872574
388 1614548794708247964
389 1707323626675124265
390 1788501892714375487
391 1916352737534366472
392 2071781255524651391
393 2190523708766143900
394 2294904780693491775
395 2457790181292273273
396 2655281799168544743
397 2807074000837983568
398 2941103888013592575
399 3148391828393959045
400 3399061241292811170
401 3592867876073081053
402 3764734180370212441
403 4028237482366249927
404 4346067675019164090
405 4593223861881730024
406 4813313650213668229
407 5147912855867667971
408 5550478169010018580
409 5865300641192469290
410 6146775512569293108
411 6571196723659904804
412 7080564019225026718
413 7481116006945214914
414 7840633571673296460
415 8378418896329574260
416 9022269692721062742
417 9531317221437398449
418 9989935308406339439
419 10670652501114013470
420 11483679037453118591
421 12129885385044630279
422 12714194072628893774
423 13574942962832800767
424 14600583559367405560
425 15419999757147910293
426 16163537172463306645
427 17250824028157022766
428 18543418361076582765
429 19581341357932665485
430 20526362583951770018
431 21898430223968786714
432 23525893863661313069
433 24839180889107487519
434 26038865842170015175
435 27768587794835009818
436 29815728343725050973
437 31475676824431009073
438 32996883328899652291
439 35175355489713107770
440 37747980845358175183
441 39843908830078421160
442 41770602193803233107
443 44511596302422654921
444 47741600115419397250
445 50385293618232867642
446 52822814866664489641
447 56268295972231804408
448 60319947668161142600
449 63651179957797199190
450 66731552815421191902
451 71058509273450250407
452 76136227767524439220
453 80329603005351105793
454 84218126305413036615
455 89647017627285315432
456 96004971149895132632
457 101278402851680262945
458 106181832240407918372
459 112987029581170223395
460 120940981366023695683
461 127566187294171926219
462 133742880226114938533
463 142265559221105735667
464 152207473235474384345
465 160522955390039366720
466 168295439349313594181
467 178959488761776208081
468 191375524879532296815
469 201802609736043660760
470 211573138845307461071
471 224904775149633122974
472 240397443664971285951
473 253460087940100632048
474 265729881865321543615
475 282381814415047504157
476 301697230997007568440
477 318046457147876029095
478 333439473609517830552
479 354220653424118487805
480 378282044090147714665
481 398726063700192475840
482 418018348194394404149
483 443930562906859085128
484 473879422295710901365
485 499420742019064387760
486 523576633095640631295
487 555859490021476232756
488 593106104779643906076
489 624987197748833422055
490 655203952548146428439
491 695390131792010902845
492 741675555861004873704
493 781435032472326509037
494 819197786285550111810
495 869180859135762366227
496 926652883154330511840
497 976194522310404976553
498 1023343921125496128611
499 1085461531208349517135
500 1156767741034860735121
501 1218445262414229452926
502 1277260624983866518545
503 1354396439478545175800
504 1442798129387520755045
505 1519519218656793218940
506 1592820714204536938126
507 1688529292436400672809
508 1798040811428403432429
509 1893394677087811112420
510 1984668770065940213436
511 2103328394223535921042
512 2238887488715495790262
513 2357301159912462520260
514 2470854502862089930575
515 2617854103220370099756
516 2785530011795351888385
517 2932459715238769403282
518 3073607799310125489640
519 3255575423683537139405
520 3462822922457488229742
521 3644988244828263338444
522 3820286486527498906577
523 4045368358251370523140
524 4301337700325302505620
525 4527007900051084082249
526 4744534502451093555212
527 5022735640164535202910
528 5338650441546632950817
529 5617994280355997817950
530 5887696217745860778732
531 6231295922342587686014
532 6620913594084784182638
533 6966426486382199735576
534 7300542395825543243015
535 7724600727708960992439
536 8204773129170288452731
537 8631798342530736376499
538 9045375051488209417992
539 9568349823844243293480
540 10159705522191629271441
541 10687069709145393859808
542 11198592690285377552979
543 11843090610434622615841
544 12570864605302747234740
545 13221652229918015212168
546 13853814578747444741297
547 14647505122444457151359
548 15542547286213713203312
549 16345043678612192192430
550 17125683408193958645662
551 18102409982054964416618
552 19202409960088638222066
553 20191248967641366959176
554 21154490689327220583540
555 22355620829326904605195
556 23706594961780121879258
557 24924154682726518979004
558 26111799310677763503747
559 27587864325273801155235
560 29245959557268934840053
561 30744058698941422722728
562 32207273940718345958452
563 34019958829364505420648
564 36053639885807593893010
565 37895598194528806381989
566 39696973583453562027705
567 41921530596415108337567
568 44414230289734909084459
569 46677369622588056433020
570 48893413084983186501366
571 51621587358574288836750
572 54674916224132022077449
573 57453594616522674897873
574 60177763497119315747505
575 63521337301768896673451
576 67258968356339295993295
577 70668258412384964988018
578 74014637040983248999335
579 78109720917529011488000
580 82682088855349511504890
581 86862234582529690016410
582 90969993496069816197161
583 95982218644218231130695
584 101572200991298325443295
585 106694014571109598193457
586 111732814174347636372993
587 117863611750468749422033
588 124693393307772085579590
589 130964786141148854173570
590 137141320811646761238766
591 144635511309676135901478
592 152974873721988753241435
593 160648755486672634076919
594 168214673998511933081725
595 177369634842017385015599
596 187545961633422966050142
597 196929788321847082591222
598 206191274280876467907671
599 217368007593122033955370
600 229778353061988824486044
601 241245661560050053254193
602 252575014865793118205148
603 266211501830889963715521
604 281337141641961114145980
605 295341476180948973846694
606 309191105208730794749020
607 325818410541627668063382
608 344242374884948570099061
609 361334091817595896601590
610 378253408255224641177325
611 398515090501473237516753
612 420943279917326693050019
613 441789814313149894164733
614 462445621016245767337405
615 487121114605979674117754
616 514407717103742989264310
617 539818010696121493588601
618 565019090670549403035356
619 595051857304178856460375
620 628229926916382563899501
621 659183855611581166942603
622 689910611008045211625687
623 726442015151862246530270
624 766760240939049044746465
625 804444045750387707273729
626 841884203984730468486369
627 886294254869665227503223
628 935261150821506343928578
629 981110073869432922345055
630 1026701678914291023064769
631 1080658005237398971162768
632 1140094991664017858981090
633 1195844554899007682163648
634 1251327701665776806507115
635 1316844392045978405112831
636 1388949525229512554198991
637 1456697171045775181377102
638 1524176226995343380694010
639 1603684487261467502655610
640 1691108935005634008010853
641 1773388083527504621522334
642 1855406483000826520281457
643 1951839440227576991439358
644 2057779206768363057814590
645 2157648184514829667906904
646 2257278288182056748826310
647 2374172722456589497417199
648 2502478609138974810404416
649 2623627380102354563189090
650 2744578376747484405223107
651 2886196698469982345911206
652 3041506061048323891338485
653 3188384258292253320078903
654 3335131663520538390554380
655 3506608092627705616135875
656 3694502639045152961008005
657 3872473069705907850562166
658 4050414063426021475209165
659 4257929726224327885456160
660 4485124410418586836981771
661 4700647009570313294230185
662 4916286671795199827107656
663 5167279233513862330884236
664 5441848265006850029326005
665 5702700427992694243634133
666 5963874904921301351480715
667 6267289428144209669022895
668 6598936562059145268677731
669 6914476918704557584265260
670 7230620706935350026417760
671 7597209699067738588888270
672 7997591330044486413947515
673 8379075370883854295710577
674 8761541280957612917433510
675 9204223404830542995427116
676 9687334600362674230552546
677 10148292163889273319145564
678 10610734155333384381609283
679 11145022869645124964738020
680 11727658390013065267105948
681 12284344917381123845013375
682 12843175933487907473939690
683 13487691455609182514219793
684 14189996073551799761684970
685 14861931787872721518865447
686 15536871015633722744296019
687 16313951519229768494809058
688 17160076637322957225728318
689 17970690473325509010711735
690 18785417178417096162838397
691 19721848124154736094357897
692 20740734867646445407968256
693 21718133140245165281974829
694 22701067456777053054112020
695 23828951490732871243023887
696 25055264218005049643839233
697 26233147765136876883908834
698 27418382647101145654799230
699 28776176688124105849638290
700 30251415315673101122395217
701 31670173287582415853738118
702 33098586362120802008495084
703 34732337453851990406438542
704 36506162262131567413486915
705 38214175980962658202199196
706 39934755410624208050209028
707 41899572774536352786560728
708 44031381591673540005372093
709 46086578118822070525565675
710 48158002931605102866139324
711 50519810587214853717288594
712 53080615611862289098094663
713 55552318009179336714655374
714 58044840868792001066915055
715 60882463377830461090666448
716 63957123603025829576655649
717 66928253561422123609395547
718 69925942834732093580667766
719 73333586403040065538730775
720 77023461878330678443296261
721 80593160653309474483577786
722 84196569133158996075488607
723 88286771732560462031341927
724 92712878032074353141504695
725 96999623752131173493832649
726 101328963800643719464990431
727 106236101464708100021824894
728 111542857043611903864600865
729 116688170775666527300688275
730 121887090305740354834100451
731 127771542674361485268309597
732 134131218682024323817156847
733 140304068537509460424289698
734 146544139547830558294882350
735 153597236516025318690975425
736 161215238545345334346508527
737 168617271048697130438030253
738 176103322839597686873382778
739 184553216310831248132482185
740 193674351032605092352369967
741 202546102487807794804292517
742 211522555762777390593477615
743 221641186609119000844286456
744 232557093893440594449867570
745 243185362204443311533715594
746 253943748652073997660679413
747 266055109737910159005968833
748 279113073434881871639249150
749 291839663501900270925379945
750 304727548914790657187155987
751 319217481263165912411251258
752 334830870162697859709492108
753 350062964456340155888867283
754 365494532867701094581934650
755 382822334694700150460790169
756 401482970317822163520743951
757 419705421544026933632740717
758 438174024293920315595802746
759 458886202827352193248499975
760 481179003800225150753426696
761 502968899903641399190328492
762 525061928209348327740686225
763 549808483256085291017501705
764 576428798465937477599815930
765 602472712974803734048621106
766 628889216908541363921364326
767 658442914577625970749261038
768 690217030726588861023134209
769 721331445254848358336328055
770 752902997707644248780755772
771 788182174333642344751318316
772 826091569787329596834603934
773 863247042295711714599230626
774 900962435496790018398782140
775 943057967746379793243977480
776 988267985936707331022163914
777 1032617740356444936121563922
778 1077652207126779223592916037
779 1127859396975763773361919055
780 1181753131655775332700870074
781 1234666864320475050324519938
782 1288416639163049849349507338
783 1348272894783251279630146293
784 1412491219178369436266155310
785 1475595058260382185467858078
786 1539718237781662173279168531
787 1611047586747444283556979132
788 1687536422647435848118668993
789 1762760142043358487789929550
790 1839224973748047170803805728
791 1924190627299171494212603337
792 2015256742530147934820733713
793 2104889525580168100933249772
794 2196031453095154451590976790
795 2297197854078095582815925308
796 2405574702422129775917016037
797 2512330978380669835603937954
798 2620920004681332192655012510
799 2741326042609874472516151120
800 2870251424750629122002868527
801 2997348567775634328430779377
802 3126668771892726856290645513
803 3269914142596252015343154154
804 3423221776656853551980865715
805 3574471769936399455731969789
806 3728415133786188156718632266
807 3898762165675542502864828093
808 4080989619075052345536245067
809 4260907153365183321966471905
810 4444084231791173678787869430
811 4646577904414456459680520910
812 4863093764078593844406780059
813 5077023669490154669019340418
814 5294894077693207908977312975
815 5535503430947088138388256752
816 5792657086836018100512892823
817 6046924499801541712343025361
818 6305950708987814647383233507
819 6591735394719764812817502030
820 6897033394385252177850585132
821 7199120650745155810830704373
822 7506949187775142695575148226
823 7846255563110545635728486341
824 8208569176790189227171310250
825 8567324111299188978431106563
826 8932998966225868703624316711
827 9335690885574417234343248910
828 9765500318743603367642441706
829 10191381457840096379836576035
830 10625595331786984665595638839
831 11103325680523834403153432403
832 11613007303157652102581161334
833 12118372381164466277438440268
834 12633762376180212133472665025
835 13200292424886404139272849679
836 13804456476407450021479620518
837 14403901808273464198873495115
838 15015397294095702891028278914
839 15686972162926486576505615560
840 16402859665089231827741774604
841 17113619197920803043652503421
842 17838850915336425138117165681
843 18634640852601099721633538752
844 19482589949828976690524401080
845 20325004321738711153198799508
846 21184785330274349374144103093
847 22127404161441489427947558738
848 23131397844799228468123662944
849 24129465539019521054747876490
850 25148356425078632485266969485
851 26264470457463653174061258169
852 27452779655694482643667816337
853 28634804392342918318835644291
854 29841777265717360284141158355
855 31162820185761958215524757014
856 32568758572522324506893650707
857 33968109478564671564062947747
858 35397327750603903784825586646
859 36960339678040724194422041770
860 38623149304266920481403567057
861 40279153200714675903297915925
862 41970887014597599998721502745
863 43819498942643411886484689979
864 45785389021536216621390106245
865 47744377431533995681565759404
866 49746077971772373141433520523
867 51931666396532341193341372640
868 54255031321043718937033940307
869 56571568609688599441460455675
870 58939128432874746783187074245
871 61522169141672204571839937886
872 64267016187825515856922789519
873 67005339683100528994179791598
874 69804570776383096035054373160
875 72856225620477790375223910443
876 76097847885582394693201338969
877 79333556002770598626210154450
878 82641922596719607359564851707
879 86245898731117631831411826980
880 90072834791435385270660394486
881 93894865210476475784967235064
882 97803514572071051936635949049
883 102058242234149649476450682839
884 106574570918142421211693285025
885 111087517883468803780514833512
886 115703659535870319102675844345
887 120724842106488004892325504539
888 126052868825523003729153844118
889 131379696812070144021615581925
890 136829389036491094990072312085
891 142752988057424826454564912825
892 149036388499064834375180749261
893 155321609003236769243461371199
894 161753021266954283025396454475
895 168738749480147017916879940522
896 176146247362422611907136514842
897 183559636649445918471017982353
898 191146867995895690012080955327
899 199382275558695348068904137340
900 208111943813332185152194300396
901 216852892333760730733872782085
902 225800439024245096172609458455
903 235505692113563731161258464641
904 245789981597362064358898179320
905 256092580766485891031927274164
906 266640561877972937412551119157
907 278074029241346906538784484528
908 290185646198282379557728733556
909 302324635649944938413358862185
910 314754903256856039262138269603
911 328219685266011712262719642755
912 342478458660844559105663011989
913 356776177332091875186866168877
914 371419458733918948098115933705
915 387271015570717381444601450309
916 404051918530981448743342950839
917 420886426458079658902182343678
918 438130670124658199366118970235
919 456785731371073760580564517680
920 476528247820977297541858391010
921 496342812853862921496436918290
922 516642937885012052610298020328
923 538589905566121500865009595500
924 561808964306330577978690078545
925 585123139682966813733752418138
926 609012421242578068371016849499
927 634823512941535655732728058706
928 662122247609174730624593672816
929 689544803174024268466961354380
930 717648164281970495861441484093
931 747993583068643514436643155359
932 780078218395576979712942115128
933 812322231007576317821803574333
934 845371755090430536816461502370
935 881036219559547901782661197079
936 918733433051370783728677837112
937 956633891343089800256152793403
938 995486921021406850568716657032
939 1037388942737553159718552306475
940 1081666107380861101038797176259
941 1126200443584707218276280293694
942 1171860690425831297500784342310
943 1221075048695325904286275082077
944 1273063827791701612529501512985
945 1325375856092342358678448731099
946 1379018014772277620848788044073
947 1436801951262191226618916539470
948 1497825792398938634390642301308
949 1559253610649183932657255331260
950 1622252050634163568113564267042
951 1690075790502990957659202464879
952 1761681953637088306464269741066
953 1833790454957008844727959579716
954 1907752655155079087294100295245
955 1987334958856849256704110180663
956 2071331815396556852945802282777
957 2155950560090667747242377302555
958 2242756058922103280739556571518
959 2336105621784272403742249256590
960 2434606079580032328812894146303
961 2533873398180718410650657064641
962 2635719155466409945321175819481
963 2745182802931937173266313936812
964 2860654848747638151113877743850
965 2977069186393450785846153947790
966 3096522397009020488508825000746
967 3224841174855545612741754464325
968 3360166684082062522244413006920
969 3496646357831031921463894302680
970 3636705923274961557254686544715
971 3787080357386971346079749910321
972 3945623503825956059987517195607
973 4105576231305640628266836848586
974 4269744287704657728619168911610
975 4445910290777567664785243225576
976 4631597101120492199698616001318
977 4819000875071039315947151935199
978 5011365998757771288632849806168
979 5217683135921495555242722574655
980 5435093978521803901261468920426
981 5654591111841776132907591615165
982 5879925081172027710176707166660
983 6121479177852639863197881174010
984 6375956258660318869063521841800
985 6632962713757349687051165342636
986 6896833003686156238501488421344
987 7179555392743693870241979244718
988 7477327658744212746999760125513
989 7778160109361975823582323898930
990 8087060639690413144944325704883
991 8417866707506611648253795700875
992 8766194936479444533176166146090
993 9118218396675519716530562510715
994 9479721452981976699641881573660
995 9866671563242644457214608821738
996 10274016855959128414821286601935
997 10685816157557653793896856216993
998 11108748863893930213253603750765
999 11561235221975108645952099238690
1000 12037454618107252317239982844321