0 0
1 1
2 2
3 2
4 4
5 5
6 7
7 10
8 13
9 16
10 23
11 30
12 35
13 50
14 61
15 73
16 95
17 123
18 139
19 187
20 216
21 269
22 328
23 411
24 461
25 594
26 688
27 836
28 980
29 1211
30 1357
31 1703
32 1936
33 2330
34 2697
35 3253
36 3649
37 4468
38 5057
39 6005
40 6841
41 8182
42 9149
43 10976
44 12341
45 14508
46 16447
47 19380
48 21611
49 25553
50 28628
51 33360
52 37530
53 43769
54 48748
55 56898
56 63526
57 73407
58 82213
59 94981
60 105477
61 121996
62 135821
63 155696
64 173612
65 199000
66 220699
67 252996
68 280782
69 319856
70 355428
71 404686
72 447682
73 509577
74 564198
75 638817
76 707761
77 800979
78 884392
79 1000321
80 1104668
81 1244529
82 1375148
83 1547927
84 1705470
85 1918612
86 2114436
87 2370792
88 2612844
89 2927466
90 3219268
91 3604378
92 3963476
93 4425489
94 4866593
95 5429262
96 5959249
97 6643888
98 7291515
99 8110346
100 8899349
101 9891356
102 10837526
103 12036401
104 13184377
105 14614429
106 16005679
107 17728206
108 19389731
109 21461351
110 23466549
111 25930390
112 28345334
113 31298329
114 34175539
115 37708794
116 41161834
117 45352669
118 49491209
119 54490793
120 59403806
121 65361416
122 71231848
123 78275740
124 85277064
125 93646441
126 101935976
127 111867440
128 121725218
129 133436527
130 145145977
131 159007282
132 172826929
133 189213837
134 205586251
135 224854609
136 244223757
137 266950653
138 289746461
139 316520011
140 343421018
141 374822269
142 406537265
143 443447592
144 480664408
145 524007826
146 567783519
147 618484581
148 669911300
149 729327637
150 789518476
151 859077470
152 929641157
153 1010806308
154 1093451296
155 1188286758
156 1284758858
157 1395471092
158 1508233884
159 1637105513
160 1768774281
161 1918946405
162 2072270828
163 2247103711
164 2425803012
165 2628845330
166 2836943144
167 3072928071
168 3314650994
169 3588699157
170 3869689247
171 4187242363
172 4513588753
173 4881761129
174 5259985227
175 5686501610
176 6125046596
177 6618220421
178 7126307592
179 7696759250
180 8284286337
181 8943641749
182 9623268856
183 10384074584
184 11169608477
185 12047690539
186 12954143130
187 13966850607
188 15012988691
189 16179202578
190 17385695814
191 18728834505
192 20118168058
193 21664022528
194 23264040569
195 25040779024
196 26882114124
197 28924297407
198 31040543878
199 33386271814
200 35818386184
201 38509506925
202 41302829008
203 44390010633
204 47594267919
205 51133608295
206 54808976504
207 58862194785
208 63075194904
209 67716397838
210 72540453407
211 77851728243
212 83374619521
213 89446588611
214 95765753330
215 102706218188
216 109929197245
217 117857862864
218 126112414965
219 135161568690
220 144589434323
221 154915403966
222 165673635566
223 177449998153
224 189723455830
225 203142556328
226 217136907214
227 232424350074
228 248367353641
229 265774024351
230 283932542265
231 303736596017
232 324407279540
233 346933200579
234 370445412302
235 396054084565
236 422790998573
237 451883155653
238 482271398655
239 515311771885
240 549824900195
241 587330832213
242 626517589915
243 669063552801
244 713534429497
245 761783908465
246 812217636897
247 866909045308
248 924087670591
249 986041688244
250 1050836275993
251 1120996334943
252 1194374816639
253 1273791253867
254 1356865248031
255 1446705418174
256 1540712096904
257 1642313301824
258 1748628602636
259 1863479083592
260 1983676363357
261 2113430900631
262 2249262200469
263 2395809208630
264 2549221919601
265 2714663372781
266 2887878194406
267 3074550604077
268 3270038359871
269 3480600446321
270 3701108909514
271 3938518609512
272 4187170076953
273 4454715553860
274 4734984655506
275 5036396221191
276 5352144594574
277 5691571896734
278 6047177101801
279 6429231147118
280 6829561174521
281 7259460336344
282 7709926149639
283 8193471932377
284 8700189559592
285 9243827961389
286 9813598255134
287 10424605727238
288 11064982760751
289 11751446615665
290 12470952026873
291 13241853481741
292 14049955836362
293 14915412029125
294 15822627541368
295 16793876510674
296 17812039777352
297 18901558232385
298 20043815467979
299 21265627926032
300 22546570254064
301 23916248899176
302 25352268186845
303 26887091554468
304 28496382605627
305 30215738665875
306 32018490845998
307 33943893481237
308 35962741280029
309 38118052366160
310 40378111281486
311 42790056809676
312 45319176212606
313 48017398176055
314 50846752714291
315 53864109068040
316 57028264839405
317 60401500553784
318 63938771385427
319 67708614019198
320 71661814613702
321 75873389268028
322 80289970985976
323 84993660345136
324 89926182866380
325 95177801607649
326 100684919672797
327 106546270791579
328 112692943346533
329 119232936367495
330 126091083661219
331 133386007592419
332 141035769433524
333 149170053582721
334 157700138630918
335 166767790855383
336 176276346786925
337 186381383910995
338 196977642343242
339 208235107731050
340 220039894883662
341 232577727820238
342 245724659242124
343 259684327091704
344 274321911452182
345 289859793011839
346 306152214483431
347 323442004313250
348 341570701944942
349 360804349525732
350 380970766760859
351 402360320281066
352 424787009712688
353 448567738250223
354 473500509836144
355 499932241681733
356 527643687522102
357 557013293852182
358 587804401091809
359 620429817439634
360 654632808365128
361 690864952406188
362 728847879642507
363 769073948252827
364 811242930072137
365 855891623080569
366 902694675009557
367 952238863441704
368 1004171796468704
369 1059132937281392
370 1116742531770950
371 1177697401605020
372 1241586455998686
373 1309170883012304
374 1380005893850174
375 1454920603800451
376 1533436103916748
377 1616455454228888
378 1703460772702233
379 1795437867565471
380 1891827006134658
381 1993701480832477
382 2100459137599383
383 2213268418457910
384 2331478876930031
385 2456365222488423
386 2587225192717299
387 2725445958016241
388 2870272719153872
389 3023214949215394
390 3183458186251148
391 3352648155623802
392 3529906474643118
393 3717023281208938
394 3913055346542318
395 4119949735326547
396 4336689794984830
397 4565397108973577
398 4804976430315822
399 5057734477393226
400 5322496282624079
401 5601769707436468
402 5894289721845024
403 6202787382995557
404 6525901413135168
405 6866599948909072
406 7223424068451308
407 7599599309888309
408 7993556735055179
409 8408807060249725
410 8843663898302903
411 9301941104981575
412 9781833213611514
413 10287483134114328
414 10816951519558779
415 11374745130940232
416 11958781934499103
417 12573955887353747
418 13218040332625762
419 13896349271805125
420 14606493852680432
421 15354251877345445
422 16137061848825489
423 16961195430973109
424 17823916347181635
425 18732031902200141
426 19682610181320927
427 20683048911079274
428 21730208315286855
429 22832115410834420
430 23985420184876093
431 25198831794027875
432 26468765451457803
433 27804681242230256
434 29202745332037434
435 30673218591140152
436 32212015739820899
437 33830265492175877
438 35523602278964252
439 37304108730818126
440 39167122581161965
441 41125744511203161
442 43175013218371895
443 45329132109469233
444 47582807301155355
445 49951452879032874
446 52429423584970359
447 55033426164552535
448 57757462145724479
449 60619638146517146
450 63613563540231843
451 66758879772672690
452 70048782981594610
453 73504554441644691
454 77118976074649302
455 80915104144059118
456 84885261686728174
457 89054449031338092
458 93414506861525270
459 97992513378750469
460 102779827670578077
461 107805776550282054
462 113061186503836625
463 118577844154812331
464 124346018047436950
465 130400125355716541
466 136729880027868804
467 143372544708473901
468 150317221344135130
469 157604282375637965
470 165222190853291094
471 173214645916375395
472 181569479392132985
473 190333988052905359
474 199495308466376340
475 209104664974050288
476 219148471707685800
477 229682156431616786
478 240691424653287015
479 252236248110347358
480 264301553637111770
481 276952269391171727
482 290172517361116595
483 304032531583682168
484 318515652444659431
485 333697848368724939
486 349561602682992373
487 366189132651177515
488 383562042116168269
489 401769240299134818
490 420791487830685066
491 440724923652100099
492 461549386454904779
493 483368887306982061
494 506162327468618434
495 530042150089565692
496 554986374209758002
497 581116550539908466
498 608409736318388289
499 636997390525252291
500 666855605506092148
501 698126456499447243
502 730785152005600778
503 764985229970582599
504 800700939679374439
505 838098280642733354
506 877150558815665924
507 918037127875243189
508 960730467784552337
509 1005424347873679435
510 1052090356938701815
511 1100937923894215101
512 1151937791673349844
513 1205316174435796122
514 1261043135552535064
515 1319363002740335133
516 1380245115105737717
517 1443953464166508162
518 1510456752160104860
519 1580040050563725842
520 1652671658248090352
521 1728659389653152699
522 1807971128764916924
523 1890939361984965218
524 1977531707011364269
525 2068107103937778292
526 2162633227251308962
527 2261497548978731666
528 2364667841624861325
529 2472562510862270003
530 2585149660380145000
531 2702880866334156515
532 2825725007753217332
533 2954169429133531939
534 3088183903516943270
535 3228294529790503591
536 3374472326396493109
537 3527284954784404650
538 3686705282812238394
539 3853345776795535241
540 4027181385830509455
541 4208873095123139535
542 4398398446475961373
543 4596470462584610196
544 4803070095439235783
545 5018966452269657554
546 5244144285357370926
547 5479433400289926041
548 5724823079318972839
549 5981208234824419272
550 6248583776157371791
551 6527914766761955998
552 6819202354837849695
553 7123487487848345982
554 7440778573714926064
555 7772197957585836111
556 8117762773510978528
557 8478683051758766204
558 8854985565743211992
559 9247975146757837594
560 9657689618438596784
561 10085535507742990878
562 10531563635838711336
563 10997290052001365391
564 11482779899263361646
565 11989667582595782911
566 12518034491881747818
567 13069641996117313034
568 13644590308690388755
569 14244777504999308151
570 14870324495172920731
571 15523277015406900213
572 16203779277526494928
573 16914035423395975846
574 17654216358303843709
575 18426696742115477233
576 19231676781050353599
577 20071715238148988501
578 20947045113479966561
579 21860422666858682737
580 22812118142737056779
581 23805100354472225313
582 24839680366204266398
583 25919056376821193863
584 27043584925778379557
585 28216710286799544356
586 29438840288938479016
587 30713683977467261456
588 32041705322935479771
589 33426898996360549696
590 34869791272175770452
591 36374683217290246738
592 37942170985004167929
593 39576885249708392015
594 41279498561498156025
595 43054997017120423432
596 44904137681870904358
597 46832287913864084529
598 48840299125402938582
599 50933948724465198121
600 53114191162346991834
601 55387245848799864860
602 57754180911730951705
603 60221689870722862654
604 62790967260217494853
605 65469216404954129405
606 68257769751323202936
607 71164379945342579964
608 74190531230073290583
609 77344565454904206895
610 80628135088001370680
611 84050215400626696267
612 87612642232264734224
613 91325073138053011412
614 95189545373094274917
615 99216448262139603550
616 103408041629771764875
617 107775501330116373581
618 112321329582465918040
619 117057549143555736515
620 121986928000850510732
621 127122397188572935819
622 132467017623686365181
623 138034696373014846512
624 143828813121369737791
625 149864325546411901130
626 156144962266995533037
627 162686807617964494962
628 169493973954585056459
629 176583756074934006801
630 183960683591849289693
631 191643353826255989911
632 199636752473331745826
633 207960873557472975636
634 216621203338026217433
635 225639236117156804608
636 235021002053051054036
637 244789609332778810521
638 254951681826128018726
639 265532058139462486711
640 276538012597899508630
641 287996242184156371530
642 299914727490168803752
643 312322163976626503246
644 325227302258133966326
645 338660980396149581446
646 352632791250875599508
647 367175873442830811178
648 382300733743402752816
649 398042984053818919877
650 414414126437016190749
651 431452424165808757660
652 449170466356369148672
653 467609362566988107041
654 486782880701584818431
655 506735189399081649501
656 527481339003110501572
657 549068777188307554325
658 571513953085924470280
659 594867833747209096435
660 619148384210933846296
661 644410352980487333330
662 670673352707429852096
663 697996184788274081902
664 726400256766651304469
665 755948719158815301468
666 786664923526045970246
667 818616692067622430083
668 851829487385669141443
669 886376138172025893065
670 922284404154660605432
671 959632485369861417772
672 998450628120341342579
673 1038822800649171657950
674 1080781947199583918897
675 1124418216875073620836
676 1169767486611279120496
677 1216926535546676136786
678 1265934413414728964072
679 1316895017364904041882
680 1369850836930728400590
681 1424913395607027612172
682 1482128918367335737414
683 1541617107663495948182
684 1603428227606674964274
685 1667690759372924845560
686 1734459342852569209119
687 1803871863688212815738
688 1875987709327258622284
689 1950954849436380323944
690 2028837802344833246313
691 2109795358469478702790
692 2193897590771092125970
693 2281314880280619436623
694 2372123321377635177256
695 2466505720825144181847
696 2564544677375624580709
697 2666436328106626865527
698 2772270308615981239375
699 2882257032813594787078
700 2996493758412032382354
701 3115206201957833071214
702 3238499850613097021354
703 3366616833589871801114
704 3499671535580918064517
705 3637923661554620151963
706 3781497226481381430156
707 3930670770319413153189
708 4085578700804905233077
709 4246519754434620749876
710 4413639568602137094533
711 4587258504595202257472
712 4767534345660214182005
713 4954810622910838998784
714 5149258221099251504977
715 5351245510257781779502
716 5560957523526058518291
717 5778789222792011732406
718 6004940933578737617515
719 6239836104168898324848
720 6483691548404548541547
721 6736961246154274043610
722 6999879807220685374571
723 7272933893081159284370
724 7556377336181160935157
725 7850731801570946961389
726 8156271838647057525713
727 8473556620646675956610
728 8802883045115445600144
729 9144850429141440707935
730 9499779795341944005885
731 9868313448764964397170
732 10250798401605379305759
733 10647923012704679234341
734 11060062315882747536711
735 11487953952717898462595
736 11932003189211152832642
737 12393000431622929492146
738 12871383501220428233194
739 13367999319661063735931
740 13883320791738056957501
741 14418255308174361088306
742 14973313603959651407501
743 15549467799195530068353
744 16147269349751926093600
745 16767759691554151337876
746 17411534142996779936403
747 18079708293891306220896
748 18772924734155570038769
749 19492378417571613102684
750 20238762797767227076537
751 21013357797794080673448
752 21816911634268334170253
753 22650795116652910177254
754 23515815450737779221533
755 24413440700300369665937
756 25344541518785503304813
757 26310690071523899413312
758 27312825293456878140161
759 28352630684006712642816
760 29431118693290819787660
761 30550091933937174560586
762 31710641898087524736462
763 32914698671361405063067
764 34163438773694163114418
765 35458928599358676921457
766 36802436170376018783427
767 38196173687341897938423
768 39641507517717314882860
769 41140805869987810575124
770 42695540860910783512954
771 44308247494617405826251
772 45980511637990787369407
773 47715046680846139817163
774 49513560703835251347194
775 51378957924853874566382
776 53313077786591827704362
777 55319028499205855014885
778 57398790744468242469575
779 59555690860262722283452
780 61791861223646635705627
781 64110861468329067612527
782 66514986958296803176825
783 69008046677893444612686
784 71592511159385121595668
785 74272455968958760134495
786 77050539710928074556661
787 79931123014361656884726
788 82917066478840110800767
789 86013035366204934932476
790 89222107279680298689887
791 92549273107247169935514
792 95997843363656700104095
793 99573157069638564750168
794 103278774802223426402701
795 107120407555907388456924
796 111101884444178957553457
797 115229313999312351884647
798 119506813462398415007883
799 123940916298053523198744
800 128536048981181026734769
801 133299198937872458473329
802 138235124595655756992070
803 143351298454945353019498
804 148652834999534159355137
805 154147725131927800052947
806 159841465341091749980276
807 165742600258147615968834
808 171857036290761039338707
809 178193909645676567451504
810 184759566275724762476307
811 191563774488054533278937
812 198613351654138525969764
813 205918741149204197108179
814 213487266028332520049868
815 221330090748841358286147
816 229455080430186244262290
817 237874169863607867711394
818 246595805347657969150683
819 255632744240432883938681
820 264994056044698764358345
821 274693376600630237051354
822 284740443248496035740812
823 295149830137750203341538
824 305931990405034027866729
825 317102499972348261066409
826 328672579270613778105330
827 340658873905330645830299
828 353073426310639084535904
829 365934024413272375827387
830 379253591401558812389521
831 393051134589954628226760
832 407340520974150781108997
833 422142059695122484774209
834 437470628555373756026722
835 453347926668364714235987
836 469789914554139802929335
837 486819774836169591503206
838 504454627888664141248163
839 522719239867235621353586
840 541631972981128578388150
841 561219283830974243970314
842 581500864404883206973493
843 602504975216824598426895
844 624252732323365625644994
845 646774321446986360328205
846 670092382939481068583376
847 694239157341171707632236
848 719238916763121465023256
849 745126094139367119850426
850 771926708504142274559945
851 799677532201707429796992
852 828406453622339544654769
853 858152741567781058850139
854 888946284994756714063797
855 920829015880122203785269
856 953832964296789669589582
857 988002903500397252713744
858 1023373154116721507199978
859 1059991520877857411902114
860 1097894775040567667792326
861 1137133954743651900184323
862 1177748453272798987279677
863 1219792757827391260685932
864 1263309065974302459340099
865 1308355544207022455551056
866 1354977389517921852381169
867 1403236692147921520687315
868 1453181857373838758594731
869 1504879160176030460369730
870 1558380436215018322869901
871 1613756423767937306711462
872 1671062626590488353627219
873 1730374542039365692659488
874 1791751596281579324879906
875 1855274361455290500776728
876 1921006456590744545378209
877 1989033865468127217034439
878 2059424689326264623913969
879 2132270681294437526415655
880 2207644734260353497204676
881 2285644752395302926932022
882 2366348749317848355835056
883 2449861187406219786810201
884 2536265552946133987173995
885 2625673298903559599933429
886 2718173760470253168848897
887 2813885842446893962128623
888 2912905129058585127259687
889 3015358468845698164157745
890 3121348122821329442119035
891 3231009405644571332611780
892 3344451712249241357867787
893 3461819380523653114953396
894 3583229425477471429259301
895 3708835802217655317000405
896 3838763665366902230258641
897 3973177218050263920374423
898 4112210309531102482132452
899 4256038063517325591794308
900 4404803614171265534270439
901 4558693722699364457094190
902 4717861438730933467296270
903 4882505922313360602683907
904 5052790811965723642437200
905 5228928478129330430862949
906 5411093864360518623105986
907 5599513416355180218176464
908 5794374147506825104459275
909 5995917497219090027524842
910 6204343365237066316283736
911 6419909163456211491485829
912 6642828546260005685754898
913 6873375940875174410154102
914 7111779683295707953441694
915 7358332323518513570006315
916 7613277868496558226910836
917 7876928170906345066002001
918 8149543960686706765319600
919 8431457650032396284946791
920 8722947814648710503058850
921 9024368760915362799454178
922 9336018108274893258567320
923 9658273478965875586553453
924 9991452809964304965446729
925 10335958553404090030328592
926 10692130322843063080589915
927 11060397008044731896302489
928 11441121348790057909197921
929 11834760384634261411388986
930 12241701522873947729367906
931 12662431775853044345966382
932 13097364862348960815159268
933 13547019703238869794073889
934 14011838081831843188034299
935 14492372888555480456634497
936 14989095835002523156140381
937 15502595975127287293920930
938 16033376936137936851855909
939 16582066265069400738682030
940 17149201623367032661740562
941 17735451530929764424848494
942 18341389935664724222592586
943 18967728969537684709831617
944 19615081267814919037507913
945 20284205376682445391099128
946 20975755177584804503783851
947 21690538613150612483181575
948 22429253530954036081435034
949 23192760443370316329790134
950 23981804062812513726699711
951 24797300840429316284641136
952 25640045442045770990708199
953 26511013842373004072922471
954 27411053943407386070812035
955 28341205057131334185310671
956 29302371819299207958709540
957 30295660927846037746190510
958 31322037478007484619991468
959 32382679860757732384112937
960 33478617590404294273950801
961 34611105332202287771375530
962 35781241237151372502341278
963 36990361107947786054986587
964 38239636223895600212815169
965 39530488697660137008910413
966 40864167709915374195485025
967 42242187183995494894031231
968 43665879284780778038950865
969 45136855585056434520355110
970 46656536645626605865663997
971 48226637897714767225364548
972 49848674048274384598726101
973 51524470988644861029810098
974 53255643693837743695619514
975 55044135522181180919124702
976 56891668233229184789117744
977 58800310102018474367935577
978 60771896595978253399292851
979 62808628826246161638384775
980 64912463337214863846896592
981 67085742480916585684286529
982 69330551720931394449622844
983 71649383584475625529205386
984 74044460785228513784012431
985 76518435521420291751973278
986 79073676622043360411668987
987 81713006033325099693681504
988 84438948131849331136671932
989 87254505321690588337416781
990 90162367545906595370792893
991 93165729047336167029431430
992 96267455994525934088394590
993 99470946545466263736140794
994 102779254432486756764494347
995 106195994561188659657531437
996 109724420269702796927475144
997 113368376845359302154606381
998 117131330040630047637103293
999 121017369990510432475157969
1000 125030188483664431680798495