0 1
1 1
2 1
3 1
4 1
5 2
6 2
7 2
8 2
9 3
10 4
11 4
12 4
13 5
14 6
15 7
16 7
17 8
18 10
19 11
20 12
21 14
22 16
23 18
24 19
25 22
26 26
27 29
28 31
29 34
30 40
31 45
32 48
33 52
34 60
35 68
36 74
37 80
38 90
39 102
40 111
41 121
42 136
43 152
44 166
45 180
46 201
47 225
48 245
49 264
50 294
51 329
52 360
53 387
54 426
55 476
56 521
57 562
58 615
59 683
60 750
61 809
62 883
63 978
64 1071
65 1156
66 1259
67 1389
68 1523
69 1642
70 1782
71 1962
72 2149
73 2321
74 2511
75 2756
76 3019
77 3261
78 3524
79 3854
80 4216
81 4558
82 4920
83 5368
84 5867
85 6342
86 6838
87 7446
88 8126
89 8787
90 9464
91 10283
92 11213
93 12125
94 13050
95 14150
96 15408
97 16663
98 17926
99 19403
100 21104
101 22818
102 24540
103 26521
104 28804
105 31144
106 33477
107 36131
108 39197
109 42365
110 45531
111 49077
112 53172
113 57454
114 61733
115 66467
116 71930
117 77688
118 83460
119 89772
120 97033
121 104761
122 112516
123 120927
124 130566
125 140894
126 151306
127 162482
128 175244
129 189011
130 202939
131 217784
132 234656
133 252944
134 271541
135 291228
136 313483
137 337731
138 362479
139 388553
140 417874
141 449934
142 482815
143 517283
144 555842
145 598137
146 641712
147 687230
148 737867
149 793524
150 851159
151 911169
152 977567
153 1050680
154 1126692
155 1205718
156 1292681
157 1388523
158 1488609
159 1592478
160 1706221
161 1831641
162 1963137
163 2099483
164 2248063
165 2411891
166 2584343
167 2763046
168 2956893
169 3170545
170 3396217
171 3630133
172 3882747
173 4160941
174 4455767
175 4761434
176 5090264
177 5451975
178 5836428
179 6235309
180 6662846
181 7132468
182 7633015
183 8152763
184 8708004
185 9316929
186 9967475
187 10643816
188 11364115
189 12152644
190 12996863
191 13875654
192 14809102
193 15828949
194 16922798
195 18063099
196 19271428
197 20588909
198 22004244
199 23481786
200 25044284
201 26744337
202 28572949
203 30485036
204 32503343
205 34694653
206 37054148
207 39525210
208 42129644
209 44951153
210 47991644
211 51181022
212 54538254
213 58167512
214 62080760
215 66191986
216 70515203
217 75178773
218 80209117
219 85502260
220 91063637
221 97050540
222 103509497
223 110315955
224 117463025
225 125141444
226 133425361
227 142167570
228 151343188
229 161181990
230 171795216
231 183010649
232 194779002
233 207374620
234 220957729
235 235330125
236 250408918
237 266519669
238 283886279
239 302283911
240 321585921
241 342174770
242 364356982
243 387882132
244 412566368
245 438855780
246 467162308
247 497212517
248 528750163
249 562290263
250 598378507
251 636724974
252 676981000
253 719736463
254 765704752
255 814589274
256 865926926
257 920385303
258 978887648
259 1041146179
260 1106556371
261 1175865732
262 1250257131
263 1329473857
264 1412739918
265 1500880326
266 1595398187
267 1696100372
268 1802002822
269 1914003702
270 2033996969
271 2161897476
272 2296473956
273 2438684846
274 2590900451
275 2753203930
276 2924071858
277 3104504650
278 3297448054
279 3503233188
280 3719997580
281 3948753247
282 4193138681
283 4453838922
284 4728600016
285 5018406047
286 5327722101
287 5657725157
288 6005718324
289 6372598514
290 6763815614
291 7181215451
292 7621606763
293 8085723970
294 8580180079
295 9107715952
296 9664602235
297 10251307908
298 10875815245
299 11542047625
300 12245700835
301 12986851803
302 13775081315
303 14615857968
304 15504286188
305 16439884781
306 17434095176
307 18494383317
308 19615272403
309 20795520497
310 22048716938
311 23384888686
312 24798031459
313 26285887408
314 27864515339
315 29547199783
316 31327517364
317 33201892459
318 35189196791
319 37306832824
320 39548150167
321 41907884593
322 44408098363
323 47071362468
324 49891100610
325 52859926596
326 56003488027
327 59350807567
328 62895835299
329 66628548106
330 70578597865
331 74783014688
332 79236919013
333 83927066812
334 88887532113
335 94165239972
336 99757381788
337 105646818737
338 111872474152
339 118493433274
340 125510190332
341 132900967818
342 140709938284
343 149011069754
344 157809819721
345 167078947978
346 176868250894
347 187269827378
348 198296296973
349 209914093841
350 222178937836
351 235204935935
352 249014754946
353 263567606692
354 278925358699
355 295228713861
356 312514139523
357 330732760019
358 349952675618
359 370346617898
360 391969693954
361 414764152085
362 438804260051
363 464301165521
364 491334804280
365 519837965118
366 549890779642
367 581750328505
368 615529238228
369 651150561478
370 688699742125
371 728488570298
372 770672302889
373 815164495927
374 862055007147
375 911720585363
376 964371608325
377 1019913110129
378 1078438096128
379 1140400167163
380 1206080443331
381 1275377511800
382 1348385776426
383 1425649500424
384 1507539976676
385 1593952916276
386 1684981894322
387 1781277757081
388 1883326067072
389 1991025314978
390 2104465440366
391 2224422231414
392 2351525263640
393 2485684235492
394 2626982104124
395 2776340646583
396 2934570042836
397 3101603375909
398 3277512675622
399 3463389847806
400 3660270499246
401 3868128169557
402 4087019568334
403 4318234250689
404 4563088029901
405 4821618393279
406 5093861975839
407 5381337368319
408 5685707282276
409 6007104916979
410 6345542074346
411 6702801995832
412 7080975288784
413 7480333330138
414 7900858660423
415 8344639634835
416 8814292777307
417 9310283736859
418 9832562468898
419 10383568199127
420 10966561763468
421 11582276522946
422 12230628510903
423 12914459635575
424 13637817604729
425 14401798822904
426 15206287532648
427 16054586815537
428 16951702574784
429 17899217192720
430 18896990506651
431 19948852995545
432 21060974033458
433 22235579476606
434 23472520149632
435 24776228764110
436 26154283735677
437 27609755036534
438 29142511294368
439 30757672365287
440 32464518731397
441 34267218740858
442 36165701916367
443 38165871663147
444 40279059624947
445 42510853286817
446 44861308494009
447 47337222362589
448 49952392594468
449 52714228732651
450 55623009015025
451 58686550525576
452 61921609499176
453 65337921618165
454 68936124705531
455 72725201743261
456 76725450866471
457 80949562226568
458 85398725427878
459 90083259003593
460 95027693214537
461 100248453235770
462 105747545050712
463 111536822137959
464 117645862044416
465 124095791590300
466 130889792830691
467 138041490405096
468 145586470986525
469 153551756402241
470 161942188057593
471 170773444862563
472 180088255901031
473 189921007218729
474 200278842888662
475 211179838501007
476 222675199911059
477 234808481355709
478 247589978444540
479 261040582421435
480 275221545167063
481 290187798780882
482 305953902505532
483 322544080266886
484 340031474781099
485 358485096012363
486 377925214003894
487 398380029605727
488 419936743544929
489 442681735566756
490 466642858869399
491 491853099535302
492 518416261986324
493 546440100688867
494 575962461165937
495 607022136328934
496 639742523483193
497 674257614856395
498 710618333286649
499 748870575714047
500 789160843435843
501 831655259817400
502 876421757606492
503 923514992443878
504 973108694307145
505 1025408247243915
506 1080503586588793
507 1138460242682360
508 1199484023226182
509 1263828182929899
510 1331610973688310
511 1402911512988165
512 1477973390118428
513 1557108112284257
514 1640470204681205
515 1728155851806744
516 1820453141787243
517 1917744333053395
518 2020230217760728
519 2128028514571473
520 2241479729865643
521 2361051899824156
522 2487004596813557
523 2619482805828178
524 2758888803333677
525 2905794443972978
526 3060533702550826
527 3223286182168470
528 3394526989751007
529 3574953432156177
530 3764993336716584
531 3964870342117860
532 4175145493325848
533 4396667460706263
534 4629982077474737
535 4875369066139999
536 5133490974439875
537 5405378838709312
538 5691726418691352
539 5992884908241968
540 6309636884185727
541 6643232805117879
542 6994551336527024
543 7364034762750089
544 7752607791946103
545 8161784559546589
546 8592674238940111
547 9045835170249656
548 9522360630113727
549 10024081237685705
550 10552392793396242
551 11108001399917289
552 11692200604628117
553 12307200479120732
554 12954752375422761
555 13635750343350254
556 14351726320290074
557 15105344867416948
558 15898797381208392
559 16733216684931901
560 17610419059439260
561 18533612929405490
562 19505533126655022
563 20527615399043831
564 21602015916715409
565 22732593368510737
566 23922752322543555
567 25174312255023955
568 26489836534465542
569 27873960744177660
570 29330913224493168
571 30862998748573276
572 32473269651202472
573 34167289075204405
574 35950296705007408
575 37825210025178452
576 39795669896794812
577 41868346260350289
578 44049718214908383
579 46343475474761697
580 48753968919615959
581 51289188500914715
582 53957129658839969
583 56762453662582098
584 59710369961298965
585 62810442158545567
586 66072517833734180
587 69502478400837125
588 73106573852077084
589 76896243211163614
590 80883592868677675
591 85076033842249627
592 89481079943084706
593 94112404726948542
594 98984865304289983
595 104107786831293800
596 109490221290694296
597 115148504249433853
598 121100837874277051
599 127358938447392867
600 133933733649775969
601 140844730129737945
602 148114192425456693
603 155756818600253275
604 163785827722597355
605 172224504040126200
606 181100039326002574
607 190430843625407874
608 200232939777087897
609 210534112661292656
610 221367523042843542
611 232756194210446594
612 244719584773003488
613 257290842714267999
614 270510351496871463
615 284406858316331069
616 299004037476875819
617 314341429597963182
618 330468148340112905
619 347420031452686051
620 365225931744494011
621 383933012354225838
622 403600928393293368
623 424274287335384442
624 445988309287763054
625 468799250352103086
626 492779481702477847
627 517984440775313985
628 544457182881779070
629 572264816659305017
630 601495038456095807
631 632216639992586235
632 664482324192906717
633 698372159708240853
634 733992296538183965
635 771427969527479371
636 810743766575945729
637 852035242874956625
638 895430751193785054
639 941035744263075877
640 988929456114603189
641 1039225960307672338
642 1092080302953287647
643 1147622761961856856
644 1205950623806444792
645 1267200122132063700
646 1331558372602329842
647 1399186095028767522
648 1470202828614798194
649 1544771345686199860
650 1623117265353324650
651 1705438588739520657
652 1791882284426909657
653 1882642933103656347
654 1977992354286116748
655 2078174149408724370
656 2183369092671554617
657 2293809921360312619
658 2409823860580432617
659 2531710219909585571
660 2659691428018495390
661 2794046033500438037
662 2935167673250987887
663 3083423633628583724
664 3239087652799391249
665 3402493329171177027
666 3574113868351492471
667 3754399410065043190
668 3943686870356503387
669 4142376057198515934
670 4351035470453284508
671 4570216124889348145
672 4800332692719383073
673 5041864683323252039
674 5295494684444151739
675 5561896397572015870
676 5841580144307714690
677 6135121459571390819
678 6443339477989092108
679 6767056963268875187
680 7106901831040108533
681 7463565407387526064
682 7838030212645784374
683 8231299940111810737
684 8644146991289795489
685 9077402432421285506
686 9532244243282253130
687 10009895518449955899
688 10511306072891352977
689 11037475748998942605
690 11589816318317809009
691 12169816685658035717
692 12778644364472535309
693 13417503196756666300
694 14088084563014657392
695 14792199120899585401
696 15531281328229406133
697 16306781777714895014
698 17120726230302081248
699 17975314484031331257
700 18872308091503706003
701 19813456306684866652
702 20801184758566195445
703 21838163505439081637
704 22926554603880864834
705 24068469025691825724
706 25266810584792090604
707 26524817188673375387
708 27845140915217323314
709 29230331074544220271
710 30683863347633296385
711 32209660822590938124
712 33810974670071517884
713 35490885665084208356
714 37253553447548906561
715 39103727274440776767
716 41045390199395079291
717 43082267673828794332
718 45219337455172969220
719 47462344294081095527
720 49816164665561375580
721 52285306346087026393
722 54875725830002207910
723 57594366616849240332
724 60447194959332416632
725 63439668335171142503
726 66578914338373980521
727 69873319088248024768
728 73330177109815710572
729 76956099114493266690
730 80759614254743445120
731 84750843744998399817
732 88938699838533864042
733 93331193977631385262
734 97938533071013191905
735 102772924053395271842
736 107845247951059905737
737 113165217879672719174
738 118745049639208466438
739 124599456064140704898
740 130741712380679073802
741 137183599271207359685
742 143939738573141512530
743 151027852379299994255
744 158464125316656586971
745 166262850435187933008
746 174441532103165771315
747 183021504486696412292
748 192022485095835240407
749 201461819978450989255
750 211360467939527594591
751 221744096935303747544
752 232636711365014802022
753 244059367241750847145
754 256037164482756466681
755 268600968684560540552
756 281779982382307126472
757 295599769699282332849
758 310090396440075280769
759 325288959579783909120
760 341230960352759608986
761 357947440389814334814
762 375474422380155680367
763 393856471465150893182
764 413136715949970921558
765 433352852015673223188
766 454548050362201783708
767 476775823757432324507
768 500088529927544664143
769 524531948309165397182
770 550157829753155436654
771 577030404135588174120
772 605213190288949427963
773 634761784484739772806
774 665738240185548643758
775 698219620464745649752
776 732282932625326006622
777 767995692521069132129
778 805432328474455092085
779 844685267086086196499
780 885847806653317526165
781 929001932173276329278
782 974236940589537046885
783 1021663647447413925497
784 1071395014906541330251
785 1123530587205419764497
786 1178177531696385398769
787 1235468670029759764168
788 1295540685390180267739
789 1358514424965903228845
790 1424518540683798339555
791 1493712184772277710113
792 1566260639271398220571
793 1642310587989727234349
794 1722016519836779165745
795 1805569087612399340036
796 1893168033866413917359
797 1984991367002040503856
798 2081224655368307189146
799 2182096233152629592011
800 2287847344036999447595
801 2398693961279471594485
802 2514859048256032736843
803 2636616009921967514582
804 2764256044021341863208
805 2898041119607567921420
806 3038239204583940007111
807 3185177609198965694065
808 3339207629437650199600
809 3500646938691341396237
810 3669817679019137426914
811 3847111628727931577844
812 4032952350847972496713
813 4227724954420022290855
814 4431816806372996779500
815 4645696782880847877752
816 4869875305798165110019
817 5104819088943289024408
818 5350994042811159528739
819 5608961243834030823124
820 5879335463333267691651
821 6162682125703266600622
822 6459561737990543784683
823 6770645637348393907294
824 7096673902488968534419
825 7438331310171559793230
826 7796292313181144165246
827 8171360109212489757696
828 8564425188397989437448
829 8976316577352444343745
830 9407845996974050144974
831 9859974340756187225422
832 10333772570939182159667
833 10830243981111963551286
834 11350365671300841353300
835 11895287135144984663777
836 12466295792048045639577
837 13064605375934839923436
838 13691392247635180158147
839 14348031472908867793098
840 15036069992943496839849
841 15756975554932545866662
842 16512164615175680295837
843 17303282047330134307735
844 18132185837410572718663
845 19000650209065853024346
846 19910380924873347617740
847 20863345599042028754505
848 21861774889544260116016
849 22907812636499305983795
850 24003513208290657573919
851 25151230306274664963495
852 26353640955531173494453
853 27613334569907090284720
854 28932785572166288879128
855 30314809568850061909858
856 31762618058899377996297
857 33279337367809039891953
858 34867948048347015006455
859 36531818367343044234335
860 38274799612411354521522
861 40100664808245285039917
862 42013004319815875175089
863 44015847721295605850222
864 46113811948513779265796
865 48311448635531757033834
866 50613082829823261848844
867 53023535493330951921197
868 55548339595447523004037
869 58192983806862622837484
870 60962678219862521783330
871 63863190942513232084100
872 66901150638712570763520
873 70083173216165071936452
874 73415534836760314689098
875 76905137278405973417341
876 80559919502824990291404
877 84387852912873277877844
878 88396497636977095208422
879 92594112509772989639575
880 96990203097219850664876
881 101594370125534067778460
882 106415719914225730781003
883 111464135913589106095634
884 116750996369046112595852
885 122287859705804863382646
886 128085693935137577680721
887 134156327614369753644412
888 140513377135041903678526
889 147170752269609639183436
890 154141662235215137712117
891 161440264620055534281041
892 169082850299896709262283
893 177086152125381749662264
894 185466076926795075867953
895 194239571264217971153358
896 203426121403250323695966
897 213045848382758499758730
898 223117905391555494785674
899 233662579002464409564739
900 244703172684023680318873
901 256263872413493785851046
902 268367737337160562830504
903 281039054256804694748415
904 294305686059102631619316
905 308196693845335348814252
906 322739835361394664863344
907 337964188690457953828228
908 353903062013215693691352
909 370591361184082041384089
910 388062494818783229584393
911 406351280126019461327590
912 425497527866852953799574
913 445543148750039389195793
914 466528346000704778633186
915 488494811687827677944329
916 511490120958568407206868
917 535564576960448198811259
918 560766550862412786104966
919 587145970477286393662351
920 614759681167127735864319
921 643668037724736225667006
922 673929227828774500335669
923 705603045700992330264007
924 738757403904775892720153
925 773464692336827692718896
926 809794893594468670660227
927 847819622215823860084802
928 887620002350199608870254
929 929282829453059393621049
930 972892254625065784070764
931 1018534053898026549885116
932 1066305121896831625838989
933 1116309491876818265676846
934 1168648330338742976325275
935 1223424379928010105813119
936 1280753359213985491079948
937 1340759922414408871402354
938 1403565665061894234475498
939 1469293657280880117362677
940 1538082085181826293192123
941 1610080264245556294078747
942 1685434311072694561893438
943 1764291649780655804071130
944 1846817281760039042713809
945 1933190007748421981792284
946 2023585369298224851144250
947 2118179968234207963807374
948 2217170809159657084741776
949 2320771936523819765637187
950 2429194191982415931831645
951 2542649133422959184029671
952 2661371959135137973400959
953 2785618829789103021758354
954 2915642923966875166865545
955 3051697677008581395665442
956 3194063867632760859165000
957 3343047973199019372908502
958 3498953935060901683591803
959 3662085355829047404686361
960 3832777408834752016604898
961 4011396671300639048825187
962 4198307933617839043698961
963 4393874893527286379960095
964 4598497636452656237748866
965 4812614508712499542421101
966 5036663220323008123337015
967 5271079452509410560995769
968 5516340752732145348307504
969 5772971152902820019051840
970 6041495724037289244661553
971 6322436365269138065386825
972 6616363061287462589244445
973 6923902123408929277477151
974 7245683256818042694092510
975 7582331620021605853161885
976 7934527504058521082223269
977 8303019282754492701438794
978 8688561950225804441327996
979 9091904323862106012617276
980 9513858323336670446995733
981 9955317966845042733296202
982 10417188229339417864426657
983 10900366003141838149518649
984 11405820279271334072987194
985 11934618826375116877519995
986 12487846110748393780137476
987 13066576319037742762919897
988 13671965872880994501913977
989 14305289785164236574094839
990 14967847273999498148239517
991 15660924783018195005783965
992 16385902390171432826459915
993 17144302261775563647224257
994 17937680487989657384042434
995 18767577597983370744032385
996 19635640551355415329829449
997 20543686215519222321816228
998 21493577854798303749194469
999 22487160118914942971357009
1000 23526398425996666064100853