1 1
2 144
3 112
4 340
5 696
6 1468
7 2528
8 4388
9 6760
10 10444
11 14928
12 21364
13 28952
14 39260
15 51136
16 66628
17 84168
18 106348
19 131120
20 161684
21 195448
22 236284
23 280992
24 334180
25 391976
26 459788
27 533008
28 617908
29 709080
30 813724
31 925568
32 1052804
33 1188232
34 1341100
35 1503216
36 1684948
37 1877048
38 2091068
39 2316640
40 2566564
41 2829288
42 3118924
43 3422672
44 3756020
45 4104856
46 4486108
47 4884288
48 5317828
49 5769800
50 6260204
51 6770608
52 7322644
53 7896312
54 8514940
55 9156896
56 9847268
57 10562728
58 11330188
59 12124560
60 12974644
61 13853528
62 14791964
63 15761152
64 16793860
65 17859336
66 18992428
67 20160368
68 21400148
69 22676920
70 24029884
71 25422048
72 26894884
73 28409192
74 30008780
75 31652176
76 33385588
77 35165208
78 37039708
79 38962880
80 40985924
81 43060168
82 45239404
83 47472432
84 49815700
85 52215416
86 54730748
87 57305248
88 60000868
89 62758440
90 65642764
91 68591888
92 71673524
93 74822872
94 78110620
95 81469056
96 84971908
97 88548488
98 92275628
99 96079600
100 100040404
101 104081208
102 108285244
103 112572512
104 117029540
105 121573096
106 126293068
107 131102928
108 136095988
109 141182360
110 146458844
111 151832128
112 157402564
113 163073352
114 168948460
115 174927536
116 181118228
117 187416568
118 193933948
119 200562720
120 207418084
121 214388648
122 221593484
123 228917392
124 236483380
125 244172376
126 252111388
127 260177408
128 268501508
129 276956680
130 285678124
131 294534768
132 303666004
133 312936632
134 322490300
135 332187616
136 342176548
137 352313448
138 362750668
139 373340240
140 384238964
141 395294488
142 406668124
143 418203072
144 430065220
145 442093256
146 454457708
147 466992688
148 479873428
149 492929400
150 506340604
151 519931808
152 533887844
153 548028712
154 562544140
155 577249296
156 592338868
157 607623128
158 623301788
159 639180160
160 655463044
161 671950728
162 688853164
163 705965552
164 723503060
165 741255736
166 759444028
167 777852768
168 796707748
169 815788520
170 835326284
171 855095248
172 875332084
173 895805592
174 916757980
175 937952576
176 959637188
177 981569608
178 1004003308
179 1026690480
180 1049890324
181 1073349368
182 1097332604
183 1121580832
184 1146364900
185 1171419816
186 1197022348
187 1222901648
188 1249340468
189 1276062040
190 1303355164
191 1330937088
192 1359102724
193 1387563272
194 1416619820
195 1445977456
196 1475943508
197 1506216888
198 1537111228
199 1568319200
200 1600160804
201 1632322408
202 1665130444
203 1698264912
204 1732058740
205 1766185496
206 1800984668
207 1836123328
208 1871947588
209 1908117960
210 1944987244
211 1982209328
212 2020143764
213 2058437752
214 2097457660
215 2136843936
216 2176969828
217 2217468968
218 2258721548
219 2300354320
220 2342754484
221 2385541848
222 2429110684
223 2473073792
224 2517832580
225 2562992776
226 2608962988
227 2655341808
228 2702545108
229 2750164280
230 2798622524
231 2847503968
232 2897239204
233 2947405032
234 2998439500
235 3049912016
236 3102268148
237 3155069848
238 3208770268
239 3262923840
240 3317991364
241 3373519688
242 3429977324
243 3486903472
244 3544774420
245 3603121656
246 3662429308
247 3722221088
248 3782989028
249 3844249000
250 3906501004
251 3969253008
252 4033013044
253 4097281112
254 4162573340
255 4228381696
256 4295230468
257 4362603528
258 4431033388
259 4499995760
260 4570031444
261 4640607928
262 4712274364
263 4784489952
264 4857812260
265 4931692136
266 5006695628
267 5082265168
268 5158975348
269 5236260120
270 5314702684
271 5393728448
272 5473929284
273 5554721992
274 5636707180
275 5719292976
276 5803088788
277 5887494008
278 5973126908
279 6059378080
280 6146874724
281 6234998568
282 6324385804
283 6414409232
284 6505714100
285 6597664216
286 6690913948
287 6784818048
288 6880040068
289 6975925640
290 7073147564
291 7171042288
292 7270291924
293 7370223672
294 7471529020
295 7573525856
296 7676915108
297 7781005288
298 7886506828
299 7992718800
300 8100361204
301 8208723608
302 8318535644
303 8429077312
304 8541087940
305 8653837896
306 8768076268
307 8883063728
308 8999559188
309 9116813560
310 9235595644
311 9355146528
312 9476244964
313 9598122152
314 9721566860
315 9845800336
316 9971621428
317 10098241368
318 10226469148
319 10355505920
320 10486170884
321 10617655048
322 10750787884
323 10884750192
324 11020381780
325 11156853176
326 11295014588
327 11434026208
328 11574748708
329 11716331880
330 11859646924
331 12003833168
332 12149772404
333 12296593432
334 12445188700
335 12594676416
336 12745959748
337 12898146248
338 13052149868
339 13207067440
340 13363823764
341 13521504888
342 13681046524
343 13841523872
344 14003883620
345 14167190056
346 14332400908
347 14498569488
348 14666664628
349 14835728600
350 15006741404
351 15178734208
352 15352698244
353 15527653512
354 15704602540
355 15882554096
356 16062522068
357 16243503928
358 16426524988
359 16610571360
360 16796679844
361 16983825128
362 17173055564
363 17363334352
364 17555721460
365 17749168536
366 17944747228
367 18141397568
368 18340202948
369 18540091720
370 18742159084
371 18945321648
372 19150686484
373 19357158392
374 19565856380
375 19775673376
376 19987740388
377 20200938408
378 20416410508
379 20633025680
380 20851939124
381 21072007768
382 21294399004
383 21517957632
384 21743863300
385 21970948616
386 22200405548
387 22431054448
388 22664099668
389 22898349240
390 23135019964
391 23372907488
392 23613241124
393 23854804072
394 24098838220
395 24344114256
396 24591886708
397 24840913688
398 25092462428
399 25345278400
400 25600641604
401 25857284808
402 26116500844
403 26377009712
404 26640117140
405 26904530296
406 27171567868
407 27439924128
408 27710930788
409 27983269160
410 28258284044
411 28534643728
412 28813706164
413 29094126552
414 29377276060
415 29661796736
416 29949073028
417 30237733768
418 30529176748
419 30822017520
420 31117667284
421 31414728248
422 31714625084
423 32015946592
424 32320130980
425 32625753576
426 32934266188
427 33244230608
428 33557112308
429 33871459480
430 34188751324
431 34507522368
432 34829265604
433 35152501832
434 35478737900
435 35806480816
436 36137251348
437 36469542648
438 36804889468
439 37141771040
440 37481736164
441 37823250088
442 38167875724
443 38514064272
444 38863392820
445 39214298456
446 39568372508
447 39924037888
448 40282900228
449 40643368200
450 41007061804
451 41372375408
452 41740943444
453 42111145912
454 42484631740
455 42859766496
456 43238213668
457 43618324328
458 44001776588
459 44386906960
460 44775408244
461 45165602328
462 45559196764
463 45954498752
464 46353230660
465 46753684936
466 47157598828
467 47563249968
468 47972390548
469 48383283320
470 48797695484
471 49213874848
472 49633603684
473 50055114792
474 50480205580
475 50907093776
476 51337591988
477 51769902808
478 52205854108
479 52643633280
480 53085083524
481 53528376968
482 53975372204
483 54424226032
484 54876812500
485 55331273016
486 55789497148
487 56249610848
488 56713519268
489 57179332840
490 57648972364
491 58120532688
492 58595950324
493 59073304472
494 59554547420
495 60037742656
496 60524858308
497 61013942088
498 61506978028
499 62001998000
500 62501002004
501 63002006008
502 63507026044
503 64014062112
504 64525146340
505 65038262696
506 65555459468
507 66074704528
508 66598062388
509 67123484760
510 67653052444
511 68184700928
512 68720527364
513 69258450952
514 69800585260
515 70344833136
516 70893324628
517 71443946168
518 71998844348
519 72555889120
520 73117243684
521 73680761448
522 74248622284
523 74818662992
524 75393080180
525 75969693976
526 76550717788
527 77133955008
528 77721635908
529 78311547080
530 78905935724
531 79502571568
532 80103718804
533 80707130232
534 81315087100
535 81925325216
536 82540142948
537 83157259048
538 83778989068
539 84403034640
540 85031728564
541 85662755288
542 86298464924
543 86936524672
544 87579302020
545 88224446856
546 88874344108
547 89526626288
548 90183695828
549 90843167800
550 91507462204
551 92174176608
552 92845748644
553 93519758312
554 94198660940
555 94880018896
556 95566305268
557 96255064728
558 96948788188
559 97645002560
560 98346216644
561 99049939528
562 99758697964
563 100469983152
564 101186339860
565 101905241336
566 102629250428
567 103355822368
568 104087538148
569 104821834920
570 105561311884
571 106303388048
572 107050680884
573 107800591192
574 108555754780
575 109313554176
576 110076643588
577 110842387208
578 111613457708
579 112387200880
580 113166307924
581 113948106168
582 114735305404
583 115525214432
584 116320561700
585 117118637416
586 117922188748
587 118728487248
588 119540298868
589 120354876440
590 121175004764
591 121997917888
592 122826419524
593 123657724872
594 124494656620
595 125334411056
596 126179829908
597 127028090488
598 127882053628
599 128738877600
600 129601442404
601 130466887208
602 131338111244
603 132212234512
604 133092175540
605 133975035096
606 134863751068
607 135755404928
608 136652953988
609 137553460360
610 138459900844
611 139369318128
612 140284708564
613 141203095352
614 142127494460
615 143054909536
616 143988376228
617 144924878568
618 145867471948
619 146813120720
620 147764900084
621 148719754648
622 149680779484
623 150644899392
624 151615229380
625 152588674376
626 153568369388
627 154551199408
628 155540319508
629 156532594680
630 157531200124
631 158532980768
632 159541132004
633 160552478632
634 161570236300
635 162591209616
636 163618634548
637 164649295448
638 165686448668
639 166726858240
640 167773800964
641 168824020488
642 169880814124
643 170940905072
644 172007611220
645 173077635256
646 174154315708
647 175234334688
648 176321051428
649 177411127400
650 178507942604
651 179608137808
652 180715113844
653 181825490712
654 182942690140
655 184063311296
656 185190796868
657 186321725128
658 187459559788
659 188600858160
660 189749105044
661 190900836728
662 192059559164
663 193221787552
664 194391049060
665 195563837736
666 196743702028
667 197927114768
668 199117645748
669 200311746520
670 201513008284
671 202717861248
672 203929918084
673 205145587592
674 206368503980
675 207595054576
676 208828895188
677 210066391608
678 211311221308
679 212559728480
680 213815612324
681 215075195368
682 216342198604
683 217612922832
684 218891110900
685 220173041816
686 221462480348
687 222755683648
688 224056438468
689 225360980040
690 226673117164
691 227989063088
692 229312648724
693 230640065272
694 231975165820
695 233314119456
696 234660801508
697 236011358888
698 237369689228
699 238731917200
700 240101962804
701 241475928408
702 242857756444
703 244243526912
704 245637204740
705 247034847496
706 248440442668
707 249850025328
708 251267605588
709 252689195960
710 254118829244
711 255552495328
712 256994249764
713 258440059752
714 259894003660
715 261352025936
716 262818227828
717 264288530968
718 265767059548
719 267249712320
720 268740636484
721 270235707848
722 271739096684
723 273246655792
724 274762578580
725 276282694776
726 277811220988
727 279343963808
728 280885163108
729 282430602280
730 283984544524
731 285542749968
732 287109505204
733 288680547032
734 290260185500
735 291844134016
736 293436726148
737 295033651848
738 296639268268
739 298249241840
740 299867953364
741 301491045688
742 303122923324
743 304759205472
744 306404320420
745 308053863656
746 309712287308
747 311375163088
748 313046967028
749 314723247000
750 316408503004
751 318098259008
752 319797039044
753 321500343112
754 323212719340
755 324929643696
756 326655688468
757 328386305528
758 330126091388
759 331870473760
760 333624073444
761 335382293928
762 337149780364
763 338921911952
764 340703358260
765 342489474136
766 344284953628
767 346085127168
768 347894713348
769 349709018120
770 351532784684
771 353361294448
772 355199315284
773 357042103992
774 358894453180
775 360751594976
776 362618346788
777 364489916008
778 366371144908
779 368257216080
780 370152996724
781 372053644568
782 373964051804
783 375879351232
784 377804460100
785 379734486216
786 381674371948
787 383619200048
788 385573938068
789 387533643640
790 389503309564
791 391477968288
792 393462637924
793 395452325672
794 397452075020
795 399456867856
796 401471773108
797 403491747288
798 405521884828
799 407557116800
800 409602563204
801 411653129608
802 413713961644
803 415779939312
804 417856233940
805 419937699896
806 422029534268
807 424126565728
808 426234017188
809 428346691560
810 430469837644
811 432598232528
812 434737150964
813 436881344152
814 439036112860
815 441196182336
816 443366879428
817 445542903368
818 447729607148
819 449921663920
820 452124452884
821 454332621048
822 456551573884
823 458775932192
824 461011127780
825 463251755176
826 465503272588
827 467760248208
828 470028166708
829 472301569880
830 474585968924
831 476875879168
832 479176838404
833 481483335432
834 483800934700
835 486124098416
836 488458417748
837 490798328248
838 493149447868
839 495506185440
840 497874185764
841 500247830888
842 502632792524
843 505023425872
844 507425429620
845 509833132056
846 512252258908
847 514677111488
848 517113442628
849 519555526600
850 522009143404
851 524468540208
852 526939524244
853 529416315512
854 531904748540
855 534399016096
856 536904980068
857 539416805928
858 541940382988
859 544469849360
860 547011121844
861 549558311128
862 552117361564
863 554682356352
864 557259267460
865 559842150536
866 562437005228
867 565037859568
868 567650740948
869 570269649720
870 572900641084
871 575537687648
872 578186872484
873 580842140392
874 583509602380
875 586183175376
876 588868998388
877 591560960408
878 594265228508
879 596975663680
880 599698461124
881 602427453768
882 605168865004
883 607916499632
884 610676609300
885 613442970616
886 616221863548
887 619007036448
888 621804797668
889 624608867240
890 627425581964
891 630248633488
892 633084387124
893 635926506072
894 638781384220
895 641642656256
896 644516744708
897 647397255688
898 650290640428
899 653190476400
900 656103243604
901 659022490808
902 661954726844
903 664893471712
904 667845263140
905 670803592296
906 673775025868
907 676753026128
908 679744188788
909 682741947160
910 685752926044
911 688770529728
912 691801412164
913 694838948552
914 697889822060
915 700947378736
916 704018331028
917 707095995768
918 710187114748
919 713284975520
920 716396349284
921 719514494248
922 722646211084
923 725784728592
924 728936876980
925 732095855576
926 735268524188
927 738448052608
928 741641330308
929 744841497480
930 748055473324
931 751276368368
932 754511131604
933 757752843832
934 761008483900
935 764271102816
936 767547709348
937 770831324648
938 774128987468
939 777433689040
940 780752498164
941 784078376088
942 787418421724
943 790765566272
944 794126938820
945 797495440456
946 800878230508
947 804268179888
948 807672478228
949 811083966200
950 814509863804
951 817942981408
952 821390569444
953 824845407912
954 828314777740
955 831791428496
956 835282671668
957 838781226328
958 842294434588
959 845814984960
960 849350250244
961 852892888328
962 856450302764
963 860015120752
964 863594776660
965 867181866936
966 870783856828
967 874393311968
968 878017728548
969 881649641320
970 885296577484
971 888951040848
972 892620589684
973 896297696792
974 899989951580
975 903689795776
976 907404849988
977 911127524808
978 914865472108
979 918611071280
980 922372005524
981 926140622968
982 929924638204
983 933716368032
984 937523558500
985 941338495016
986 945168955148
987 949007192848
988 952861017268
989 956722650840
990 960599934364
991 964485058688
992 968385896324
993 972294606472
994 976219093420
995 980151484656
996 984099716308
997 988055884088
998 992027956028
999 996007996000
1000 1000004004004