1 1
2 2
3 3
4 4
5 6
6 8
7 11
8 14
9 18
10 23
11 29
12 36
13 45
14 55
15 67
16 81
17 98
18 117
19 140
20 166
21 196
22 231
23 271
24 317
25 369
26 429
27 496
28 573
29 660
30 758
31 869
32 993
33 1133
34 1290
35 1465
36 1662
37 1881
38 2125
39 2397
40 2699
41 3035
42 3407
43 3820
44 4276
45 4780
46 5337
47 5951
48 6628
49 7372
50 8191
51 9090
52 10077
53 11160
54 12346
55 13644
56 15064
57 16616
58 18311
59 20161
60 22179
61 24377
62 26771
63 29376
64 32209
65 35288
66 38632
67 42262
68 46198
69 50466
70 55090
71 60097
72 65516
73 71377
74 77713
75 84558
76 91951
77 99930
78 108538
79 117820
80 127823
81 138599
82 150202
83 162690
84 176125
85 190570
86 206097
87 222778
88 240692
89 259924
90 280560
91 302694
92 326426
93 351862
94 379113
95 408299
96 439545
97 472984
98 508756
99 547013
100 587912
101 631621
102 678317
103 728188
104 781431
105 838257
106 898888
107 963559
108 1032516
109 1106022
110 1184353
111 1267800
112 1356674
113 1451299
114 1552018
115 1659193
116 1773207
117 1894462
118 2023385
119 2160423
120 2306050
121 2460759
122 2625079
123 2799561
124 2984786
125 3181369
126 3389954
127 3611219
128 3845877
129 4094684
130 4358429
131 4637945
132 4934106
133 5247833
134 5580091
135 5931899
136 6304326
137 6698496
138 7115584
139 7556834
140 8023545
141 8517083
142 9038887
143 9590460
144 10173385
145 10789318
146 11440004
147 12127266
148 12853023
149 13619285
150 14428157
151 15281849
152 16182676
153 17133069
154 18135571
155 19192849
156 20307698
157 21483042
158 22721946
159 24027625
160 25403440
161 26852911
162 28379723
163 29987737
164 31680984
165 33463696
166 35340294
167 37315402
168 39393862
169 41580729
170 43881305
171 46301117
172 48845960
173 51521885
174 54335211
175 57292553
176 60400818
177 63667227
178 67099324
179 70704990
180 74492457
181 78470318
182 82647557
183 87033551
184 91638088
185 96471394
186 101544134
187 106867447
188 112452952
189 118312785
190 124459601
191 130906604
192 137667571
193 144756870
194 152189488
195 159981055
196 168147879
197 176706948
198 185675983
199 195073457
200 204918621
201 215231548
202 226033155
203 237345235
204 249190500
205 261592604
206 274576205
207 288166974
208 302391660
209 317278118
210 332855352
211 349153564
212 366204203
213 384040016
214 402695081
215 422204882
216 442606344
217 463937892
218 486239521
219 509552849
220 533921173
221 559389538
222 586004802
223 613815712
224 642872958
225 673229275
226 704939495
227 738060635
228 772651974
229 808775151
230 846494241
231 885875848
232 926989213
233 969906290
234 1014701855
235 1061453618
236 1110242331
237 1161151888
238 1214269459
239 1269685595
240 1327494354
241 1387793432
242 1450684307
243 1516272363
244 1584667037
245 1655981964
246 1730335136
247 1807849044
248 1888650860
249 1972872610
250 2060651318
251 2152129216
252 2247453914
253 2346778598
254 2450262230
255 2558069759
256 2670372332
257 2787347504
258 2909179467
259 3036059306
260 3168185218
261 3305762776
262 3449005199
263 3598133590
264 3753377237
265 3914973889
266 4083170072
267 4258221369
268 4440392754
269 4629958915
270 4827204576
271 5032424864
272 5245925668
273 5468024011
274 5699048420
275 5939339340
276 6189249530
277 6449144490
278 6719402899
279 7000417085
280 7292593459
281 7596353004
282 7912131784
283 8240381447
284 8581569744
285 8936181112
286 9304717202
287 9687697456
288 10085659738
289 10499160920
290 10928777562
291 11375106525
292 11838765699
293 12320394666
294 12820655429
295 13340233182
296 13879837072
297 14440200990
298 15022084392
299 15626273154
300 16253580424
301 16904847533
302 17580944953
303 18282773218
304 19011263920
305 19767380745
306 20552120488
307 21366514179
308 22211628161
309 23088565297
310 23998466094
311 24942509959
312 25921916462
313 26937946624
314 27991904274
315 29085137427
316 30219039717
317 31395051836
318 32614663063
319 33879412852
320 35190892395
321 36550746315
322 37960674369
323 39422433174
324 40937838054
325 42508764882
326 44137152054
327 45825002410
328 47574385326
329 49387438785
330 51266371555
331 53213465416
332 55231077485
333 57321642583
334 59487675629
335 61731774210
336 64056621137
337 66464987098
338 68959733456
339 71543815041
340 74220283061
341 76992288099
342 79863083194
343 82836027050
344 85914587256
345 89102343727
346 92402992112
347 95820347372
348 99358347461
349 103021057123
350 106812671780
351 110737521522
352 114800075275
353 119004944995
354 123356890043
355 127860821723
356 132521807891
357 137345077703
358 142336026540
359 147500221034
360 152843404241
361 158371501002
362 164090623461
363 170007076681
364 176127364471
365 182458195353
366 189006488738
367 195779381234
368 202784233174
369 210028635358
370 217520415853
371 225267647132
372 233278653363
373 241562017891
374 250126590961
375 258981497660
376 268136146062
377 277600235576
378 287383765608
379 297497044429
380 307950698288
381 318755680781
382 329923282512
383 341465140966
384 353393250696
385 365719973834
386 378458050872
387 391620611675
388 405221186914
389 419273719736
390 433792577770
391 448792565517
392 464288937071
393 480297409166
394 496834174547
395 513915915831
396 531559819625
397 549783591116
398 568605469053
399 588044241156
400 608119259856
401 628850458564
402 650258368370
403 672364135200
404 695189537403
405 718757003914
406 743089632825
407 768211210423
408 794146230912
409 820919916542
410 848558238339
411 877087937370
412 906536546637
413 936932413461
414 968304722583
415 1000683519851
416 1034099736593
417 1068585214535
418 1104172731500
419 1140896027766
420 1178789833088
421 1217889894519
422 1258233005017
423 1299857032682
424 1342800950855
425 1387104869054
426 1432810064660
427 1479959015538
428 1528595433467
429 1578764298564
430 1630511894414
431 1683885844333
432 1738935148534
433 1795710222273
434 1854262935008
435 1914646650640
436 1976916268750
437 2041128266923
438 2107340744244
439 2175613465998
440 2246007909394
441 2318587310621
442 2393416713122
443 2470563017025
444 2550095030009
445 2632083519475
446 2716601266108
447 2803723118707
448 2893526050629
449 2986089217556
450 3081494016850
451 3179824148452
452 3281165677407
453 3385607097949
454 3493239399188
455 3604156132675
456 3718453481602
457 3836230331771
458 3957588344571
459 4082632031685
460 4211468831700
461 4344209188802
462 4480966633457
463 4621857865197
464 4767002837466
465 4916524844793
466 5070550612009
467 5229210385834
468 5392638028863
469 5560971115937
470 5734351032975
471 5912923078255
472 6096836566444
473 6286244935057
474 6481305853774
475 6682181336610
476 6889037856798
477 7102046464619
478 7321382908247
479 7547227757657
480 7779766531599
481 8019189827908
482 8265693457117
483 8519478579272
484 8780751844320
485 9049725536026
486 9326617719476
487 9611652392352
488 9905059639951
489 10207075794233
490 10517943596555
491 10837912364729
492 11167238164260
493 11506183983756
494 11855019914787
495 12214023336275
496 12583479103380
497 12963679741028
498 13354925642504
499 13757525272806
500 14171795377093
501 14598061194290
502 15036656676022
503 15487924710883
504 15952217354312
505 16429896064227
506 16921331942470
507 17426905981996
508 17947009320441
509 18482043499726
510 19032420732101
511 19598564172825
512 20180908199531
513 20779898698348
514 21395993356974
515 22029661965187
516 22681386722433
517 23351662553122
518 24040997429599
519 24749912702999
520 25478943441980
521 26228638779926
522 26999562270545
523 27792292252126
524 28607422220562
525 29445561211611
526 30307334192202
527 31193382461240
528 32104364060289
529 33040954194135
530 34003845661421
531 34993749295704
532 36011394417276
533 37057529295550
534 38132921622931
535 39238358999953
536 40374649432132
537 41542621838582
538 42743126572984
539 43977035956980
540 45245244826325
541 46548671090157
542 47888256303776
543 49264966254802
544 50679791563429
545 52133748297123
546 53627878599793
547 55163251336041
548 56740962750770
549 58362137144449
550 60027927564161
551 61739516511333
552 63498116666158
553 65304971629179
554 67161356680358
555 69068579556235
556 71027981245230
557 73040936801725
558 75108856179515
559 77233185084901
560 79415405849661
561 81657038324681
562 83959640794607
563 86324810913773
564 88754186664254
565 91249447336468
566 93812314532643
567 96444553193570
568 99147972649670
569 101924427696368
570 104775819694616
571 107704097697249
572 110711259601494
573 113799353328241
574 116970478028651
575 120226785319032
576 123570480544278
577 127003824070576
578 130529132608297
579 134148780565377
580 137865201431808
581 141680889196435
582 145598399796485
583 149620352600439
584 153749431925172
585 157988388588164
586 162340041495205
587 166807279264694
588 171393061889497
589 176100422436871
590 180932468787430
591 185892385413848
592 190983435200608
593 196208961305021
594 201572389061117
595 207077227927181
596 212727073477584
597 218525609440012
598 224476609779275
599 230583940828600
600 236851563469318
601 243283535360405
602 249884013218700
603 256657255150633
604 263607623036980
605 270739584971891
606 278057717756946
607 285566709451935
608 293271361983214
609 301176593811207
610 309287442657705
611 317609068295118
612 326146755398678
613 334905916462757
614 343892094782918
615 353110967505178
616 362568348743638
617 372270192768000
618 382222597263170
619 392431806661705
620 402904215550874
621 413646372156169
622 424664981902716
623 435966911056150
624 447559190445151
625 459449019267002
626 471643768978241
627 484150987271507
628 496978402141506
629 510133926041226
630 523625660130571
631 537461898619680
632 551651133208685
633 566202057625750
634 581123572265672
635 596424788931701
636 612115035681924
637 628203861783159
638 644701042774390
639 661616585641974
640 678960734108780
641 696743974040393
642 714977038970409
643 733670915747467
644 752836850306374
645 772486353566496
646 792631207459304
647 813283471088431
648 834455487025105
649 856159887741673
650 878409602185812
651 901217862498708
652 924598210880535
653 948564506605364
654 973130933189932
655 998312005718878
656 1024122578329600
657 1050577851860122
658 1077693381663745
659 1105485085593671
660 1133969252161315
661 1163162548872043
662 1193082030742109
663 1223745148999973
664 1255169759976384
665 1287374134187418
666 1320376965614016
667 1354197381182316
668 1388854950449229
669 1424369695497160
670 1460762101041890
671 1498053124759165
672 1536264207833814
673 1575417285736063
674 1615534799229933
675 1656639705618537
676 1698755490230903
677 1741906178155477
678 1786116346226020
679 1831411135264525
680 1877816262586331
681 1925358034773279
682 1974063360720347
683 2023959764961092
684 2075075401278205
685 2127439066605095
686 2181080215223978
687 2236028973266473
688 2292316153523818
689 2349973270572297
690 2409032556220562
691 2469526975286011
692 2531490241706318
693 2594956834993002
694 2659962017034139
695 2726541849253960
696 2794733210135884
697 2864573813116889
698 2936102224860789
699 3009357883917964
700 3084381119779095
701 3161213172331781
702 3239896211728157
703 3320473358671234
704 3402988705128999
705 3487487335485120
706 3574015348134366
707 3662619877532414
708 3753349116709787
709 3846252340258419
710 3941379927800836
711 4038783387951520
712 4138515382780968
713 4240629752791759
714 4345181542417985
715 4452227026058418
716 4561823734653750
717 4674030482818751
718 4788907396541399
719 4906515941459859
720 5026918951728864
721 5150180659488146
722 5276366724944457
723 5405544267079052
724 5537781894993833
725 5673149739909432
726 5811719487827361
727 5953564412870380
728 6098759411314316
729 6247381036325271
730 6399507533415627
731 6555218876634682
732 6714596805507873
733 6877724862739452
734 7044688432693948
735 7215574780672286
736 7390473092997793
737 7569474517928429
738 7752672207412782
739 7940161359705546
740 8132039262859445
741 8328405339111784
742 8529361190183073
743 8735010643505350
744 8945459799399955
745 9160817079222764
746 9381193274496189
747 9606701597046838
748 9837457730170096
749 10073579880840942
750 10315188832992136
751 10562408001881061
752 10815363489566684
753 11074184141517688
754 11339001604374750
755 11609950384890550
756 11887167910069355
757 12170794588530680
758 12460973873121195
759 12757852324798717
760 13061579677813245
761 13372308906211702
762 13690196291691672
763 14015401492830618
764 14348087615717328
765 14688421286013846
766 15036572722474627
767 15392715811952456
768 15757028185920558
769 16129691298539993
770 16510890506302140
771 16900815149277450
772 17299658634002320
773 17707618518034674
774 18124896596212444
775 18551698988647786
776 18988236230489804
777 19434723363490596
778 19891380029410421
779 20358430565297023
780 20836104100675688
781 21324634656687766
782 21824261247214878
783 22335227982026630
784 22857784171991924
785 23392184436394134
786 23938688812390281
787 24497562866655784
788 25069077809257412
789 25653510609797129
790 26251144115869593
791 26862267173880348
792 27487174752269008
793 28126168067183297
794 28779554710652060
795 29447648781304839
796 30130771017686781
797 30829248934218952
798 31543416959856120
799 32273616579492444
800 33020196478167831
801 33783512688129149
802 34563928738801042
803 35361815809721467
804 36177552886499772
805 37011526919855169
806 37864132987793506
807 38735774460982154
808 39626863171385668
809 40537819584223232
810 41469072973311509
811 42421061599858469
812 43394232894772822
813 44389043644555774
814 45405960180843696
815 46445458573672393
816 47508024828531907
817 48594155087285234
818 49704355833023905
819 50839144098934805
820 51999047681253976
821 53184605356386142
822 54396367102268879
823 55634894324060730
824 56900760084235496
825 58194549337166901
826 59516859168286706
827 60868299037903965
828 62249491029774542
829 63661070104508692
830 65103684357908472
831 66577995284327898
832 68084678045151126
833 69624421742483541
834 71197929698156037
835 72805919738141411
836 74449124482484136
837 76128291640846795
838 77844184313779944
839 79597581299822153
840 81389277408539279
841 83220083779615444
842 85090828208108489
843 87002355475983801
844 88955527690045751
845 90951224626386837
846 92990344081474850
847 95073802230003307
848 97202533989631004
849 99377493392739026
850 101599653965334966
851 103870009113240392
852 106189572515695596
853 108559378526519733
854 110980482582966953
855 113453961622422155
856 115980914507080998
857 118562462456763145
858 121199749490011126
859 123893942873627204
860 126646233580803966
861 129457836758009341
862 132329992200787871
863 135263964838642317
864 138261045229165718
865 141322550061594224
866 144449822669953902
867 147644233555978566
868 150907180921980929
869 154240091213859051
870 157644419674426063
871 161121650907253583
872 164673299451222248
873 168300910365975263
874 172006059828476650
875 175790355740879876
876 179655438349912854
877 183602980877991641
878 187634690166279058
879 191752307329905731
880 195957608425576647
881 200252405131792682
882 204638545441916934
883 209117914370320724
884 213692434671848938
885 218364067574848946
886 223134813528009521
887 228006712961263508
888 232981847061012157
889 238062338559931184
890 243250352541624042
891 248548097260393911
892 253957824976410617
893 259481832806551065
894 265122463591201008
895 270882106777308224
896 276763199317980770
897 282768226588931590
898 288899723322077059
899 295160274556599826
900 301552516607792852
901 308079138054008811
902 314742880742041486
903 321546540811272177
904 328492969736922626
905 335585075392760821
906 342825823133610359
907 350218236898022222
908 357765400331473142
909 365470457930461171
910 373336616207873963
911 381367144880017212
912 389565378075692676
913 397934715567721597
914 406478624027319464
915 415200638301733187
916 424104362715558263
917 433193472396162708
918 442471714623653377
919 451942910205822715
920 461610954878525038
921 471479820731939257
922 481553557663182686
923 491836294855747414
924 502332242286241836
925 513045692258926102
926 523981020968537813
927 535142690091913252
928 546535248408922295
929 558163333453238927
930 570031673193480591
931 582145087745260636
932 594508491114703385
933 607126892973982586
934 620005400469455031
935 633149220062972441
936 646563659406959399
937 660254129253860521
938 674226145400567950
939 688485330668450143
940 703037416919614448
941 717888247110049849
942 733043777380303821
943 748510079184358463
944 764293341457383493
945 780399872823056909
946 796836103841151783
947 813608589296104219
948 830724010527289975
949 848189177801745012
950 866011032730080318
951 884196650726355458
952 902753243512688267
953 921688161669387860
954 941008897231418869
955 960723086332011923
956 980838511894250623
957 1001363106371480497
958 1022304954537401565
959 1043672296326718581
960 1065473529727238221
961 1087717213724319270
962 1110412071298595698
963 1133566992477905560
964 1157191037444380836
965 1181293439697667291
966 1205883609275256658
967 1230971136030934164
968 1256565792972359800
969 1282677539658818189
970 1309316525660189088
971 1336493094078214663
972 1364217785131150529
973 1392501339802908353
974 1421354703557817300
975 1450789030122150725
976 1480815685333582239
977 1511446251059757495
978 1542692529187189453
979 1574566545681700533
980 1607080554721656726
981 1640247042905263626
982 1674078733533212999
983 1708588590967989494
984 1743789825071173175
985 1779695895720093231
986 1816320517405208725
987 1853677663909617805
988 1891781573072124535
989 1930646751635309430
990 1970287980180079176
991 2010720318148195070
992 2051959108954302247
993 2094019985189008150
994 2136918873914586906
995 2180672002054914312
996 2225295901881259481
997 2270807416595590299
998 2317223706013077929
999 2364562252345510462
1000 2412840866087356219