0 1
1 1
2 1
3 2
4 1
5 3
6 2
7 5
8 3
9 7
10 6
11 10
12 9
13 13
14 15
15 18
16 22
17 23
18 33
19 31
20 46
21 41
22 65
23 55
24 87
25 73
26 117
27 99
28 153
29 132
30 199
31 177
32 254
33 236
34 324
35 313
36 408
37 412
38 512
39 540
40 639
41 701
42 795
43 904
44 986
45 1159
46 1221
47 1473
48 1509
49 1861
50 1862
51 2336
52 2298
53 2915
54 2830
55 3615
56 3485
57 4463
58 4285
59 5478
60 5267
61 6698
62 6460
63 8152
64 7920
65 9887
66 9687
67 11944
68 11836
69 14391
70 14426
71 17280
72 17557
73 20703
74 21310
75 24739
76 25823
77 29506
78 31204
79 35115
80 37632
81 41730
82 45262
83 49501
84 54326
85 58650
86 65029
87 69389
88 77678
89 82009
90 92549
91 96807
92 110035
93 114175
94 130509
95 134513
96 154478
97 158344
98 182434
99 186217
100 215036
101 218819
102 252934
103 256891
104 296969
105 301343
106 348008
107 353158
108 407133
109 413534
110 475473
111 483779
112 554429
113 565448
114 645484
115 660270
116 750431
117 770268
118 871214
119 897694
120 1010144
121 1045172
122 1169746
123 1215632
124 1353002
125 1412447
126 1563198
127 1639409
128 1804155
129 1900847
130 2080146
131 2201632
132 2396089
133 2547306
134 2757491
135 2944106
136 3170677
137 3399082
138 3642758
139 3920200
140 4181823
141 4516417
142 4797026
143 5197844
144 5498727
145 5975840
146 6298644
147 6863214
148 7210017
149 7874310
150 8247833
151 9025326
152 9428936
153 10334346
154 10772439
155 11821776
156 12299762
157 13510390
158 14035156
159 15425849
160 16005784
161 17596752
162 18242381
163 20055330
164 20779251
165 22837449
166 23655217
167 25983484
168 26913544
169 29538371
170 30603077
171 33552624
172 34778227
173 38082420
174 39500333
175 43190892
176 44837581
177 48948184
178 50866780
179 55433042
180 57673227
181 62732975
182 65352780
183 70946076
184 74011856
185 80181315
186 83769866
187 90560764
188 94759181
189 102219947
190 107128171
191 115310513
192 121041198
193 130000824
194 136682115
195 146479029
196 154254534
197 164953928
198 173985876
199 185658677
200 196127755
201 208851876
202 220960894
203 234821967
204 248795713
205 263888817
206 279977965
207 296408760
208 314889872
209 332776768
210 353956630
211 373432462
212 397647935
213 418862828
214 446485760
215 469609323
216 501046458
217 526271522
218 561969670
219 589515303
220 629961478
221 660077601
222 705804677
223 738776109
224 790362867
225 826515176
226 884592643
227 924297232
228 989548927
229 1033230390
230 1106398992
231 1154541660
232 1236429713
233 1289586533
234 1381063778
235 1439864641
236 1541868870
237 1607031490
238 1720576828
239 1792916898
240 1919095259
241 1999539708
242 2139529700
243 2229129209
244 2384198628
245 2484143335
246 2655659203
247 2767294011
248 2956725892
249 3081569229
250 3290500892
251 3430262908
252 3660397200
253 3817002057
254 4070173996
255 4245781649
256 4523965585
257 4720997702
258 5026322680
259 5247488577
260 5582247824
261 5830574781
262 6197244185
263 6476107654
264 6877358778
265 7190517739
266 7629239519
267 7980871833
268 8460188369
269 8854931314
270 9378228181
271 9821219710
272 10392167003
273 10889092419
274 11511677133
275 12068816462
276 12747372742
277 13371654397
278 14110902636
279 14809958052
280 15615044381
281 16397268923
282 17273813274
283 18148429170
284 19102575277
285 20079701082
286 21118175890
287 22208898111
288 23339075297
289 24555527655
290 25785499946
291 27140945318
292 28479604766
293 29988524775
294 31445651496
295 33123840366
296 34710201971
297 36574868388
298 38302328870
299 40372202636
300 42253845560
301 44549293720
302 46599554162
303 49142702945
304 51377519306
305 54192385794
306 56629360077
307 59741992107
308 62400574438
309 65839200958
310 68740883840
311 72536074747
312 75704616964
313 79889455606
314 83351115271
315 87961382421
316 91745187435
317 96819558745
318 100957586328
319 106537845150
320 111065545186
321 117196810435
322 122153339696
323 128884311669
324 134312919619
325 141696144481
326 147644569643
327 155736725525
328 162257653877
329 171119857829
330 178271392256
331 187969535043
332 195815735816
333 206420840839
334 215032279865
335 226620894926
336 236075291611
337 248729910889
338 259112782231
339 272922307692
340 284327713834
341 299387951519
342 311919257035
343 328333462862
344 342104205716
345 359983672588
346 375118453116
347 394583156496
348 411218648328
349 432397943416
350 450683926329
351 473717315015
352 493817847741
353 518855806263
354 540950424765
355 568155317240
356 592440389349
357 621987453701
358 648677566190
359 680756001292
360 710085522298
361 744899664566
362 777124343153
363 814894963096
364 850293727857
365 891259432395
366 930136234238
367 974555014199
368 1017240890244
369 1065391793869
370 1112246987259
371 1164431963956
372 1215848290388
373 1272394187962
374 1328797467961
375 1390058230151
376 1451910999497
377 1518270044545
378 1586074343950
379 1657947182229
380 1732247655664
381 1810084721553
382 1891471813633
383 1975761576058
384 2064875073437
385 2156147403771
386 2253680094615
387 2352509959844
388 2459211680522
389 2566223138212
390 2682904962841
391 2798775539630
392 2926314400097
393 3051779824525
394 3191123307291
395 3326982686840
396 3479154310845
397 3626275729055
398 3792380435415
399 3951707063738
400 4132937247967
401 4305493946737
402 4503135746991
403 4690036267096
404 4905476458899
405 5107931213033
406 5342664417542
407 5561988942819
408 5817625516500
409 6055249604877
410 6333523905096
411 6591001529449
412 6893780952094
413 7172800964382
414 7502095434242
415 7804493184235
416 8162465514501
417 8490235360900
418 8879212162143
419 9234521037260
420 9657004609882
421 10042206620678
422 10500887504225
423 10918539738835
424 11416310382039
425 11869189907068
426 12409159124921
427 12900281367571
428 13485790069841
429 14018428567581
430 14653066434206
431 15230774161837
432 15918397766787
433 16545030039749
434 17289782101898
435 17969521275955
436 18775851569714
437 19513233542359
438 20385921150354
439 21185863914612
440 22130041375630
441 22997875632650
442 24019054690919
443 24960556791936
444 26064656317781
445 27086083565379
446 28279459371086
447 29387587964144
448 30677065117814
449 31879230783057
450 33272138164789
451 34576279796953
452 36080487520581
453 37495193881439
454 39119153370922
455 40653713195070
456 42406500555030
457 44070956146967
458 45962318656242
459 47767523345923
460 49807929748778
461 51765609313051
462 53966303780838
463 56089122245681
464 58462182705011
465 60763812653601
466 63322213427795
467 65817411263904
468 68575090740841
469 71279777082804
470 74251710425868
471 77183056108649
472 80385333762924
473 83561851661946
474 87011763749560
475 90453406965938
476 94169534346802
477 97897801001483
478 101900113206657
479 105938158431605
480 110248119265554
481 114620874712890
482 119261555843027
483 123995857342681
484 128992060719096
485 134116784467833
486 139495174012914
487 145041382009017
488 150830625450417
489 156831720616262
490 163062642069044
491 169554533845729
492 176260278044291
493 183281559008330
494 190497767959973
495 198089902312069
496 205854905332246
497 214062429905764
498 222417447987642
499 231288186743090
500 240277552264983
501 249862845016401
502 259534237974389
503 269889184417870
504 280293886229043
505 291477606177461
506 302670772479500
507 314746683476758
508 326787637051246
509 339823750421212
510 352776295924925
511 366845532594015
512 380778294292108
513 395958821598012
514 410945606108576
515 427321197090552
516 443441382402752
517 461101799017700
518 478440752126146
519 497482154047782
520 516131678584392
521 536657059259893
522 556715875826804
523 578835527688265
524 600409788379807
525 624241799129936
526 647445639389533
527 673116421495997
528 698072550909985
529 725717406566523
530 752557742198863
531 782321466139409
532 811187810188163
533 843225332958214
534 874270098833502
535 908747173256098
536 942134162032630
537 979228095847022
538 1015133327787841
539 1055033765556637
540 1093646368850597
541 1136556126605760
542 1178079288637657
543 1224215244749191
544 1268867228319252
545 1318461274570936
546 1366476505057190
547 1419776561927700
548 1471406788085942
549 1528677888780424
550 1584193423976460
551 1645718871745055
552 1705409918623671
553 1771492522623993
554 1835670588851975
555 1906633983681420
556 1975633392191409
557 2051823447100715
558 2126002949387861
559 2207789273054582
560 2287533769396762
561 2375311317098132
562 2461033693326915
563 2555224483191522
564 2647367568384209
565 2748422514584422
566 2847461170443729
567 2955862040891549
568 3062305387833883
569 3178566895337896
570 3292960687298574
571 3417632722839614
572 3540561876516190
573 3674231894806897
574 3806323186797132
575 3949618753962078
576 4091543692309197
577 4245135207309420
578 4397613092458493
579 4562216693403016
580 4726017876079049
581 4902398544622724
582 5078347897326109
583 5267322773878840
584 5456303384600184
585 5658745309287684
586 5861702416099625
587 6078543709918489
588 6296488886283125
589 6528725389457629
590 6762741001020188
591 7011436384910652
592 7262680329137639
593 7528970700953780
594 7798681452707262
595 8083780271646255
596 8373282247732238
597 8678485574280081
598 8989194842741230
599 9315886942235680
600 9649317291331477
601 9998976616436703
602 10356746011987630
603 10730951587933533
604 11114789036269812
605 11515227276683512
606 11926980125080436
607 12355452105495856
608 12797093799892262
609 13255523020284631
610 13729161355853309
611 14219602022828693
612 14727487910093221
613 15252133774159284
614 15796670560253377
615 16357864342743168
616 16941617713949835
617 17541861163491242
618 18167569673116789
619 18809534290794858
620 19480120542362047
621 20166659020417042
622 20885241555343553
623 21619399973583012
624 22389305897687183
625 23174336728145169
626 23999115131761135
627 24838491101379095
628 25721927312539438
629 26619356180649243
630 27565486912355732
631 28524927219179230
632 29538056655948262
633 30563734505822010
634 31648451397656230
635 32744878340293412
636 33906074155746268
637 35078066237155771
638 36320954451511664
639 37573652505782972
640 38903789083556311
641 40242680345835797
642 41665985502376304
643 43096926623269660
644 44619707933124461
645 46148949484510815
646 47777926431321295
647 49412138993780470
648 51154469038903043
649 52900770971716728
650 54764077247413412
651 56630064242432118
652 58622464957826307
653 60616241490264832
654 62746381168253581
655 64876593958318104
656 67153676603972873
657 69429550215819384
658 71863374548500194
659 74294749254376000
660 76895746117996362
661 79493118169271530
662 82272390268523615
663 85046954716989996
664 88016318809907587
665 90980015037852558
666 94152046749921316
667 97317606869938103
668 100705688277987601
669 104086688579696863
670 107705058750511390
671 111315974374633834
672 115179783026603209
673 119036046064623123
674 123161410559312999
675 127279471780861593
676 131683537635723174
677 136080932065234039
678 140781937218839525
679 145477353788095907
680 150494696834748604
681 155508052358798440
682 160862365011614439
683 166214882741838321
684 171928106769921614
685 177642399800920048
686 183737868730575763
687 189838028544923576
688 196340554403175773
689 202852244863067092
690 209788210287874879
691 216738767391800308
692 224136223423732490
693 231554761173222053
694 239443531091838305
695 247361053824276460
696 255772843384866230
697 264222364957894872
698 273190879435085730
699 282207549660803781
700 291768618100896094
701 301389856860310366
702 311581563997140469
703 321847203480539075
704 332710029768316818
705 343662465322070111
706 355239435594326179
707 366923785672555679
708 379260626938342995
709 391724902696161761
710 404870211643139651
711 418165496728744237
712 432170917509257430
713 446351558654037727
714 461271971591292706
715 476395780621324822
716 492289502484220127
717 508417970421920677
718 525346966981379266
719 542545490934226523
720 560575602530473943
721 578913726113661707
722 598114907031596160
723 617666575103554812
724 638113147576457826
725 658956976120988354
726 680727899853670143
727 702947461879652603
728 726126620012410971
729 749810748401704545
730 774487250911438912
731 799730359188414135
732 825998864761014756
733 852901286822910649
734 880862344310333546
735 909530694206212962
736 939291104828600605
737 969838657746986351
738 1001511859283599629
739 1034058954964708466
740 1067765429234467220
741 1102439899101956282
742 1138307604123115829
743 1175245223494020241
744 1213410051780131250
745 1252755018598912185
746 1293361283142625934
747 1335266724757289176
748 1378467674333845916
749 1423096183928260155
750 1469054549450496013
751 1516578753829227747
752 1565467327580078885
753 1616070488107497808
754 1668072737783087335
755 1721949386371803597
756 1777260105976978029
757 1834616718137326513
758 1893442717890310713
759 1954498424957655319
760 2017059262486470477
761 2082046605271971760
762 2148575360507837999
763 2217741086737492242
764 2288485183055219880
765 2362091091103706997
766 2437313165391382970
767 2515636996951908835
768 2595615821456901769
769 2678952205945278428
770 2763983664886530950
771 2852645118528897365
772 2943043242653298048
773 3037361225380708131
774 3133459287795299557
775 3233785321239062284
776 3335936998063905901
777 3442643848137226636
778 3551224447691246507
779 3664707375434804928
780 3780115139906857841
781 3900793224488614288
782 4023450708228464828
783 4151768246203080186
784 4282123775037705211
785 4418551760206649717
786 4557080976385478119
787 4702118664840814976
788 4849326162517902206
789 5003502727713139580
790 5159923784091498873
791 5323800067054304404
792 5490002474657941085
793 5664172834748691506
794 5840758840526220248
795 6025853112449587909
796 6213461469794540180
797 6410147032892132706
798 6609455172925989058
799 6818439139118001606
800 7030165468007862561
801 7252196995106681542
802 7477103324477333999
803 7712976061976366317
804 7951870179950229962
805 8202424854785617930
806 8456163245501840293
807 8722290395708820504
808 8991781115700646516
809 9274423980324093164
810 9560629700483799178
811 9860787274576644838
812 10164728497024292515
813 10483458761052391161
814 10806217220612924905
815 11144640554114154679
816 11487362814757873790
817 11846665604642046551
818 12210566861674208177
819 12592005316139443598
820 12978373415646800023
821 13383277595286195952
822 13793477282825252355
823 14223255361154765154
824 14658732772466758566
825 15114875538768072037
826 15577162945836515742
827 16061248563940580911
828 16551969390591726405
829 17065668427965089398
830 17586542549802562308
831 18131623292111994973
832 18684472636555902448
833 19262806703704410479
834 19849561166561897414
835 20463129447094625809
836 21085833143171274232
837 21736732064855961350
838 22397549930850022361
839 23087998086243390690
840 23789222855359057985
841 24521568002176844384
842 25265627570710013762
843 26042354027935598346
844 26831819235404789474
845 27655555697188186976
846 28493148542493559692
847 29366676333134041851
848 30255278650683496994
849 31181540445226782644
850 32124203065984955798
851 33106312102344124021
852 34106264526364516882
853 35147514336247553567
854 36208174944383619955
855 37312049631838097746
856 38437036466099042896
857 39607221564008270323
858 40800363707291694135
859 42040757643851546306
860 43306107231736325271
861 44620833440630198116
862 45962678339328276193
863 47356098049196530343
864 48778975235910666792
865 50255700976583551411
866 51764410660099139514
867 53329320525142411548
868 54928941046849300900
869 56587193754047705051
870 58283097311351890253
871 60040148105060618815
872 61838017341754095300
873 63699634783347235013
874 65605480293475319115
875 67577763988672464802
876 69597942783308457628
877 71687342097708812932
878 73828577086247197391
879 76041910903223282066
880 78311311443964593210
881 80655789021890595956
882 83060872599146615045
883 85544115588060565562
884 88092830676490192074
885 90722896357413545016
886 93423646537041756019
887 96209052350635564280
888 99070721739838577043
889 102020471174536029901
890 105052451251336182327
891 108176061164909956077
892 111388279051141907598
893 114695808503495884432
894 118098756789817595400
895 121600837469014594084
896 125205605663380029655
897 128913473991155046295
898 132731781677172032836
899 136657312684846275375
900 140701544481551473074
901 144857287551952825533
902 149140529970780155049
903 153539746546927820305
904 158075826847270789610
905 162732530213770788470
906 167536057363266929506
907 172465054612056627967
908 177551462463912834890
909 182768398761729144302
910 188153991566675420582
911 193675396847906001524
912 199377397225175746430
913 205220735440096990095
914 211257334937700195278
915 217441055993040947641
916 223831468375093971800
917 230375062910878107400
918 237139580316283549817
919 244063637470560103055
920 251223689595582340077
921 258549957916401712232
922 266128174380951733520
923 273879626053394334654
924 281899902119916497415
925 290100800684545536550
926 298588366506484104267
927 307264338254911212907
928 316245831841728420505
929 325423941084444275328
930 334927485179148283348
931 344636313591048723099
932 354691596667189510553
933 364961326926677905901
934 375599688521758958607
935 386462192470641085918
936 397716713084997234988
937 409205644647927603812
938 421111240449218351689
939 433262133563952593703
940 445855656150741750312
941 458706027973195138418
942 472026369463409332762
943 485615829125299124634
944 499704032850019475082
945 514074396060935896319
946 528973773157656678948
947 544169182958594646885
948 559925435174214745636
949 575992489165127035872
950 592653838194119122312
951 609641722574786391279
952 627259046275744385441
953 645219677056394768212
954 663846652906991420350
955 682834824663545559095
956 702528080833472687527
957 722601623401195199375
958 743420897841321396597
959 764640841360981422879
960 786649149328461576158
961 809079898079963141219
962 832343708539716432317
963 856053224020543492859
964 880642645387177521108
965 905702639116005841842
966 931691614823170863895
967 958177751373658430467
968 985644265783852699741
969 1013636376578989464239
970 1042662671772203512881
971 1072244980196762605853
972 1102917784204994970306
973 1134179142621603443936
974 1166589909704359083679
975 1199624048988614834045
976 1233869212576017196985
977 1268775004816922749250
978 1304956243778132937926
979 1341837978823054234172
980 1380062497752370202774
981 1419030174309724371904
982 1459410998557091522103
983 1500580630606234899913
984 1543236916817046847905
985 1586730856112306468281
986 1631788219079362498456
987 1677735494575078428214
988 1725326351247532115026
989 1773863026312273495424
990 1824126957848385285700
991 1875396506180456461789
992 1928480638977128720243
993 1982634340178978740590
994 2038693746857432163679
995 2095891102674963620302
996 2155089224052686425951
997 2215498396335586998733
998 2278007485465911936775
999 2341805756958378937704
1000 2407807346374887164002