1 1
2 5
3 20
4 68
5 190
6 441
7 907
8 1690
9 2916
10 4734
11 7310
12 10836
13 15528
14 21619
15 29365
16 39045
17 50961
18 65434
19 82809
20 103453
21 127751
22 156117
23 188980
24 226794
25 270037
26 319204
27 374813
28 437409
29 507553
30 585831
31 672847
32 769233
33 875637
34 992735
35 1121218
36 1261802
37 1415227
38 1582254
39 1763660
40 1960255
41 2172859
42 2402323
43 2649514
44 2915326
45 3200669
46 3506481
47 3833715
48 4183353
49 4556394
50 4953864
51 5376799
52 5826274
53 6303372
54 6809206
55 7344905
56 7911625
57 8510538
58 9142848
59 9809767
60 10512542
61 11252431
62 12030725
63 12848723
64 13707762
65 14609187
66 15554373
67 16544711
68 17581623
69 18666540
70 19800931
71 20986267
72 22224060
73 23515831
74 24863133
75 26267527
76 27730612
77 29253995
78 30839317
79 32488228
80 34202415
81 35983568
82 37833421
83 39753708
84 41746203
85 43812689
86 45954981
87 48174902
88 50474317
89 52855092
90 55319133
91 57868349
92 60504692
93 63230115
94 66046614
95 68956185
96 71960864
97 75062696
98 78263762
99 81566144
100 84971972
101 88483371
102 92102512
103 95831567
104 99672750
105 103628276
106 107700403
107 111891389
108 116203536
109 120639148
110 125200571
111 129890146
112 134710268
113 139663325
114 144751750
115 149977977
116 155344482
117 160853742
118 166508281
119 172310616
120 178263314
121 184368938
122 190630099
123 197049401
124 203629501
125 210373049
126 217282740
127 224361270
128 231611381
129 239035809
130 246637343
131 254418759
132 262382889
133 270532559
134 278870642
135 287400004
136 296123564
137 305044234
138 314164975
139 323488742
140 333018542
141 342757370
142 352708280
143 362874311
144 373258557
145 383864106
146 394694093
147 405751646
148 417039950
149 428562176
150 440321550
151 452321286
152 464564656
153 477054918
154 489795388
155 502789367
156 516040211
157 529551270
158 543325945
159 557367623
160 571679754
161 586265768
162 601129156
163 616273395
164 631702019
165 647418548
166 663426560
167 679729618
168 696331344
169 713235347
170 730445293
171 747964828
172 765797667
173 783947503
174 802418089
175 821213164
176 840336524
177 859791951
178 879583289
179 899714360
180 920189051
181 941011230
182 962184828
183 983713754
184 1005601985
185 1027853476
186 1050472242
187 1073462284
188 1096827664
189 1120572423
190 1144700670
191 1169216486
192 1194124023
193 1219427412
194 1245130846
195 1271238496
196 1297754601
197 1324683378
198 1352029108
199 1379796051
200 1407988534
201 1436610857
202 1465667394
203 1495162489
204 1525100556
205 1555485988
206 1586323240
207 1617616745
208 1649371008
209 1681590505
210 1714279782
211 1747443358
212 1781085825
213 1815211746
214 1849825757
215 1884932464
216 1920536543
217 1956642649
218 1993255503
219 2030379797
220 2068020301
221 2106181750
222 2144868955
223 2184086698
224 2223839833
225 2264133185
226 2304971652
227 2346360102
228 2388303477
229 2430806691
230 2473874730
231 2517512545
232 2561725171
233 2606517606
234 2651894923
235 2697862166
236 2744424451
237 2791586865
238 2839354572
239 2887732699
240 2936726453
241 2986341007
242 3036581612
243 3087453482
244 3138961914
245 3191112168
246 3243909579
247 3297359453
248 3351467172
249 3406238082
250 3461677612
251 3517791148
252 3574584162
253 3632062090
254 3690230445
255 3749094703
256 3808660423
257 3868933127
258 3929918416
259 3991621855
260 4054049091
261 4117205729
262 4181097463
263 4245729942
264 4311108900
265 4377240035
266 4444129122
267 4511781899
268 4580204191
269 4649401779
270 4719380529
271 4790146265
272 4861704899
273 4934062299
274 5007224421
275 5081197176
276 5155986560
277 5231598533
278 5308039136
279 5385314366
280 5463430313
281 5542393017
282 5622208609
283 5702883176
284 5784422892
285 5866833887
286 5950122379
287 6034294541
288 6119356635
289 6205314880
290 6292175582
291 6379944997
292 6468629480
293 6558235334
294 6648768952
295 6740236683
296 6832644963
297 6926000184
298 7020308830
299 7115577333
300 7211812220
301 7309019969
302 7407207151
303 7506380285
304 7606545988
305 7707710825
306 7809881451
307 7913064477
308 8017266605
309 8122494486
310 8228754869
311 8336054445
312 8444400006
313 8553798293
314 8664256139
315 8775780325
316 8888377730
317 9002055181
318 9116819599
319 9232677854
320 9349636913
321 9467703686
322 9586885187
323 9707188370
324 9828620289
325 9951187947
326 10074898439
327 10199758808
328 10325776199
329 10452957698
330 10581310491
331 10710841707
332 10841558578
333 10973468277
334 11106578080
335 11240895203
336 11376426962
337 11513180622
338 11651163544
339 11790383030
340 11930846490
341 12072561269
342 12215534818
343 12359774529
344 12505287896
345 12652082354
346 12800165441
347 12949544635
348 13100227518
349 13252221614
350 13405534549
351 13560173884
352 13716147294
353 13873462387
354 14032126876
355 14192148415
356 14353534760
357 14516293608
358 14680432763
359 14845959962
360 15012883052
361 15181209816
362 15350948145
363 15522105863
364 15694690907
365 15868711147
366 16044174558
367 16221089056
368 16399462663
369 16579303335
370 16760619141
371 16943418077
372 17127708255
373 17313497721
374 17500794628
375 17689607062
376 17879943222
377 18071811240
378 18265219357
379 18460175748
380 18656688700
381 18854766428
382 19054417266
383 19255649473
384 19458471423
385 19662891424
386 19868917891
387 20076559172
388 20285823732
389 20496719962
390 20709256368
391 20923441384
392 21139283562
393 21356791380
394 21575973434
395 21796838245
396 22019394449
397 22243650616
398 22469615427
399 22697297489
400 22926705532
401 23157848206
402 23390734282
403 23625372457
404 23861771545
405 24099940286
406 24339887538
407 24581622084
408 24825152826
409 25070488593
410 25317638331
411 25566610906
412 25817415313
413 26070060465
414 26324555395
415 26580909062
416 26839130542
417 27099228837
418 27361213071
419 27625092286
420 27890875649
421 28158572248
422 28428191294
423 28699741916
424 28973233371
425 29248674834
426 29526075600
427 29805444890
428 30086792046
429 30370126329
430 30655457128
431 30942793744
432 31232145609
433 31523522074
434 31816932612
435 32112386614
436 32409893599
437 32709463004
438 33011104390
439 33314827237
440 33620641152
441 33928555655
442 34238580400
443 34550724951
444 34864999002
445 35181412166
446 35499974178
447 35820694691
448 36143583490
449 36468650271
450 36795904860
451 37125356996
452 37457016551
453 37790893308
454 38126997183
455 38465338002
456 38805925721
457 39148770215
458 39493881485
459 39841269443
460 40190944139
461 40542915528
462 40897193701
463 41253788660
464 41612710539
465 41973969383
466 42337575370
467 42703538588
468 43071869259
469 43442577517
470 43815673628
471 44191167763
472 44569070237
473 44949391268
474 45332141209
475 45717330324
476 46104969009
477 46495067571
478 46887636454
479 47282686005
480 47680226711
481 48080268965
482 48482823298
483 48887900144
484 49295510080
485 49705663586
486 50118371277
487 50533643679
488 50951491454
489 51371925168
490 51794955530
491 52220593146
492 52648848768
493 53079733052
494 53513256791
495 53949430681
496 54388265561
497 54829772173
498 55273961398
499 55720844021
500 56170430969
501 56622733067
502 57077761289
503 57535526504
504 57996039726
505 58459311873
506 58925354000
507 59394177065
508 59865792173
509 60340210325
510 60817442667
511 61297500243
512 61780394245
513 62266135761
514 62754736027
515 63246206174
516 63740557478
517 64237801119
518 64737948418
519 65241010592
520 65746999011
521 66255924935
522 66767799775
523 67282634838
524 67800441578
525 68321231345
526 68845015637
527 69371805847
528 69901613517
529 70434450086
530 70970327140
531 71509256155
532 72051248766
533 72596316496
534 73144471018
535 73695723901
536 74250086861
537 74807571510
538 75368189612
539 75931952819
540 76498872938
541 77068961667
542 77642230857
543 78218692247
544 78798357734
545 79381239103
546 79967348289
547 80556697123
548 81149297587
549 81745161552
550 82344301047
551 82946727983
552 83552454432
553 84161492355
554 84773853865
555 85389550963
556 86008595808
557 86631000447
558 87256777081
559 87885937800
560 88518494851
561 89154460364
562 89793846633
563 90436665832
564 91082930295
565 91732652245
566 92385844057
567 93042517994
568 93702686481
569 94366361824
570 95033556489
571 95704282825
572 96378553344
573 97056380439
574 97737776666
575 98422754461
576 99111326420
577 99803505028
578 100499302926
579 101198732636
580 101901806848
581 102608538127
582 103318939204
583 104033022691
584 104750801362
585 105472287872
586 106197495039
587 106926435561
588 107659122300
589 108395568000
590 109135785567
591 109879787782
592 110627587600
593 111379197849
594 112134631522
595 112893901493
596 113657020798
597 114424002354
598 115194859245
599 115969604428
600 116748251030
601 117530812054
602 118317300671
603 119107729925
604 119902113033
605 120700463085
606 121502793336
607 122309116922
608 123119447145
609 123933797181
610 124752180379
611 125574609955
612 126401099301
613 127231661683
614 128066310534
615 128905059160
616 129747921040
617 130594909526
618 131446038139
619 132301320274
620 133160769498
621 134024399246
622 134892223132
623 135764254635
624 136640507409
625 137520994982
626 138405731049
627 139294729178
628 140188003114
629 141085566468
630 141987433026
631 142893616442
632 143804130548
633 144718989042
634 145638205800
635 146561794563
636 147489769247
637 148422143642
638 149358931709
639 150300147275
640 151245804350
641 152195916804
642 153150498688
643 154109563919
644 155073126591
645 156041200664
646 157013800276
647 157990939430
648 158972632308
649 159958892959
650 160949735609
651 161945174344
652 162945223439
653 163949897027
654 164959209421
655 165973174800
656 166991807520
657 168015121803
658 169043132053
659 170075852532
660 171113297687
661 172155481826
662 173202419440
663 174254124878
664 175310612677
665 176371897232
666 177437993118
667 178508914776
668 179584676828
669 180665293755
670 181750780226
671 182841150762
672 183936420075
673 185036602736
674 186141713498
675 187251766972
676 188366777957
677 189486761110
678 190611731272
679 191741703143
680 192876691610
681 194016711413
682 195161777486
683 196311904613
684 197467107768
685 198627401784
686 199792801676
687 200963322317
688 202138978772
689 203319785957
690 204505758978
691 205696912794
692 206893262557
693 208094823270
694 209301610129
695 210513638180
696 211730922659
697 212953478661
698 214181321467
699 215414466209
700 216652928217
701 217896722666
702 219145864927
703 220400370222
704 221660253965
705 222925531421
706 224196218048
707 225472329154
708 226753880241
709 228040886663
710 229333363966
711 230631327541
712 231934792983
713 233243775730
714 234558291415
715 235878355522
716 237203983727
717 238535191557
718 239871994736
719 241214408831
720 242562449609
721 243916132683
722 245275473864
723 246640488806
724 248011193366
725 249387603244
726 250769734335
727 252157602385
728 253551223336
729 254950612974
730 256355787288
731 257766762104
732 259183553454
733 260606177214
734 262034649457
735 263468986099
736 264909203259
737 266355316899
738 267807343180
739 269265298107
740 270729197887
741 272199058565
742 273674896395
743 275156727466
744 276644568072
745 278138434351
746 279638342638
747 281144309111
748 282656350155
749 284174481991
750 285698721045
751 287229083581
752 288765586071
753 290308244823
754 291857076353
755 293412097012
756 294973323356
757 296540771785
758 298114458900
759 299694401138
760 301280615149
761 302873117413
762 304471924621
763 306077053300
764 307688520184
765 309306341843
766 310930535055
767 312561116433
768 314198102799
769 315841510812
770 317491357338
771 319147659073
772 320810432932
773 322479695658
774 324155464204
775 325837755359
776 327526586119
777 329221973316
778 330923933994
779 332632485025
780 334347643496
781 336069426325
782 337797850643
783 339532933409
784 341274691800
785 343023142821
786 344778303687
787 346540191449
788 348308823369
789 350084216538
790 351866388265
791 353655355681
792 355451136138
793 357253746817
794 359063205111
795 360879528241
796 362702733646
797 364532838593
798 366369860563
799 368213816866
800 370064725029
801 371922602402
802 373787466559
803 375659334894
804 377538225021
805 379424154383
806 381317140635
807 383217201260
808 385124353963
809 387038616270
810 388960005927
811 390888540503
812 392824237790
813 394767115401
814 396717191172
815 398674482759
816 400639008038
817 402610784714
818 404589830708
819 406576163762
820 408569801846
821 410570762745
822 412579064470
823 414594724853
824 416617761948
825 418648193630
826 420686037997
827 422731312967
828 424784036682
829 426844227106
830 428911902425
831 430987080640
832 433069779986
833 435160018511
834 437257814488
835 439363186011
836 441476151396
837 443596728780
838 445724936527
839 447860792814
840 450004316048
841 452155524452
842 454314436477
843 456481070387
844 458655444679
845 460837577663
846 463027487874
847 465225193668
848 467430713627
849 469644066147
850 471865269857
851 474094343193
852 476331304827
853 478576173245
854 480828967160
855 483089705098
856 485358405818
857 487635087892
858 489919770121
859 492212471120
860 494513209736
861 496822004624
862 499138874678
863 501463838597
864 503796915315
865 506138123580
866 508487482367
867 510845010464
868 513210726896
869 515584650494
870 517966800324
871 520357195260
872 522755854414
873 525162796704
874 527578041286
875 530001607121
876 532433513405
877 534873779148
878 537322423591
879 539779465781
880 542244925008
881 544718820362
882 547201171174
883 549691996581
884 552191315957
885 554699148482
886 557215513574
887 559740430456
888 562273918590
889 564815997245
890 567366685927
891 569926003942
892 572493970845
893 575070605989
894 577655928967
895 580249959178
896 582852716258
897 585464219649
898 588084489035
899 590713543898
900 593351403965
901 595998088764
902 598653618066
903 601318011440
904 603991288703
905 606673469470
906 609364573596
907 612064620742
908 614773630810
909 617491623501
910 620218618764
911 622954636340
912 625699696221
913 628453818198
914 631217022304
915 633989328370
916 636770756475
917 639561326496
918 642361058554
919 645169972569
920 647988088708
921 650815426931
922 653652007452
923 656497850275
924 659352975654
925 662217403642
926 665091154534
927 667974248423
928 670866705654
929 673768546363
930 676679790936
931 679600459552
932 682530572643
933 685470150432
934 688419213395
935 691377781798
936 694345876157
937 697323516787
938 700310724249
939 703307518895
940 706313921335
941 709329951964
942 712355631433
943 715390980184
944 718436018911
945 721490768099
946 724555248486
947 727629480600
948 730713485223
949 733807282929
950 736910894544
951 740024340679
952 743147642209
953 746280819792
954 749423894341
955 752576886560
956 755739817405
957 758912707623
958 762095578218
959 765288449977
960 768491343947
961 771704280961
962 774927282110
963 778160368268
964 781403560572
965 784656879942
966 787920347553
967 791193984371
968 794477811618
969 797771850300
970 801076121686
971 804390646822
972 807715447020
973 811050543376
974 814395957243
975 817751709757
976 821117822317
977 824494316105
978 827881212562
979 831278532913
980 834686298645
981 838104531023
982 841533251581
983 844972481628
984 848422242738
985 851882556269
986 855353443836
987 858834926837
988 862327026937
989 865829765577
990 869343164463
991 872867245079
992 876402029177
993 879947538285
994 883503794199
995 887070818490
996 890648632994
997 894237259331
998 897836719382
999 901447034804
1000 905068227527