1 19
2 98
3 218
4 988
5 866
6 2716
7 1946
8 5308
9 12222
10 5402
11 20862
12 18268
13 10586
14 24316
15 45054
16 56502
17 21602
18 73782
19 57148
20 31106
21 104022
22 78748
23 133182
24 207704
25 117628
26 62426
27 132316
28 69986
29 147868
30 605486
31 199708
32 323262
33 114266
34 622330
35 135002
36 426942
37 460854
38 326716
39 520254
40 557622
41 194402
42 1038130
43 221186
44 456316
45 235226
46 1513332
47 1695636
48 607516
49 311906
50 640348
51 1002582
52 345602
53 1815730
54 1161342
55 1216854
56 1273662
57 437402
58 1351422
59 934108
60 477146
61 2488570
62 3780686
63 1145788
64 584066
65 1190716
66 4409678
67 2008062
68 3509170
69 726626
70 1478428
71 2281302
72 3162584
73 2464254
74 2544822
75 1741948
76 2681982
77 3706904
78 1910428
79 3936728
80 5142130
81 1058402
82 5444530
83 1119746
84 3421782
85 2333788
86 3580542
87 4925144
88 2528188
89 1280666
90 2594716
91 8054676
92 5599064
93 2869468
94 5880728
95 3012028
96 4608702
97 9548532
98 1634906
99 15284754
100 5326902
101 9141370
102 5644854
103 5766462
104 1949402
105 5930622
106 10161970
107 6265854
108 6393942
109 2160002
110 6566742
111 6697854
112 4538716
113 2291546
114 14062932
115 12135130
116 2472986
117 4992316
118 7605054
119 7746102
120 2613602
121 16016436
122 5467516
123 8323254
124 11327384
125 14532730
126 11928728
127 15294130
128 12545624
129 9592254
130 9750582
131 6588988
132 13392344
133 10233342
134 6912988
135 14045528
136 7133308
137 25553486
138 18818170
139 23213556
140 3936602
141 19975930
142 4054106
143 8167516
144 4113506
145 20866930
146 30060758
147 8772316
148 4416986
149 8895868
150 31790486
151 9271708
152 4667546
153 9398716
154 48278540
155 9915388
156 20093528
157 25613530
158 20891864
159 10580668
160 16040502
161 16245054
162 38707886
163 11267548
164 17076222
165 17287254
166 23380184
167 17784702
168 36216756
169 12265468
170 18580662
171 6242402
172 31580530
173 6390146
174 19319382
175 32698330
176 6615002
177 33454330
178 6767066
179 20454462
180 62753994
181 14231068
182 7154786
183 14388316
184 21780054
185 22018302
186 29730584
187 22579254
188 22821822
189 85776262
190 7962626
191 40229170
192 32685464
193 41489530
194 25233462
195 25489854
196 34387544
197 52446996
198 17714716
199 26791254
200 27055422
201 9077402
202 27409662
203 55622196
204 47175730
205 86823954
206 9799706
207 19691548
208 29768382
209 9984602
210 30139902
211 20248828
212 10171226
213 20436316
214 62063316
215 10454402
216 31553622
217 184256098
218 33488982
219 33784254
220 45507224
221 104334858
222 59136730
223 84213038
224 24367516
225 12235106
226 24573148
227 37117782
228 49974104
229 25195228
230 12649826
231 38158902
232 77264532
233 65357530
234 13177946
235 26462716
236 13284866
237 26676988
238 40284342
239 81541332
240 82846836
241 55961624
242 85045716
243 43022142
244 28867228
245 43580502
246 58631384
247 29541148
248 59535128
249 29994748
250 106180886
251 30681628
252 46310742
253 15513986
254 31143868
255 47006262
256 15746402
257 47472822
258 79902970
259 162758540
260 49600854
261 33266716
262 16693346
263 203458248
264 34476316
265 17299226
266 87108730
267 105884532
268 17791706
269 89579770
270 72412184
271 54747702
272 55125054
273 55503702
274 168795954
275 57031254
276 38234716
277 19181666
278 115993332
279 97849330
280 118854036
281 80110424
282 162333232
283 144367958
284 62540982
285 41917948
286 21026306
287 42187516
288 21161306
289 106483930
290 129277332
291 65253942
292 65665854
293 199481994
294 22395746
295 180840112
296 22815002
297 254065966
298 70282422
299 94375064
300 71281854
301 47760316
302 23952026
303 48048028
304 96673304
305 73011582
306 122654770
307 24676706
308 124114930
309 175817558
310 127061170
311 76830462
312 155002932
313 26008346
314 52166716
315 26158466
316 131545330
317 159517332
318 26763266
319 215935792
320 27221402
321 81971262
322 54903868
323 27528986
324 138417370
325 111663704
326 254282058
327 345638088
328 58344316
329 87913854
330 117962264
331 238486192
332 30051866
333 60264988
334 121176344
335 244948912
336 30862946
337 61889308
338 124433624
339 93899862
340 94393854
341 63204316
342 190937556
343 32016602
344 355853806
345 98224182
346 32853602
347 98898102
348 66213628
349 99743742
350 234717518
351 101445822
352 67915708
353 34043546
354 102473982
355 68602588
356 103334742
357 208225332
358 104893182
359 105415254
360 248006486
361 71384668
362 107516502
363 216619956
364 145592984
365 109816254
366 73507516
367 483612194
368 340749234
369 191420530
370 154229528
371 77480188
372 116678142
373 39015002
374 117412542
375 435247846
376 240560532
377 40310786
378 324730672
379 163866584
380 82309948
381 248441076
382 292723886
383 210993370
384 42389786
385 84971068
386 170709464
387 128705022
388 129283254
389 86510716
390 43352066
391 86897788
392 130831542
393 175349144
394 88064188
395 44129666
396 132779862
397 222605530
398 44717402
399 224571130
400 180840728
401 90816028
402 319939886
403 230519770
404 278823636
405 46704602
406 140515902
407 94012828
408 47107226
409 379283632
410 335424278
411 96446716
412 145180854
413 194529944
414 146615742
415 98086588
416 444794058
417 199480664
418 250910170
419 151380054
420 152007102
421 203653784
422 256142770
423 309690036
424 364515158
425 104784316
426 157708854
427 158348862
428 52925402
429 748464388
430 54000002
431 271081330
432 218165528
433 109517308
434 385598486
435 110826268
436 222528728
437 335989332
438 168985782
439 339960276
440 113910748
441 171421182
442 576230060
443 290910130
444 58406402
445 469951792
446 773959394
447 120206716
448 60217346
449 362902932
450 182481462
451 122036668
452 367949556
453 185011902
454 247760984
455 124343548
456 249615128
457 692844262
458 63453026
459 127140316
460 63687386
461 383768532
462 906468388
463 65340002
464 196495542
465 197209854
466 197925462
467 132348508
468 199121022
469 66533402
470 400880916
471 134268316
472 404734356
473 67737602
474 339898930
475 68222306
476 548696752
477 68952602
478 554554672
479 209305854
480 703017740
481 568344112
482 286157144
483 143576188
484 71912666
485 144074716
486 72162146
487 799289062
488 293160728
489 442261332
490 222267582
491 372134770
492 74680706
493 149615548
494 225059382
495 75189602
496 226078902
497 378501370
498 75956186
499 457532532
500 383633530
501 76984346
502 386212570
503 544320686
504 234577854
505 156818716
506 235879254
507 315723224
508 237707262
509 238492854
510 639831472
511 483560532
512 80901506
513 162067516
514 570018638
515 245621502
516 164191228
517 329448728
518 413814130
519 332657624
520 250432254
521 251238582
522 928127662
523 255018582
524 85186946
525 427292530
526 602020118
527 172824316
528 259920054
529 784694034
530 87646106
531 439607770
532 619315886
533 177777628
534 89027426
535 446525170
536 629030486
537 180559708
538 362237528
539 820499274
540 183363388
541 275749182
542 92104346
543 184490908
544 277442622
545 92669402
546 557999316
547 186756316
548 939472940
549 1044418606
550 574561332
551 96096026
552 192480316
553 289441854
554 290308662
555 96962402
556 291466422
557 1076161966
558 98415002
559 295828542
560 793163824
561 299048022
562 600740532
563 100466786
564 301989942
565 606637332
566 814376752
567 102242306
568 204781948
569 307916982
570 721951958
571 207168316
572 103733786
573 938101554
574 1263439368
575 530713330
576 319640382
577 106749146
578 535265530
579 107357402
580 538311130
581 107967386
582 541365370
583 326043702
584 108885602
585 545962930
586 109499906
587 549038770
588 330656382
589 442316504
590 1673407710
591 562986970
592 112909466
593 566110330
594 454766744
595 342172854
596 572382970
597 1036905354
598 347530302
599 697911156
600 701720532
601 117324506
602 1060703154
603 355484502
604 237523228
605 357086142
606 358048854
607 1079935794
608 120529946
609 604264570
610 850500686
611 366121854
612 244622716
613 122473946
614 245273308
615 1480771656
616 124105826
617 746929332
618 374941782
619 1004671024
620 504973784
621 379887102
622 380880054
623 1148610834
624 1028527792
625 129066266
626 258466588
627 388535742
628 129735002
629 389874942
630 390880854
631 653706970
632 393569622
633 790172532
634 794225556
635 1198960434
636 133783706
637 402031422
638 268588348
639 1214275914
640 542640728
641 1638899208
642 274754716
643 137549666
644 275444188
645 414029142
646 138240002
647 831861396
648 278210716
649 977381678
650 2113541190
651 710338930
652 427605822
653 858373236
654 1006774958
655 433239102
656 724422130
657 873202932
658 145947746
659 292250716
660 439264854
661 587347544
662 441758142
663 738643570
664 148086146
665 296530108
666 1041617486
667 448201854
668 449280342
669 300120028
670 451080702
671 150600602
672 754807930
673 151322906
674 1214927152
675 916273332
676 613272728
677 1386971154
678 309554908
679 465247062
680 933791796
681 156060002
682 468914742
683 470017854
684 471122262
685 2213211364
686 477405054
687 1118275886
688 320622748
689 642735128
690 806215930
691 647214104
692 974563956
693 1470287754
694 328109308
695 164242946
696 328862716
697 1983747528
698 998686836
699 501051222
700 167270402
701 1342730032
702 505620054
703 506765502
704 1186914638
705 851627770
706 1197655886
707 343341628
708 2591462790
709 521774262
710 522937854
711 524102742
712 700617944
713 526825854
714 351866716
715 176128346
716 1059502932
717 531510462
718 354992668
719 177692186
720 533860542
721 1967568262
722 539364222
723 180050906
724 360496348
725 1628752914
726 181632026
727 363660316
728 1094154516
729 182822402
730 549262422
731 366838108
732 2397407402
733 556444854
734 557646462
735 372432508
736 746470424
737 936102130
738 3018099296
739 1521992752
740 190857602
741 573385302
742 382934428
743 191670626
744 383748316
745 192077786
746 962427130
747 1353113678
748 581950782
749 388649788
750 778939544
751 976753330
752 587696382
753 1967913740
754 395233468
755 197823386
756 594297342
757 2990139390
758 401039548
759 803744984
760 1007808730
761 606355542
762 607609854
763 812099864
764 610541622
765 1224860436
766 409407388
767 615162942
768 205335002
769 616847742
770 411934588
771 618956982
772 206600546
773 1035116530
774 207446402
775 1664656432
776 626580054
777 2097816140
778 421267516
779 1267218036
780 1484907158
781 2990832964
782 644548662
783 2157842540
784 433296988
785 1956983058
786 873530264
787 656668854
788 438504316
789 658845054
790 1542391886
791 663208254
792 664520022
793 1110451930
794 222528602
795 1114836730
796 1342636596
797 898024664
798 1125836530
799 225608546
800 1130251570
801 906854744
802 1364711796
803 1141326970
804 2754307656
805 230491226
806 461428828
807 924644504
808 695048382
809 464111548
810 930015128
811 2101284234
812 1172625370
813 705376854
814 706729662
815 235877402
816 708535422
817 1183905970
818 1425666996
819 238140002
820 1192969330
821 717598782
822 718963254
823 720329022
824 962565464
825 723520854
826 1208913370
827 727177302
828 242697602
829 729008982
830 730384254
831 731760822
832 1222663930
833 980890904
834 2957423688
835 742820022
836 2735560366
837 249615002
838 2253507858
839 502486108
840 1006836824
841 1262046130
842 3809529990
843 1021815128
844 2308255434
845 514672828
846 257572226
847 1290221170
848 776022462
849 258989402
850 777914622
851 519398908
852 2345118858
853 1046390744
854 1574344116
855 2372242194
856 2119490224
857 797442102
858 266133602
859 1600160436
860 802241622
861 1340275930
862 268536602
863 1345092730
864 269500826
865 809467902
866 1352334130
867 1900041878
868 544322716
869 3279531528
870 274347866
871 2200630192
872 275810402
873 1381494130
874 276787586
875 1386384370
876 2785020140
877 558967516
878 279729506
879 559950748
880 1121869784
881 2251623472
882 847072854
883 848555262
884 283181402
885 1702553076
886 2279323312
887 1143633944
888 572811388
889 860461182
890 4324742910
891 289648226
892 1450743730
893 290649602
894 872951382
895 582803548
896 875460222
897 876967254
898 1171636184
899 880488702
900 587832028
901 1767530196
902 886036662
903 1183740824
904 1780671636
905 594908188
906 2087505686
907 1795895316
908 1501244530
909 3620327688
910 908914302
911 1822436532
912 913524822
913 304850306
914 3364656262
915 1228656728
916 2774533554
917 1547433970
918 930529854
919 2177280686
920 623636188
921 312077666
922 937271862
923 1565585530
924 1255591064
925 943516854
926 629880316
927 946125054
928 4754150910
929 2232052886
930 1599576370
931 320441186
932 1926332532
933 1610108530
934 322549346
935 2586734512
936 324135002
937 2925159858
938 3922503048
939 2958640074
940 989413182
941 2646271024
942 2990703114
943 1000118142
944 333730586
945 3011636754
946 671225308
947 1008184662
948 336420866
949 1684801330
950 1351080344
951 1692904570
952 1017907254
953 1019532222
954 1361906264
955 682038268
956 1024414902
957 341833826
958 1711887730
959 342921602
960 2061342036
961 688567516
962 1034215254
963 1035853182
964 345648602
965 2077719156
966 694032316
967 2434866518
968 3143714058
969 700618588
970 1052303742
971 3519618860
972 706130908
973 1414472024
974 1062789462
975 709448668
976 1421112728
977 711664828
978 2496652886
979 1072771254
980 716107516
981 2512220438
982 2160576756
983 721680316
984 361119386
985 5439163590
986 728396188
987 4386101256
988 1100743254
989 1102433022
990 2209940532
991 2216715156
992 2594743886
993 1114864254
994 744187516
995 372377306
996 745321948
997 3363319314
998 1124517942
999 2254160916
1000 1506574424