0 1
1 1
2 2
3 6
4 21
5 69
6 190
7 446
8 927
9 1745
10 3036
11 4960
12 7701
13 11467
14 16490
15 23026
16 31355
17 41781
18 54632
19 70260
20 89041
21 111375
22 137686
23 168422
24 204055
25 245081
26 292020
27 345416
28 405837
29 473875
30 550146
31 635290
32 729971
33 834877
34 950720
35 1078236
36 1218185
37 1371351
38 1538542
39 1720590
40 1918351
41 2132705
42 2364556
43 2614832
44 2884485
45 3174491
46 3485850
47 3819586
48 4176747
49 4558405
50 4965656
51 5399620
52 5861441
53 6352287
54 6873350
55 7425846
56 8011015
57 8630121
58 9284452
59 9975320
60 10704061
61 11472035
62 12280626
63 13131242
64 14025315
65 14964301
66 15949680
67 16982956
68 18065657
69 19199335
70 20385566
71 21625950
72 22922111
73 24275697
74 25688380
75 27161856
76 28697845
77 30298091
78 31964362
79 33698450
80 35502171
81 37377365
82 39325896
83 41349652
84 43450545
85 45630511
86 47891510
87 50235526
88 52664567
89 55180665
90 57785876
91 60482280
92 63271981
93 66157107
94 69139810
95 72222266
96 75406675
97 78695261
98 82090272
99 85593980
100 89208681
101 92936695
102 96780366
103 100742062
104 104824175
105 109029121
106 113359340
107 117817296
108 122405477
109 127126395
110 131982586
111 136976610
112 142111051
113 147388517
114 152811640
115 158383076
116 164105505
117 169981631
118 176014182
119 182205910
120 188559591
121 195078025
122 201764036
123 208620472
124 215650205
125 222856131
126 230241170
127 237808266
128 245560387
129 253500525
130 261631696
131 269956940
132 278479321
133 287201927
134 296127870
135 305260286
136 314602335
137 324157201
138 333928092
139 343918240
140 354130901
141 364569355
142 375236906
143 386136882
144 397272635
145 408647541
146 420265000
147 432128436
148 444241297
149 456607055
150 469229206
151 482111270
152 495256791
153 508669337
154 522352500
155 536309896
156 550545165
157 565061971
158 579864002
159 594954970
160 610338611
161 626018685
162 641998976
163 658283292
164 674875465
165 691779351
166 708998830
167 726537806
168 744400207
169 762589985
170 781111116
171 799967600
172 819163461
173 838702747
174 858589530
175 878827906
176 899421995
177 920375941
178 941693912
179 963380100
180 985438721
181 1007874015
182 1030690246
183 1053891702
184 1077482695
185 1101467561
186 1125850660
187 1150636376
188 1175829117
189 1201433315
190 1227453426
191 1253893930
192 1280759331
193 1308054157
194 1335782960
195 1363950316
196 1392560825
197 1421619111
198 1451129822
199 1481097630
200 1511527231
201 1542423345
202 1573790716
203 1605634112
204 1637958325
205 1670768171
206 1704068490
207 1737864146
208 1772160027
209 1806961045
210 1842272136
211 1878098260
212 1914444401
213 1951315567
214 1988716790
215 2026653126
216 2065129655
217 2104151481
218 2143723732
219 2183851560
220 2224540141
221 2265794675
222 2307620386
223 2350022522
224 2393006355
225 2436577181
226 2480740320
227 2525501116
228 2570864937
229 2616837175
230 2663423246
231 2710628590
232 2758458671
233 2806918977
234 2856015020
235 2905752336
236 2956136485
237 3007173051
238 3058867642
239 3111225890
240 3164253451
241 3217956005
242 3272339256
243 3327408932
244 3383170785
245 3439630591
246 3496794150
247 3554667286
248 3613255847
249 3672565705
250 3732602756
251 3793372920
252 3854882141
253 3917136387
254 3980141650
255 4043903946
256 4108429315
257 4173723821
258 4239793552
259 4306644620
260 4374283161
261 4442715335
262 4511947326
263 4581985342
264 4652835615
265 4724504401
266 4796997980
267 4870322656
268 4944484757
269 5019490635
270 5095346666
271 5172059250
272 5249634811
273 5328079797
274 5407400680
275 5487603956
276 5568696145
277 5650683791
278 5733573462
279 5817371750
280 5902085271
281 5987720665
282 6074284596
283 6161783752
284 6250224845
285 6339614611
286 6429959810
287 6521267226
288 6613543667
289 6706795965
290 6801030976
291 6896255580
292 6992476681
293 7089701207
294 7187936110
295 7287188366
296 7387464975
297 7488772961
298 7591119372
299 7694511280
300 7798955781
301 7904459995
302 8011031066
303 8118676162
304 8227402475
305 8337217221
306 8448127640
307 8560140996
308 8673264577
309 8787505695
310 8902871686
311 9019369910
312 9137007751
313 9255792617
314 9375731940
315 9496833176
316 9619103805
317 9742551331
318 9867183282
319 9993007210
320 10120030691
321 10248261325
322 10377706736
323 10508374572
324 10640272505
325 10773408231
326 10907789470
327 11043423966
328 11180319487
329 11318483825
330 11457924796
331 11598650240
332 11740668021
333 11883986027
334 12028612170
335 12174554386
336 12321820635
337 12470418901
338 12620357192
339 12771643540
340 12924286001
341 13078292655
342 13233671606
343 13390430982
344 13548578935
345 13708123641
346 13869073300
347 14031436136
348 14195220397
349 14360434355
350 14527086306
351 14695184570
352 14864737491
353 15035753437
354 15208240800
355 15382207996
356 15557663465
357 15734615671
358 15913073102
359 16093044270
360 16274537711
361 16457561985
362 16642125676
363 16828237392
364 17015905765
365 17205139451
366 17395947130
367 17588337506
368 17782319307
369 17977901285
370 18175092216
371 18373900900
372 18574336161
373 18776406847
374 18980121830
375 19185490006
376 19392520295
377 19601221641
378 19811603012
379 20023673400
380 20237441821
381 20452917315
382 20670108946
383 20889025802
384 21109676995
385 21332071661
386 21556218960
387 21782128076
388 22009808217
389 22239268615
390 22470518526
391 22703567230
392 22938424031
393 23175098257
394 23413599260
395 23653936416
396 23896119125
397 24140156811
398 24386058922
399 24633834930
400 24883494331
401 25135046645
402 25388501416
403 25643868212
404 25901156625
405 26160376271
406 26421536790
407 26684647846
408 26949719127
409 27216760345
410 27485781236
411 27756791560
412 28029801101
413 28304819667
414 28581857090
415 28860923226
416 29142027955
417 29425181181
418 29710392832
419 29997672860
420 30287031241
421 30578477975
422 30872023086
423 31167676622
424 31465448655
425 31765349281
426 32067388620
427 32371576816
428 32677924037
429 32986440475
430 33297136346
431 33610021890
432 33925107371
433 34242403077
434 34561919320
435 34883666436
436 35207654785
437 35533894751
438 35862396742
439 36193171190
440 36526228551
441 36861579305
442 37199233956
443 37539203032
444 37881497085
445 38226126691
446 38573102450
447 38922434986
448 39274134947
449 39628213005
450 39984679856
451 40343546220
452 40704822841
453 41068520487
454 41434649950
455 41803222046
456 42174247615
457 42547737521
458 42923702652
459 43302153920
460 43683102261
461 44066558635
462 44452534026
463 44841039442
464 45232085915
465 45625684501
466 46021846280
467 46420582356
468 46821903857
469 47225821935
470 47632347766
471 48041492550
472 48453267511
473 48867683897
474 49284752980
475 49704486056
476 50126894445
477 50551989491
478 50979782562
479 51410285050
480 51843508371
481 52279463965
482 52718163296
483 53159617852
484 53603839145
485 54050838711
486 54500628110
487 54953218926
488 55408622767
489 55866851265
490 56327916076
491 56791828880
492 57258601381
493 57728245307
494 58200772410
495 58676194466
496 59154523275
497 59635770661
498 60119948472
499 60607068580
500 61097142881
501 61590183295
502 62086201766
503 62585210262
504 63087220775
505 63592245321
506 64100295940
507 64611384696
508 65125523677
509 65642724995
510 66163000786
511 66686363210
512 67212824451
513 67742396717
514 68275092240
515 68810923276
516 69349902105
517 69892041031
518 70437352382
519 70985848510
520 71537541791
521 72092444625
522 72650569436
523 73211928672
524 73776534805
525 74344400331
526 74915537770
527 75489959666
528 76067678587
529 76648707125
530 77233057896
531 77820743540
532 78411776721
533 79006170127
534 79603936470
535 80205088486
536 80809638935
537 81417600601
538 82028986292
539 82643808840
540 83262081101
541 83883815955
542 84509026306
543 85137725082
544 85769925235
545 86405639741
546 87044881600
547 87687663836
548 88333999497
549 88983901655
550 89637383406
551 90294457870
552 90955138191
553 91619437537
554 92287369100
555 92958946096
556 93634181765
557 94313089371
558 94995682202
559 95681973570
560 96371976811
561 97065705285
562 97763172376
563 98464391492
564 99169376065
565 99878139551
566 100590695430
567 101307057206
568 102027238407
569 102751252585
570 103479113316
571 104210834200
572 104946428861
573 105685910947
574 106429294130
575 107176592106
576 107927818595
577 108682987341
578 109442112112
579 110205206700
580 110972284921
581 111743360615
582 112518447646
583 113297559902
584 114080711295
585 114867915761
586 115659187260
587 116454539776
588 117253987317
589 118057543915
590 118865223626
591 119677040530
592 120493008731
593 121313142357
594 122137455560
595 122965962516
596 123798677425
597 124635614511
598 125476788022
599 126322212230
600 127171901431
601 128025869945
602 128884132116
603 129746702312
604 130613594925
605 131484824371
606 132360405090
607 133240351546
608 134124678227
609 135013399645
610 135906530336
611 136804084860
612 137706077801
613 138612523767
614 139523437390
615 140438833326
616 141358726255
617 142283130881
618 143212061932
619 144145534160
620 145083562341
621 146026161275
622 146973345786
623 147925130722
624 148881530955
625 149842561381
626 150808236920
627 151778572516
628 152753583137
629 153733283775
630 154717689446
631 155706815190
632 156700676071
633 157699287177
634 158702663620
635 159710820536
636 160723773085
637 161741536451
638 162764125842
639 163791556490
640 164823843651
641 165861002605
642 166903048656
643 167949997132
644 169001863385
645 170058662791
646 171120410750
647 172187122686
648 173258814047
649 174335500305
650 175417196956
651 176503919520
652 177595683541
653 178692504587
654 179794398250
655 180901380146
656 182013465915
657 183130671221
658 184253011752
659 185380503220
660 186513161361
661 187651001935
662 188794040726
663 189942293542
664 191095776215
665 192254504601
666 193418494580
667 194587762056
668 195762322957
669 196942193235
670 198127388866
671 199317925850
672 200513820211
673 201715087997
674 202921745280
675 204133808156
676 205351292745
677 206574215191
678 207802591662
679 209036438350
680 210275771471
681 211520607265
682 212770961996
683 214026851952
684 215288293445
685 216555302811
686 217827896410
687 219106090626
688 220389901867
689 221679346565
690 222974441176
691 224275202180
692 225581646081
693 226893789407
694 228211648710
695 229535240566
696 230864581575
697 232199688361
698 233540577572
699 234887265880
700 236239769981
701 237598106595
702 238962292466
703 240332344362
704 241708279075
705 243090113421
706 244477864240
707 245871548396
708 247271182777
709 248676784295
710 250088369886
711 251505956510
712 252929561151
713 254359200817
714 255794892540
715 257236653376
716 258684500405
717 260138450731
718 261598521482
719 263064729810
720 264537092891
721 266015627925
722 267500352136
723 268991282772
724 270488437105
725 271991832431
726 273501486070
727 275017415366
728 276539637687
729 278068170425
730 279603030996
731 281144236840
732 282691805421
733 284245754227
734 285806100770
735 287372862586
736 288946057235
737 290525702301
738 292111815392
739 293704414140
740 295303516201
741 296909139255
742 298521301006
743 300140019182
744 301765311535
745 303397195841
746 305035689900
747 306680811536
748 308332578597
749 309991008955
750 311656120506
751 313327931170
752 315006458891
753 316691721637
754 318383737400
755 320082524196
756 321788100065
757 323500483071
758 325219691302
759 326945742870
760 328678655911
761 330418448585
762 332165139076
763 333918745592
764 335679286365
765 337446779651
766 339221243730
767 341002696906
768 342791157507
769 344586643885
770 346389174416
771 348198767500
772 350015441561
773 351839215047
774 353670106430
775 355508134206
776 357353316895
777 359205673041
778 361065221212
779 362931980000
780 364805968021
781 366687203915
782 368575706346
783 370471494002
784 372374585595
785 374284999861
786 376202755560
787 378127871476
788 380060366417
789 382000259215
790 383947568726
791 385902313830
792 387864513431
793 389834186457
794 391811351860
795 393796028616
796 395788235725
797 397787992211
798 399795317122
799 401810229530
800 403832748531
801 405862893245
802 407900682816
803 409946136412
804 411999273225
805 414060112471
806 416128673390
807 418204975246
808 420289037327
809 422380878945
810 424480519436
811 426587978160
812 428703274501
813 430826427867
814 432957457690
815 435096383426
816 437243224555
817 439398000581
818 441560731032
819 443731435460
820 445910133441
821 448096844575
822 450291588486
823 452494384822
824 454705253255
825 456924213481
826 459151285220
827 461386488216
828 463629842237
829 465881367075
830 468141082546
831 470409008490
832 472685164771
833 474969571277
834 477262247920
835 479563214636
836 481872491385
837 484190098151
838 486516054942
839 488850381790
840 491193098751
841 493544225905
842 495903783356
843 498271791232
844 500648269685
845 503033238891
846 505426719050
847 507828730386
848 510239293147
849 512658427605
850 515086154056
851 517522492820
852 519967464241
853 522421088687
854 524883386550
855 527354378246
856 529834084215
857 532322524921
858 534819720852
859 537325692520
860 539840460461
861 542364045235
862 544896467426
863 547437747642
864 549987906515
865 552546964701
866 555114942880
867 557691861756
868 560277742057
869 562872604535
870 565476469966
871 568089359150
872 570711292911
873 573342292097
874 575982377580
875 578631570256
876 581289891045
877 583957360891
878 586634000762
879 589319831650
880 592014874571
881 594719150565
882 597432680696
883 600155486052
884 602887587745
885 605629006911
886 608379764710
887 611139882326
888 613909380967
889 616688281865
890 619476606276
891 622274375480
892 625081610781
893 627898333507
894 630724565010
895 633560326666
896 636405639875
897 639260526061
898 642125006672
899 644999103180
900 647882837081
901 650776229895
902 653679303166
903 656592078462
904 659514577375
905 662446821521
906 665388832540
907 668340632096
908 671302241877
909 674273683595
910 677254978986
911 680246149810
912 683247217851
913 686258204917
914 689279132840
915 692310023476
916 695350898705
917 698401780431
918 701462690582
919 704533651110
920 707614683991
921 710705811225
922 713807054836
923 716918436872
924 720039979405
925 723171704531
926 726313634370
927 729465791066
928 732628196787
929 735800873725
930 738983844096
931 742177130140
932 745380754121
933 748594738327
934 751819105070
935 755053876686
936 758299075535
937 761554724001
938 764820844492
939 768097459440
940 771384591301
941 774682262555
942 777990495706
943 781309313282
944 784638737835
945 787978791941
946 791329498200
947 794690879236
948 798062957697
949 801445756255
950 804839297606
951 808243604470
952 811658699591
953 815084605737
954 818521345700
955 821968942296
956 825427418365
957 828896796771
958 832377100402
959 835868352170
960 839370575011
961 842883791885
962 846408025776
963 849943299692
964 853489636665
965 857047059751
966 860615592030
967 864195256606
968 867786076607
969 871388075185
970 875001275516
971 878625700800
972 882261374261
973 885908319147
974 889566558730
975 893236116306
976 896917015195
977 900609278741
978 904312930312
979 908027993300
980 911754491121
981 915492447215
982 919241885046
983 923002828102
984 926775299895
985 930559323961
986 934354923860
987 938162123176
988 941980945517
989 945811414515
990 949653553826
991 953507387130
992 957372938131
993 961250230557
994 965139288160
995 969040134716
996 972952794025
997 976877289911
998 980813646222
999 984761886830
1000 988722035631