0 1
1 0
2 1
3 0
4 2
5 0
6 2
7 0
8 3
9 1
10 3
11 1
12 4
13 2
14 4
15 3
16 6
17 4
18 8
19 5
20 10
21 7
22 13
23 8
24 16
25 11
26 19
27 15
28 23
29 18
30 29
31 25
32 34
33 30
34 43
35 38
36 54
37 46
38 64
39 58
40 79
41 68
42 93
43 86
44 112
45 105
46 133
47 127
48 160
49 156
50 187
51 188
52 228
53 226
54 270
55 269
56 320
57 323
58 381
59 379
60 450
61 456
62 531
63 538
64 625
65 637
66 737
67 754
68 860
69 888
70 1013
71 1042
72 1184
73 1222
74 1381
75 1433
76 1614
77 1668
78 1877
79 1957
80 2183
81 2278
82 2534
83 2652
84 2943
85 3084
86 3397
87 3578
88 3946
89 4140
90 4552
91 4790
92 5258
93 5534
94 6061
95 6374
96 6983
97 7361
98 8025
99 8464
100 9225
101 9731
102 10584
103 11179
104 12124
105 12822
106 13903
107 14686
108 15897
109 16815
110 18173
111 19226
112 20759
113 21951
114 23682
115 25072
116 26987
117 28567
118 30742
119 32546
120 34977
121 37038
122 39751
123 42112
124 45181
125 47825
126 51263
127 54294
128 58149
129 61563
130 65893
131 69745
132 74616
133 78997
134 84408
135 89353
136 95451
137 101025
138 107818
139 114132
140 121716
141 128845
142 137341
143 145326
144 154816
145 163840
146 174418
147 184539
148 196380
149 207729
150 220948
151 233715
152 248412
153 262717
154 279161
155 295170
156 313470
157 331426
158 351791
159 371888
160 394611
161 417010
162 442298
163 467397
164 495512
165 523480
166 554802
167 586003
168 620818
169 655648
170 694283
171 733099
172 776092
173 819284
174 866963
175 915123
176 968023
177 1021580
178 1080316
179 1139823
180 1204951
181 1271152
182 1343310
183 1416790
184 1496845
185 1578388
186 1667036
187 1757579
188 1855696
189 1956070
190 2064762
191 2175983
192 2296188
193 2419506
194 2552432
195 2688952
196 2835992
197 2987045
198 3149525
199 3316738
200 3496211
201 3681062
202 3879372
203 4083684
204 4302552
205 4528387
206 4769859
207 5019265
208 5285746
209 5561042
210 5854822
211 6158782
212 6482576
213 6817795
214 7174730
215 7544328
216 7937474
217 8344951
218 8777846
219 9226728
220 9703442
221 10197756
222 10722270
223 11266654
224 11843643
225 12442658
226 13077310
227 13736297
228 14433933
229 15158814
230 15925455
231 16722285
232 17564734
233 18440364
234 19365502
235 20327634
236 21343367
237 22399890
238 23514948
239 24674812
240 25898178
241 27171325
242 28513210
243 29909885
244 31381536
245 32913371
246 34526539
247 36206305
248 37974119
249 39815104
250 41752150
251 43769350
252 45890768
253 48100537
254 50423416
255 52843119
256 55386017
257 58034802
258 60817415
259 63716544
260 66760683
261 69932312
262 73261893
263 76730922
264 80371283
265 84164665
266 88143774
267 92290295
268 96638945
269 101170244
270 105920806
271 110871595
272 116060176
273 121467256
274 127132899
275 133036894
276 139221390
277 145666638
278 152415817
279 159449354
280 166813289
281 174487142
282 182519187
283 190889654
284 199648338
285 208775770
286 218324950
287 228275324
288 238682921
289 249528172
290 260869015
291 272685941
292 285040827
293 297913460
294 311369210
295 325389011
296 340040276
297 355304719
298 371254485
299 387870696
300 405228971
301 423312364
302 442199484
303 461874411
304 482420716
305 503822233
306 526167334
307 549442213
308 573738582
309 599043808
310 625455983
311 652962900
312 681668018
313 711561796
314 742751979
315 775231381
316 809115034
317 844396331
318 881196685
319 919513433
320 959473402
321 1001076696
322 1044458659
323 1089620751
324 1136706396
325 1185721884
326 1236817216
327 1290002109
328 1345437079
329 1403134463
330 1463264026
331 1525844052
332 1591052396
333 1658912784
334 1729615193
335 1803186948
336 1879828915
337 1959576631
338 2042641036
339 2129064369
340 2219071703
341 2312710733
342 2410220407
343 2511658290
344 2617275281
345 2727137608
346 2841514004
347 2960477985
348 3084314409
349 3213109260
350 3347162705
351 3486572061
352 3631658357
353 3782528629
354 3939523592
355 4102766298
356 4272616273
357 4449210640
358 4632933969
359 4823936741
360 5022627588
361 5229176438
362 5444015092
363 5667331648
364 5899588215
365 6140990279
366 6392028832
367 6652933828
368 6924224662
369 7206154824
370 7499279803
371 7803875477
372 8120532443
373 8449557558
374 8791576153
375 9146924243
376 9516270948
377 9899981294
378 10298767354
379 10713031889
380 11143529923
381 11590700842
382 12055352934
383 12537962193
384 13039388877
385 13560156002
386 14101176887
387 14663020543
388 15246663791
389 15852722420
390 16482236916
391 17135881115
392 17814759934
393 18519604923
394 19251598364
395 20011530440
396 20800660592
397 21619850773
398 22470439690
399 23353360968
400 24270046811
401 25221504380
402 26209259788
403 27234409210
404 28298575291
405 29402943061
406 30549248358
407 31738768696
408 32973353829
409 34254390427
410 35583846707
411 36963219397
412 38394613935
413 39879641703
414 41420547133
415 43019075155
416 44677615805
417 46398049794
418 48182933008
419 50034288037
420 51954840596
421 53946777606
422 56013001481
423 58155866554
424 60378476475
425 62683362018
426 65073832324
427 67552619099
428 70123247296
429 72788655436
430 75552612251
431 78418272983
432 81389655938
433 84470163122
434 87664076698
435 90975051235
436 94407663272
437 97965835404
438 101654448498
439 105477725833
440 109440868088
441 113548409231
442 117805907110
443 122218224832
444 126791288841
445 131530328551
446 136441660800
447 141530895991
448 146804782747
449 152269333037
450 157931744011
451 163798475432
452 169877198633
453 176174837170
454 182699585034
455 189458858855
456 196461396443
457 203715158950
458 211229458701
459 219012823994
460 227075200010
461 235425717772
462 244074979416
463 253032777928
464 262310414506
465 271918373947
466 281868720618
467 292172672958
468 302843093094
469 313892004691
470 325333116264
471 337179291445
472 349445161318
473 362144484681
474 375292858710
475 388905017232
476 402997581095
477 417586307348
478 432688932531
479 448322299994
480 464505312738
481 481255997159
482 498594497824
483 516540081663
484 535114237984
485 554337552651
486 574232926720
487 594822378813
488 616130309653
489 638180240606
490 660998194870
491 684609295970
492 709041270919
493 734320974422
494 760477944087
495 787540857894
496 815541208891
497 844509613434
498 874479619638
499 905483937490
500 937558301912
501 970737627151
502 1005060002282
503 1040562685429
504 1077286246432
505 1115270471781
506 1154558565771
507 1195192976650
508 1237219745242
509 1280684153829
510 1325635229839
511 1372121303141
512 1420194576575
513 1469906595023
514 1521312973026
515 1574468674143
516 1629432907804
517 1686264311317
518 1745025918847
519 1805780242752
520 1868594416245
521 1933535074687
522 2000673678378
523 2070081284975
524 2141833951885
525 2216007405614
526 2292682629977
527 2371940318063
528 2453866652362
529 2538547645195
530 2626075004571
531 2716540363319
532 2810041343007
533 2906675549969
534 3006546849618
535 3109759243482
536 3216423233874
537 3326649576310
538 3440555867019
539 3558260043695
540 3679887197484
541 3805562943105
542 3935420334766
543 4069593100784
544 4208222800765
545 4351451788467
546 4499430610042
547 4652310828646
548 4810252539381
549 4973417044829
550 5141974626853
551 5316096935155
552 5495965022071
553 5681761579267
554 5873679097343
555 6071911944220
556 6276664806563
557 6488144457173
558 6706568477900
559 6932156867720
560 7165140900188
561 7405754563747
562 7654243722179
563 7910857221393
564 8175856351489
565 8449505789400
566 8732083205072
567 9023870019446
568 9325161342132
569 9636256374789
570 9957468672411
571 10289116367049
572 10631532592512
573 10985055506828
574 11350039077724
575 11726842723036
576 12115842446964
577 12517420287321
578 12931975633438
579 13359914457205
580 13801661017315
581 14257646683253
582 14728322021684
583 15214145414342
584 15715595336924
585 16233158748002
586 16767343790986
587 17318667746418
588 17887670140245
589 18474900480785
590 19080931580357
591 19706347044587
592 20351755052646
593 21017775378830
594 21705053610272
595 22414247945994
596 23146043647041
597 23901139563983
598 24680263084236
599 25484156169407
600 26313590773021
601 27169354634246
602 28052266952631
603 28963163896758
604 29902914817957
605 30872407231311
606 31872563539293
607 32904325752341
608 33968672502004
609 35066603453795
610 36199156903492
611 37367393620796
612 38572415007872
613 39815346670410
614 41097356885044
615 42419639838197
616 43783434733463
617 45190008432278
618 46640675157809
619 48136778848382
620 49679713201198
621 51270903677844
622 52911828242266
623 54603998728227
624 56348982213988
625 58148382095400
626 60003859843468
627 61917115698916
628 63889911174453
629 65924049078624
630 68021396718040
631 70183865607805
632 72413435084047
633 74712131616685
634 77082053237414
635 79525348143242
636 82044239877556
637 84641005600399
638 87318001724969
639 90077641775121
640 92922422909670
641 95854903013531
642 98877728040696
643 101993608769151
644 105205348651689
645 108515820116383
646 111927993384845
647 115444911971826
648 119069722393699
649 122805649315823
650 126656025814898
651 130624268048241
652 134713906572630
653 138928560182008
654 143271968175399
655 147747963825452
656 152360507267588
657 157113658480011
658 162011611309884
659 167058665567689
660 172259262093816
661 177617954482608
662 183139444834821
663 188828554956581
664 194690263353934
665 200729675504282
666 206952061996376
667 213362828415008
668 219967554225158
669 226771962115891
670 233781958255923
671 241003600663043
672 248443140685460
673 256106990983588
674 264001767855235
675 272134258651641
676 280511465589355
677 289140572143947
678 298028988208526
679 307184316099245
680 316614396654721
681 326327274641020
682 336331246473753
683 346634824575362
684 357246786569321
685 368176139240066
686 379432168757796
687 391024404044383
688 402962668771157
689 415257043636822
690 427917919957514
691 440955961566280
692 454382159552785
693 468207793560812
694 482444488462787
695 497104174519740
696 512199145811580
697 527742020044527
698 543745798257705
699 560223823995977
700 577189845153074
701 594657971990593
702 612642740897819
703 631159072063771
704 650222334665522
705 669848303918769
706 690053228604183
707 710853786937575
708 732267156189500
709 754310968243058
710 777003380824393
711 800363032442599
712 824409116169320
713 849161333382731
714 874639969870160
715 900865849296019
716 927860411089108
717 955645663310660
718 984244263359171
719 1013679469634620
720 1043975224788100
721 1075156107172093
722 1107247416080998
723 1140275122641450
724 1174265958150950
725 1209247363768830
726 1245247581647072
727 1282295604494247
728 1320421268946208
729 1359655204597118
730 1400028930785962
731 1441574804450668
732 1484326120010464
733 1528317057167311
734 1573582783310887
735 1620159400845106
736 1668084053363620
737 1717394871839654
738 1768131084226575
739 1820332961701628
740 1874041931095996
741 1929300520768248
742 1986152477185464
743 2044642709713317
744 2104817410996065
745 2166724001956161
746 2230411255343662
747 2295929240465718
748 2363329451343041
749 2432664750443676
750 2503989501047048
751 2577359511360897
752 2652832170456191
753 2730466392254286
754 2810322756567169
755 2892463452210506
756 2976952422701720
757 3063855309985866
758 3153239604161197
759 3245174587245938
760 3339731488549703
761 3436983427743501
762 3537005575425626
763 3639875097040240
764 3745671317987951
765 3854475667814725
766 3966371851604381
767 4081445793650975
768 4199785814656764
769 4321482576554302
770 4446629264841947
771 4575321533951621
772 4707657696572047
773 4843738668740751
774 4983668165656449
775 5127552648307741
776 5275501525077373
777 5427627099240925
778 5584044778358748
779 5744873021835252
780 5910233557553423
781 6080251331409381
782 6255054730503393
783 6434775533943726
784 6619549144737133
785 6809514541044887
786 7004814516173298
787 7205595632319777
788 7412008468017512
789 7624207573641715
790 7842351728543207
791 8066603897478848
792 8297131496860856
793 8534106354307479
794 8777704983311901
795 9028108545135039
796 9285503134326132
797 9550079742125649
798 9822034552231131
799 10101568908034049
800 10388889617932150
801 10684208925622710
802 10987744827599862
803 11299721045615225
804 11620367355688494
805 11949919565291446
806 12288619853223865
807 12636716750657408
808 12994465494655860
809 13362128012245992
810 13739973286915525
811 14128277348427619
812 14527323651645736
813 14937403071190353
814 15358814295585624
815 15791863825977425
816 16236866384902442
817 16694144921916044
818 17164031036384330
819 17646864989153969
820 18142996142571399
821 18652782977365704
822 19176593549185759
823 19714805513815628
824 20267806599676069
825 20835994640444664
826 21419778066938980
827 22019575946344243
828 22635818492811825
829 23268947116669858
830 23919414953153538
831 24587686920616474
832 25274240271160783
833 25979564657137305
834 26704162702913442
835 27448550083238370
836 28213256115713867
837 28998823850079550
838 29805810685378205
839 30634788469448685
840 31486344140056827
841 32361079838503112
842 33259613574372520
843 34182579352255159
844 35130627864355239
845 36104426629754871
846 37104660714236350
847 38132032886235235
848 39187264363542263
849 40271094985009455
850 41384283988782892
851 42527610199236542
852 43701872836057908
853 44907891720900790
854 46146508117155402
855 47418584955404067
856 48725007708886692
857 50066684637282994
858 51444547697239201
859 52859552809421615
860 54312680804081042
861 55804937710392488
862 57337355742456132
863 58910993610680892
864 60526937547660312
865 62186301646870937
866 63890228928534434
867 65639891704751727
868 67436492691224898
869 69281265398732262
870 71175475290181216
871 73120420204103073
872 75117431557421032
873 77167874800211763
874 79273150670457425
875 81434695680103482
876 83653983421467516
877 85932525090827783
878 88271870847018322
879 90673610371832795
880 93139374287664837
881 95670834755044637
882 98269706949098342
883 100937749700950912
884 103676767033800958
885 106488608847628753
886 109375172522384270
887 112338403646557558
888 115380297687350301
889 118502900770467498
890 121708311418483074
891 124998681381398622
892 128376217451295030
893 131843182344564262
894 135401896592978274
895 139054739485585687
896 142804151037759553
897 146652632992525858
898 150602750876382608
899 154657135061366155
900 158818482908058957
901 163089559897076700
902 167473201861210342
903 171972316186428776
904 176589884142782023
905 181328962156594719
906 186192684240839488
907 191184263348063221
908 196306993902705085
909 201564253235122952
910 206959504226366576
911 212496296825497920
912 218178270807905342
913 224009157386395368
914 229992782086098304
915 236133066450021508
916 242434031042062962
917 248899797249899007
918 255534590417580800
919 262342741757184539
920 269328691614795659
921 276496991492088595
922 283852307458256673
923 291399422285081001
924 299143239006870380
925 307088783181541885
926 315241206603147282
927 323605789690703089
928 332187945367086741
929 340993221579952973
930 350027305349722996
931 359296025436382762
932 368805356561993501
933 378561422225793174
934 388570499116401293
935 398839020080458978
936 409373578727983379
937 420180932569796792
938 431268007822501125
939 442641902717833034
940 454309892523980634
941 466279433033226837
942 478558165803907685
943 491153921843133112
944 504074727077119764
945 517328806233012948
946 530924588555993416
947 544870711897861521
948 559176028686244565
949 573849610238430203
950 588900752991830135
951 604338983048218076
952 620174062685695313
953 636415995142393477
954 653075031416535416
955 670161675310087026
956 687686690527620908
957 705661105986314570
958 724096223236032389
959 743003622046359309
960 762395168155945908
961 782283019159286338
962 802679632597775434
963 823597772154103693
964 845050516109967207
965 867051263860643243
966 889613744748903201
967 912752024925022046
968 936480516571538301
969 960813985118261125
970 985767558885410666
971 1011356736668400720
972 1037597397810872918
973 1064505810187314457
974 1092098640723026661
975 1120392963786072029
976 1149406272184718501
977 1179156485986109984
978 1209661964004957279
979 1240941513079988510
980 1273014400073643775
981 1305900361620272280
982 1339619616670810007
983 1374192876732862011
984 1409641358976658049
985 1445986797001730061
986 1483251454527063709
987 1521458136701002301
988 1560630204413384316
989 1600791586172034433
990 1641966793056214886
991 1684180931198540412
992 1727459717406150195
993 1771829492267625502
994 1817317236484134597
995 1863950584628624029
996 1911757842209570134
997 1960768000125670372
998 2011010752492759478
999 2062516511817305119
1000 2115316427633603548