0 1
1 1
2 1
3 2
4 3
5 3
6 4
7 6
8 7
9 9
10 11
11 13
12 17
13 21
14 24
15 29
16 37
17 42
18 49
19 60
20 70
21 82
22 96
23 111
24 129
25 152
26 173
27 199
28 234
29 266
30 302
31 349
32 399
33 451
34 515
35 585
36 661
37 752
38 847
39 954
40 1081
41 1215
42 1359
43 1531
44 1719
45 1917
46 2147
47 2400
48 2675
49 2985
50 3322
51 3690
52 4110
53 4563
54 5048
55 5603
56 6211
57 6859
58 7582
59 8380
60 9241
61 10192
62 11230
63 12355
64 13606
65 14961
66 16417
67 18033
68 19799
69 21689
70 23764
71 26036
72 28479
73 31150
74 34052
75 37184
76 40610
77 44323
78 48308
79 52662
80 57397
81 62466
82 67975
83 73964
84 80399
85 87361
86 94898
87 103006
88 111786
89 121269
90 131433
91 142440
92 154336
93 167069
94 180801
95 195644
96 211555
97 228667
98 247112
99 266888
100 288174
101 311063
102 335558
103 361903
104 390245
105 420538
106 453032
107 487980
108 525349
109 565378
110 608326
111 654257
112 703457
113 756164
114 812447
115 872692
116 937243
117 1006091
118 1079670
119 1158458
120 1242509
121 1332226
122 1428130
123 1530432
124 1639598
125 1756174
126 1880365
127 2012833
128 2154250
129 2304774
130 2465137
131 2636228
132 2818338
133 3012150
134 3218685
135 3438439
136 3672260
137 3921205
138 4185826
139 4467261
140 4766782
141 5084947
142 5422986
143 5782567
144 6164445
145 6569871
146 7000719
147 7458103
148 7943550
149 8459029
150 9005844
151 9585936
152 10201690
153 10854461
154 11546430
155 12280572
156 13058621
157 13882874
158 14756669
159 15682371
160 16662704
161 17701299
162 18800863
163 19964835
164 21197509
165 22501820
166 23881666
167 25342265
168 26887275
169 28520851
170 30248914
171 32076122
172 34007427
173 36049316
174 38207124
175 40486989
176 42896461
177 45441494
178 48129009
179 50968112
180 53965953
181 57130127
182 60470945
183 63997196
184 67717883
185 71644355
186 75786752
187 80155920
188 84765081
189 89625578
190 94749741
191 100153267
192 105849547
193 111852329
194 118179336
195 124846756
196 131870644
197 139270724
198 147065557
199 155274271
200 163919711
201 173022678
202 182605043
203 192693544
204 203312567
205 214486555
206 226245814
207 238619283
208 251635351
209 265327918
210 279730010
211 294875156
212 310802315
213 327548717
214 345152570
215 363659180
216 383111787
217 403553304
218 425035087
219 447607727
220 471320904
221 496232153
222 522399129
223 549879861
224 578740268
225 609045414
226 640861310
227 674264177
228 709328959
229 746130077
230 784753793
231 825287070
232 867815520
233 912436000
234 959247403
235 1008348913
236 1059851154
237 1113865654
238 1170505192
239 1229896842
240 1292168422
241 1357447122
242 1425876695
243 1497604356
244 1572775753
245 1651552481
246 1734101476
247 1820590459
248 1911203340
249 2006128357
250 2105555756
251 2209695868
252 2318763455
253 2432973019
254 2552562245
255 2677776954
256 2808861933
257 2946084268
258 3089722189
259 3240055949
260 3397388706
261 3562033863
262 3734308655
263 3914558476
264 4103139364
265 4300408908
266 4506756736
267 4722588526
268 4948310710
269 5184361093
270 5431197845
271 5689284044
272 5959115403
273 6241207302
274 6536082965
275 6844304988
276 7166457016
277 7503128094
278 7854951916
279 8222590870
280 8606712183
281 9008027536
282 9427283268
283 9865236751
284 10322691670
285 10800486513
286 11299475156
287 11820566834
288 12364708388
289 12932859643
290 13526043274
291 14145329965
292 14791803883
293 15466612289
294 16170959270
295 16906071067
296 17673240205
297 18473817619
298 19309182869
299 20180794137
300 21090172795
301 22038867395
302 23028515255
303 24060831499
304 25137560515
305 26260536973
306 27431686091
307 28652974615
308 29926465099
309 31254314230
310 32638730366
311 34082034254
312 35586648973
313 37155049351
314 38789836940
315 40493736111
316 42269527661
317 44120123053
318 46048574610
319 48058009161
320 50151692734
321 52333039715
322 54605554097
323 56972902063
324 59438911346
325 62007502363
326 64682778221
327 67469031939
328 70370658837
329 73392244318
330 76538589820
331 79814625056
332 83225483691
333 86776528884
334 90473274463
335 94321470594
336 98327117226
337 102496373893
338 106835665251
339 111351705785
340 116051386495
341 120941876977
342 126030674484
343 131325489848
344 136834335105
345 142565571865
346 148527809640
347 154730003955
348 161181491527
349 167891874884
350 174871143858
351 182129726033
352 189678342722
353 197528126417
354 205690701182
355 214178038929
356 223002557820
357 232177203040
358 241715319049
359 251630759532
360 261937953873
361 272651762283
362 283787614417
363 295361594939
364 307390265027
365 319890794477
366 332881085280
367 346379594679
368 360405442484
369 374978536959
370 390119417485
371 405849375918
372 422190565440
373 439165824196
374 456798829780
375 475114233147
376 494137442352
377 513894768018
378 534413605016
379 555722218823
380 577849860649
381 600826952630
382 624684899850
383 649456220889
384 675174714306
385 701875248990
386 729593933457
387 758368314893
388 788237122013
389 819240423152
390 851419883860
391 884818515749
392 919480795862
393 955452930419
394 992782636978
395 1031519280940
396 1071714119070
397 1113420056287
398 1156691829519
399 1201586290985
400 1248162111066
401 1296479946307
402 1346602796199
403 1398595715722
404 1452525934879
405 1508463225784
406 1566479656989
407 1626649733880
408 1689050742283
409 1753762476178
410 1820867433159
411 1890451208456
412 1962602161504
413 2037411590142
414 2114974216472
415 2195387867377
416 2278753591028
417 2365176155861
418 2454763786055
419 2547628302022
420 2643885593237
421 2743655326506
422 2847061150647
423 2954231234207
424 3065297902761
425 3180397818770
426 3299672631188
427 3423268635317
428 3551336881843
429 3684033845074
430 3821521154650
431 3963965731951
432 4111540430603
433 4264423740205
434 4422800000355
435 4586860121307
436 4756801209042
437 4932826748919
438 5115147463622
439 5303980972256
440 5499551888489
441 5702092704827
442 5911843543636
443 6129052289435
444 6353975443020
445 6586877846700
446 6828032909052
447 7077723559452
448 7336241887665
449 7603889331624
450 7880977801491
451 8167829367261
452 8464776347059
453 8772162464807
454 9090342658921
455 9419683211081
456 9760562873343
457 10113372655881
458 10478516067325
459 10856410367768
460 11247486263039
461 11652188105215
462 12070975351153
463 12504322327112
464 12952718311676
465 13416669040669
466 13896696628939
467 14393339703118
468 14907154878082
469 15438716664387
470 15988617740127
471 16557470581917
472 17145907276577
473 17754579748582
474 18384161642342
475 19035348234932
476 19708856525675
477 20405427183760
478 21125824660882
479 21870837349586
480 22641279502276
481 23437991345477
482 24261839409044
483 25113718637945
484 25994552412564
485 26905292829785
486 27846923125714
487 28820457833170
488 29826942910086
489 30867458247924
490 31943118088721
491 33055071244351
492 34204503581491
493 35392638465339
494 36620737189307
495 37890101703352
496 39202074968478
497 40558041343322
498 41959429692636
499 43407713931035
500 44904413242727
501 46451095303612
502 48049377163553
503 49700925585419
504 51407460257974
505 53170754736192
506 54992637049418
507 56874993217084
508 58819768116430
509 60828966057384
510 62904654765772
511 65048966511757
512 67264098504563
513 69552317032412
514 71915959025670
515 74357432618236
516 76879221295655
517 79483885567389
518 82174063870625
519 84952477099336
520 87821930235273
521 90785313236647
522 93845606147455
523 97005881079180
524 100269302920431
525 103639134656114
526 107118739911223
527 110711583891800
528 114421238741813
529 118251386271142
530 122205819331910
531 126288447663014
532 130503300620288
533 134854528579342
534 139346409496591
535 143983352114450
536 148769897197396
537 153710724376197
538 158810656084315
539 164074659109219
540 169507851528237
541 175115506926002
542 180903056515329
543 186876096690749
544 193040393322209
545 199401883966528
546 205966686310352
547 212741103107190
548 219731624250306
549 226944935607206
550 234387924898201
551 242067684210897
552 249991519002102
553 258166954394446
554 266601738438895
555 275303851902550
556 284281514759279
557 293543189632463
558 303097592702504
559 312953701055563
560 323120756054210
561 333608274779714
562 344426058596861
563 355584197143489
564 367093080047356
565 378963406106844
566 391206188258263
567 403832766308752
568 416854816471345
569 430284356659097
570 444133760628895
571 458415768660048
572 473143492889991
573 488330432188225
574 503990484413031
575 520137952602818
576 536787560290054
577 553954464638377
578 571654263925072
579 589903014171690
580 608717242865700
581 628113956986435
582 648110661418938
583 668725374205436
584 689976634785503
585 711883523415298
586 734465678460694
587 757743305827719
588 781737199055975
589 806468757851555
590 831959999230835
591 858233579325887
592 885312812833884
593 913221685005927
594 941984875731589
595 971627781018713
596 1002176525470063
597 1033657987745733
598 1066099824691060
599 1099530485460134
600 1133979237984811
601 1169476194837958
602 1206052329626234
603 1243739505703355
604 1282570503405534
605 1322579037728292
606 1363799789961053
607 1406268437614796
608 1450021672995151
609 1495097236720087
610 1541533951094568
611 1589371740943249
612 1638651668615417
613 1689415969754964
614 1741708077154224
615 1795572658709631
616 1851055655191180
617 1908204306000847
618 1967067190885561
619 2027694271287772
620 2090136917574560
621 2154447953337518
622 2220681701223219
623 2288894013265611
624 2359142317339536
625 2431485666276513
626 2505984772226141
627 2582702056996596
628 2661701704040601
629 2743049695573552
630 2826813867781319
631 2913063967552974
632 3001871691896537
633 3093310746691963
634 3187456909249037
635 3284388071973603
636 3384184304196298
637 3486927919222315
638 3592703523357331
639 3701598082882801
640 3813700995158550
641 3929104141586761
642 4047901960916192
643 4170191526628394
644 4296072603368342
645 4425647725086842
646 4559022280026194
647 4696304572934159
648 4837605907568767
649 4983040677782581
650 5132726436881053
651 5286783986948073
652 5445337475587674
653 5608514470842690
654 5776446058776089
655 5949266948534814
656 6127115552346781
657 6310134089705697
658 6498468702348728
659 6692269542106695
660 6891690881214307
661 7096891235535772
662 7308033461935436
663 7525284877637271
664 7748817391288526
665 7978807608085422
666 8215436959946208
667 8458891847580720
668 8709363752924778
669 8967049378298956
670 9232150801419012
671 9504875598468461
672 9785436991780905
673 10074054015983851
674 10370951653725857
675 10676360995399606
676 10990519416043157
677 11313670721810359
678 11646065323883040
679 11987960429917577
680 12339620200879797
681 12701315937145085
682 13073326286871659
683 13455937417173223
684 13849443212023067
685 14254145495592855
686 14670354220245768
687 15098387680459935
688 15538572750838441
689 15991245088886665
690 16456749367573182
691 16935439532572315
692 17427679019538209
693 17933841003171715
694 18454308676606970
695 18989475487961936
696 19539745405654357
697 20105533217834491
698 20687264791288322
699 21285377358047919
700 21900319834754174
701 22532553101742926
702 23182550314193268
703 23850797246889836
704 24537792593396615
705 25244048299498253
706 25970089936939538
707 26716457028454067
708 27483703403434722
709 28272397598482200
710 29083123212076945
711 29916479288564415
712 30773080745639735
713 31653558756435864
714 32558561165836079
715 33488752951471574
716 34444816633428466
717 35427452720578224
718 36437380209523856
719 37475337028869064
720 38542080515826896
721 39638387950926978
722 40765057041550920
723 41922906436170172
724 43112776295298188
725 44335528812102514
726 45592048769229047
727 46883244153971435
728 48210046716553349
729 49573412567289197
730 50974322841448802
731 52413784303637677
732 53892829986005010
733 55412519900697459
734 56973941696202733
735 58578211345497923
736 60226473907126658
737 61919904231430811
738 63659707704832583
739 65447121069185098
740 67283413179090240
741 69169885800237889
742 71107874493824395
743 73098749435218822
744 75143916267702670
745 77244817050115068
746 79402931144154230
747 81619776134344681
748 83896908840694805
749 86235926272864727
750 88638466624107757
751 91106210360640065
752 93640881244757456
753 96244247400998938
754 98918122490739688
755 101664366816721738
756 104484888463731206
757 107381644557012778
758 110356642457339556
759 113411940989409410
760 116549651786900517
761 119771940576877247
762 123081028505593540
763 126479193584475574
764 129968772067105545
765 133552159871304965
766 137231814136698814
767 141010254709505947
768 144890065664484662
769 148873896973397999
770 152964466109088217
771 157164559683418702
772 161477035230918796
773 165904822931797481
774 170450927378066190
775 175118429489839672
776 179910488362138356
777 184830343159057106
778 189881315176063871
779 195066809829292268
780 200390318683069470
781 205855421658704641
782 211465789180667934
783 217225184357307279
784 223137465342356435
785 229206587638991172
786 235436606449078369
787 241831679208839290
788 248396068057841148
789 255134142358096190
790 262050381420691513
791 269149377162679766
792 276435836803743443
793 283914585785964592
794 291590570636772422
795 299468861867586736
796 307554657095583234
797 315853284115653587
798 324370204020374372
799 333111014550183853
800 342081453384322739
801 351287401485606263
802 360734886700211606
803 370430087295910195
804 380379335542580996
805 390589121566165613
806 401066097157184406
807 411817079617085775
808 422849055878819267
809 434169186591287789
810 445784810256050254
811 457703447647112961
812 469932806185217863
813 482480784371415705
814 495355476532831000
815 508565177521849839
816 522118387461742714
817 536023816826390164
818 550290391493422336
819 564927257839189286
820 579943788169622095
821 595349586136787542
822 611154492214301755
823 627368589519656224
824 644002209613349105
825 661065938365436339
826 678570622203226935
827 696527374336446690
828 714947581035787950
829 733842908318678149
830 753225308637264377
831 773107027615318605
832 793500611195449781
833 814418912804686857
834 835875100589153236
835 857882665072845009
836 880455426826829882
837 903607544218175219
838 927353521623283805
839 951708217654729402
840 976686853452815237
841 1002305021472537483
842 1028578694314790244
843 1055524233618237296
844 1083158399451529516
845 1111498359770753269
846 1140561699961724399
847 1170366432899863180
848 1200931009068954685
849 1232274326778180222
850 1264415742944200624
851 1297375083938601133
852 1331172656517863281
853 1365829259355384890
854 1401366194676946431
855 1437805279975623055
856 1475168860336183803
857 1513479820890007789
858 1552761599378711073
859 1593038199348731924
860 1634334203472710469
861 1676674786996576623
862 1720085731873708672
863 1764593441036866602
864 1810224952779888729
865 1857007955870706672
866 1904970804849254359
867 1954142535433851140
868 2004552880669577608
869 2056232287296435702
870 2109211932261530476
871 2163523740000164813
872 2219200399936712513
873 2276275384151336145
874 2334782965882068601
875 2394758238263615162
876 2456237133216634133
877 2519256441225378665
878 2583853831410455371
879 2650067871753488491
880 2717938050225232179
881 2787504796253474780
882 2858809502386382140
883 2931894546893114462
884 3006803316709421715
885 3083580230606965077
886 3162270763378681483
887 3242921470394082842
888 3325580012364425899
889 3410295181187694845
890 3497116926235782910
891 3586096380857126391
892 3677285889980134653
893 3770739038215689240
894 3866510678228884752
895 3964656960253995954
896 4065235362121045826
897 4168304719588239414
898 4273925257911400423
899 4382158623960348049
900 4493067918630298396
901 4606717730567277403
902 4723174170529811198
903 4842504906057336971
904 4964779197481311652
905 5090067934644916502
906 5218443673996182669
907 5349980677077210081
908 5484754949744444672
909 5622844281809948769
910 5764328288190801811
911 5909288450838272376
912 6057808161082289249
913 6209972763577256594
914 6365869601138197206
915 6525588060012428337
916 6689219616791499680
917 6856857886305106743
918 7028598670033657145
919 7204540006228499039
920 7384782221049747307
921 7569427980284750891
922 7758582342908399976
923 7952352815727181382
924 8150849408605920576
925 8354184691649729711
926 8562473853606417564
927 8775834760883743889
928 8994388018574226852
929 9218257032816230970
930 9447568073873974433
931 9682450341310208266
932 9923036030548346805
933 10169460400234150697
934 10421861841851440600
935 10680381950815742984
936 10945165598380972987
937 11216361005938564725
938 11494119820963490442
939 11778597193821871449
940 12069951857040866195
941 12368346206371698757
942 12673946382844816233
943 12986922357395113341
944 13307448017356449060
945 13635701254053115874
946 13971864053156202361
947 14316122587026169824
948 14668667308182328898
949 15029693045706609330
950 15399399103842632330
951 15777989361792142564
952 16165672376538532474
953 16562661488049920029
954 16969174925843806151
955 17385435918715552913
956 17811672806952365321
957 18248119156045109558
958 18695013873799907386
959 19152601330088606859
960 19621131478149758943
961 20100859979497530389
962 20592048331728238329
963 21094963997977093166
964 21609880540105676541
965 22137077755018702118
966 22676841812838096398
967 23229465398981303340
968 23795247859513596228
969 24374495348534357814
970 24967520979754430154
971 25574644981547237334
972 26196194854117583177
973 26832505531118250577
974 27483919545060450969
975 28150787194980571915
976 28833466718716303463
977 29532324469267782917
978 30247735093676349028
979 30980081716733176032
980 31729756128967542288
981 32497158977381338804
982 33282699961363443879
983 34086798033142277580
984 34909881601110261064
985 35752388738645601568
986 36614767397868564100
987 37497475626459201251
988 38400981790184339888
989 39325764800724584451
990 40272314346892810677
991 41241131131842381065
992 42232727115833912504
993 43247625762688986087
994 44286362292661861886
995 45349483941202963511
996 46437550221590727578
997 47551133194375201418
998 48690817743204234840
999 49857201854774086185
1000 51050896905868913212