0 1
1 1
2 2
3 2
4 4
5 4
6 8
7 7
8 14
9 12
10 24
11 19
12 39
13 30
14 62
15 45
16 95
17 67
18 144
19 97
20 212
21 139
22 309
23 195
24 442
25 272
26 626
27 373
28 873
29 508
30 1209
31 684
32 1653
33 915
34 2245
35 1212
36 3019
37 1597
38 4035
39 2087
40 5348
41 2714
42 7051
43 3506
44 9229
45 4508
46 12022
47 5763
48 15565
49 7338
50 20063
51 9296
52 25722
53 11732
54 32847
55 14742
56 41746
57 18460
58 52862
59 23025
60 66657
61 28629
62 83768
63 35471
64 104873
65 43820
66 130889
67 53963
68 162797
69 66273
70 201902
71 81156
72 249620
73 99133
74 307789
75 120770
76 378428
77 146785
78 464122
79 177970
80 567721
81 215308
82 692828
83 259891
84 843448
85 313065
86 1024571
87 376326
88 1241775
89 451501
90 1501945
91 540635
92 1812793
93 646193
94 2183758
95 770947
96 2625455
97 918220
98 3150749
99 1091745
100 3774153
101 1295971
102 4513138
103 1535914
104 5387430
105 1817503
106 6420629
107 2147434
108 7639430
109 2533589
110 9075563
111 2984865
112 10764963
113 3511688
114 12750129
115 4125842
116 15079202
117 4841062
118 17808857
119 5672882
120 21003331
121 6639349
122 24737891
123 7760854
124 29097874
125 9061010
126 34182895
127 10566509
128 40105857
129 12308139
130 46998093
131 14320697
132 55008444
133 16644217
134 64309441
135 19323906
136 75096565
137 22411641
138 87595738
139 25965986
140 102062784
141 30053954
142 118792552
143 34751159
144 138118758
145 40143942
146 160424978
147 46329631
148 186145106
149 53419131
150 215776684
151 61537395
152 249882092
153 70826486
154 289104769
155 81446349
156 334171514
157 93578513
158 385912069
159 107427163
160 445262989
161 123223639
162 513291385
163 141227966
164 591200734
165 161734221
166 680359748
167 185072690
168 782310829
169 211616350
170 898804986
171 241783707
172 1031813838
173 276046669
174 1183571971
175 314934342
176 1356593327
177 359042451
178 1553722674
179 409038376
180 1778157767
181 465672549
182 2033511657
183 529784908
184 2323842309
185 602318715
186 2653728190
187 684328892
188 3028307114
189 776998612
190 3453368044
191 881650031
192 3935401729
193 999764335
194 4481711890
195 1132995265
196 5100480826
197 1283193401
198 5800904236
199 1452423276
200 6593275258
201 1642992568
202 7489148055
203 1857473694
204 8501445039
205 2098739073
206 9644654952
207 2369988023
208 10934969048
209 2674789388
210 12390521099
211 3017115097
212 14031559116
213 3401391433
214 15880736212
215 3832540822
216 17963326446
217 4316043666
218 20307576729
219 4857989906
220 22944977254
221 5465153652
222 25910687344
223 6145056855
224 29243872519
225 6906059011
226 32988219780
227 7757435639
228 37192356667
229 8709486304
230 41910473907
231 9773630755
232 47202845005
233 10962539003
234 53136578535
235 12290249079
236 59786259979
237 13772323222
238 67234860346
239 15425991887
240 75574527283
241 17270341447
242 84907681179
243 19326489498
244 95347988133
245 21617810410
246 107021681779
247 24170148651
248 120068756372
249 27012089151
250 134644560041
251 30175216503
252 150921255067
253 33694439195
254 169089736179
255 37608303490
256 189361414465
257 41959382090
258 211970525844
259 46794653960
260 237176305225
261 52165969360
262 265265762838
263 58130508864
264 296556329578
265 64751339753
266 331399192599
267 72097969265
268 370182508649
269 80247009960
270 413335409123
271 89282846036
272 461331895670
273 99298427716
274 514695645779
275 110396072732
276 574004728553
277 122688414563
278 639897365221
279 136299364458
280 713077629315
281 151365242593
282 794322347127
283 168035931801
284 884487976301
285 186476225121
286 984518865797
287 206867207878
288 1095455545304
289 229407862323
290 1218444603372
291 254316720332
292 1354748663790
293 281833772931
294 1505758190272
295 312222444909
296 1673003475597
297 345771864406
298 1858168737900
299 382799219606
300 2063106511019
301 423652454919
302 2289854462201
303 468713079501
304 2540652643628
305 518399367922
306 2817963541865
307 573169704246
308 3124492732733
309 633526377526
310 3463212765164
311 700019559623
312 3837387862835
313 773251803382
314 4250602351218
315 853882768151
316 4706790166029
317 942634546953
318 5210268661957
319 1040297275508
320 5765773822201
321 1147735434974
322 6378500436803
323 1265894503401
324 7054144070773
325 1395808408038
326 7798948772344
327 1538607403968
328 8619757045399
329 1695526879263
330 9524066455932
331 1867916679518
332 10520089072201
333 2057251502097
334 11616818577876
335 2265141922199
336 12824100904572
337 2493346654950
338 14152713737839
339 2743785580065
340 15614450369016
341 3018554197195
342 17222213811967
343 3319938999243
344 18990116250742
345 3650434498856
346 20933590368670
347 4012761358751
348 23069507184630
349 4409886433501
350 25416307640106
351 4845044131331
352 27994142098501
353 5321759988621
354 30825025762092
355 5843875819816
356 33933003666682
357 6415577425471
358 37344334109488
359 7041424178591
360 41087683630554
361 7726381569527
362 45194343337676
363 8475855981308
364 49698459129249
365 9295732889631
366 54637286633053
367 10192417707158
368 60051462808514
369 11172880587588
370 65985306177451
371 12244704361925
372 72487136982382
373 13416137054298
374 79609630499680
375 14696148096566
376 87410194132146
377 16094489842137
378 95951382899174
379 17621763441762
380 105301343232430
381 19289490845855
382 115534301246056
383 21110191946507
384 126731084631207
385 23097468802870
386 138979696053743
387 25266095908339
388 152375926425028
389 27632118650184
390 167024027811431
391 30212958863157
392 183037433533931
393 33027529850748
394 200539547327736
395 36096359729278
396 219664588259316
397 39441725712976
398 240558515594307
399 43087798145101
400 263380019450107
401 47060797174489
402 288301603995318
403 51389160833136
404 315510748139938
405 56103727719219
406 345211173343863
407 61237933007192
408 377624202578542
409 66828021324687
410 412990243239837
411 72913275183947
412 451570377153034
413 79536262891987
414 493648093979054
415 86743104598477
416 539531150269608
417 94583760824614
418 589553594399553
419 103112342126989
420 644077938745815
421 112387444702344
422 703497523685289
423 122472510588111
424 768239053963830
425 133436217793370
426 838765356829170
427 145352899029648
428 915578341714114
429 158302994955543
430 999222216247722
431 172373540654830
432 1090286937691530
433 187658691903311
434 1189411960559660
435 204260290011225
436 1297290258970945
437 222288472527896
438 1414672691140787
439 241862328689041
440 1542372684152682
441 263110607698408
442 1681271313851899
443 286172478872257
444 1832322757775683
445 311198352632368
446 1996560204236033
447 338350761557983
448 2175102195515305
449 367805311499733
450 2369159497506308
451 399751702195890
452 2580042474091964
453 434394828518409
454 2809169068911130
455 471955962100979
456 3058073373497786
457 512674025728341
458 3328414895941156
459 556806960612596
460 3621988510228940
461 604633200358516
462 3940735213254129
463 656453252197228
464 4286753671351195
465 712591400868175
466 4662312697721921
467 773397536306504
468 5069864644957027
469 839249122276779
470 5512059870075290
471 910553307791698
472 5991762259441962
473 987749200455210
474 6512065988941452
475 1071310304381081
476 7076313510828348
477 1161747144049898
478 7688114962769064
479 1259610077753483
480 8351368995635747
481 1365492324476216
482 9070285238094733
483 1480033209029254
484 9849408401019527
485 1603921652106513
486 10693644264993096
487 1737899911451401
488 11608287561890114
489 1882767603947846
490 12599052022124000
491 2039386016475792
492 13672102608261015
493 2208682738867346
494 14834090238317426
495 2391656628721372
496 16092189031272505
497 2589383145403044
498 17454136413687069
499 2803020065223669
500 18928276134179183
501 3033813619588350
502 20523604564623353
503 3283105070756909
504 22249820351823990
505 3552337772009488
506 24117377843380394
507 3843064729925600
508 26137544371803676
509 4156956721232265
510 28322461870945227
511 4495810985480945
512 30685212932848738
513 4861560552351727
514 33239891835703631
515 5256284229007084
516 36001680679394396
517 5682217313416440
518 38986931222913389
519 6141763063865115
520 42213252593611001
521 6637504998625961
522 45699605533999284
523 7172220061534570
524 49466403395331893
525 7748892736481738
526 53535620624082028
527 8370730152991353
528 57930908996436248
529 9041178276051523
530 62677722437314308
531 9763939229741895
532 67803450732680140
533 10542989859304062
534 73337563073294812
535 11382601589670876
536 79311761801105209
537 12287361697987236
538 85760147410859859
539 13262196067931861
540 92719395250651827
541 14312393557862978
542 100228945102716818
543 15443632061801584
544 108331204172366627
545 16662006411645917
546 117071764811240344
547 17974058212462132
548 126499637600157876
549 19386807777635582
550 136667501280910886
551 20907788270486757
552 147631970274808354
553 22545082239823928
554 159453881460940908
555 24307360672881197
556 172198601081943964
557 26203924776472781
558 185936353656931495
559 28244750629047856
560 200742573919082752
561 30440536940730372
562 216698283890424503
563 32802756086068083
564 233890496283514017
565 35343708676113781
566 252412646604748108
567 38076581859661316
568 272365055347059190
569 41015511653590871
570 293855422941940441
571 44175649520739868
572 316999359085856276
573 47573233532726641
574 341920949443589138
575 51225664368797694
576 368753361604156619
577 55151586530287116
578 397639493666392296
579 59370975058874211
580 428732667628442294
581 63905228185775097
582 462197371380052382
583 68777266242247181
584 498210051813542261
585 74011637312000853
586 536959963327531756
587 79634630003951458
588 578650074629835562
589 85674393886046973
590 623498038648707212
591 92161068013126061
592 671737228905061939
593 99126918157321892
594 723617847757460600
595 106606483235832476
596 779408110381641624
597 114636731620775516
598 839395510575190557
599 123257227896240541
600 903888172829662727
601 132510310832964143
602 973216297525093176
603 142441283225367644
604 1047733704350855608
605 153098614457916483
606 1127819481668428262
607 164534156535738587
608 1213879747673274821
609 176803374554968052
610 1306349532040631914
611 189965592450025756
612 1405694784769351117
613 204084255115305761
614 1512414521999737165
615 219227207854162955
616 1627043116494063730
617 235466994389992618
618 1750152743784019884
619 252881174523139913
620 1882355992780974344
621 271552662822740277
622 2024308653236189811
623 291570089585317222
624 2176712690104044093
625 313028185622670113
626 2340319418751770316
627 336028192278157450
628 2515932892495679142
629 360678298428987940
630 2704413518158837245
631 387094106062554266
632 2906681912748398921
633 415399126403550269
634 3123723018918664152
635 445725308393393233
636 3356590494152262805
637 478213601744859887
638 3606411393543121905
639 513014556614300717
640 3874391163191844945
641 550288962391048794
642 4161818966591729860
643 590208527918048785
644 4470073363369100349
645 632956605954003481
646 4800628365562311378
647 678728964497581509
648 5155059893465965037
649 727734608132819384
650 5535052659380381375
651 780196652361648025
652 5942407504305249476
653 836353254474522314
654 6379049219465741592
655 896458604314188858
656 6847034881115678595
657 960783978923303408
658 7348562734495452306
659 1029618864869377258
660 7885981659237791642
661 1103272152731227597
662 8461801256583272668
663 1182073408033894212
664 9078702595046060634
665 1266374223670119331
666 9739549659931275007
667 1356549658650668954
668 10447401548252707229
669 1452999768842871714
670 11205525460115332423
671 1556151235164607039
672 12017410533650404280
673 1666459095589899811
674 12886782580929610881
675 1784408587136013783
676 13817619778194921646
677 1910517104969810138
678 14814169374976608567
679 2045336285593111658
680 15880965482482110781
681 2189454222120985490
682 17022848013853868567
683 2343497819500561520
684 18244982844620559513
685 2508135298666322564
686 19552883274951037854
687 2684078858476745317
688 20952432870983836766
689 2872087505529038297
690 22449909776957336557
691 3072970061816721456
692 24052012585491551541
693 3287588361560007755
694 25765887869100878303
695 3516860648431224905
696 27599159471634872553
697 3761765185886607311
698 29559959675467412589
699 4023344093237751436
700 31656962355900943735
701 4302707421721453588
702 33899418252900480128
703 4601037484784211664
704 36297192485989782331
705 4919593458572540748
706 38860804458458840228
707 5259716268621118176
708 41601470292870681428
709 5622833780669228181
710 44531147961998520204
711 6010466313588257404
712 47662585275344171189
713 6424232494521599766
714 51009370905530449184
715 6865855476450958203
716 54585988635130185810
717 7337169540719356983
718 58407875030826447750
719 7840127107225357003
720 62491480748397835154
721 8376806177536048124
722 66854335700754533413
723 8949418236434085683
724 71515118318273113817
725 9560316640185969784
726 76493729162039672597
727 10212005520183176743
728 81811369148163352499
729 10907149233642122783
730 87490622675568670105
731 11648582393526204467
732 93555545947880022245
733 12439320513175615786
734 100031760817422732634
735 13282571301738144213
736 106946554478364843488
737 14181746650134232562
738 114328985376906774814
739 15140475348046570607
740 122209995706382671108
741 16162616576413915969
742 130622530899832752520
743 17252274220838315751
744 139601666533703604347
745 18413812055688278601
746 149184743105215756424
747 19651869849807403686
748 159411509148388518683
749 20971380449534877186
750 170324273207192992579
751 22377587896096361240
752 181968065188347987504
753 23876066639686942321
754 194390807674809207637
755 25472741914177699112
756 207643497786910919060
757 27173911342153512637
758 221780400242211436433
759 28986267841892985587
760 236859252273178556934
761 30916923914243451399
762 252941481132052048687
763 32973437389580085204
764 270092434922831941457
765 35163838722003850335
766 288381627577263157553
767 37496659920547742671
768 307882998805221337177
769 39980965214813160851
770 328675189934221189769
771 42626383555501924552
772 350841836569675786341
773 45443143058719867344
774 374471879099988745606
775 48442107506456319538
776 399659892091347695913
777 51634815024889852364
778 426506433718500306051
779 55033519066248012639
780 455118416403029780149
781 58651231830115617062
782 485609499941925192024
783 62501770264783046248
784 518100508439571816765
785 66599804800409641039
786 552719872478429687991
787 70960910971171925153
788 589604097999816770642
789 75601624095871548668
790 628898263500327144200
791 80539497192659740323
792 670756547192193862613
793 85793162317076715486
794 715342785923211072519
795 91382395519672119974
796 762831067702156882021
797 97328185634379994571
798 813406359837499956927
799 103652807116884288896
800 867265174756074338246
801 110379897168625330822
802 924616275746274935745
803 117534537391279273143
804 985681424938952448732
805 125143340234619152412
806 1050696176034724611417
807 133234540511103617993
808 1119910714366064842516
809 141838092270452273053
810 1193590747097551536491
811 150985771339311390655
812 1272018446459769599840
813 160711283853053412384
814 1355493449148869778514
815 171050381120177359625
816 1444333915129980864730
817 182040981183953286619
818 1538877649342891435672
819 193723297461145604399
820 1639483289930501732517
821 206139974864296794781
822 1746531566896921348375
823 219336233831222230483
824 1860426635242091619962
825 233360022714741077827
826 1981597486935046939468
827 248262179005051026795
828 2110499446248111987183
829 264096599889539214565
830 2247615753321415440609
831 280920422676678450109
832 2393459241009992125526
833 298794215646368326113
834 2548574110447976195735
835 317782179913699990670
836 2713537810972808173851
837 337952362932505924329
838 2888963030473406091827
839 359376884292761560649
840 3075499802463343826100
841 382132174509341585908
842 3273837736643933405376
843 406299227530782949869
844 3484708379991384465556
845 431963867744620664715
846 3708887715913343127869
847 459217032290851086454
848 3947198809325482635314
849 488155069547935884604
850 4200514606062143641833
851 518880054695030935703
852 4469760895380839005056
853 551500123312441167892
854 4755919444941393334560
855 586129824026344743826
856 5060031318031605044002
857 622890491268176271135
858 5383200383495903289426
859 661910639268413530800
860 5726597029265289405871
861 703326378475515889178
862 6091462091141700035473
863 747281855646034005712
864 6479111008988450321196
865 793929718930263273703
866 6890938223310850343357
867 843431609339668424418
868 7328421825772997718228
869 895958680068776665023
870 7793128478114858144321
871 951692145213412951679
872 8286718614566472047947
873 1010823859522582570324
874 8810951943868847507204
875 1073556930898625649539
876 9367693267722894376208
877 1140106367465591946906
878 9958918633604958510405
879 1210699761112154082416
880 10586721840687553047490
881 1285578009531624968649
882 11253321318836464745784
883 1364996078878068370889
884 11961067401553880031927
885 1449223809285797870670
886 12712450015097172859881
887 1538546765607151516337
888 13510106807011195520303
889 1633267135865044988157
890 14356831738812617049975
891 1733704680036797835761
892 15255584168695339002825
893 1840197731942036954342
894 16209498451782097260067
895 1953104257141233057696
896 17221894086714053147894
897 2072802969923953263650
898 18296286439197835838363
899 2199694512614934681650
900 19436398074547840547430
901 2334202700616507605490
902 20646170733278709430082
903 2476775836771855009719
904 21929777985390039946987
905 2627888098843772323397
906 23291638601211688064835
907 2788041004088326038982
908 24736430678452906713256
909 2957764955134784079947
910 26269106567555876696795
911 3137620871588742347545
912 27894908639437842950870
913 3328201912031394278579
914 29619385942418427396405
915 3530135291316508967208
916 31448411797344433056176
917 3744084198349242036340
918 33388202382918386089681
919 3970749819785073381905
920 35445336365710698561030
921 4210873475398998573986
922 37626775632640127518077
923 4465238871157572773961
924 39939887186467301137381
925 4734674476370527768432
926 42392466268494043072821
927 5020056031612489754719
928 44992760775739412534234
929 5322309194485066391324
930 47749497043890140768402
931 5642412330638059681868
932 50671907070754421012046
933 5981399457887585114417
934 53769757259392895468888
935 6340363351655747991030
936 57053378763923764169004
937 6720458820418868589507
938 60533699525905312656942
939 7122906160280580064667
940 64222278093456876048611
941 7548994798296232478084
942 68131339320694929759730
943 8000087134651328577948
944 72273812049800716328735
945 8477622594359492693541
946 76663368884013530982965
947 8983121899673697323099
948 81314468165117856798366
949 9518191575025304585224
950 86242398275590436538306
951 10084528696891110184899
952 91463324391439661574066
953 10683925901673412037825
954 96994337819051830005039
955 11318276665327199066408
956 102853508055881290594780
957 11989580869223930873640
958 109059937722858602088101
959 12699950667460559111645
960 115633820523640111024784
961 13451616671655552237236
962 122596502394692284319512
963 14246934470070310469416
964 129970546018258252018064
965 15088391498813134118871
966 137779798880042588294497
967 15978614283765062207165
968 146049465062395488273829
969 16920376072880059905220
970 154806180974579293522435
971 17916604879488633316232
972 164078095231631579238519
973 18970391958351088662745
974 173894952905258235258416
975 20085000737287515146993
976 184288184381212374841645
977 21263876228443250949639
978 195290999070766332643472
979 22510654944444523869304
980 206938484236113433141526
981 23829175346056794102527
982 219267709204046301643273
983 25223488849281241919466
984 232317835255822768780901
985 26697871421321605872598
986 246130231497138437505105
987 28256835796316583678771
988 260748597027165160945300
989 29905144343382756117531
990 276219089743273976797650
991 31647822621130517098718
992 292590462134732665496724
993 33490173654633676990184
994 309914204438147550870654
995 35437792972621335054191
996 328244695545893725561012
997 37496584444664219955754
998 347639362080263400224026
999 39672776960103507417379
1000 368158846066528672071855