0 1
1 2
2 1
3 2
4 4
5 4
6 5
7 6
8 9
9 12
10 13
11 16
12 21
13 26
14 29
15 36
16 46
17 54
18 62
19 74
20 90
21 106
22 122
23 142
24 171
25 200
26 227
27 264
28 311
29 358
30 408
31 470
32 545
33 626
34 709
35 810
36 933
37 1062
38 1198
39 1362
40 1555
41 1760
42 1980
43 2238
44 2536
45 2858
46 3205
47 3602
48 4063
49 4560
50 5092
51 5704
52 6400
53 7150
54 7966
55 8888
56 9928
57 11058
58 12281
59 13654
60 15198
61 16872
62 18684
63 20714
64 22979
65 25432
66 28097
67 31060
68 34346
69 37916
70 41789
71 46072
72 50813
73 55956
74 61527
75 67678
76 74453
77 81792
78 89757
79 98508
80 108114
81 118530
82 129809
83 142166
84 155704
85 170360
86 186221
87 203562
88 222503
89 242988
90 265152
91 289318
92 315644
93 344110
94 374874
95 408336
96 444735
97 484044
98 526477
99 572568
100 622590
101 676554
102 734783
103 797896
104 866269
105 939990
106 1019441
107 1105410
108 1198417
109 1298588
110 1406444
111 1522996
112 1648881
113 1784334
114 1930072
115 2087318
116 2256910
117 2439256
118 2635260
119 2846446
120 3073953
121 3318336
122 3580771
123 3863228
124 4167112
125 4493242
126 4843215
127 5219410
128 5623672
129 6057208
130 6522010
131 7021084
132 7556848
133 8130904
134 8745855
135 9405500
136 10112885
137 10870206
138 11680873
139 12549572
140 13480212
141 14475824
142 15540709
143 16680732
144 17900971
145 19205368
146 20599445
147 22090616
148 23685254
149 25388590
150 27207772
151 29151940
152 31229233
153 33446602
154 35813023
155 38339950
156 41037790
157 43915478
158 46984464
159 50259108
160 53752480
161 57476180
162 61444797
163 65676128
164 70186701
165 74991566
166 80109051
167 85561320
168 91369344
169 97552274
170 104133229
171 111139942
172 118598614
173 126533738
174 134974555
175 143955344
176 153509059
177 163666972
178 174465607
179 185947600
180 198154353
181 211125320
182 224906311
183 239550342
184 255109009
185 271632174
186 289177253
187 307809756
188 327594106
189 348593246
190 370878621
191 394531334
192 419631816
193 446258862
194 474501458
195 504460090
196 536234502
197 569923376
198 605637557
199 643500824
200 683637050
201 726169664
202 771235880
203 818988458
204 869581055
205 923167134
206 979916724
207 1040018168
208 1103661251
209 1171036744
210 1242355061
211 1317847646
212 1397748866
213 1482295540
214 1571747069
215 1666387850
216 1766507106
217 1872397512
218 1984378740
219 2102800128
220 2228017252
221 2360391620
222 2500316819
223 2648220596
224 2804540028
225 2969720984
226 3144246460
227 3328640210
228 3523438837
229 3729190448
230 3946487515
231 4175970696
232 4418297018
233 4674139688
234 4944224548
235 5229333514
236 5530270479
237 5847861138
238 6182992603
239 6536618584
240 6909721620
241 7303311796
242 7718472357
243 8156365592
244 8618189606
245 9105178810
246 9618654561
247 10160030386
248 10730766156
249 11332368426
250 11966445528
251 12634715512
252 13338955034
253 14080998878
254 14862803055
255 15686453472
256 16554108388
257 17467999926
258 18430504122
259 19444149416
260 20511555102
261 21635433310
262 22818665318
263 24064313322
264 25375552677
265 26755672766
266 28208164106
267 29736731712
268 31345218719
269 33037610402
270 34818130758
271 36691255810
272 38661632544
273 40734083568
274 42913712548
275 45205922380
276 47616325801
277 50150749548
278 52815354321
279 55616655056
280 58561421405
281 61656685944
282 64909877116
283 68328840684
284 71921733642
285 75697034304
286 79663687819
287 83831133804
288 88209190725
289 92808065742
290 97638519719
291 102711898990
292 108040006605
293 113635118584
294 119510166846
295 125678772998
296 132155112421
297 138953933374
298 146090757678
299 153581923888
300 161444439105
301 169695999800
302 178355218774
303 187441674402
304 196975747617
305 206978651422
306 217472682782
307 228481276730
308 240028834262
309 252140757764
310 264843727899
311 278165770664
312 292136071843
313 306785016202
314 322144500119
315 338248009088
316 355130414354
317 372828025696
318 391378938783
319 410823120880
320 431202198472
321 452559519698
322 474940536979
323 498392912548
324 522966290359
325 548712367298
326 575685324862
327 603941950472
328 633541391005
329 664545243748
330 697018036547
331 731027364650
332 766643634603
333 803940172512
334 842993754338
335 883884771140
336 926696958355
337 971517519504
338 1018437724165
339 1067553099454
340 1118963139760
341 1172771461748
342 1229086470388
343 1288021575786
344 1349694897135
345 1414229445332
346 1481753860753
347 1552402673544
348 1626315994502
349 1703639726246
350 1784526394916
351 1869135451234
352 1957632946044
353 2050191788666
354 2146992674923
355 2248224431278
356 2354083690363
357 2464775195576
358 2580512832068
359 2701520035400
360 2828029462686
361 2960283344896
362 3098534649339
363 3243047554064
364 3394097111065
365 3551969672526
366 3716964190703
367 3889392761032
368 4069580300932
369 4257865049616
370 4454600016205
371 4660153622412
372 4874909391103
373 5099266526876
374 5333641549946
375 5578469040636
376 5834201340277
377 6101309244672
378 6380283835047
379 6671637334436
380 6975902848629
381 7293635179026
382 7625412868084
383 7971839206154
384 8333542013509
385 8711174583202
386 9105417991215
387 9516982264038
388 9946606206231
389 10395058519456
390 10863140396721
391 11351686866328
392 11861566706883
393 12393683754144
394 12948979807342
395 13528436204458
396 14133073828948
397 14763954626932
398 15422184893181
399 16108917095072
400 16825349987840
401 17572730402496
402 18352356943673
403 19165582093158
404 20013812487721
405 20898511004048
406 21821200912757
407 22783468333312
408 23786962694365
409 24833399150662
410 25924563284850
411 27062313950224
412 28248583940364
413 29485382825386
414 30774802253938
415 32119019230424
416 33520297076327
417 34980988728106
418 36503542708113
419 38090506940444
420 39744530037877
421 41468365123722
422 43264876597641
423 45137044547962
424 47087966419321
425 49120861476730
426 51239078449820
427 53446100621256
428 55745547987419
429 58141182441026
430 60636916398673
431 63236818708296
432 65945117372125
433 68766205543322
434 71704651312710
435 74765204534864
436 77952800200447
437 81272565418908
438 84729830494631
439 88330136792968
440 92079240930921
441 95983122865864
442 100047998420447
443 104280328397158
444 108686823699041
445 113274454679424
446 118050465363727
447 123022383966242
448 128198029091536
449 133585520586872
450 139193295660805
451 145030120997654
452 151105100278069
453 157427686730738
454 164007701389080
455 170855347096522
456 177981217539714
457 185396311734116
458 193112054771233
459 201140313962646
460 209493409617470
461 218184131816690
462 227225763955228
463 236632101319864
464 246417463969185
465 256596716097242
466 267185292734109
467 278199221186760
468 289655136322687
469 301570302889888
470 313962645878979
471 326850775204900
472 340254003766758
473 354192373232262
474 368686688522147
475 383758546189328
476 399430355772769
477 415725369516312
478 432667721519801
479 450282460431454
480 468595574578401
481 487634026172338
482 507425795849616
483 527999920262744
484 549386521553993
485 571616846793138
486 594723318599782
487 618739578317036
488 643700520601017
489 669642338800538
490 696602582472216
491 724620207040680
492 753735614239000
493 783990704272558
494 815428941268858
495 848095410303722
496 882036864571262
497 917301785409760
498 953940456722337
499 992005030404978
500 1031549581371245
501 1072630176522674
502 1115304959342993
503 1159634225037184
504 1205680484547321
505 1253508543721660
506 1303185599589756
507 1354781326544344
508 1408367950666793
509 1464020340676542
510 1521816117426738
511 1581835752668508
512 1644162655353690
513 1708883275980214
514 1776087231087453
515 1845867416520440
516 1918320107417048
517 1993545077828824
518 2071645742398965
519 2152729286107328
520 2236906779936838
521 2324293318068832
522 2415008179021877
523 2509174974176678
524 2606921781557754
525 2708381303021512
526 2813691047478865
527 2922993500984238
528 3036436281210128
529 3154172317406652
530 3276360058870300
531 3403163669552392
532 3534753206187849
533 3671304824389710
534 3813001015722502
535 3960030830218704
536 4112590081750840
537 4270881583834664
538 4435115419159681
539 4605509194081690
540 4782288275062021
541 4965686058295492
542 5155944276279752
543 5353313288640070
544 5558052354047357
545 5770429938556944
546 5990724064149277
547 6219222640889482
548 6456223779557986
549 6702036143985266
550 6956979347202399
551 7221384330841996
552 7495593724162857
553 7779962246419994
554 8074857157260805
555 8380658689788348
556 8697760462473040
557 9026569938675928
558 9367508938507037
559 9721014132874992
560 10087537515942900
561 10467546929553882
562 10861526644779001
563 11269977925546876
564 11693419569993662
565 12132388508647408
566 12587440465266435
567 13059150599438802
568 13548114126383609
569 14054946999212406
570 14580286659578643
571 15124792769964888
572 15689147923059935
573 16274058419444346
574 16880255120020801
575 17508494280429734
576 18159558362266232
577 18834256919093472
578 19533427564523655
579 20257936922479240
580 21008681554199408
581 21786588967544910
582 22592618716017802
583 23427763480454606
584 24293050127997554
585 25189540861201446
586 26118334465355527
587 27080567539621430
588 28077415705842953
589 29110094916229832
590 30179862868982312
591 31288020408796690
592 32435912905851071
593 33624931743674966
594 34856515925225314
595 36132153665389300
596 37453383963540620
597 38821798295574232
598 40239042435545393
599 41706818266148902
600 43226885570849460
601 44801063957262858
602 46431234923146329
603 48119343913732838
604 49867402362910137
605 51677489879123048
606 53551756587705994
607 55492425467774076
608 57501794676257045
609 59582240030985128
610 61736217665575528
611 63966266683309752
612 66275011801642049
613 68665166171738398
614 71139534387271626
615 73701015496953016
616 76352606012150489
617 79097403107698132
618 81938608030668977
619 84879529518723402
620 87923587219478330
621 91074315322579814
622 94335366420527107
623 97710515386577592
624 101203663260175087
625 104818841366787922
626 108560215690063533
627 112432091269277574
628 116438916612204516
629 120585288367048940
630 124875956272081458
631 129315828140386976
632 133909974870052699
633 138663635740011234
634 143582224011839314
635 148671332578829208
636 153936739651548080
637 159384414758705604
638 165020525085896338
639 170851441875034976
640 176883746873459965
641 183124239131868294
642 189579942174726151
643 196258111247182226
644 203166240627736078
645 210312071326162816
646 217703599192409802
647 225349083121048066
648 233257053339417643
649 241436320121586904
650 249895982956709773
651 258645439834130520
652 267694396633178819
653 277052876984595914
654 286731232633629094
655 296740153944519226
656 307090680534829978
657 317794212431346466
658 328862521780286016
659 340307764728118742
660 352142493460297365
661 364379668817253704
662 377032673523948081
663 390115325622614552
664 403641892096013093
665 417627103130661926
666 432086167058406541
667 447034785538799534
668 462489168970347156
669 478466052610437848
670 494982713445741545
671 512056987347414020
672 529707286498150270
673 547952617604477432
674 566812600940599740
675 586307489726255312
676 606458189825873399
677 627286280319108856
678 648814034991866420
679 671064444217745064
680 694061237218412060
681 717828905289941690
682 742392726048728986
683 767778788133214152
684 794014016349084380
685 821126197885942440
686 849144009664743417
687 878097046214221064
688 908015848064724700
689 938931931331961658
690 970877818553856167
691 1003887070139926332
692 1037994316423389569
693 1073235291033677878
694 1109646865658361666
695 1147267085513663518
696 1186135205513413300
697 1226291727903878566
698 1267778441440815883
699 1310638461382731538
700 1354916270291596272
701 1400657760462641752
702 1447910278064865438
703 1496722668220059236
704 1547145321014376612
705 1599230219319095228
706 1653030988509845660
707 1708602947264278656
708 1766003159432483735
709 1825290487917472136
710 1886525650664377071
711 1949771277884801736
712 2015091970513136978
713 2082554360897950736
714 2152227175834397753
715 2224181301009356312
716 2298489846860156926
717 2375228216917242402
718 2454474178746679848
719 2536307936507542498
720 2620812205126536023
721 2708072287233956624
722 2798176152989121951
723 2891214521747097674
724 2987280945573090755
725 3086471895828723728
726 3188886852968215195
727 3294628398431683176
728 3403802308647989118
729 3516517652453275272
730 3632886892076463938
731 3753025986512060244
732 3877054497295857593
733 4005095698079659490
734 4137276688172111117
735 4273728508791694810
736 4414586262053846873
737 4559989234185698584
738 4710081023149114367
739 4865009669342155352
740 5024927789409639500
741 5189992714756484168
742 5360366634961949734
743 5536216744686395390
744 5717715394107102390
745 5905040244586388966
746 6098374429790954635
747 6297906720767142602
748 6503831695018243202
749 6716349911405822816
750 6935668091112423398
751 7161999303081549522
752 7395563153993758327
753 7636585984723135664
754 7885301073534794579
755 8141948844347619632
756 8406777080130719409
757 8680041143511672270
758 8962004204884496126
759 9252937476240405642
760 9553120450804180972
761 9862841150698920568
762 10182396382952279675
763 10512092001964071942
764 10852243178536144985
765 11203174677837069456
766 11565221146645698338
767 11938727407887046696
768 12324048762576725268
769 12721551301709790492
770 13131612228474248595
771 13554620188685677502
772 13990975609580114944
773 14441091049677935386
774 14905391560133091836
775 15384315055345043512
776 15878312692996422076
777 16387849266412456436
778 16913403609698049549
779 17455469013307200016
780 18014553650231002089
781 18591181015900274940
782 19185890382306576754
783 19799237263861995026
784 20431793895214349085
785 21084149724330026996
786 21756911921394789020
787 22450705900916451712
788 23166175857282649141
789 23903985317310979686
790 24664817710397371285
791 25449376953506504956
792 26258388051292072553
793 27092597715129219624
794 27952775001728835724
795 28839711968424696728
796 29754224345464653245
797 30697152229353343520
798 31669360797979286665
799 32671741044462525448
800 33705210530105666092
801 34770714160772320450
802 35869224987500446339
803 37001745028128422176
804 38169306110367023149
805 39372970740942528616
806 40613833001703499349
807 41893019469296979848
808 43211690158909142280
809 44571039497021061328
810 45972297324158178804
811 47416729924065632704
812 48905641079876710019
813 50440373162566031494
814 52022308252766207771
815 53652869292203462792
816 55333521265392130234
817 57065772417250313770
818 58851175507829370266
819 60691329100221554582
820 62587878882372799386
821 64542519028863925632
822 66556993603969576308
823 68633098001867503348
824 70772680424826188232
825 72977643405854917816
826 75249945377260609706
827 77591602280790094964
828 80004689220289167968
829 82491342163820385364
830 85053759696836379932
831 87694204821878695964
832 90415006805855696306
833 93218563082336436074
834 96107341210615720083
835 99083880886812700752
836 102150796008196801199
837 105310776798699246958
838 108566591997547069484
839 111921091106073691792
840 115377206694046014207
841 118937956774032891014
842 122606447245956627709
843 126385874406658955070
844 130279527525991660358
845 134290791498569944262
846 138423149573544808665
847 142680186157006874726
848 147065589688726258762
849 151583155603013856344
850 156236789376305295883
851 161030509655863013170
852 165968451471505744915
853 171054869540854720960
854 176294141670972635384
855 181690772250560844888
856 187249395834860657325
857 192974780834509458480
858 198871833311518855923
859 204945600876317824564
860 211201276688274885656
861 217644203571756791572
862 224279878251220791194
863 231113955699067313736
864 238152253598952552713
865 245400756937495106120
866 252865622728243350755
867 260553184861404025066
868 268469959082358283723
869 276622648112848835330
870 285018146919098689426
871 293663548120149060330
872 302566147539811904841
873 311733449917128722790
874 321173174780040973543
875 330893262475359368908
876 340901880358822989555
877 351207429161236078432
878 361818549535884572458
879 372744128780114132946
880 383993307735310912219
881 395575487882460128986
882 407500338639017446444
883 419777804849791461704
884 432418114476584793835
885 445431786505033374488
886 458829639074978041813
887 472622797826905202734
888 486822704469750064892
889 501441125589876772362
890 516490161708237715966
891 531982256578090141226
892 547930206729181295369
893 564347171279707032858
894 581246682023765983702
895 598642653786563131410
896 616549395053966949200
897 634981618899315951752
898 653954454216003977640
899 673483457248009094976
900 693584623425720421580
901 714274399531689668536
902 735569696205734771903
903 757487900781486870104
904 780046890462580465146
905 803265045864990845194
906 827161264935918115339
907 851754977241287278774
908 877066158631009439317
909 903115346310517657280
910 929923654330063119716
911 957512789483873674904
912 985905067629347403838
913 1015123430456981015372
914 1045191462723726082837
915 1076133409941941491182
916 1107974196535268126016
917 1140739444494499236816
918 1174455492547449829907
919 1209149415835136095126
920 1244849046106877934455
921 1281582992469943876736
922 1319380662709203412689
923 1358272285169321671946
924 1398288931213511888957
925 1439462538297236909068
926 1481825933673946458941
927 1525412858725669346066
928 1570257993934045918103
929 1616396984533202826112
930 1663866466863322111520
931 1712704095418118460886
932 1762948570603557520323
933 1814639667252454720286
934 1867818263915771078149
935 1922526372924333135560
936 1978807171240219018131
937 2036705032145975543284
938 2096265557794660540518
939 2157535612615049122288
940 2220563357593376589193
941 2285398285483616062542
942 2352091256971659670470
943 2420694537788511122820
944 2491261836796230934977
945 2563848345102761484448
946 2638510776233639508330
947 2715307407356643215500
948 2794298121585706267979
949 2875544451424725586328
950 2959109623382191870955
951 3045058603753780957918
952 3133458145602124365262
953 3224376836999280911094
954 3317885150566029902615
955 3414055494306437033438
956 3512962263770113995260
957 3614681895612977756492
958 3719292922594170351147
959 3826876030009144436976
960 3937514113594844294031
961 4051292338983548232400
962 4168298202746949730274
963 4288621595032262447958
964 4412354863830178629533
965 4539592880957518348572
966 4670433109800430488328
967 4804975674822020607680
968 4943323432878558037111
969 5085582046433880339416
970 5231860058722602216634
971 5382268970868431914600
972 5536923321006486735983
973 5695940765506622077246
974 5859442162353625993948
975 6027551656693338151156
976 6200396768598844694156
977 6378108483161820451872
978 6560821342970613769149
979 6748673542987318372040
980 6941807027883806318615
981 7140367591950519987290
982 7344504981645973372997
983 7554373000802861973412
984 7770129618557144077156
985 7991937080123413047418
986 8219962020491529170355
987 8454375581064532904872
988 8695353529311281610272
989 8943076381567509474616
990 9197729529067969104617
991 9459503367234390716672
992 9728593428300530255542
993 10005200517419263614590
994 10289530852342886448419
995 10581796206706716662524
996 10882214057005864448131
997 11191007733422416900314
998 11508406574603577136101
999 11834646086426873966158
1000 12169968104851818279375