0 1
1 1
2 0
3 0
4 1
5 1
6 2
7 1
8 4
9 2
10 6
11 6
12 8
13 10
14 16
15 15
16 22
17 32
18 31
19 47
20 54
21 72
22 81
23 111
24 123
25 166
26 189
27 244
28 274
29 366
30 411
31 509
32 614
33 736
34 872
35 1056
36 1256
37 1479
38 1785
39 2099
40 2479
41 2942
42 3498
43 4028
44 4870
45 5600
46 6655
47 7712
48 9127
49 10512
50 12431
51 14327
52 16776
53 19401
54 22670
55 26047
56 30404
57 35017
58 40531
59 46695
60 54042
61 61979
62 71566
63 82191
64 94338
65 108395
66 124221
67 142314
68 162744
69 186529
70 212587
71 243156
72 277164
73 316164
74 359651
75 410220
76 465459
77 530023
78 601228
79 682964
80 773593
81 878333
82 992918
83 1125523
84 1271785
85 1438996
86 1623746
87 1835715
88 2068663
89 2334766
90 2630050
91 2963206
92 3334193
93 3753445
94 4218193
95 4741949
96 5325681
97 5979400
98 6707570
99 7524456
100 8432509
101 9447072
102 10580351
103 11839908
104 13245829
105 14811573
106 16553991
107 18490398
108 20651008
109 23044114
110 25711872
111 28668207
112 31960375
113 35599772
114 39658284
115 44137752
116 49122929
117 54632448
118 60753520
119 67507342
120 75016549
121 83293098
122 92477306
123 102609618
124 113837382
125 126209072
126 139919922
127 155017210
128 171720795
129 190123306
130 210461355
131 232842515
132 257576152
133 284782804
134 314798863
135 347830507
136 384237587
137 424264376
138 468370536
139 516841621
140 570182621
141 628809507
142 693274534
143 764070905
144 841885125
145 927319664
146 1021107603
147 1124076924
148 1237045795
149 1360970096
150 1496882371
151 1645919359
152 1809216916
153 1988248932
154 2184308893
155 2399096583
156 2634229989
157 2891724178
158 3173381845
159 3481729339
160 3818867145
161 4187695672
162 4590803608
163 5031640867
164 5513115403
165 6039458343
166 6614106908
167 7241884655
168 7927037239
169 8675235744
170 9491330005
171 10382155743
172 11353482808
173 12413121649
174 13568078987
175 14827566540
176 16199625153
177 17695219121
178 19323982910
179 21098361246
180 23030070006
181 25133655286
182 27422672722
183 29914307429
184 32624730002
185 35573546378
186 38780143622
187 42267476751
188 46058023195
189 50178705725
190 54656299224
191 59521546482
192 64806300972
193 70546579785
194 76779216675
195 83546403724
196 90891789279
197 98863627376
198 107513595299
199 116898010564
200 127076815369
201 138115660956
202 150085251531
203 163060985257
204 177125840849
205 192368002014
206 208883410778
207 226774717801
208 246154736163
209 267141348661
210 289866523119
211 314467826806
212 341097752525
213 369916222694
214 401101618503
215 434838113317
216 471333316336
217 510801992158
218 553483698887
219 599627692588
220 649513277254
221 703427757540
222 761694950387
223 824649575488
224 892664681666
225 966128266444
226 1045473854523
227 1131148756964
228 1223654411318
229 1323510740185
230 1431295016097
231 1547608860841
232 1673121306311
233 1808526046934
234 1954594754898
235 2112132497383
236 2282026763627
237 2465207360765
238 2662700821836
239 2875578255069
240 3105021706835
241 3352271811080
242 3618686308789
243 3905696383621
244 4214868698063
245 4547850907297
246 4906444006738
247 5292552203000
248 5708243160851
249 6155709062845
250 6637331988016
251 7155632839911
252 7713346021330
253 8313379594344
254 8958869470377
255 9653158601627
256 10399853755370
257 11202794374263
258 12066115833998
259 12994238229854
260 13991900499958
261 15064175506896
262 16216505529446
263 17454709431804
264 18785020384624
265 20214124073148
266 21749157882773
267 23397782359336
268 25168183601820
269 27069136716394
270 29110007207279
271 31300860118824
272 33652409057918
273 36176170910689
274 38884416103602
275 41790320444641
276 44907907971965
277 48252265138520
278 51839420460559
279 55686612202155
280 59812174521348
281 64235804245180
282 68978432524833
283 74062578916060
284 79512141863122
285 85352819615313
286 91611914834533
287 98318752530826
288 105504473355074
289 113202553666826
290 121448513242681
291 130280508210908
292 139739065547723
293 149867677143882
294 160712516625280
295 172323165907788
296 184752238059072
297 198056178753212
298 212294946831207
299 227532806421511
300 243837999846742
301 261283697045234
302 279947573341342
303 299912838061702
304 321267905715275
305 344107405058305
306 368531863767339
307 394648890396983
308 422572790574567
309 452425807344675
310 484337895562743
311 518447932344809
312 554903517007053
313 593862402023421
314 635492233155224
315 679972036262382
316 727492195897677
317 778255881960117
318 832479113747915
319 890392417962756
320 952240896489503
321 1018285909997922
322 1088805489182274
323 1164095953191203
324 1244472445422432
325 1330270832891588
326 1421848319070455
327 1519585325420576
328 1623886615891814
329 1735183068698849
330 1853933022371260
331 1980624372647703
332 2115776094787578
333 2259940298009672
334 2413704438327831
335 2577693256414915
336 2752571321090874
337 2939045347230032
338 3137867077078056
339 3349835510525010
340 3575800718303865
341 3816665973101403
342 4073392006528874
343 4346999648288724
344 4638574595157586
345 4949269940844827
346 5280312196867750
347 5633003732507172
348 6008729448014397
349 6408959843448651
350 6835258466764138
351 7289284897678353
352 7772803777124471
353 8287687857961047
354 8835927844725650
355 9419636345013814
356 10041058791837692
357 10702577358726814
358 11406723944172907
359 12156184330802957
360 12953812245143982
361 13802634783166905
362 14705867925304658
363 15666922122851313
364 16689420395868423
365 17777204512016968
366 18934354502502614
367 20165196590201472
368 21474324712771929
369 22866608889971244
370 24347219985602145
371 25921639277192443
372 27595684961201128
373 29375524295453748
374 31267702730578790
375 33279156996550900
376 35417248345210503
377 37689777613730692
378 40105020796941356
379 42671747723203298
380 45399261094982812
381 48297416969406954
382 51376668846167904
383 54648091493038165
384 58123427948742962
385 61815118516326236
386 65736352366300051
387 69901099499205045
388 74324168778908895
389 79021244981140384
390 84008950692656791
391 89304890629209526
392 94927719605679944
393 100897191619844600
394 107234235958932689
395 113961013884802172
396 121100999934554067
397 128679048669869431
398 136721484141413658
399 145256173911104880
400 154312628905399688
401 163922088586505884
402 174117627761748426
403 184934255730036166
404 196409034071866558
405 208581186502519303
406 221492230288321167
407 235186101829247438
408 249709297823334271
409 265111019892632862
410 281443330654580536
411 298761313952915363
412 317123248730463331
413 336590791391439800
414 357229163343180841
415 379107359076903879
416 402298354361502029
417 426879336210728997
418 452931935016428651
419 480542485050795084
420 509802275825089172
421 540807847499408006
422 573661270404206529
423 608470471355246843
424 645349545313058772
425 684419123397449448
426 725806712100086939
427 769647107859842483
428 816082775449061837
429 865264305227821622
430 917350835150037335
431 972510564765090799
432 1030921216252425114
433 1092770610741656897
434 1158257183640449725
435 1227590619392977471
436 1300992426683705344
437 1378696649405495152
438 1460950497579422829
439 1548015141352408588
440 1640166416945717645
441 1737695700674942423
442 1840910696727967196
443 1950136413578950820
444 2065716030919599613
445 2188011986055478599
446 2317406945256487444
447 2454304998305580143
448 2599132742489486549
449 2752340614231285325
450 2914404084303824961
451 3085825136381689665
452 3267133605643558814
453 3458888804189925987
454 3661681014282243934
455 3876133296380864714
456 4102903139283827151
457 4342684462651898356
458 4596209465027119728
459 4864250824702031644
460 5147623759349856529
461 5447188471168796636
462 5763852424812888298
463 6098573051692975172
464 6452360299222433451
465 6826279602313101260
466 7221454722756848132
467 7639071045955301876
468 8080378723432401866
469 8546696315018891722
470 9039414301138266977
471 9559999086456330357
472 10109996906850876152
473 10691038267565425927
474 11304842268393630842
475 11953221502098467211
476 12638086883486330872
477 13361453034451842227
478 14125443650020468521
479 14932297463753942226
480 15784374186847265964
481 16684161089295814886
482 17634279621169930908
483 18637492650159984351
484 19696711811022965111
485 20815005517384671884
486 21995607094871413128
487 23241923615479949700
488 24557544952396688401
489 25946253499690446268
490 27412034209656694987
491 28959085349282771236
492 30591829601033831550
493 32314925921423991569
494 34133281882878075578
495 36052066724161373711
496 38076725017681422992
497 40212991104770182287
498 42466904203161494162
499 44844824319319827034
500 47353449020324242194
501 49999830953512718449
502 52791396397504427368
503 55735964635271012506
504 58841768447336448350
505 62117475463573938343
506 65572210885926950785
507 69215581002866879243
508 73057698296664395936
509 77109207438066571517
510 81381313002344988932
511 85885808118119980423
512 90635105160118566722
513 95642267305953500935
514 100921042419823748283
515 106485897923209620201
516 112352058177798191896
517 118535542911109681630
518 125053208566680938822
519 131922790638286676834
520 139162949275872494208
521 146793316052143499992
522 154834544244755406700
523 163308360363874186076
524 172237619714367962188
525 181646363163818918966
526 191559878378961322614
527 202004762510147236299
528 213008989667433836905
529 224601979976013580813
530 236814674063557296315
531 249679609139339028056
532 263231001028260845120
533 277504828143298132256
534 292538921830964051477
535 308373058853601953468
536 325049061041250805402
537 342610897163947675845
538 361104792612161394566
539 380579341788028882746
540 401085628833257401311
541 422677351380462784137
542 445410953611337810599
543 469345762545934570429
544 494544134410488798857
545 521071604922651704472
546 548997050328244448680
547 578392852824534746770
548 609335077918340055814
549 641903656563580916353
550 676182580158300522399
551 712260101285722423359
552 750228948158960522312
553 790186545502416840955
554 832235250586920042830
555 876482596343495795049
556 923041550760783373483
557 972030784684709416733
558 1023574956967249075359
559 1077805009028653580118
560 1134858478526474799283
561 1194879823453452373223
562 1258020766707422474668
563 1324440652901645097347
564 1394306827000703465947
565 1467795026621565147621
566 1545089798328980639379
567 1626384929092262614475
568 1711883903420289235810
569 1801800378105206044667
570 1896358684364239700412
571 1995794349587859044878
572 2100354649155107983642
573 2210299180007733578864
574 2325900466392142768599
575 2447444590621327152125
576 2575231858225116740413
577 2709577490862433704014
578 2850812356932812916560
579 2999283732984927410330
580 3155356105449848999235
581 3319412007508652618192
582 3491852899156513052545
583 3673100086114650374422
584 3863595686104912921990
585 4063803638121866340999
586 4274210762438675730714
587 4495327869297040759698
588 4727690922081820929775
589 4971862254175146363609
590 5228431845539211057292
591 5498018658619271346022
592 5781272038316925073334
593 6078873178696248153025
594 6391536658717575980519
595 6720012051310003726967
596 7065085608181578214122
597 7427582025494220828656
598 7808366290940681211922
599 8208345621312365727124
600 8628471488003860771354
601 9069741741735602628483
602 9533202833816705313418
603 10019952146585623349666
604 10531140427858665145893
605 11067974346947882306424
606 11631719163390276568829
607 12223701528658098397289
608 12845312411692238510605
609 13498010170509285413866
610 14183323757495886999232
611 14902856086702183038756
612 15658287546419400069680
613 16451379688578894683350
614 17283979077915850844716
615 18158021334978096959427
616 19075535352044285626688
617 20038647723262165918444
618 21049587363130498758044
619 22110690358453975165914
620 23224405027471337847151
621 24393297234570413845710
622 25620055929684840184812
623 26907498969250435746461
624 28258579182473420022977
625 29676390743950701898962
626 31164175816271507573081
627 32725331527512285610016
628 34363417242031642704913
629 36082162199296502783286
630 37885473473405426835398
631 39777444332628216165493
632 41762362951911736020756
633 43844721562134899471440
634 46029225983436937027723
635 48320805637409722995495
636 50724623979792808487692
637 53246089453159894975616
638 55890866902319650311293
639 58664889556971432595083
640 61574371518359034573885
641 64625820866800020450518
642 67826053321456655665308
643 71182206573795790033578
644 74701755228571874953569
645 78392526479091059097640
646 82262716444781062515261
647 86320907311263944266488
648 90576085196390858761515
649 95037658886689913818622
650 99715479371932314808207
651 104619860327859889916676
652 109761599469460860334399
653 115152000939188605258389
654 120802898649605674002936
655 126726680748112788539399
656 132936315130268441461920
657 139445376174894730419270
658 146268072623131423566677
659 153419276789967249553067
660 160914555029616406114670
661 168770199645425770895665
662 177003262176206101494586
663 185631588254864840370224
664 194673853968820366899552
665 204149603933767664745822
666 214079291012993277776219
667 224484317894090707669047
668 235387080470383366494197
669 246811013243756166141958
670 258780636696159705979439
671 271321606862705431591350
672 284460767060800355589745
673 298226202006081160049481
674 312647294290829849058724
675 327754783459500734656886
676 343580827660760572991967
677 360159068126969222071553
678 377524696473555851583774
679 395714525064314004321521
680 414767060463515337490830
681 434722580223946435429157
682 455623213040266291197488
683 477513022532898643069209
684 500438094712757595915340
685 524446629383446612672797
686 549589035568863168620120
687 575918031225098943607711
688 603488747338850508763545
689 632358836687705373417956
690 662588587394518288936133
691 694241041539063954986481
692 727382119007769094743582
693 762080746846014995904385
694 798408994316037602686656
695 836442213941156958801906
696 876259188781216701627141
697 917942286203758822240910
698 961577618457173377136608
699 1007255210311935992478363
700 1055069174107088882147084
701 1105117892485373387102913
702 1157504209209887367130714
703 1212335628325425801138904
704 1269724522134367012808105
705 1329788348252349734900413
706 1392649876255698003633653
707 1458437424204867587051981
708 1527285105627868741679554
709 1599333087224905886434213
710 1674727857972457380731747
711 1753622509892936713679273
712 1836177031223149994374494
713 1922558612269732206140173
714 2012941964776767550044349
715 2107509655068266690529576
716 2206452451905646264985168
717 2309969689332885444172690
718 2418269645519127272767739
719 2531569937899745662716510
720 2650097935739850952905218
721 2774091190396149611057791
722 2903797884539435049379871
723 3039477300631896836657698
724 3181400310008967642344783
725 3329849882897063248570562
726 3485121620857660870477413
727 3647524311967518888025922
728 3817380510389701739950260
729 3995027140677830173583737
730 4180816128574893282560457
731 4375115058700649054185135
732 4578307861060234138637715
733 4790795526753861755867301
734 5012996855015294394632981
735 5245349232011100773264286
736 5488309443658282136209558
737 5742354522964625884318193
738 6007982634355188481725374
739 6285713995490338867607273
740 6576091839267086121657965
741 6879683416590757222132825
742 7197081042764990969595243
743 7528903188188160578071108
744 7875795616451353861072242
745 8238432570549393371125016
746 8617518010567418368736725
747 9013786903676783744162152
748 9428006569988780827360848
749 9860978085242309830254620
750 10313537744167448387135354
751 10786558585559119032288065
752 11280951983214724589476415
753 11797669303946531064568751
754 12337703637045125405350343
755 12902091596601173260451422
756 13491915201410252435610034
757 14108303833975712707804264
758 14752436283696372675326249
759 15425542876005094273469336
760 16128907692809014334237849
761 16863870886266619464665614
762 17631831091666607598739938
763 18434247941617648534863548
764 19272644687737582547554485
765 20148610932397287068073026
766 21063805477023206160366516
767 22019959289878619276145479
768 23018878600317950978289897
769 24062448122700766011533840
770 25152634417453509730093597
771 26291489392936601226538732
772 27481153955983933586383141
773 28723861815258683651700011
774 30021943445878281267067817
775 31377830219837804419907392
776 32794058711265331164652901
777 34273275181669079541527915
778 35818240254666534111067749
779 37431833786000044295727894
780 39117059939028850310204826
781 40877052472043677047408295
782 42715080248281738786248757
783 44634552975818745835104727
784 46639027188774543557195474
785 48732212477851002491586539
786 50917977982481580336278483
787 53200359153354011181706350
788 55583564798404640974858727
789 58071984422131096605628326
790 60670195872008808556843171
791 63382973302949489960132116
792 66215295474610186508323874
793 69172354393486445553244091
794 72259564315587147684282010
795 75482571123024647385206838
796 78847262091172032239439396
797 82359776061125941649542585
798 86026514035373771632467526
799 89854150212722135900470400
800 93849643481588062899236928
801 98020249389500543897721755
802 102373532608990285756542753
803 106917379919503032817620651
804 111660013727053219508123512
805 116610006142971220060240150
806 121776293644939774460897717
807 127168192343949182591891899
808 132795413881727383915911393
809 138668081984543587320047186
810 144796749699847537251199070
811 151192417343860916426371357
812 157866551188420711727467082
813 164831102918059135406802339
814 172098529887360529939537961
815 179681816212436304128974026
816 187594494728937465496333608
817 195850669853285751364253899
818 204465041381840059477104704
819 213452929268279938262334123
820 222830299416156052775977740
821 232613790530469388330665751
822 242820742068219039915268919
823 253469223335383309635547765
824 264578063773173320864833140
825 276166884485517766059100193
826 288256131053494933914692702
827 300867107693144100968190206
828 314022012806138200144248727
829 327743975984302586586421942
830 342057096521136075483086630
831 356986483496904554187639723
832 372558297494186043863364114
833 388799794015996521635818407
834 405739368668147179015576967
835 423406604183679287988323544
836 441832319355702286307686225
837 461048619963409836111837455
838 481088951762406663083188440
839 501988155631025392707646685
840 523782524949815987996703065
841 546509865313040304890320238
842 570209556655324591910730236
843 594922617900863144649657299
844 620691774224547277935548393
845 647561527040961030946551407
846 675578226818300803924354489
847 704790148842090239859392054
848 735247572033369360667802779
849 767002860956801060934985576
850 800110551131406786361720675
851 834627437789943922981305184
852 870612668209406335956970979
853 908127837769769700464467652
854 947237089873210604871702653
855 988007219893952690172001869
856 1030507783301320489194875048
857 1074811208139222480689321835
858 1120992912017047525517393445
859 1169131423809009370700250635
860 1219308510229374504710635506
861 1271609307496658366345314291
862 1326122458267547431616946954
863 1382940254069766176804465919
864 1442158783430397477001034025
865 1503878085946026029119043862
866 1568202312507094107630950292
867 1635239891942620456371935554
868 1705103704314747114328141448
869 1777911261149205674320542256
870 1853784892851134806739151594
871 1932851943613616668837309084
872 2015244974088607675822872547
873 2101101972151985817586805701
874 2190566572054241938646036563
875 2283788282313177160093002788
876 2380922722665402866769282917
877 2482131870459414694125480790
878 2587584316832761300680781929
879 2697455533086108427072761975
880 2811928147624580914539083817
881 2931192233909652478743235982
882 3055445609823901515166530044
883 3184894148924664219126529466
884 3319752104021545660524220823
885 3460242443590860137140944353
886 3606597201497378742127020578
887 3759057840574181876116350031
888 3917875630571253720476689916
889 4083312041064292202631446076
890 4255639149875692779282362784
891 4435140067644896199738650761
892 4622109379144976220947222193
893 4816853602029383085917747724
894 5019691663656394149804054468
895 5230955396725709893338978602
896 5450990054426917057548588240
897 5680154845890774265638744069
898 5918823492699807302484818141
899 6167384807307130239998515968
900 6426243294183630509517642922
901 6695819774605205982891453599
902 6976552035965951217481512356
903 7268895506598875248303748552
904 7573323957061633978339363747
905 7890330228940814393444217411
906 8220426992212032835132116685
907 8564147532287463306661477438
908 8922046567870712093409659861
909 9294701100837223550661980915
910 9682711299350164363991744707
911 10086701415519369139820976107
912 10507320738913143290397195703
913 10945244587327629386865637570
914 11401175336227249882829787671
915 11875843488368239822819443439
916 12370008785131731615249274753
917 12884461361189611557448939424
918 13420022944154304589405069977
919 13977548100956625891269568474
920 14557925532732731490749494425
921 15162079420097418462349363296
922 15790970820726250203773061396
923 16445599121262133618161301150
924 17127003545624337498974747430
925 17836264721886170413273295584
926 18574506309961626192320395229
927 19342896692432504663239243222
928 20142650730933040948029005901
929 20975031590595870405749854833
930 21841352635170018681017853714
931 22742979395502312550527918755
932 23681331614195489502817153326
933 24657885369339706238589747220
934 25674175280351182530948225896
935 26731796799029355027839416675
936 27832408589107058718199494180
937 28977734997638851887528658038
938 30169568621754390344395761078
939 31409772974377139171090674364
940 32700285252709900116225088175
941 34043119213354896886524049944
942 35440368158168994695437818095
943 36894208035012988084853192392
944 38406900657809610158618308546
945 39980797050386417099839898128
946 41618340918859651987813809591
947 43322072257368556192573782521
948 45094631092287274806324309999
949 46938761370086626434646457642
950 48857314994363230813916176590
951 50853256017602637026195581986
952 52929664993618109476969662762
953 55089743496646987034706881298
954 57336818813506188744835268324
955 59674348815240690832168040022
956 62105927015151124287785755646
957 64635287820124680997608488322
958 67266311982681725401885007656
959 70003032261179624339111358630
960 72849639296155794869202685851
961 75810487710814134738101881185
962 78890102444237918260480705511
963 82093185325942849644266581586
964 85424621901005685118389569783
965 88889488515026360080060912596
966 92493059668863892199596293687
967 96240815653104337845171935260
968 100138450472945948015155378672
969 104191880074217300585703529545
970 108407250882021519271108801976
971 112790948663524191008474862996
972 117349607727249919407492851414
973 122090120471276257976469290184
974 127019647293612427478918262977
975 132145626878092619786357002960
976 137475786870071185134136110803
977 143018154956247094160657378894
978 148781070363982576225961225201
979 154773195795526337702354067272
980 161003529813647938701187147536
981 167481419695262178659185700378
982 174216574770786863003083788514
983 181219080267052989503889303260
984 188499411672842152553923403632
985 196068449646215733926459331974
986 203937495484122766661822732046
987 212118287174901194193459470657
988 220623016055688221881426932273
989 229464344096895309240148589992
990 238655421837407853981786506041
991 248209906994335511238500534472
992 258141983772719027086230370704
993 268466382900818081809738973811
994 279198402418274946045504241891
995 290353929244691411488246496601
996 301949461557943762974031078314
997 314002132011845574739189319207
998 326529731824640430017742149424
999 339550735770163611334618554709
1000 353084328105487770092735994800