0 1
1 1
2 1
3 2
4 2
5 4
6 3
7 7
8 5
9 12
10 7
11 19
12 11
13 30
14 15
15 45
16 22
17 67
18 30
19 97
20 42
21 139
22 56
23 195
24 77
25 272
26 101
27 373
28 135
29 508
30 176
31 684
32 231
33 915
34 297
35 1212
36 385
37 1597
38 490
39 2087
40 627
41 2714
42 792
43 3506
44 1002
45 4508
46 1255
47 5763
48 1575
49 7338
50 1958
51 9296
52 2436
53 11732
54 3010
55 14742
56 3718
57 18460
58 4565
59 23025
60 5604
61 28629
62 6842
63 35471
64 8349
65 43820
66 10143
67 53963
68 12310
69 66273
70 14883
71 81156
72 17977
73 99133
74 21637
75 120770
76 26015
77 146785
78 31185
79 177970
80 37338
81 215308
82 44583
83 259891
84 53174
85 313065
86 63261
87 376326
88 75175
89 451501
90 89134
91 540635
92 105558
93 646193
94 124754
95 770947
96 147273
97 918220
98 173525
99 1091745
100 204226
101 1295971
102 239943
103 1535914
104 281589
105 1817503
106 329931
107 2147434
108 386155
109 2533589
110 451276
111 2984865
112 526823
113 3511688
114 614154
115 4125842
116 715220
117 4841062
118 831820
119 5672882
120 966467
121 6639349
122 1121505
123 7760854
124 1300156
125 9061010
126 1505499
127 10566509
128 1741630
129 12308139
130 2012558
131 14320697
132 2323520
133 16644217
134 2679689
135 19323906
136 3087735
137 22411641
138 3554345
139 25965986
140 4087968
141 30053954
142 4697205
143 34751159
144 5392783
145 40143942
146 6185689
147 46329631
148 7089500
149 53419131
150 8118264
151 61537395
152 9289091
153 70826486
154 10619863
155 81446349
156 12132164
157 93578513
158 13848650
159 107427163
160 15796476
161 123223639
162 18004327
163 141227966
164 20506255
165 161734221
166 23338469
167 185072690
168 26543660
169 211616350
170 30167357
171 241783707
172 34262962
173 276046669
174 38887673
175 314934342
176 44108109
177 359042451
178 49995925
179 409038376
180 56634173
181 465672549
182 64112359
183 529784908
184 72533807
185 602318715
186 82010177
187 684328892
188 92669720
189 776998612
190 104651419
191 881650031
192 118114304
193 999764335
194 133230930
195 1132995265
196 150198136
197 1283193401
198 169229875
199 1452423276
200 190569292
201 1642992568
202 214481126
203 1857473694
204 241265379
205 2098739073
206 271248950
207 2369988023
208 304801365
209 2674789388
210 342325709
211 3017115097
212 384276336
213 3401391433
214 431149389
215 3832540822
216 483502844
217 4316043666
218 541946240
219 4857989906
220 607163746
221 5465153652
222 679903203
223 6145056855
224 761002156
225 6906059011
226 851376628
227 7757435639
228 952050665
229 8709486304
230 1064144451
231 9773630755
232 1188908248
233 10962539003
234 1327710076
235 12290249079
236 1482074143
237 13772323222
238 1653668665
239 15425991887
240 1844349560
241 17270341447
242 2056148051
243 19326489498
244 2291320912
245 21617810410
246 2552338241
247 24170148651
248 2841940500
249 27012089151
250 3163127352
251 30175216503
252 3519222692
253 33694439195
254 3913864295
255 37608303490
256 4351078600
257 41959382090
258 4835271870
259 46794653960
260 5371315400
261 52165969360
262 5964539504
263 58130508864
264 6620830889
265 64751339753
266 7346629512
267 72097969265
268 8149040695
269 80247009960
270 9035836076
271 89282846036
272 10015581680
273 99298427716
274 11097645016
275 110396072732
276 12292341831
277 122688414563
278 13610949895
279 136299364458
280 15065878135
281 151365242593
282 16670689208
283 168035931801
284 18440293320
285 186476225121
286 20390982757
287 206867207878
288 22540654445
289 229407862323
290 24908858009
291 254316720332
292 27517052599
293 281833772931
294 30388671978
295 312222444909
296 33549419497
297 345771864406
298 37027355200
299 382799219606
300 40853235313
301 423652454919
302 45060624582
303 468713079501
304 49686288421
305 518399367922
306 54770336324
307 573169704246
308 60356673280
309 633526377526
310 66493182097
311 700019559623
312 73232243759
313 773251803382
314 80630964769
315 853882768151
316 88751778802
317 942634546953
318 97662728555
319 1040297275508
320 107438159466
321 1147735434974
322 118159068427
323 1265894503401
324 129913904637
325 1395808408038
326 142798995930
327 1538607403968
328 156919475295
329 1695526879263
330 172389800255
331 1867916679518
332 189334822579
333 2057251502097
334 207890420102
335 2265141922199
336 228204732751
337 2493346654950
338 250438925115
339 2743785580065
340 274768617130
341 3018554197195
342 301384802048
343 3319938999243
344 330495499613
345 3650434498856
346 362326859895
347 4012761358751
348 397125074750
349 4409886433501
350 435157697830
351 4845044131331
352 476715857290
353 5321759988621
354 522115831195
355 5843875819816
356 571701605655
357 6415577425471
358 625846753120
359 7041424178591
360 684957390936
361 7726381569527
362 749474411781
363 8475855981308
364 819876908323
365 9295732889631
366 896684817527
367 10192417707158
368 980462880430
369 11172880587588
370 1071823774337
371 12244704361925
372 1171432692373
373 13416137054298
374 1280011042268
375 14696148096566
376 1398341745571
377 16094489842137
378 1527273599625
379 17621763441762
380 1667727404093
381 19289490845855
382 1820701100652
383 21110191946507
384 1987276856363
385 23097468802870
386 2168627105469
387 25266095908339
388 2366022741845
389 27632118650184
390 2580840212973
391 30212958863157
392 2814570987591
393 33027529850748
394 3068829878530
395 36096359729278
396 3345365983698
397 39441725712976
398 3646072432125
399 43087798145101
400 3972999029388
401 47060797174489
402 4328363658647
403 51389160833136
404 4714566886083
405 56103727719219
406 5134205287973
407 61237933007192
408 5590088317495
409 66828021324687
410 6085253859260
411 72913275183947
412 6622987708040
413 79536262891987
414 7206841706490
415 86743104598477
416 7840656226137
417 94583760824614
418 8528581302375
419 103112342126989
420 9275102575355
421 112387444702344
422 10085065885767
423 122472510588111
424 10963707205259
425 133436217793370
426 11916681236278
427 145352899029648
428 12950095925895
429 158302994955543
430 14070545699287
431 172373540654830
432 15285151248481
433 187658691903311
434 16601598107914
435 204260290011225
436 18028182516671
437 222288472527896
438 19573856161145
439 241862328689041
440 21248279009367
441 263110607698408
442 23061871173849
443 286172478872257
444 25025873760111
445 311198352632368
446 27152408925615
447 338350761557983
448 29454549941750
449 367805311499733
450 31946390696157
451 399751702195890
452 34643126322519
453 434394828518409
454 37561133582570
455 471955962100979
456 40718063627362
457 512674025728341
458 44132934884255
459 556806960612596
460 47826239745920
461 604633200358516
462 51820051838712
463 656453252197228
464 56138148670947
465 712591400868175
466 60806135438329
467 773397536306504
468 65851585970275
469 839249122276779
470 71304185514919
471 910553307791698
472 77195892663512
473 987749200455210
474 83561103925871
475 1071310304381081
476 90436839668817
477 1161747144049898
478 97862933703585
479 1259610077753483
480 105882246722733
481 1365492324476216
482 114540884553038
483 1480033209029254
484 123888443077259
485 1603921652106513
486 133978259344888
487 1737899911451401
488 144867692496445
489 1882767603947846
490 156618412527946
491 2039386016475792
492 169296722391554
493 2208682738867346
494 182973889854026
495 2391656628721372
496 197726516681672
497 2589383145403044
498 213636919820625
499 2803020065223669
500 230793554364681
501 3033813619588350
502 249291451168559
503 3283105070756909
504 269232701252579
505 3552337772009488
506 290726957916112
507 3843064729925600
508 313891991306665
509 4156956721232265
510 338854264248680
511 4495810985480945
512 365749566870782
513 4861560552351727
514 394723676655357
515 5256284229007084
516 425933084409356
517 5682217313416440
518 459545750448675
519 6141763063865115
520 495741934760846
521 6637504998625961
522 534715062908609
523 7172220061534570
524 576672674947168
525 7748892736481738
526 621837416509615
527 8370730152991353
528 670448123060170
529 9041178276051523
530 722760953690372
531 9763939229741895
532 779050629562167
533 10542989859304062
534 839611730366814
535 11382601589670876
536 904760108316360
537 12287361697987236
538 974834369944625
539 13262196067931861
540 1050197489931117
541 14312393557862978
542 1131238503938606
543 15443632061801584
544 1218374349844333
545 16662006411645917
546 1312051800816215
547 17974058212462132
548 1412749565173450
549 19386807777635582
550 1520980492851175
551 20907788270486757
552 1637293969337171
553 22545082239823928
554 1762278433057269
555 24307360672881197
556 1896564103591584
557 26203924776472781
558 2040825852575075
559 28244750629047856
560 2195786311682516
561 30440536940730372
562 2362219145337711
563 32802756086068083
564 2540952590045698
565 35343708676113781
566 2732873183547535
567 38076581859661316
568 2938929793929555
569 41015511653590871
570 3160137867148997
571 44175649520739868
572 3397584011986773
573 47573233532726641
574 3652430836071053
575 51225664368797694
576 3925922161489422
577 55151586530287116
578 4219388528587095
579 59370975058874211
580 4534253126900886
581 63905228185775097
582 4872038056472084
583 68777266242247181
584 5234371069753672
585 74011637312000853
586 5622992691950605
587 79634630003951458
588 6039763882095515
589 85674393886046973
590 6486674127079088
591 92161068013126061
592 6965850144195831
593 99126918157321892
594 7479565078510584
595 106606483235832476
596 8030248384943040
597 114636731620775516
598 8620496275465025
599 123257227896240541
600 9253082936723602
601 132510310832964143
602 9930972392403501
603 142441283225367644
604 10657331232548839
605 153098614457916483
606 11435542077822104
607 164534156535738587
608 12269218019229465
609 176803374554968052
610 13162217895057704
611 189965592450025756
612 14118662665280005
613 204084255115305761
614 15142952738857194
615 219227207854162955
616 16239786535829663
617 235466994389992618
618 17414180133147295
619 252881174523139913
620 18671488299600364
621 271552662822740277
622 20017426762576945
623 291570089585317222
624 21458096037352891
625 313028185622670113
626 23000006655487337
627 336028192278157450
628 24650106150830490
629 360678298428987940
630 26415807633566326
631 387094106062554266
632 28305020340996003
633 415399126403550269
634 30326181989842964
635 445725308393393233
636 32488293351466654
637 478213601744859887
638 34800954869440830
639 513014556614300717
640 37274405776748077
641 550288962391048794
642 39919565526999991
643 590208527918048785
644 42748078035954696
645 632956605954003481
646 45772358543578028
647 678728964497581509
648 49005643635237875
649 727734608132819384
650 52462044228828641
651 780196652361648025
652 56156602112874289
653 836353254474522314
654 60105349839666544
655 896458604314188858
656 64325374609114550
657 960783978923303408
658 68834885946073850
659 1029618864869377258
660 73653287861850339
661 1103272152731227597
662 78801255302666615
663 1182073408033894212
664 84300815636225119
665 1266374223670119331
666 90175434980549623
667 1356549658650668954
668 96450110192202760
669 1452999768842871714
670 103151466321735325
671 1556151235164607039
672 110307860425292772
673 1666459095589899811
674 117949491546113972
675 1784408587136013783
676 126108517833796355
677 1910517104969810138
678 134819180623301520
679 2045336285593111658
680 144117936527873832
681 2189454222120985490
682 154043597379576030
683 2343497819500561520
684 164637479165761044
685 2508135298666322564
686 175943559810422753
687 2684078858476745317
688 188008647052292980
689 2872087505529038297
690 200882556287683159
691 3072970061816721456
692 214618299743286299
693 3287588361560007755
694 229272286871217150
695 3516860648431224905
696 244904537455382406
697 3761765185886607311
698 261578907351144125
699 4023344093237751436
700 279363328483702152
701 4302707421721453588
702 298330063062758076
703 4601037484784211664
704 318555973788329084
705 4919593458572540748
706 340122810048577428
707 5259716268621118176
708 363117512048110005
709 5622833780669228181
710 387632532919029223
711 6010466313588257404
712 413766180933342362
713 6424232494521599766
714 441622981929358437
715 6865855476450958203
716 471314064268398780
717 7337169540719356983
718 502957566506000020
719 7840127107225357003
720 536679070310691121
721 8376806177536048124
722 572612058898037559
723 8949418236434085683
724 610898403751884101
725 9560316640185969784
726 651688879997206959
727 10212005520183176743
728 695143713458946040
729 10907149233642122783
730 741433159884081684
731 11648582393526204467
732 790738119649411319
733 12439320513175615786
734 843250788562528427
735 13282571301738144213
736 899175348396088349
737 14181746650134232562
738 958728697912338045
739 15140475348046570607
740 1022141228367345362
741 16162616576413915969
742 1089657644424399782
743 17252274220838315751
744 1161537834849962850
745 18413812055688278601
746 1238057794119125085
747 19651869849807403686
748 1319510599727473500
749 20971380449534877186
750 1406207446561484054
751 22377587896096361240
752 1498478743590581081
753 23876066639686942321
754 1596675274490756791
755 25472741914177699112
756 1701169427975813525
757 27173911342153512637
758 1812356499739472950
759 28986267841892985587
760 1930656072350465812
761 30916923914243451399
762 2056513475336633805
763 32973437389580085204
764 2190401332423765131
765 35163838722003850335
766 2332821198543892336
767 37496659920547742671
768 2484305294265418180
769 39980965214813160851
770 2645418340688763701
771 42626383555501924552
772 2816759503217942792
773 45443143058719867344
774 2998964447736452194
775 48442107506456319538
776 3192707518433532826
777 51634815024889852364
778 3398704041358160275
779 55033519066248012639
780 3617712763867604423
781 58651231830115617062
782 3850538434667429186
783 62501770264783046248
784 4098034535626594791
785 66599804800409641039
786 4361106170762284114
787 70960910971171925153
788 4640713124699623515
789 75601624095871548668
790 4937873096788191655
791 80539497192659740323
792 5253665124416975163
793 85793162317076715486
794 5589233202595404488
795 91382395519672119974
796 5945790114707874597
797 97328185634379994571
798 6324621482504294325
799 103652807116884288896
800 6727090051741041926
801 110379897168625330822
802 7154640222653942321
803 117534537391279273143
804 7608802843339879269
805 125143340234619152412
806 8091200276484465581
807 133234540511103617993
808 8603551759348655060
809 141838092270452273053
810 9147679068859117602
811 150985771339311390655
812 9725512513742021729
813 160711283853053412384
814 10339097267123947241
815 171050381120177359625
816 10990600063775926994
817 182040981183953286619
818 11682316277192317780
819 193723297461145604399
820 12416677403151190382
821 206139974864296794781
822 13196258966925435702
823 219336233831222230483
824 14023788883518847344
825 233360022714741077827
826 14902156290309948968
827 248262179005051026795
828 15834420884488187770
829 264096599889539214565
830 16823822787139235544
831 280920422676678450109
832 17873792969689876004
833 298794215646368326113
834 18987964267331664557
835 317782179913699990670
836 20170183018805933659
837 337952362932505924329
838 21424521360255636320
839 359376884292761560649
840 22755290216580025259
841 382132174509341585908
842 24167053021441363961
843 406299227530782949869
844 25664640213837714846
845 431963867744620664715
846 27253164546230421739
847 459217032290851086454
848 28938037257084798150
849 488155069547935884604
850 30724985147095051099
851 518880054695030935703
852 32620068617410232189
853 551500123312441167892
854 34629700713903575934
855 586129824026344743826
856 36760667241831527309
857 622890491268176271135
858 39020148000237259665
859 661910639268413530800
860 41415739207102358378
861 703326378475515889178
862 43955477170518116534
863 747281855646034005712
864 46647863284229267991
865 793929718930263273703
866 49501890409405150715
867 843431609339668424418
868 52527070729108240605
869 895958680068776665023
870 55733465144636286656
871 951692145213412951679
872 59131714309169618645
873 1010823859522582570324
874 62733071376043079215
875 1073556930898625649539
876 66549436566966297367
877 1140106367465591946906
878 70593393646562135510
879 1210699761112154082416
880 74878248419470886233
881 1285578009531624968649
882 79418069346443402240
883 1364996078878068370889
884 84227730407729499781
885 1449223809285797870670
886 89322956321353645667
887 1538546765607151516337
888 94720370257893471820
889 1633267135865044988157
890 100437544171752847604
891 1733704680036797835761
892 106493051905239118581
893 1840197731942036954342
894 112906525199196103354
895 1953104257141233057696
896 119698712782720205954
897 2072802969923953263650
898 126891542690981418000
899 2199694512614934681650
900 134508188001572923840
901 2334202700616507605490
902 142573136155347404229
903 2476775836771855009719
904 151112262071917313678
905 2627888098843772323397
906 160152905244553715585
907 2788041004088326038982
908 169723951046458040965
909 2957764955134784079947
910 179855916453958267598
911 3137620871588742347545
912 190581040442651931034
913 3328201912031394278579
914 201933379285114688629
915 3530135291316508967208
916 213948907032733069132
917 3744084198349242036340
918 226665621435831345565
919 3970749819785073381905
920 240123655613925192081
921 4210873475398998573986
922 254365395758574199975
923 4465238871157572773961
924 269435605212954994471
925 4734674476370527768432
926 285381555241961986287
927 5020056031612489754719
928 302253162872576636605
929 5322309194485066391324
930 320103136152993290544
931 5642412330638059681868
932 338987127249525432549
933 5981399457887585114417
934 358963893768162876613
935 6340363351655747991030
936 380095468763120598477
937 6720458820418868589507
938 402447339861711475160
939 7122906160280580064667
940 426088638015652413417
941 7548994798296232478084
942 451092336355096099864
943 8000087134651328577948
944 477535459708164115593
945 8477622594359492693541
946 505499305314204629558
947 8983121899673697323099
948 535069675351607262125
949 9518191575025304585224
950 566337121865805599675
951 10084528696891110184899
952 599397204782301852926
953 10683925901673412037825
954 634350763653787028583
955 11318276665327199066408
956 671304203896731807232
957 11989580869223930873640
958 710369798236628238005
959 12699950667460559111645
960 751666004194993125591
961 13451616671655552237236
962 795317798414758232180
963 14246934470070310469416
964 841457028742823649455
965 15088391498813134118871
966 890222784951928088294
967 15978614283765062207165
968 941761789114997698055
969 16920376072880059905220
970 996228806608573411012
971 17916604879488633316232
972 1053787078862455346513
973 18970391958351088662745
974 1114608778936426484248
975 20085000737287515146993
976 1178875491155735802646
977 21263876228443250949639
978 1246778716001272919665
979 22510654944444523869304
980 1318520401612270233223
981 23829175346056794102527
982 1394313503224447816939
983 25223488849281241919466
984 1474382572040363953132
985 26697871421321605872598
986 1558964374994977806173
987 28256835796316583678771
988 1648308547066172438760
989 29905144343382756117531
990 1742678277747760981187
991 31647822621130517098718
992 1842351033503159891466
993 33490173654633676990184
994 1947619317987658064007
995 35437792972621335054191
996 2058791472042884901563
997 37496584444664219955754
998 2176192515439287461625
999 39672776960103507417379
1000 2300165032574323995027