1 1
2 1
3 3
4 9
5 23
6 54
7 120
8 249
9 478
10 864
11 1495
12 2484
13 3969
14 6136
15 9234
16 13561
17 19464
18 27378
19 37845
20 51488
21 69012
22 91260
23 119239
24 154078
25 197026
26 249535
27 313290
28 390144
29 482120
30 591519
31 720954
32 873264
33 1051513
34 1259130
35 1499950
36 1778097
37 2097984
38 2464489
39 2883000
40 3359266
41 3899397
42 4510080
43 5198628
44 5972795
45 6840777
46 7811469
47 8894521
48 10100113
49 11438953
50 12922585
51 14563449
52 16374609
53 18369755
54 20563560
55 22971744
56 25610757
57 28497778
58 31651128
59 35090341
60 38835792
61 42908697
62 47331586
63 52128378
64 57323953
65 62944152
66 69016314
67 75569355
68 82633280
69 90239184
70 98419854
71 107209855
72 116644978
73 126762238
74 137600551
75 149200824
76 161605332
77 174857720
78 189003753
79 204091410
80 220170192
81 237291121
82 255507570
83 274875364
84 295452009
85 317296692
86 340471195
87 365040000
88 391069438
89 418627689
90 447785784
91 478617714
92 511199495
93 545609169
94 581927895
95 620240065
96 660632281
97 703193353
98 748015489
99 795194415
100 844828257
101 897017543
102 951866490
103 1009483128
104 1069978089
105 1133464606
106 1200059904
107 1269885331
108 1343065044
109 1419726009
110 1499999500
111 1584021234
112 1671929953
113 1763867424
114 1859980050
115 1960419009
116 2065338728
117 2174896884
118 2289256128
119 2408584231
120 2533052446
121 2662835506
122 2798113471
123 2939071878
124 3085899984
125 3238790768
126 3397942899
127 3563560890
128 3735853224
129 3915032353
130 4101316794
131 4294931290
132 4496104809
133 4705070544
134 4922068141
135 5147343864
136 5381148466
137 5623737189
138 5875372128
139 6136322400
140 6406861883
141 6687269217
142 6977830305
143 7278838489
144 7590592153
145 7913394721
146 8247557305
147 8593398885
148 8951243769
149 9321421595
150 9704270124
151 10100135424
152 10509369189
153 10932328738
154 11369379960
155 11820897505
156 12287261952
157 12768859809
158 13266086614
159 13779347130
160 14309052361
161 14855619552
162 15419475450
163 16001056503
164 16600805720
165 17219172672
166 17856616914
167 18513608191
168 19190623138
169 19888145278
170 20606668615
171 21346697844
172 22108744884
173 22893328880
174 23700979965
175 24532239474
176 25387656312
177 26267786953
178 27173199378
179 28104473296
180 29062196337
181 30046964052
182 31059384031
183 32100076128
184 33169668478
185 34268797497
186 35398112184
187 36558274350
188 37749954455
189 38973831609
190 40230598059
191 41520959425
192 42845630353
193 44205334513
194 45600809281
195 47032805979
196 48502085337
197 50009417495
198 51555586878
199 53141392440
200 54767642937
201 56435156926
202 58144767840
203 59897324239
204 61693684884
205 63534718737
206 65421310240
207 67354359570
208 69334777513
209 71363485464
210 73441420914
211 75569537709
212 77748800720
213 79980185844
214 82264685700
215 84603309895
216 86997079486
217 89447026978
218 91954202239
219 94519672770
220 97144517952
221 99829829048
222 102576715335
223 105386304378
224 108259736064
225 111198162601
226 114202754874
227 117274702726
228 120415208769
229 123625488384
230 126906776305
231 130260326904
232 133687407778
233 137189299749
234 140767303680
235 144422740764
236 148156945883
237 151971267609
238 155867075253
239 159845759161
240 163908723841
241 168057387961
242 172293191641
243 176617596753
244 181032079809
245 185538131963
246 190137266544
247 194831019360
248 199620941349
249 204508598578
250 209495580024
251 214583497885
252 219773979984
253 225068669769
254 230469234346
255 235977364794
256 241594768321
257 247323168264
258 253164312378
259 259119973155
260 265191939728
261 271382017872
262 277692038550
263 284123858239
264 290679350578
265 297360406366
266 304168942375
267 311106901680
268 318176245044
269 325378950920
270 332717024529
271 340192498194
272 347807422464
273 355563866113
274 363463925490
275 371509724860
276 379703407257
277 388047134484
278 396543096739
279 405193512960
280 414000621406
281 422966679657
282 432093974520
283 441384822378
284 450841559495
285 460466542017
286 470262156159
287 480230818561
288 490374966313
289 500697056953
290 511199578945
291 521885052039
292 532756017009
293 543815035655
294 555064701570
295 566507640504
296 578146499817
297 589983948478
298 602022688128
299 614265453451
300 626715001332
301 639374110857
302 652245594676
303 665332299378
304 678637094353
305 692162871792
306 705912558354
307 719889115545
308 734095528280
309 748534804884
310 763209989064
311 778124160295
312 793280422078
313 808681901938
314 824331763711
315 840233207934
316 856389459792
317 872803769120
318 889479423003
319 906419746170
320 923628088632
321 941107825681
322 958862370810
323 976895176114
324 995209719609
325 1013809505232
326 1032698076085
327 1051879014840
328 1071355930738
329 1091132459589
330 1111212277344
331 1131599100504
332 1152296672795
333 1173308765169
334 1194639189705
335 1216291800025
336 1238270477641
337 1260579131953
338 1283221714489
339 1306202219325
340 1329524669097
341 1353193115003
342 1377211651380
343 1401584416128
344 1426315576389
345 1451409328546
346 1476869913144
347 1502701615321
348 1528908750144
349 1555495662609
350 1582466742910
351 1609826426874
352 1637579180953
353 1665729502224
354 1694281934010
355 1723241066319
356 1752611520488
357 1782397949184
358 1812605052378
359 1843237577791
360 1874300305186
361 1905798046366
362 1937735661511
363 1970118059628
364 2002950182484
365 2036237004608
366 2069983549989
367 2104194892530
368 2138876139624
369 2174032432153
370 2209668961554
371 2245790970280
372 2282403735009
373 2319512566644
374 2357122827751
375 2395239933024
376 2433869332126
377 2473016509689
378 2512687003128
379 2552886403110
380 2593620336023
381 2634894463977
382 2676714502995
383 2719086223489
384 2762015432353
385 2805507972961
386 2849569743745
387 2894206698675
388 2939424828969
389 2985230163095
390 3031628785734
391 3078626838264
392 3126230500089
393 3174445988638
394 3223279578720
395 3272737603015
396 3322826433012
397 3373552479009
398 3424922209864
399 3476942153490
400 3529618877401
401 3582958988712
402 3636969154290
403 3691656101253
404 3747026597120
405 3803087449812
406 3859845528204
407 3917307762631
408 3975481124638
409 4034372626978
410 4093989344575
411 4154338415034
412 4215427017984
413 4277262375080
414 4339851771375
415 4403202555834
416 4467322120272
417 4532217899353
418 4597897392378
419 4664368163806
420 4731637821777
421 4799714018112
422 4868604470521
423 4938316963128
424 5008859324578
425 5080239428037
426 5152465213824
427 5225544689940
428 5299485909755
429 5374296972009
430 5449986043869
431 5526561361465
432 5604031207153
433 5682403909513
434 5761687866841
435 5841891547689
436 5923023467697
437 6005092189595
438 6088106347128
439 6172074645600
440 6257005838277
441 6342908726386
442 6429792183480
443 6517665155989
444 6606536639184
445 6696415677177
446 6787311387730
447 6879232962810
448 6972189644113
449 7066190723064
450 7161245566074
451 7257363615099
452 7354554362720
453 7452827352144
454 7552192202910
455 7652658611455
456 7754236325746
457 7856935145278
458 7960764947239
459 8065735687080
460 8171857372692
461 8279140064408
462 8387593901625
463 8497229103378
464 8608055942064
465 8720084743441
466 8833325913714
467 8947789940116
468 9063487364169
469 9180428781684
470 9298624870315
471 9418086390144
472 9538824156478
473 9660849039849
474 9784171994040
475 9908804056674
476 10034756321543
477 10162039938609
478 10290666142503
479 10420646253121
480 10551991647481
481 10684713759721
482 10818824110081
483 10954334305503
484 11091256011009
485 11229600949703
486 11369380932234
487 11510607857400
488 11653293683049
489 11797450426078
490 11943090192384
491 12090225177475
492 12238867636884
493 12389029886169
494 12540724331356
495 12693963469554
496 12848759858881
497 13005126118464
498 13163074959378
499 13322619185265
500 13483771661768
501 13646545316532
502 13810953170640
503 13977008339239
504 14144724000478
505 14314113395506
506 14485189860415
507 14657966826870
508 14832457790544
509 15008676311120
510 15186636044739
511 15366350744634
512 15547834229064
513 15731100381313
514 15916163182650
515 16103036712970
516 16291735118217
517 16482272610384
518 16674663500989
519 16868922201720
520 17065063191346
521 17263101015717
522 17463050321760
523 17664925858128
524 17868742441595
525 18074514957057
526 18282258392049
527 18491987837401
528 18703718453113
529 18917465468353
530 19133244216505
531 19351070135829
532 19570958734809
533 19792925592155
534 20016986392380
535 20243156926464
536 20471453056677
537 20701890716578
538 20934485947128
539 21169254897361
540 21406213788672
541 21645378914817
542 21886766678566
543 22130393592378
544 22376276242153
545 22624431287232
546 22874875497594
547 23127625754535
548 23382699013880
549 23640112305984
550 23899882773474
551 24162027671935
552 24426564332578
553 24693510162238
554 24962882681671
555 25234699526244
556 25508978408052
557 25785737115920
558 26064993554253
559 26346765743730
560 26631071782872
561 26917929848041
562 27207358232850
563 27499375348864
564 27793999686609
565 28091249815572
566 28391144424175
567 28693702320480
568 28998942392638
569 29306883608889
570 29617545058104
571 29930945950494
572 30247105577495
573 30566043311769
574 30887778648315
575 31212331205185
576 31539720682801
577 31869966863953
578 32203089655489
579 32539109089035
580 32878045279737
581 33219918426263
582 33564748853070
583 33912557011128
584 34263363436089
585 34617188748286
586 34974053695584
587 35333979154111
588 35696986085844
589 36063095538609
590 36432328689520
591 36804706845714
592 37180251401353
593 37558983837624
594 37940925766770
595 38326098932829
596 38714525168048
597 39106226392884
598 39501224660628
599 39899542158151
600 40301201161726
601 40706224037026
602 41114633284351
603 41526451539378
604 41941701528384
605 42360406068248
606 42782588112279
607 43208270750970
608 43637477166624
609 44070230633353
610 44506554563514
611 44946472508470
612 45390008112609
613 45837185113344
614 46288027388161
615 46742558955384
616 47200803927586
617 47662786511589
618 48128531056128
619 48598062052620
620 49071404087963
621 49548581844537
622 50029620148485
623 50514543970489
624 51003378377953
625 51496148535001
626 51992879751385
627 52493597483265
628 52998327284769
629 53507094807995
630 54019925852544
631 54536846366304
632 55057882396389
633 55583060089138
634 56112405740280
635 56645945795725
636 57183706801872
637 57725715405609
638 58271998405114
639 58822582750650
640 59377495494241
641 59936763789672
642 60500414943930
643 61068476418003
644 61640975775920
645 62217940684752
646 62799398966694
647 63385378599871
648 63975907666738
649 64571014354078
650 65170727005735
651 65775074123424
652 66384084314484
653 66997786291880
654 67616208927585
655 68239381253394
656 68867332408032
657 69500091637153
658 70137688347378
659 70780152107116
660 71427512593017
661 72079799589972
662 72737043045811
663 73399273072128
664 74066519890078
665 74738813830377
666 75416185388664
667 76098665226330
668 76786284115655
669 77479072939809
670 78177062748879
671 78880284760705
672 79588770305353
673 80302550825113
674 81021657931201
675 81746123404599
676 82475979139857
677 83211257145095
678 83951989599378
679 84698208853560
680 85449947373417
681 86207237739646
682 86970112705920
683 87738605199739
684 88512748264884
685 89292575061417
686 90078118924420
687 90869413364850
688 91666492011313
689 92469388610064
690 93278137084434
691 94092771535689
692 94913326184120
693 95739835369044
694 96572333608920
695 97410855602215
696 98255436167806
697 99106110244978
698 99962912954239
699 100825879598190
700 101695045601232
701 102570446509568
702 103452118052715
703 104340096144378
704 105234416821464
705 106135116244081
706 107042230757754
707 107955796894306
708 108875851310169
709 109802430786384
710 110735572291525
711 111675312982584
712 112621690142578
713 113574741180549
714 114534503695200
715 115501015475784
716 116474314439003
717 117454438629009
718 118441426281753
719 119435315825881
720 120436145818921
721 121443954947281
722 122458782091321
723 123480666326253
724 124509646857609
725 125545763021243
726 126589054349124
727 127639560570240
728 128697321545349
729 129762377266978
730 130834767925944
731 131914533912265
732 133001715749184
733 134096354093169
734 135198489801166
735 136308163931514
736 137425417677241
737 138550292366064
738 139682829528378
739 140823070898175
740 141971058345608
741 143126833876992
742 144290439703530
743 145461918242239
744 146641312047778
745 147828663812446
746 149024016435655
747 150227413024860
748 151438896826644
749 152658511226720
750 153886299820149
751 155122306412274
752 156366574949064
753 157619149517113
754 158880074414610
755 160149394152280
756 161427153382977
757 162713396901684
758 164008169717239
759 165311517053280
760 166623484277086
761 167944116899577
762 169273460647800
763 170611561465878
764 171958465443095
765 173314218813897
766 174678868031139
767 176052459767041
768 177435040840513
769 178826658217153
770 180227359083265
771 181637190846819
772 183056201064009
773 184484437439255
774 185921947899990
775 187368780597624
776 188824983833337
777 190290606058078
778 191765695948128
779 193250302406071
780 194744474485812
781 196248261392577
782 197761712559256
783 199284877647378
784 200817806471353
785 202360548998472
786 203913155426034
787 205475676182325
788 207048161850080
789 208630663166484
790 210223231101084
791 211825916856775
792 213438771792478
793 215061847423138
794 216695195498431
795 218338868003754
796 219992917082112
797 221657395034120
798 223332354397503
799 225017847948090
800 226713928620912
801 228420649510201
802 230138063949690
803 231866225513614
804 233605187937009
805 235355005115712
806 237115731187465
807 238887420532920
808 240670127695138
809 242463907379589
810 244268814536064
811 246084904359684
812 247912232209595
813 249750853608969
814 251600824327725
815 253462200383545
816 255335037959761
817 257219393405353
818 259115323318489
819 261022884547545
820 262942134108177
821 264873129183323
822 266815927207560
823 268770585868128
824 270737163021189
825 272715716691826
826 274706305159224
827 276708986957701
828 278723820792144
829 280750865538009
830 282790180327330
831 284841824549754
832 286905857767153
833 288982339713624
834 291071330382330
835 293172890026539
836 295287079073408
837 297413958123984
838 299553588040878
839 301706029949311
840 303871345150066
841 306049595119486
842 308240841597991
843 310445146591128
844 312662572281684
845 314893181029688
846 317137035461769
847 319394198472210
848 321664733134224
849 323948702699953
850 326246170690674
851 328557200897860
852 330881857293609
853 333220204030644
854 335572305533371
855 337938226498944
856 340318031806846
857 342711786518889
858 345119555971128
859 347541405774930
860 349977401725703
861 352427609802897
862 354892096262775
863 357370927639489
864 359864170652953
865 362371892208841
866 364894159492225
867 367431039968655
868 369982601291169
869 372548911300295
870 375130038118554
871 377726050151544
872 380337015994089
873 382963004430238
874 385604084528640
875 388260325643635
876 390931797320532
877 393618569295609
878 396320711592364
879 399038294522610
880 401771388590881
881 404520064494432
882 407284393220370
883 410064446046753
884 412860294446120
885 415672010085492
886 418499664924384
887 421343331215911
888 424203081409438
889 427078988150578
890 429971124380095
891 432879563335014
892 435804378450384
893 438745643359280
894 441703431992595
895 444677818580154
896 447668877551592
897 450676683536353
898 453701311464378
899 456742836567226
900 459801334278057
901 462876880231632
902 465969550365901
903 469079420923128
904 472206568348978
905 475351069292517
906 478513000708704
907 481692439859520
908 484889464212155
909 488104151439009
910 491336579521089
911 494586826749145
912 497854971620953
913 501141092841313
914 504445269426361
915 507767580704709
916 511108106213817
917 514466925699995
918 517844119223628
919 521239767160320
920 524653950096357
921 528086748828706
922 531538244471160
923 535008518455489
924 538497652425984
925 542005728239457
926 545532828072310
927 549079034421690
928 552644429999113
929 556229097730464
930 559833120863994
931 563456582971479
932 567099567840920
933 570762159476544
934 574444442207730
935 578146500690175
936 581868419797666
937 585610284622078
938 589372180583239
939 593154193430100
940 596956409131572
941 600778913876528
942 604621794184605
943 608485136907378
944 612369029118264
945 616273558112521
946 620198811518994
947 624144877301296
948 628111843646769
949 632099798966484
950 636108832007935
951 640139031856224
952 644190487822078
953 648263289441849
954 652357526591160
955 656473289486094
956 660610668570263
957 664769754514809
958 668950638333003
959 673153411381441
960 677378165246161
961 681624991742641
962 685893983031361
963 690185231619003
964 694498830243609
965 698834871874583
966 703193449829214
967 707574657773880
968 711978589608249
969 716405339465278
970 720855001828704
971 725327671534255
972 729823443652884
973 734342413490769
974 738884676707776
975 743450329318674
976 748039467575401
977 752652187967064
978 757288587339378
979 761948762895885
980 766632812079248
981 771340832571252
982 776072922413220
983 780829180007239
984 785609703996478
985 790414593265186
986 795243947060095
987 800097864991650
988 804976446913344
989 809879792921720
990 814808003478759
991 819761179413114
992 824739421798464
993 829742831953513
994 834771511565370
995 839825562690790
996 844905087633537
997 850010188944384
998 855140969545489
999 860297532731640
1000 865479982046626