0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 42
11 56
12 76
13 99
14 130
15 168
16 216
17 274
18 348
19 435
20 544
21 674
22 831
23 1017
24 1244
25 1507
26 1823
27 2193
28 2629
29 3136
30 3734
31 4420
32 5223
33 6148
34 7215
35 8438
36 9850
37 11453
38 13292
39 15382
40 17758
41 20447
42 23502
43 26935
44 30818
45 35181
46 40082
47 45570
48 51729
49 58589
50 66259
51 74796
52 84293
53 94833
54 106543
55 119485
56 133822
57 149651
58 167116
59 186351
60 207547
61 230813
62 256387
63 284427
64 315151
65 348766
66 385550
67 425685
68 469512
69 517276
70 569297
71 625886
72 687443
73 754251
74 826791
75 905430
76 990630
77 1082843
78 1182631
79 1290422
80 1406883
81 1532548
82 1668066
83 1814083
84 1971377
85 2140571
86 2322575
87 2518148
88 2728191
89 2953602
90 3195442
91 3454594
92 3732287
93 4029574
94 4347681
95 4687839
96 5051474
97 5439812
98 5854485
99 6296932
100 6768797
101 7271739
102 7807648
103 8378193
104 8985521
105 9631561
106 10318490
107 11048510
108 11824100
109 12647490
110 13521472
111 14448598
112 15431715
113 16473707
114 17577785
115 18746892
116 19984620
117 21294300
118 22679608
119 24144282
120 25692441
121 27327912
122 29055272
123 30878818
124 32803255
125 34833367
126 36974387
127 39231233
128 41609691
129 44115241
130 46753842
131 49531561
132 52454988
133 55530378
134 58764975
135 62165706
136 65740050
137 69495632
138 73440678
139 77583066
140 81931801
141 86495553
142 91283636
143 96305547
144 101571483
145 107091269
146 112876019
147 118936497
148 125284212
149 131930901
150 138889105
151 146170989
152 153790170
153 161759910
154 170094321
155 178807810
156 187915700
157 197432930
158 207376078
159 217761365
160 228605992
161 239927510
162 251744524
163 264075249
164 276939753
165 290357741
166 304350038
167 318937899
168 334143777
169 349989742
170 366499935
171 383698152
172 401609457
173 420259437
174 439675034
175 459882823
176 480911697
177 502790216
178 525548385
179 549216828
180 573827710
181 599412839
182 626006620
183 653643147
184 682358151
185 712188093
186 743171173
187 775345272
188 808751154
189 843429311
190 879422074
191 916772648
192 955526189
193 995727573
194 1037424879
195 1080665963
196 1125500757
197 1171980202
198 1220157439
199 1270085376
200 1321820484
201 1375419058
202 1430939727
203 1488442297
204 1547989038
205 1609642056
206 1673467388
207 1739530981
208 1807901385
209 1878648522
210 1951845060
211 2027563590
212 2105881044
213 2186874347
214 2270623341
215 2357209440
216 2446717132
217 2539230911
218 2634840069
219 2733633992
220 2835705320
221 2941148493
222 3050061370
223 3162541944
224 3278693474
225 3398619444
226 3522426947
227 3650225150
228 3782127009
229 3918245748
230 4058700376
231 4203610274
232 4353098839
233 4507291810
234 4666319138
235 4830311193
236 4999404702
237 5173736920
238 5353449553
239 5538686968
240 5729598190
241 5926332849
242 6129047522
243 6337899521
244 6553051069
245 6774667406
246 7002918907
247 7237976767
248 7480019775
249 7729227669
250 7985785617
251 8249882176
252 8521711576
253 8801469087
254 9089358284
255 9385583934
256 9690356790
257 10003891406
258 10326408578
259 10658130422
260 10999288092
261 11350114222
262 11710848017
263 12081732960
264 12463019381
265 12854959229
266 13257814291
267 13671848151
268 14097331619
269 14534540262
270 14983757172
271 15445267386
272 15919366654
273 16406352857
274 16906531802
275 17420214600
276 17947720601
277 18489371480
278 19045500526
279 19616443568
280 20202545096
281 20804155507
282 21421634197
283 22055343309
284 22705657581
285 23372954715
286 24057621892
287 24760052829
288 25480651085
289 26219823405
290 26977990194
291 27755575291
292 28553012883
293 29370744383
294 30209221933
295 31068901383
296 31950253343
297 32853752391
298 33779884368
299 34729143115
300 35702034145
301 36699067232
302 37720768101
303 38767667023
304 39840306540
305 40939237983
306 42065025392
307 43218237667
308 44399460945
309 45609286522
310 46848319035
311 48117172790
312 49416475894
313 50746861985
314 52108983270
315 53503497823
316 54931078184
317 56392407519
318 57888183951
319 59419111869
320 60985915664
321 62589326336
322 64230090582
323 65908966725
324 67626729310
325 69384159915
326 71182061664
327 73021245096
328 74902537752
329 76826779881
330 78794829284
331 80807551670
332 82865835891
333 84970579109
334 87122696857
335 89323118571
336 91572792644
337 93872676304
338 96223751636
339 98627009994
340 101083462594
341 103594135779
342 106160076379
343 108782341050
344 111462013144
345 114200186295
346 116997975575
347 119856512527
348 122776950785
349 125760454902
350 128808218029
351 131921444738
352 135101362692
353 138349217471
354 141666278441
355 145053827064
356 148513175436
357 152045648265
358 155652595140
359 159335385078
360 163095412715
361 166934086015
362 170852845751
363 174853146590
364 178936469968
365 183104318371
366 187358221826
367 191699725059
368 196130407857
369 200651865299
370 205265721213
371 209973622240
372 214777244588
373 219678280610
374 224678460121
375 229779529717
376 234983266875
377 240291473702
378 245705984053
379 251228649466
380 256861361499
381 262606030059
382 268464598181
383 274439035497
384 280531345673
385 286743551726
386 293077719342
387 299535934283
388 306120317790
389 312833019804
390 319676226703
391 326652146001
392 333763030696
393 341011155668
394 348398833800
395 355928408868
396 363602263664
397 371422803980
398 379392484084
399 387513782052
400 395789216617
401 404221339742
402 412812745104
403 421566051420
404 430483928979
405 439569073957
406 448824225961
407 458252160345
408 467855697010
409 477637683042
410 487601020383
411 497748639060
412 508083515499
413 518608664468
414 529327148311
415 540242058825
416 551356546142
417 562673790789
418 574197022806
419 585929513362
420 597874584366
421 610035589617
422 622415944850
423 635019098703
424 647848552581
425 660907851975
426 674200596436
427 687730419991
428 701501022412
429 715516138993
430 729779561262
431 744295127915
432 759066735243
433 774098316713
434 789393875563
435 804957453329
436 820793151415
437 836905121658
438 853297577181
439 869974771200
440 886941030869
441 904200724607
442 921758284494
443 939618196529
444 957785011862
445 976263324795
446 995057807964
447 1014173178397
448 1033614220811
449 1053385777442
450 1073492759782
451 1093940125694
452 1114732916013
453 1135876219239
454 1157375195779
455 1179235067393
456 1201461129378
457 1224058726833
458 1247033292626
459 1270390310809
460 1294135341736
461 1318274011165
462 1342812022867
463 1367755134038
464 1393109194695
465 1418880109706
466 1445073864899
467 1471696515718
468 1498754200362
469 1526253114229
470 1554199550856
471 1582599862498
472 1611460487238
473 1640787937217
474 1670588812270
475 1700869773473
476 1731637585539
477 1762899076006
478 1794661163309
479 1826930844654
480 1859715210100
481 1893021415171
482 1926856724809
483 1961228471088
484 1996144082337
485 2031611070522
486 2067637045912
487 2104229688672
488 2141396794456
489 2179146230551
490 2217485966091
491 2256424059000
492 2295968671177
493 2336128039109
494 2376910521049
495 2418324551680
496 2460378673351
497 2503081522619
498 2546441845933
499 2590468469262
500 2635170346926
501 2680556514667
502 2726636122027
503 2773418418384
504 2820912769244
505 2869128624763
506 2918075570354
507 2967763278093
508 3018201540252
509 3069400254848
510 3121369442511
511 3174119213973
512 3227659822359
513 3282001612991
514 3337155058035
515 3393130741639
516 3449939377319
517 3507591774380
518 3566098891993
519 3625471787314
520 3685721651337
521 3746859793475
522 3808897659616
523 3871846797379
524 3935718912075
525 4000525813030
526 4066279450692
527 4132991900711
528 4200675382593
529 4269342223838
530 4339004917719
531 4409676067913
532 4481368426782
533 4554094878997
534 4627868460767
535 4702702322853
536 4778609790241
537 4855604304955
538 4933699465647
539 5012909010646
540 5093246837884
541 5174726966654
542 5257363599309
543 5341171062182
544 5426163846495
545 5512356590859
546 5599764101857
547 5688401314629
548 5778283356495
549 5869425486052
550 5961843135358
551 6055551891962
552 6150567520087
553 6246905919998
554 6344583193665
555 6443615581943
556 6544019508132
557 6645811559382
558 6749008508634
559 6853627272675
560 6959684979938
561 7067198905652
562 7176186516827
563 7286665453093
564 7398653549326
565 7512168792435
566 7627229391234
567 7743853709669
568 7862060313145
569 7981867948847
570 8103295569025
571 8226362286509
572 8351087446731
573 8477490558899
574 8605591343806
575 8735409713509
576 8866965795402
577 9000279886318
578 9135372526844
579 9272264430358
580 9410976532336
581 9551529969412
582 9693946104200
583 9838246478070
584 9984452887647
585 10132587311788
586 10282671962336
587 10434729262651
588 10588781873114
589 10744852642536
590 10902964686961
591 11063141314484
592 11225406077562
593 11389782750845
594 11556295357539
595 11724968119337
596 11895825537636
597 12068892316073
598 12244193414444
599 12421754025903
600 12601599604099
601 12783755811685
602 12968248603873
603 13155104148806
604 13344348882996
605 13536009487941
606 13730112918011
607 13926686347527
608 14125757256742
609 14327353349906
610 14531502612376
611 14738233286516
612 14947573900471
613 15159553213667
614 15374200305367
615 15591544490345
616 15811615377679
617 16034442845964
618 16260057072929
619 16488488479452
620 16719767820576
621 16953926098871
622 17190994624861
623 17431004991640
624 17673989105266
625 17919979127244
626 18169007568131
627 18421107198482
628 18676311111024
629 18934652694500
630 19196165665021
631 19460884006905
632 19728842068985
633 20000074473008
634 20274616177614
635 20552502451474
636 20833768905517
637 21118451432179
638 21406586304336
639 21698210081282
640 21993359674416
641 22292072319731
642 22594385610885
643 22900337436856
644 23209966083590
645 23523310137409
646 23840408552567
647 24161300622947
648 24486026016125
649 24814624709270
650 25147137093670
651 25483603875475
652 25824066145139
653 26168565348354
654 26517143321060
655 26869842223692
656 27226704648457
657 27587773517503
658 27953092154188
659 28322704253352
660 28696653917200
661 29074985587847
662 29457744157485
663 29844974863863
664 30236723363510
665 30633035701152
666 31033958346666
667 31439538125801
668 31849822333356
669 32264858625836
670 32684695096684
671 33109380244921
672 33538963013076
673 33973492716145
674 34413019157696
675 34857592519833
676 35307263440338
677 35762082980590
678 36222102664443
679 36687374405415
680 37157950625818
681 37633884143871
682 38115228252923
683 38602036688500
684 39094363668287
685 39592263817381
686 40095792290613
687 40605004656715
688 41119956979638
689 41640705784760
690 42167308099923
691 42699821378854
692 43238303626551
693 43782813280594
694 44333409294501
695 44890151103201
696 45453098665049
697 46022312383366
698 46597853235031
699 47179782648821
700 47768162590933
701 48363055529523
702 48964524477906
703 49572632914086
704 50187444912685
705 50809025020164
706 51437438342576
707 52072750509247
708 52715027717065
709 53364336648065
710 54020744604604
711 54684319381607
712 55355129356441
713 56033243451803
714 56718731181064
715 57411662563903
716 58112108264831
717 58820139462294
718 59535827940850
719 60259246053102
720 60990466766266
721 61729563575674
722 62476610646828
723 63231682681256
724 63994855011009
725 64766203559675
726 65545804890115
727 66333736115952
728 67130075047012
729 67934900052035
730 68748290155428
731 69570324997470
732 70401084883138
733 71240650691525
734 72089104024825
735 72946527067771
736 73813002686784
737 74688614389157
738 75573446373189
739 76467583435399
740 77371111123188
741 78284115590855
742 79206683701204
743 80138902983792
744 81080861686268
745 82032648679451
746 82994353613576
747 83966066771035
748 84947879170332
749 85939882523459
750 86942169288407
751 87954832572101
752 88977966290338
753 90011665017078
754 91056024090936
755 92111139571519
756 93177108293283
757 94254027766140
758 95341996339275
759 96441113046880
760 97551477717201
761 98673190927871
762 99806354061060
763 100951069201870
764 102107439305887
765 103275568041462
766 104455559901246
767 105647520156638
768 106851554914140
769 108067771011488
770 109296276189097
771 110537178928759
772 111790588567812
773 113056615252479
774 114335369995661
775 115626964570659
776 116931511686658
777 118249124823680
778 119579918349456
779 120924007471744
780 122281508297451
781 123652537724021
782 125037213618855
783 126435654650680
784 127847980409003
785 129274311355479
786 130714768884326
787 132169475211371
788 133638553557522
789 135122127976366
790 136620323476408
791 138133265971309
792 139661082341781
793 141203900322094
794 142761848687798
795 144335057079438
796 145923656127594
797 147527777402032
798 149147553475016
799 150783117805405
800 152434604930469
801 154102150285832
802 155785890333245
803 157485962508769
804 159202505287420
805 160935658064794
806 162685561353148
807 164452356597433
808 166236186305952
809 168037193997344
810 169855524266801
811 171691322665075
812 173544735898972
813 175415911643309
814 177304998674528
815 179212146816573
816 181137507008567
817 183081231181276
818 185043472461913
819 187024384982183
820 189024124014730
821 191042845917980
822 193080708205240
823 195137869418613
824 197214489338230
825 199310728786192
826 201426749766058
827 203562715406469
828 205718790031863
829 207895139033636
830 210091929084010
831 212309327935752
832 214547504564725
833 216806629112332
834 219086872957787
835 221388408586653
836 223711409809184
837 226056051555940
838 228422510023324
839 230810962614979
840 233221588015519
841 235654566056385
842 238110077938838
843 240588306025324
844 243089433988161
845 245613646749641
846 248161130557478
847 250732072847824
848 253326662473071
849 255945089488792
850 258587545305651
851 261254222628309
852 263945315532468
853 266661019325131
854 269401530777100
855 272167047905669
856 274957770129626
857 277773898207040
858 280615634313863
859 283483181901424
860 286376745933752
861 289296532665816
862 292242749801841
863 295215606431780
864 298215313111678
865 301242081718187
866 304296125690928
867 307377659806158
868 310486900338417
869 313624064995732
870 316789373001676
871 319983044947043
872 323205303037081
873 326456370860706
874 329736473555407
875 333045837741313
876 336384691604853
877 339753264747527
878 343151788438194
879 346580495377685
880 350039619867131
881 353529397740641
882 357050066450826
883 360601864914504
884 364185033770208
885 367799815138015
886 371446452791376
887 375125192088505
888 378836280059645
889 382579965249791
890 386356497981303
891 390166130109133
892 394009115196021
893 397885708442677
894 401796166776746
895 405740748692544
896 409719714518905
897 413733326169597
898 417781847322113
899 421865543346442
900 425984681395948
901 430139530243893
902 434330360556747
903 438557444639662
904 442821056618881
905 447121472369144
906 451458969606412
907 455833827721324
908 460246328057790
909 464696753653656
910 469185389426647
911 473712522100551
912 478278440299687
913 482883434379229
914 487527796709278
915 492211821410557
916 496935804544068
917 501700044035785
918 506504839773144
919 511350493432065
920 516237308766673
921 521165591339836
922 526135648716614
923 531147790387570
924 536202327867151
925 541299574517499
926 546439845843699
927 551623459219351
928 556850734083670
929 562121991863498
930 567437556073536
931 572797752136933
932 578202907686201
933 583653352283600
934 589149417622129
935 594691437446028
936 600279747653081
937 605914686111754
938 611596592968009
939 617325810360371
940 623102682624831
941 628927556213887
942 634800779800848
943 640722704093670
944 646693682147488
945 652714069074497
946 658784222252685
947 664904501243559
948 671075267898345
949 677296886168456
950 683569722423940
951 689894145158015
952 696270525199813
953 702699235630515
954 709180651891736
955 715715151592447
956 722303114833520
957 728944923906718
958 735640963511536
959 742391620669855
960 749197284836378
961 756058347702100
962 762975203524823
963 769948248822801
964 776977882595529
965 784064506237007
966 791208523648180
967 798410341036950
968 805670367254803
969 812989013484881
970 820366693466970
971 827803823409150
972 835300822102475
973 842858110717282
974 850476113146177
975 858155255686395
976 865895967269009
977 873698679369020
978 881563826122199
979 889491844117855
980 897483172747985
981 905538253884065
982 913657532110392
983 921841454632766
984 930090471397388
985 938405034880013
986 946785600441477
987 955232625998746
988 963746572262584
989 972327902644539
990 980977083378196
991 989694583304534
992 998480874234013
993 1007336430611680
994 1016261729759248
995 1025257251780503
996 1034323479684772
997 1043460899168582
998 1052669998984176
999 1061951270598882
1000 1071305208441452