0 1
1 1
2 2
3 3
4 4
5 6
6 8
7 12
8 14
9 22
10 24
11 38
12 39
13 63
14 62
15 102
16 95
17 159
18 144
19 244
20 212
21 366
22 309
23 540
24 442
25 784
26 626
27 1125
28 873
29 1591
30 1209
31 2229
32 1653
33 3089
34 2245
35 4243
36 3019
37 5776
38 4035
39 7806
40 5348
41 10466
42 7051
43 13944
44 9229
45 18454
46 12022
47 24282
48 15565
49 31766
50 20063
51 41347
52 25722
53 53537
54 32847
55 69007
56 41746
57 88539
58 52862
59 113127
60 66657
61 143947
62 83768
63 182476
64 104873
65 230446
66 130889
67 290027
68 162797
69 363765
70 201902
71 454801
72 249620
73 566840
74 307789
75 704414
76 378428
77 872843
78 464122
79 1078614
80 567721
81 1329335
82 692828
83 1634194
84 843448
85 2003983
86 1024571
87 2451663
88 1241775
89 2992404
90 1501945
91 3644364
92 1812793
93 4428765
94 2183758
95 5370854
96 2625455
97 6500131
98 3150749
99 7851541
100 3774153
101 9465805
102 4513138
103 11391020
104 5387430
105 13683140
106 6420629
107 16407966
108 7639430
109 19641970
110 9075563
111 23474789
112 10764963
113 28010360
114 12750129
115 33370198
116 15079202
117 39694968
118 17808857
119 47148591
120 21003331
121 55920569
122 24737891
123 66231146
124 29097874
125 78334437
126 34182895
127 92525125
128 40105857
129 109142658
130 46998093
131 128579659
132 55008444
133 151287757
134 64309441
135 177788177
136 75096565
137 208679433
138 87595738
139 244650919
140 102062784
141 286493041
142 118792552
143 335114298
144 138118758
145 391554850
146 160424978
147 457008007
148 186145106
149 532837876
150 215776684
151 620606723
152 249882092
153 722097863
154 289104769
155 839350000
156 334171514
157 974687191
158 385912069
159 1130761959
160 445262989
161 1310593803
162 513291385
163 1517623702
164 591200734
165 1755763496
166 680359748
167 2029464133
168 782310829
169 2343779255
170 898804986
171 2704450611
172 1031813838
173 3117988988
174 1183571971
175 3591781545
176 1356593327
177 4134194573
178 1553722674
179 4754707444
180 1778157767
181 5464043346
182 2033511657
183 6274336328
184 2323842309
185 7199296285
186 2653728190
187 8254417702
188 3028307114
189 9457187426
190 3453368044
191 10827344226
192 3935401729
193 12387140570
194 4481711890
195 14161665039
196 5100480826
197 16179170286
198 5800904236
199 18471473872
200 6593275258
201 21074368308
202 7489148055
203 24028117508
204 8501445039
205 27377969329
206 9644654952
207 31174769765
208 10934969048
209 35475600885
210 12390521099
211 40344540743
212 14031559116
213 45853455955
214 15880736212
215 52082939142
216 17963326446
217 59123292914
218 20307576729
219 67075684917
220 22944977254
221 76053365480
222 25910687344
223 86183090244
224 29243872519
225 97606624385
226 32988219780
227 110482490619
228 37192356667
229 124987825695
230 41910473907
231 141320525585
232 47202845005
233 159701530740
234 53136578535
235 180377456929
236 59786259979
237 203623403888
238 67234860346
239 229746175305
240 75574527283
241 259087727020
242 84907681179
243 292029103292
244 95347988133
245 328994661049
246 107021681779
247 370456877762
248 120068756372
249 416941518817
250 134644560041
251 469033499831
252 150921255067
253 527383200681
254 169089736179
255 592713605040
256 189361414465
257 665828001283
258 211970525844
259 747618669420
260 237176305225
261 839076260735
262 265265762838
263 941300351391
264 296556329578
265 1055510853902
266 331399192599
267 1183060823727
268 370182508649
269 1325450320441
270 413335409123
271 1484341933232
272 461331895670
273 1661577596168
274 514695645779
275 1859197383976
276 574004728553
277 2079459888481
278 639897365221
279 2324864948236
280 713077629315
281 2598178305017
282 794322347127
283 2902459063638
284 884487976301
285 3241089491880
286 984518865797
287 3617808153342
288 1095455545304
289 4036745885019
290 1218444603372
291 4502465732454
292 1354748663790
293 5020006329586
294 1505758190272
295 5594929985899
296 1673003475597
297 6233374932628
298 1858168737900
299 6942113158961
300 2063106511019
301 7728613271615
302 2289854462201
303 8601109985342
304 2540652643628
305 9568679662484
306 2817963541865
307 10641323726483
308 3124492732733
309 11830059342820
310 3463212765164
311 13147019437252
312 3837387862835
313 14605561444695
314 4250602351218
315 16220387119894
316 4706790166029
317 18007672811809
318 5210268661957
319 19985212850223
320 5765773822201
321 22172575449452
322 6378500436803
323 24591274136633
324 7054144070773
325 27264954148889
326 7798948772344
327 30219597194860
328 8619757045399
329 33483744082599
330 9524066455932
331 37088739076046
332 10520089072201
333 41068995542611
334 11616818577876
335 45462287283309
336 12824100904572
337 50310065223299
338 14152713737839
339 55657804433303
340 15614450369016
341 61555381310191
342 17222213811967
343 68057486577511
344 18990116250742
345 75224074103223
346 20933590368670
347 83120851980522
348 23069507184630
349 91819816121649
350 25416307640106
351 101399833677974
352 27994142098501
353 111947276851603
354 30825025762092
355 123556715438861
356 33933003666682
357 136331669033141
358 37344334109488
359 150385428397941
360 41087683630554
361 165841947428190
362 45194343337676
363 182836816514873
364 49698459129249
365 201518319329907
366 54637286633053
367 222048585381347
368 60051462808514
369 244604841049237
370 65985306177451
371 269380773205315
372 72487136982382
373 296588009018496
374 79609630499680
375 326457728015627
376 87410194132146
377 359242411072102
378 95951382899174
379 395217744705509
380 105301343232430
381 434684686593253
382 115534301246056
383 477971713321876
384 126731084631207
385 525437257841461
386 138979696053743
387 577472360604011
388 152375926425028
389 634503543708736
390 167024027811431
391 696995935500206
392 183037433533931
393 765456657092760
394 200539547327736
395 840438502237036
396 219664588259316
397 922543924625643
398 240558515594307
399 1012429368549295
400 263380019450107
401 1110809960102966
402 288301603995318
403 1218464600082474
404 315510748139938
405 1336241479377268
406 345211173343863
407 1465064063991559
408 377624202578542
409 1605937574835072
410 412990243239837
411 1759956016222573
412 451570377153034
413 1928309783321348
414 493648093979054
415 2112293910381426
416 539531150269608
417 2313316995906711
418 589553594399553
419 2532910875653528
420 644077938745815
421 2772741086655753
422 703497523685289
423 3034618203469730
424 768239053963830
425 3320510098078480
426 838765356829170
427 3632555216575949
428 915578341714114
429 3973076933625381
430 999222216247722
431 4344599091488375
432 1090286937691530
433 4749862795892661
434 1189411960559660
435 5191844591132809
436 1297290258970945
437 5673776099815715
438 1414672691140787
439 6199165267658033
440 1542372684152682
441 6771819313963307
442 1681271313851899
443 7395869548838126
444 1832322757775683
445 8075798175616932
446 1996560204236033
447 8816467263133300
448 2175102195515305
449 9623150027039157
450 2369159497506308
451 10501564631990605
452 2580042474091964
453 11457910677863171
454 2809169068911130
455 12498908612968963
456 3058073373497786
457 13631842265393480
458 3328414895941156
459 14864604771014259
460 3621988510228940
461 16205748121709520
462 3940735213254129
463 17664536653277784
464 4286753671351195
465 19251004733950086
466 4662312697721921
467 20976019019941100
468 5069864644957027
469 22851345582344087
470 5512059870075290
471 24889722325433980
472 5991762259441962
473 27104937050868256
474 6512065988941452
475 29511911649463970
476 7076313510828348
477 32126792832851711
478 7688114962769064
479 34967049957232008
480 8351368995635747
481 38051580418472119
482 9070285238094733
483 41400823251372762
484 9849408401019527
485 45036881489527306
486 10693644264993096
487 48983654011095512
488 11608287561890114
489 53266977515685023
490 12599052022124000
491 57914779463492639
492 13672102608261015
493 62957242724380918
494 14834090238317426
495 68426982888921949
496 16092189031272505
497 74359239107010724
498 17454136413687069
499 80792079544603685
500 18928276134179183
501 87766622459603429
502 20523604564623353
503 95327274145819383
504 22249820351823990
505 103521984901960915
506 24117377843380394
507 112402524455404961
508 26137544371803676
509 122024778176791750
510 28322461870945227
511 132449065722128919
512 30685212932848738
513 143740483643809044
514 33239891835703631
515 155969273843614843
516 36001680679394396
517 169211219645049454
518 38986931222913389
519 183548071627787146
520 42213252593611001
521 199068005272083875
522 45699605533999284
523 215866112864258259
524 49466403395331893
525 234044932020788494
526 53535620624082028
527 253715013634021680
528 57930908996436248
529 274995531952151290
530 62677722437314308
531 298014939997672587
532 67803450732680140
533 322911673443452362
534 73337563073294812
535 349834906608698641
536 79311761801105209
537 378945364158706777
538 85760147410859859
539 410416192692995395
540 92719395250651827
541 444433896337611453
542 100228945102716818
543 481199341121299337
544 108331204172366627
545 520928832859231745
546 117071764811240344
547 563855274002634736
548 126499637600157876
549 610229404872117761
550 136667501280910886
551 660321135506132296
552 147631970274808354
553 714420974335467715
554 159453881460940908
555 772841560795247015
556 172198601081943964
557 835919308990470700
558 185936353656931495
559 904016170529048063
560 200742573919082752
561 977521524670496426
562 216698283890424503
563 1056854205045152794
564 233890496283514017
565 1142464672269582307
566 252412646604748108
567 1234837343010627943
568 272365055347059190
569 1334493086165805217
570 293855422941940441
571 1441991898188999838
572 316999359085856276
573 1557935769757562771
574 341920949443589138
575 1682971757488530125
576 368753361604156619
577 1817795274641214283
578 397639493666392296
579 1963153616421515542
580 428732667628442294
581 2119849735807048936
582 462197371380052382
583 2288746287676754646
584 498210051813542261
585 2470769959418430773
586 536959963327531756
587 2666916108260806448
588 578650074629835562
589 2878253726068294485
590 623498038648707212
591 3105930754641184105
592 671737228905061939
593 3351179775175042990
594 723617847757460600
595 3615324098097030004
596 779408110381641624
597 3899784280245532144
598 839395510575190557
599 4206085099213687171
600 903888172829662727
601 4535863015587100796
602 973216297525093176
603 4890874156982813947
604 1047733704350855608
605 5273002858893669882
606 1127819481668428262
607 5684270800880481398
608 1213879747673274821
609 6126846777966459711
610 1306349532040631914
611 6603057151031353365
612 1405694784769351117
613 7115397021564119684
614 1512414521999737165
615 7666542180526534585
616 1627043116494063730
617 8259361882929554294
618 1750152743784019884
619 8896932504622826425
620 1882355992780974344
621 9582552139976485887
622 2024308653236189811
623 10319756204598491764
624 2176712690104044093
625 11112334109789047827
626 2340319418751770316
627 11964347081528186039
628 2515932892495679142
629 12880147199787011134
630 2704413518158837245
631 13864397740754202899
632 2906681912748398921
633 14922094908060981776
634 3123723018918664152
635 16058591046680237615
636 3356590494152262805
637 17279619437237304671
638 3606411393543121905
639 18591320776945413299
640 3874391163191844945
641 20000271458092990044
642 4161818966591729860
643 21513513764475223438
644 4470073363369100349
645 23138588111618261716
646 4800628365562311378
647 24883567467218256109
648 5155059893465965037
649 26757094094520721199
650 5535052659380381375
651 28768418773177458994
652 5942407504305249476
653 30927442659387572101
654 6379049219465741592
655 33244761960328165721
656 6847034881115678595
657 35731715606245678422
658 7348562734495452306
659 38400436118331805501
660 7885981659237791642
661 41263903880121145763
662 8461801256583272668
663 44336005036636875279
664 9078702595046060634
665 47631593256542383089
666 9739549659931275007
667 51166555610991312504
668 10447401548252707229
669 54957882835506357250
670 11205525460115332423
671 59023744261830467895
672 12017410533650404280
673 63383567721155654869
674 12886782580929610881
675 68058124743182996228
676 13817619778194921646
677 73069621391996796285
678 14814169374976608567
679 78441795105512173763
680 15880965482482110781
681 84200017924122204884
682 17022848013853868567
683 90371406523001840204
684 18244982844620559513
685 96984939484040183138
686 19552883274951037854
687 104071582275618579812
688 20952432870983836766
689 111664420432961860767
690 22449909776957336557
691 119798801467860235428
692 24052012585491551541
693 128512486064450107492
694 25765887869100878303
695 137845809158093708528
696 27599159471634872553
697 147841851526109611430
698 29559959675467412589
699 158546622564244119637
700 31656962355900943735
701 170009254958801178794
702 33899418252900480128
703 182282212014844937835
704 36297192485989782331
705 195421508441780362196
706 38860804458458840228
707 209486945454111106182
708 41601470292870681428
709 224542361091552525775
710 44531147961998520204
711 240655896725875569833
712 47662585275344171189
713 257900280774422416599
714 51009370905530449184
715 276353130710935346544
716 54585988635130185810
717 296097274523868456442
718 58407875030826447750
719 317221092851446621566
720 62491480748397835154
721 339818883090107580498
722 66854335700754533413
723 363991246861439680996
724 71515118318273113817
725 389845502298928464063
726 76493729162039672597
727 417496122714797174755
728 81811369148163352499
729 447065203293352124555
730 87490622675568670105
731 478682957567953287167
732 93555545947880022245
733 512488245536020224724
734 100031760817422732634
735 548629135390308350192
736 106946554478364843488
737 587263500954530070401
738 114328985376906774814
739 628559657049885616314
740 122209995706382671108
741 672697035142999447694
742 130622530899832752520
743 719866901780642506328
744 139601666533703604347
745 770273122456380965805
746 149184743105215756424
747 824132973727489566750
748 159411509148388518683
749 881678006558000112946
750 170324273207192992579
751 943154964057420556969
752 181968065188347987504
753 1008826756962126511808
754 194390807674809207637
755 1078973500422961385718
756 207643497786910919060
757 1153893615862412813901
758 221780400242211436433
759 1233905001906804518557
760 236859252273178556934
761 1319346278623855229127
762 252941481132052048687
763 1410578109566554801350
764 270092434922831941457
765 1507984606377323559631
766 288381627577263157553
767 1611974821008878785616
768 307882998805221337177
769 1722984330902743795994
770 328675189934221189769
771 1841476922804354059916
772 350841836569675786341
773 1967946381213508753838
774 374471879099988745606
775 2102918387846639248093
776 399659892091347695913
777 2246952538846656150815
778 426506433718500306051
779 2400644486898179044909
780 455118416403029780149
781 2564628215809460721343
782 485609499941925192024
783 2739578455593807107537
784 518100508439571816765
785 2926213246536285895283
786 552719872478429687991
787 3125296661258184433311
788 589604097999816770642
789 3337641694300012757084
790 628898263500327144200
791 3564113329332074947112
792 670756547192193862613
793 3805631794671866111094
794 715342785923211072519
795 4063176018444428996421
796 762831067702156882021
797 4337787295361244208784
798 813406359837499956927
799 4630573177826669347106
800 867265174756074338246
801 4942711604797715503589
802 924616275746274935745
803 5275455282641764480780
804 985681424938952448732
805 5630136333040016780085
806 1050696176034724611417
807 6008171223898433936596
808 1119910714366064842516
809 6411066000127653668146
810 1193590747097551536491
811 6840421832173401437217
812 1272018446459769599840
813 7297940901186411309098
814 1355493449148869778514
815 7785432640859124585991
816 1444333915129980864730
817 8304820357084248270917
818 1538877649342891435672
819 8858148247860202619005
820 1639483289930501732517
821 9447588847130594563282
822 1746531566896921348375
823 10075450917661513127454
824 1860426635242091619962
825 10744187819472370865051
826 1981597486935046939468
827 11456406381916085785796
828 2110499446248111987183
829 12214876309083453910949
830 2247615753321415440609
831 13022540149968584442398
832 2393459241009992125526
833 13882523866597705334636
834 2548574110447976195735
835 14798148035288259218232
836 2713537810972808173851
837 15772939718178414156810
838 2888963030473406091827
839 16810645044357249024679
840 3075499802463343826100
841 17915242542130664614311
842 3273837736643933405376
843 19090957266399183223765
844 3484708379991384465556
845 20342275767586654879455
846 3708887715913343127869
847 21673961951279286820987
848 3947198809325482635314
849 23091073880484733995664
850 4200514606062143641833
851 24598981575452113741177
852 4469760895380839005056
853 26203385869064305675292
854 4755919444941393334560
855 27910338379190632613512
856 5060031318031605044002
857 29726262662815032593302
858 5383200383495903289426
859 31657976620515944067961
860 5726597029265289405871
861 33712716223697990806357
862 6091462091141700035473
863 35898160641164072246818
864 6479111008988450321196
865 38222458845882014864069
866 6890938223310850343357
867 40694257787463588534239
868 7328421825772997718228
869 43322732220630704383752
870 7793128478114858144321
871 46117616285135386399710
872 8286718614566472047947
873 49089236937903805109447
874 8810951943868847507204
875 52248549343953357796257
876 9367693267722894376208
877 55607174338543493473778
878 9958918633604958510405
879 59177438079451772996434
880 10586721840687553047490
881 62972414014854439276624
882 11253321318836464745784
883 67005967299445991241305
884 11961067401553880031927
885 71292801798771567316834
886 12712450015097172859881
887 75848509829705785038526
888 13510106807011195520303
889 80689624793186269907056
890 14356831738812617049975
891 85833676864163431484296
892 15255584168695339002825
893 91299251912830770360775
894 16209498451782097260067
895 97106053841045359133308
896 17221894086714053147894
897 103274970527981919854125
898 18296286439197835838363
899 109828143590010522508446
900 19436398074547840547430
901 116789042171066901304692
902 20646170733278709430082
903 124182540991953183626047
904 21929777985390039946987
905 132035002899557482783502
906 23291638601211688064835
907 140374366170505854087434
908 24736430678452906713256
909 149230236837722561368566
910 26269106567555876696795
911 158633986323404371236847
912 27894908639437842950870
913 168618854677444113346867
914 29619385942418427396405
915 179220059737037598963603
916 31448411797344433056176
917 190474912540476570912686
918 33388202382918386089681
919 202422939346680347194309
920 35445336365710698561030
921 215106010631216861939330
922 37626775632640127518077
923 228568477450166454968409
924 39939887186467301137381
925 242857315584520147723746
926 42392466268494043072821
927 258022277900682434206597
928 44992760775739412534234
929 274116055386360784483401
930 47749497043890140768402
931 291194447346524827115040
932 50671907070754421012046
933 309316541270462425145792
934 53769757259392895468888
935 328544902909156198675382
936 57053378763923764169004
937 348945777131466279593206
938 60533699525905312656942
939 370589300158899021277824
940 64222278093456876048611
941 393549723811237906797630
942 68131339320694929759730
943 417905652430038573241513
944 72273812049800716328735
945 443740293183070486119840
946 76663368884013530982965
947 471141720491314697996052
948 81314468165117856798366
949 500203155360178798785030
950 86242398275590436538306
951 531023260439326734549829
952 91463324391439661574066
953 563706451679971772431918
954 96994337819051830005039
955 598363227505878736242670
956 102853508055881290594780
957 635110516463644114026118
958 109059937722858602088101
959 674072044370380893355834
960 115633820523640111024784
961 715378722031652207312691
962 122596502394692284319512
963 759169054660768019709226
964 129970546018258252018064
965 805589574191248896731669
966 137779798880042588294497
967 854795295738852377488823
968 146049465062395488273829
969 906950199536858259720804
970 154806180974579293522435
971 962227739739895116040453
972 164078095231631579238519
973 1020811381566207527836409
974 173894952905258235258416
975 1082895168327587523736745
976 184288184381212374841645
977 1148684319978906372712859
978 195290999070766332643472
979 1218395864907066022766775
980 206938484236113433141526
981 1292259306770857965600582
982 219267709204046301643273
983 1370517328300566217509020
984 232317835255822768780901
985 1453426534067725509597838
986 246130231497138437505105
987 1541258234343261214875758
988 260748597027165160945300
989 1634299272274766720213625
990 276219089743273976797650
991 1732852896733060636640421
992 292590462134732665496724
993 1837239683302807813792429
994 309914204438147550870654
995 1947798506024165191956932
996 328244695545893725561012
997 2064887562630445180156906
998 347639362080263400224026
999 2188885456173101756982025
1000 368158846066528672071855