0 1
1 0
2 1
3 1
4 1
5 1
6 3
7 1
8 3
9 4
10 4
11 4
12 8
13 5
14 9
15 11
16 11
17 12
18 20
19 15
20 23
21 27
22 28
23 31
24 45
25 38
26 52
27 61
28 64
29 71
30 96
31 87
32 112
33 129
34 136
35 151
36 194
37 184
38 227
39 259
40 275
41 304
42 376
43 368
44 441
45 499
46 531
47 586
48 704
49 705
50 826
51 927
52 989
53 1088
54 1280
55 1302
56 1500
57 1672
58 1787
59 1960
60 2267
61 2332
62 2652
63 2940
64 3144
65 3439
66 3924
67 4071
68 4581
69 5053
70 5406
71 5896
72 6656
73 6948
74 7752
75 8513
76 9108
77 9908
78 11085
79 11624
80 12878
81 14088
82 15069
83 16353
84 18160
85 19107
86 21043
87 22940
88 24528
89 26557
90 29309
91 30911
92 33873
93 36812
94 39340
95 42503
96 46657
97 49293
98 53784
99 58288
100 62252
101 67123
102 73346
103 77584
104 84336
105 91166
106 97299
107 104717
108 113972
109 120653
110 130725
111 140984
112 150360
113 161540
114 175205
115 185566
116 200475
117 215752
118 229925
119 246617
120 266658
121 282496
122 304408
123 326967
124 348175
125 372877
126 402080
127 425984
128 457968
129 491024
130 522464
131 558720
132 601008
133 636680
134 683059
135 731148
136 777349
137 830160
138 891031
139 943724
140 1010557
141 1080032
142 1147380
143 1223753
144 1310875
145 1387988
146 1483720
147 1583445
148 1680881
149 1790585
150 1914590
151 2026484
152 2162828
153 2305099
154 2445069
155 2601650
156 2777220
157 2938317
158 3131437
159 3333221
160 3532963
161 3755107
162 4002424
163 4232679
164 4504783
165 4789392
166 5072652
167 5386019
168 5732693
169 6059579
170 6441040
171 6840355
172 7239687
173 7679347
174 8163004
175 8624155
176 9156335
177 9713763
178 10273592
179 10887268
180 11558974
181 12205691
182 12944696
183 13719099
184 14499781
185 15352145
186 16280924
187 17182841
188 18204464
189 19275348
190 20358533
191 21536876
192 22815693
193 24066916
194 25473168
195 26947499
196 28443208
197 30064899
198 31818504
199 33545692
200 35473372
201 37494547
202 39550460
203 41772729
204 44167928
205 46540906
206 49172812
207 51932393
208 54745996
209 57778732
210 61037831
211 64283448
212 67863031
213 71616032
214 75450495
215 79572922
216 83991220
217 88411424
218 93261845
219 98346661
220 103551487
221 109133855
222 115102367
223 121097702
224 127646579
225 134510824
226 141548640
227 149080356
228 157115272
229 165215333
230 174026784
231 183260717
232 192741981
233 202867968
234 213648715
235 224551517
236 236367535
237 248747249
238 261475028
239 275042648
240 289460938
241 304083700
242 319877456
243 336420460
244 353448096
245 371567527
246 390790460
247 410334924
248 431379260
249 453415875
250 476121089
251 500242815
252 525793833
253 551830064
254 579785319
255 609050212
256 639230048
257 671244132
258 705106603
259 739680313
260 776706651
261 815455857
262 855448096
263 897811016
264 942560588
265 988330200
266 1037230993
267 1088391214
268 1141229288
269 1197125668
270 1256098915
271 1316510252
272 1380914704
273 1448273426
274 1517883627
275 1591432029
276 1668940901
277 1748449408
278 1833044634
279 1921491661
280 2012943680
281 2109457900
282 2211061964
283 2315414709
284 2426240136
285 2542073823
286 2661898417
287 2788218608
288 2921069827
289 3057662713
290 3202482749
291 3353797584
292 3510388528
293 3675299972
294 3848578572
295 4026907948
296 4215682815
297 4412858941
298 4616980632
299 4831742384
300 5057206883
301 5289439345
302 5534918877
303 5791239188
304 6056666556
305 6335677504
306 6628357437
307 6930047467
308 7248518552
309 7580945328
310 7925268966
311 8286905559
312 8665972388
313 9056964561
314 9469190337
315 9899340800
316 10344978195
317 10812646216
318 11302506401
319 11808067592
320 12340465560
321 12895835184
322 13471298692
323 14074751432
324 14706415924
325 15358653718
326 16044771007
327 16760265056
328 17501748957
329 18278736608
330 19091533782
331 19931170507
332 20813528200
333 21733375809
334 22686739556
335 23685069573
336 24728784376
337 25807372223
338 26939767332
339 28119909893
340 29343152484
341 30623259200
342 31960800192
343 33343482660
344 34793856793
345 36304923581
346 37871265688
347 39509410116
348 41220129472
349 42989078616
350 44843087267
351 46774096833
352 48775814142
353 50868062308
354 53051882555
355 55310570758
356 57676017674
357 60138975145
358 62692158799
359 65359320688
360 68141856372
361 71020357373
362 74032695520
363 77168294320
364 80418753931
365 83812506025
366 87351410952
367 91012968627
368 94842114337
369 98826797352
370 102957370257
371 107267834404
372 111760656703
373 116409812959
374 121268574929
375 126323266877
376 131562855937
377 137027967801
378 142721857192
379 148614495096
380 154768986371
381 161169878157
382 167804611339
383 174721685096
384 181925372792
385 189381109293
386 197163591252
387 205255440307
388 213642431491
389 222382416455
390 231480980109
391 240898437368
392 250723142819
393 260935654576
394 271519949583
395 282544982109
396 294018019164
397 305893618541
398 318276219316
399 331144197656
400 344479615444
401 358364599940
402 372808567484
403 387759628973
404 403341156912
405 419529258826
406 436303990600
407 453763100896
408 471918742735
409 490711840240
410 510288043469
411 530621151992
412 551689165288
413 573608347624
414 596394325201
415 619980050462
416 644537375577
417 670037820676
418 696457337301
419 723934125669
420 752488206025
421 782043737965
422 812803380435
423 844736496564
424 877817081292
425 912209311752
426 947938750763
427 984919920548
428 1023391688560
429 1063321510408
430 1104681629456
431 1147666972398
432 1192310073868
433 1238514969340
434 1286563070768
435 1336420344562
436 1388057640024
437 1441706269011
438 1497407512176
439 1555054090223
440 1614977390126
441 1677142528931
442 1741519521016
443 1808382716375
444 1877784339476
445 1949605024351
446 2024234846296
447 2101638999889
448 2181787487251
449 2265005548563
450 2351359069027
451 2440715926552
452 2533535101445
453 2629783161337
454 2729431259337
455 2832864791232
456 2940166654679
457 3051191465481
458 3166479086983
459 3285999225422
460 3409725784561
461 3538115246863
462 3671271649495
463 3809036081683
464 3952043332204
465 4100268606112
466 4253690713168
467 4412850115939
468 4577877063500
469 4748599195819
470 4925762688688
471 5109351354544
472 5299351766923
473 5496403573880
474 5700669459544
475 5911964161147
476 6131164537781
477 6358267054900
478 6593269790696
479 6836929507683
480 7089448946946
481 7350631118691
482 7621506183868
483 7902088473973
484 8192392418253
485 8493313030040
486 8805102427253
487 9127553898583
488 9461877418772
489 9808111847380
490 10166294188048
491 10537482618557
492 10921990011527
493 11319603019568
494 11731742505648
495 12158480311167
496 12599883946096
497 13057204114037
498 13530828311193
499 14020541029168
500 14528010440651
501 15053352030460
502 15596673859984
503 16159453755640
504 16742170717832
505 17344613324207
506 17968739745144
507 18614722483016
508 19282722799604
509 19974486404318
510 20690604318246
511 21430877695040
512 22197604734152
513 22991031652892
514 23811388762000
515 24660737667542
516 25539806312200
517 26448419735087
518 27389274801963
519 28362712203068
520 29369051067716
521 30410725447013
522 31488630387185
523 32602629646360
524 33755887479100
525 34948864756329
526 36181993987547
527 37458148258799
528 38778426254524
529 40142749669104
530 41554830686098
531 43015282085200
532 44524680160618
533 46086415434904
534 47701834399469
535 49370941329455
536 51098090725800
537 52884086311639
538 54729685679151
539 56638889080017
540 58613344144967
541 60653169067440
542 62763471280791
543 64945293336584
544 67199620268332
545 69531170683398
546 71941957671432
547 74432252906780
548 77008046381744
549 79670678062272
550 82421417023064
551 85265828056165
552 88206367190368
553 91243509216924
554 94384278587720
555 97630384183968
556 100983448368179
557 104450032515472
558 108033128821659
559 111733477132000
560 115559314352629
561 119512805342641
562 123596010266958
563 127816664003781
564 132178406968035
565 136682320976878
566 141338063950901
567 146148362511639
568 151115817542812
569 156249545504912
570 161553969564116
571 167030608624433
572 172690785982056
573 178537918294551
574 184575272225949
575 190813590496148
576 197258240375492
577 203911295022477
578 210786029397727
579 217886705445179
580 225217407278698
581 232790791531672
582 240613362900704
583 248687892634013
584 257029942741887
585 265644808020734
586 274537573628722
587 283723148222040
588 293209405317100
589 302999990268826
590 313113145006317
591 323555423404852
592 334333133514080
593 345463833340492
594 356957041912872
595 368817493472003
596 381066570029188
597 393712356958527
598 406762652820632
599 420238131786497
600 434150288940176
601 448505208793112
602 463327952367789
603 478628464085357
604 494416355338776
605 510715964790638
606 527541158085408
607 544899687330112
608 562820923665142
609 581317063821896
610 600399919641600
611 620098138198536
612 640428426112631
613 661400587448413
614 683049042425559
615 705388711596723
616 728434072712976
617 752218837255259
618 776763113248096
619 802079221290643
620 828207495815368
621 855166145778688
622 882972873008408
623 911667340746443
624 941273725505556
625 971807424840285
626 1003315700102116
627 1035820723821648
628 1069344090352125
629 1103932455966216
630 1139614859020062
631 1176410448805105
632 1214374598864769
633 1253534251743872
634 1293915693821169
635 1335573795960783
636 1378543401097556
637 1422848221319828
638 1468553129383363
639 1515690799956344
640 1564293166516897
641 1614424747201586
642 1666127308844239
643 1719430099581232
644 1774409114212201
645 1831103906066156
646 1889553195298560
647 1949832827141276
648 2011992820236000
649 2076069124819451
650 2142150756126033
651 2210285510985537
652 2280520254411510
653 2352944127771536
654 2427616975635772
655 2504582845319136
656 2583945992808324
657 2665764081443732
658 2750093738040536
659 2837039707488432
660 2926673524819026
661 3019049000919441
662 3114288228848160
663 3212460666518850
664 3313634625518204
665 3417933157330286
666 3525441694287916
667 3636225799033608
668 3750428437060688
669 3868133149067883
670 3989422215985181
671 4114440161552672
672 4243288925437108
673 4376048190963411
674 4512885343937794
675 4653900720904541
676 4799193283614817
677 4948932734346456
678 5103240604717844
679 5262213517855573
680 5426047425872910
681 5594862674991135
682 5768778122846828
683 5947992988129408
684 6132652037270872
685 6322872184118140
686 6518882790900576
687 6720828017151235
688 6928850425010915
689 7143183825071960
690 7364000517656454
691 7591441685870895
692 7825775759762444
693 8067175209948329
694 8315810810736387
695 8571956901248872
696 8835818385652228
697 9107565434892736
698 9387512153534824
699 9675864637374215
700 9972827203195233
701 10278721660254193
702 10593791491513684
703 10918241446180137
704 11252439016228567
705 11596630196045664
706 11951059142572628
707 12316103249230501
708 12692051614508756
709 13079150182543460
710 13477828834639746
711 13888380863752575
712 14311097701378403
713 14746421806412384
714 15194696174551312
715 15656215768541289
716 16131483362544368
717 16620848270110439
718 17124657966437969
719 17643431051136648
720 18177574157616942
721 18727440509397088
722 19293618025709427
723 19876522313126360
724 20476567225864524
725 21094360436962893
726 21730383666464224
727 22385059306532535
728 23059074709441567
729 23752923864199024
730 24467099175800410
731 25202312487220380
732 25959134053564537
733 26738068298065000
734 27539918663189592
735 28365271737807901
736 29214712801360613
737 30089075482949832
738 30989034360015237
739 31915191041061992
740 32868484472201740
741 33849610550281505
742 34859264272732704
743 35898421603999165
744 36967879965299262
745 38068355989887292
746 39200946746555337
747 40366477061586088
748 41565771442802948
749 42799972152091852
750 44070021170401912
751 45376771139319802
752 46721503596207612
753 48105195323852920
754 49528823581532624
755 50993724860437336
756 52501011147446217
757 54051695754882260
758 55647275365966531
759 57288905725707656
760 58977744116542256
761 60715353806594465
762 62503046588288195
763 64342025408672880
764 66234037806392296
765 68180450139725446
766 70182631693920884
767 72242410426532115
768 74361332813050442
769 76540825425713504
770 78782928212685510
771 81089255217118946
772 83461425202465552
773 85901574961380090
774 88411526449715556
775 90992969725097707
776 93648285484837128
777 96379378850065628
778 99188161949368920
779 102077131795457004
780 105048433519360970
781 108104067374459420
782 111246811022091719
783 114478911422494040
784 117802625431899944
785 121220870072621461
786 124736169378218320
787 128350888497604312
788 132068267407797479
789 135890954252256616
790 139821610688586830
791 143863643292026132
792 148020020075465712
793 152293535095641625
794 156687966593499188
795 161206433232662443
796 165852071691164725
797 170628858955746217
798 175540282972114459
799 180589641565380839
800 185781339473964784
801 191119046846539912
802 196606457409614152
803 202248212541723452
804 208048408721843731
805 214010935033944736
806 220140925185502249
807 226442695298524120
808 232920591913977196
809 239580029993294167
810 246425817847181642
811 253462538004749969
812 260696172109368163
813 268131792464242312
814 275774510164139701
815 283630640570309088
816 291705824196869952
817 300005456294335291
818 308536504512269444
819 317304925805902368
820 326316726125808209
821 335579268466497285
822 345099165739742727
823 354882765056953832
824 364938180260339687
825 375272402635004704
826 385892484849765416
827 396807008405984392
828 408023721810821768
829 419550086250058345
830 431395547539732646
831 443568305585969467
832 456076636667668427
833 468930539029060281
834 482139086652526468
835 495711043801114324
836 509657403655681344
837 523987777587021540
838 538711871417722799
839 553841330029774767
840 569386773694953964
841 585358489843254780
842 601769268653750248
843 618630368911481796
844 635953165596786992
845 653751216740490625
846 672036945565412156
847 690822418813030304
848 710122512879588248
849 729950408280920624
850 750319427809934115
851 771245351491239797
852 792742703682069552
853 814825628375531137
854 837511423149989300
855 860815509011467104
856 884753480452369287
857 909343697262146513
858 934603131187955120
859 960548349840797616
860 987199459792273831
861 1014574492754656526
862 1042691691186909733
863 1071572408938174655
864 1101236467031818937
865 1131703259143801538
866 1162996149676503485
867 1195136210814173740
868 1228144769878355160
869 1262046654349822060
870 1296865000763511187
871 1332622496221231112
872 1369346282241403094
873 1407060970129824116
874 1445791479110570701
875 1485566665226013035
876 1526413521158732548
877 1568358569899337912
878 1611433330661930849
879 1655666532168373159
880 1701087273699864303
881 1747729081754022325
882 1795623431781942332
883 1844801311974197352
884 1895299313597822309
885 1947150953131105342
886 2000390191825278135
887 2055055968846711057
888 2111184968365278832
889 2168813373467321037
890 2227983649969257195
891 2288734878776595672
892 2351106673347440280
893 2415144243415363708
894 2480890322515097895
895 2548387134302007966
896 2617683946294270288
897 2688826303273416432
898 2761860386237820431
899 2836838666741457935
900 2913810900713175512
901 2992826331982067184
902 3073942100564891188
903 3157211256276340307
904 3242687607391031951
905 3330432032204220044
906 3420502434802007836
907 3512956213387381127
908 3607859616739520308
909 3705274404350754747
910 3805263238123420036
911 3907896725025655700
912 4013242219203633800
913 4121366585803059123
914 4232346609167185536
915 4346254151644067148
916 4463162147277874185
917 4583152457467634891
918 4706303391370969049
919 4832692799352793840
920 4962409647452350547
921 5095537511377382173
922 5232161237360637688
923 5372375701610424591
924 5516271907220003768
925 5663940445184538598
926 5815484361756518592
927 5971000806918696667
928 6130588434423215265
929 6294357165636540152
930 6462412706009627872
931 6634860415824930947
932 6811819610386480684
933 6993403163282752611
934 7179725725171423919
935 7370914603462598901
936 7567092524679564665
937 7768381961773015067
938 7974921021779773712
939 8186840783277107920
940 8404274421789963201
941 8627369328729768964
942 8856267927527664872
943 9091112509530556520
944 9332062879945950880
945 9579271185860986196
946 9832892045307222784
947 10093096042092387879
948 10360048383245964455
949 10633914301243564004
950 10914878646882594229
951 11203117938884729316
952 11498811603739493671
953 11802156997658976857
954 12113345670451765125
955 12432569398166030442
956 12760041931173957189
957 13095967968468212385
958 13440555626511175200
959 13794033155646274495
960 14156622550804467048
961 14528546285675911232
962 14910051445897982676
963 15301375300445721779
964 15702759129939012631
965 16114466822610602108
966 16536755545024146025
967 16969883256649223296
968 17414135481843201176
969 17869787116950351411
970 18337117761974616519
971 18816432400800225732
972 19308028815114730695
973 19812205966849339855
974 20329293688832274392
975 20859610329053423735
976 21403479744416130617
977 21961254291514597088
978 22533278633938791996
979 23119899089536360488
980 23721496548428171922
981 24338439515039345045
982 24971102938931864417
983 25619893766264392044
984 26285210754312398560
985 26967454891002369119
986 27667065880675055580
987 28384470099573262208
988 29120101456672886756
989 29874429782205509637
990 30647916223232598180
991 31441024854499899152
992 32254263107190800415
993 33088124104207145378
994 33943109763618066278
995 34819762329555380068
996 35718614878680743559
997 36640204254220794788
998 37585115851278875272
999 38553919744021950437
1000 39547196266028073751