1000
36739073 920956960 173021185 271876097 348694529 951360513 511970305 450629632 685553696 615260160 79202305 577251328 511455264 608449568 783057920 620272672 306748417 582524961 540836897 141563937 645412865 878455809 813171712 270054433 4726816 576980001 818189312 984130592 819246081 79728672 781713409 844380160 514591777 851228704 168073216 168334336 247234593 879493120 718841857 742395905 338728961 813179937 584328225 917548065 620267520 783552544 945863680 911222817 235415552 209191936 614990881 618405921 373856257 503359489 671918112 184033312 348423200 406326272 616084481 179315744 713599009 879790112 113258528 975966241 205531169 103845888 347608096 8400897 138980385 542653441 551325697 510930976 313042944 574628864 542379040 779878401 444080161 607391776 506724384 955297793 779919361 945827873 674018304 948442145 50114592 519052289 382745632 850920480 953422848 754195488 754225184 708327456 110624800 774383649 542936064 977836032 209200129 236749856 811898912 311431168 347113473 607391777 604506144 350492672 575970336 953943040 518298625 979679232 303598625 168302593 684234753 550244353 335588384 11273217 579088385 342918176 3932161 784868384 135835680 480282657 347638784 615557153 809802753 237505537 778602496 708851744 614733824 647014400 442772512 910994433 752393249 941655041 351834145 706747392 109877281 243302432 551599136 137397249 206057504 753448992 811604001 951101473 683409408 382504993 916229152 570439681 951106560 438083584 72613920 5017632 282856448 585933824 168037408 686031873 246716448 886608896 373044256 77340672 114077697 377762817 716739585 874285089 710719489 246718465 572566561 671093792 108792833 183022593 672142336 978852897 314048512 305443840 407116833 671387649 979121185 379882529 577776641 583568416 472125473 620532769 350000160 511975456 271064097 614999040 312510464 610539553 449886240 710422560 540062720 444341249 214438945 742694912 382206976 503616545 308582400 137374721 644395009 345809921 82873376 779923489 6038561 378580992 513055776 506761217 180096033 773339136 438081537 709670944 235188257 681584641 145538048 10493984 370159617 618699808 37269537 505682945 538228769 951889952 284997632 80781344 506738689 907284480 269257761 805342240 36214816 241961984 682635296 611847200 347119649 446734368 773101569 942712833 752652289 349734912 271851552 912788481 278429728 372520993 277646337 613457920 241971200 35697697 410812416 741118977 67122209 506500096 10234913 645660705 911510561 682919968 270056481 81573921 873212928 82870305 649103392 738757632 510926848 680267777 816885793 647760896 449885184 977799169 144705568 211552289 674506752 271062048 507292672 742136864 876622880 646220832 315664417 777006112 483405825 517216257 921212960 786437153 508344353 72137728 280012832 744784896 170393600 103036928 81276960 71842816 742955008 712023040 407150592 649116673 919906305 609491968 444119041 9484288 441465889 308024321 115344385 205002753 213426208 571483168 849389568 174099456 81540129 614763553 512497665 849655841 108828673 547137537 404787232 40930304 913048608 381727744 317467680 671366176 248810496 349211680 35690496 740568064 275548160 485235745 741909536 704685088 744501249 642779137 39888929 175932417 180890625 821858336 741643264 107264001 35665952 485230592 38016033 741355520 276083712 640201728 813965345 376177696 781233185 916469793 640192545 278960128 444597248 819244065 515902464 177770529 438308896 771793953 709367840 243537952 316680225 941374465 810290176 37267457 847032352 578063392 680002592 950840353 406626305 111709217 43552769 174626816 444906529 720419872 440154113 443592736 44598305 316968960 173016097 272403488 952896544 178523168 470292480 505186304 539272224 708885537 851740673 379879456 346588192 306713600 976748577 271877153 946877473 111684608 271322112 853031936 505953281 238042113 339248128 207402016 242233344 102802432 278396960 404786208 820558849 49297440 739804193 378813472 475533312 316705825 516982817 515411968 710452225 240430113 751076384 302290945 744498176 312213537 683970593 514071553 281060384 248777729 942453792 841484288 369365024 584590337 778844192 872954880 814489600 940063744 441193505 580920352 586448929 482346016 818675744 385367073 649606177 37259265 951626785 240657409 515679233 175934465 778613792 280266785 512244768 946879489 544473120 49813505 509885440 913354785 848598017 739545120 36997152 239375392 550240257 240391169 179343393 272669697 773885953 577020928 846234656 439133185 779364385 383560704 239605792 821035041 719629345 438053920 3178496 374346752 614768673 282899488 310157344 406100993 806622208 576460800 249335841 210778144 806879233 752397344 240400417 182983681 16991198 14460961 552867873 83366944 977840161 985665569 845683712 847250432 169655328 810071040 248515585 246191105 854067200 940088352 377784321 940358657 684764193 738470944 417370112 584620033 516729888 212600865 250877984 783592449 242255905 415251457 981743617 439651328 579896321 302517280 651440160 886308896 135267361 676896801 618925088 341578784 147109920 646452257 109315105 507026433 450375680 404764704 909946913 179046400 204482561 654083105 406072352 15775777 976237601 645933056 378802176 539009024 944808992 384335873 982824992 379100193 739017729 515151905 849126433 371469345 617916416 548450304 611849249 176719873 939524128 210272257 380909601 274735137 741872672 651990048 83623969 945077280 671383584 340303872 243050497 817931296 448541729 754727936 878192640 807702560 750795776 550812673 917550112 848049152 620246048 147327009 573836321 821823488 104636448 976234497 169082913 978099233 179316736 411604993 683421729 974690305 145784833 309632033 846768129 619493409 279195681 402692096 848861216 411075585 337682464 955530241 10785824 647279649 808226848 986201089 610567201 179601441 484711424 921963553 820027393 406587393 947655680 881630209 909381633 619981856 620004352 739510305 672414720 485493792 241180704 417599521 317765665 211334144 174359584 210025504 43821088 519345153 705697792 239902753 375917569 111944737 205790209 101726240 307543040 281542689 108828705 340830240 136090656 909377568 202413088 310916129 506734625 104599585 250915841 886578176 45616128 707298304 884214785 780406785 605298720 278444064 149731329 347614208 375700481 110901280 239375393 879541280 384839680 881066017 14418977 617389088 781491200 951320609 537666561 72125472 374351873 982266913 853554177 914134049 208670752 542686241 513020961 607948832 16023584 445165600 647239680 414724096 714637344 619748385 581483552 505973761 315654177 719894528 376741921 979123233 814782464 513279008 81797152 414487584 752661504 114603009 12103681 747409408 246943776 906542112 415806497 170669089 69217280 440696864 76853249 917250048 605298720 12105728 581481505 547922976 537180160 407633953 747897888 2928672 515156992 172275744 240685088 179089409 178294784 76550177 375433249 708880416 238589952 181940225 916202528 503353345 503841825 79465473 276083712 578828288 270532609 637576193 985701408 308067361 414455840 612666400 249039872 68721664 275024929 141605888 608701441 109882401 68685825 416326689 777828353 820778016 314882048 974400512 653562881 148147201 217317377 174365729 545796097 438086657 682399776 214181920 310393856 986975233 539004929 450375713 887888896 278139937 409743361 515122208 135050272 305695744 750034977 854603809 37003265 919109632 81834017 986725376 645435392 379360288 686328832 142608384 106736640 551848960 711232544 10520577 341095457 68201473 12884000 141307905 713831457 375655425 419183648 684506144 576495617 179581984 481820705 953713696 377002016 610048033 74747905 609223713 815271936 41980928 981220385 115085312 172236833 841232417 476588033 615022593 706222112 678990849 70823937 821281 182200320 38545408 819724288 336116769 110367744 144476193 47495201 142086145 942407713 213162017 743184416 615818272 786183201 40405025 450630657 920922113 107480097 381985824 405572609 41169921 951323648 579373057 654082049 850397184 306223104 550772737 509643776 310902784 442276864 986719232 777031680 715398144 270270496 875871265 5282849 541893664 276332544 9707520 406596609 404274176 743440417 779103233 347083776 744500256 513289248 69211169 6066176 77597696 3936257 348696609 544771072 244628512 275284992 172787713 140814368 686302240 906542081 102796288 485762048 512230400 81803297 552600576 476849153 550504448 640191488 752922625 884508705 277348353 715921440 875311105 909904896 450404384 379862016 505684992 855152640 249561121 208710657 812920832 45615136 452235296 681065473 136056832 44341281 550024192 205534208 410263584 114605089 79444001 606339072 504642592 305930273 573047840 609760289 283906049 956078113 179052545 576496640 874812448 584360993 143659008 775171072 772575265 704680992 13639680 810066944 681056257 944520225 817377281 641473568 544213024 184321024 315633696 674502657 618695712 81532929 348697632 371733536 954732544 987249697 644394017 141819936 150744097 450407457 680036353 82352161 983043104 685511680 135299104 134742048 440971264 72616961 108570657 412921857 347123744 542115873 947954721 268732416 974394401 351808544 70530049 614212608 872417312 46404608 206089249 347120672 848574464 549496865 989341696 112729121 315400224 147100704 273165312 303040544 482905088 772847616 42251264 470819841 201600001 484221953 176174081 582521856 34381824 751567872 544224257 744787969 269784097 749245473 614771744 541896704 715687968 613722112 872681504 746329120 548185121 848573472 410039329 134217728 953984033 674544641 750299136 108561408 912037888 403736609 847809536 34125824 741880865 678199296 639147041 939791361 102538241 314343457 579635232 975483937 141079585 284734496 646486049 102539296 707304481 275523584 74230816 820813856 103813121 311704609 840728608 618182689 484227072 374113313 810554368 643340289 618142720 14688289 886316064 484213760 947135521 77631521 885567521 910164001 611844097 543990817 440410113 172788768 240680961
2 1
3 2
4 2
5 3
6 1
7 2
8 4
9 8
10 7
11 7
12 2
13 4
14 4
15 6
16 6
17 7
18 13
19 14
20 1
21 18
22 16
23 21
24 10
25 5
26 20
27 14
28 24
29 9
30 2
31 18
32 27
33 16
34 14
35 9
36 2
37 7
38 19
39 27
40 10
41 34
42 22
43 3
44 39
45 13
46 25
47 28
48 7
49 48
50 17
51 28
52 14
53 52
54 40
55 17
56 14
57 10
58 7
59 19
60 4
61 32
62 23
63 60
64 29
65 13
66 23
67 11
68 55
69 17
70 64
71 33
72 38
73 45
74 21
75 9
76 24
77 20
78 31
79 44
80 33
81 72
82 62
83 74
84 27
85 68
86 19
87 74
88 45
89 74
90 36
91 84
92 84
93 9
94 67
95 20
96 16
97 23
98 93
99 52
100 15
101 63
102 80
103 3
104 48
105 94
106 83
107 42
108 48
109 29
110 17
111 62
112 53
113 11
114 60
115 111
116 32
117 101
118 5
119 85
120 50
121 92
122 90
123 105
124 110
125 84
126 66
127 79
128 101
129 126
130 4
131 20
132 41
133 31
134 54
135 11
136 41
137 134
138 118
139 14
140 78
141 50
142 38
143 108
144 86
145 119
146 142
147 122
148 147
149 95
150 40
151 135
152 4
153 57
154 23
155 146
156 66
157 19
158 104
159 78
160 6
161 23
162 32
163 65
164 118
165 17
166 13
167 119
168 55
169 129
170 1
171 26
172 87
173 59
174 127
175 110
176 58
177 79
178 56
179 77
180 130
181 28
182 23
183 144
184 96
185 169
186 113
187 62
188 94
189 10
190 20
191 95
192 117
193 119
194 12
195 30
196 118
197 156
198 49
199 123
200 74
201 123
202 49
203 126
204 105
205 16
206 124
207 101
208 133
209 66
210 127
211 22
212 82
213 95
214 107
215 182
216 152
217 138
218 191
219 114
220 51
221 112
222 90
223 78
224 188
225 147
226 151
227 139
228 158
229 47
230 164
231 57
232 214
233 216
234 197
235 47
236 213
237 42
238 153
239 185
240 67
241 79
242 100
243 46
244 97
245 133
246 210
247 104
248 160
249 160
250 39
251 38
252 231
253 30
254 80
255 193
256 236
257 227
258 72
259 257
260 113
261 221
262 32
263 119
264 163
265 3
266 224
267 202
268 41
269 267
270 40
271 120
272 25
273 197
274 33
275 266
276 168
277 3
278 229
279 218
280 12
281 82
282 48
283 244
284 257
285 278
286 175
287 275
288 133
289 195
290 156
291 137
292 29
293 292
294 180
295 143
296 52
297 131
298 22
299 298
300 95
301 64
302 207
303 233
304 82
305 212
306 70
307 47
308 304
309 266
310 74
311 5
312 55
313 252
314 169
315 141
316 57
317 262
318 303
319 73
320 55
321 219
322 321
323 309
324 240
325 282
326 253
327 103
328 206
329 72
330 277
331 3
332 38
333 46
334 70
335 110
336 23
337 311
338 33
339 119
340 1
341 237
342 89
343 263
344 90
345 150
346 316
347 134
348 80
349 80
350 275
351 81
352 278
353 324
354 211
355 69
356 88
357 143
358 250
359 74
360 126
361 319
362 140
363 8
364 217
365 155
366 228
367 201
368 251
369 75
370 26
371 228
372 129
373 154
374 240
375 184
376 198
377 8
378 298
379 94
380 68
381 184
382 196
383 190
384 367
385 35
386 104
387 381
388 351
389 200
390 159
391 299
392 311
393 3
394 382
395 232
396 333
397 191
398 236
399 243
400 336
401 396
402 277
403 10
404 185
405 326
406 242
407 298
408 182
409 231
410 175
411 398
412 397
413 36
414 192
415 49
416 110
417 122
418 71
419 34
420 412
421 154
422 288
423 87
424 160
425 182
426 11
427 284
428 132
429 253
430 248
431 114
432 129
433 334
434 227
435 357
436 11
437 317
438 68
439 209
440 247
441 350
442 233
443 186
444 97
445 60
446 369
447 13
448 374
449 320
450 413
451 308
452 373
453 259
454 226
455 252
456 193
457 162
458 110
459 336
460 179
461 112
462 422
463 382
464 28
465 108
466 105
467 409
468 113
469 317
470 205
471 248
472 265
473 458
474 75
475 144
476 418
477 368
478 49
479 296
480 440
481 97
482 127
483 468
484 167
485 55
486 48
487 365
488 455
489 293
490 384
491 294
492 489
493 305
494 114
495 86
496 171
497 491
498 293
499 249
500 330
501 370
502 471
503 300
504 97
505 240
506 98
507 138
508 336
509 337
510 386
511 392
512 48
513 470
514 458
515 317
516 24
517 447
518 194
519 311
520 92
521 171
522 226
523 409
524 440
525 513
526 475
527 11
528 454
529 517
530 290
531 168
532 490
533 248
534 164
535 156
536 339
537 215
538 43
539 340
540 484
541 350
542 536
543 340
544 306
545 275
546 66
547 205
548 352
549 427
550 263
551 436
552 313
553 222
554 546
555 6
556 547
557 203
558 308
559 493
560 129
561 157
562 210
563 463
564 381
565 285
566 362
567 227
568 322
569 51
570 58
571 328
572 251
573 412
574 282
575 234
576 373
577 312
578 346
579 178
580 54
581 502
582 142
583 73
584 571
585 368
586 233
587 145
588 429
589 336
590 504
591 58
592 152
593 70
594 158
595 586
596 458
597 118
598 586
599 537
600 299
601 535
602 242
603 570
604 68
605 501
606 46
607 308
608 29
609 171
610 161
611 450
612 525
613 315
614 235
615 359
616 355
617 283
618 231
619 588
620 449
621 198
622 393
623 254
624 315
625 523
626 468
627 588
628 28
629 524
630 546
631 617
632 369
633 580
634 313
635 185
636 229
637 303
638 23
639 296
640 493
641 291
642 327
643 309
644 18
645 366
646 52
647 24
648 296
649 247
650 157
651 469
652 386
653 435
654 276
655 437
656 46
657 218
658 88
659 385
660 238
661 530
662 182
663 18
664 299
665 406
666 88
667 420
668 142
669 112
670 594
671 413
672 505
673 555
674 127
675 528
676 16
677 548
678 582
679 635
680 652
681 87
682 538
683 270
684 382
685 262
686 429
687 662
688 272
689 253
690 489
691 56
692 19
693 314
694 458
695 78
696 334
697 516
698 37
699 270
700 258
701 118
702 220
703 381
704 129
705 188
706 289
707 359
708 558
709 274
710 688
711 243
712 166
713 55
714 370
715 622
716 704
717 651
718 334
719 264
720 78
721 705
722 240
723 704
724 514
725 220
726 9
727 165
728 215
729 183
730 700
731 304
732 283
733 706
734 353
735 411
736 10
737 608
738 262
739 481
740 369
741 606
742 50
743 374
744 495
745 273
746 254
747 249
748 422
749 258
750 402
751 274
752 604
753 273
754 514
755 200
756 696
757 641
758 384
759 625
760 321
761 155
762 399
763 142
764 575
765 605
766 461
767 457
768 112
769 44
770 586
771 735
772 345
773 699
774 284
775 773
776 65
777 412
778 676
779 410
780 471
781 587
782 762
783 63
784 179
785 537
786 580
787 19
788 2
789 607
790 21
791 220
792 697
793 541
794 211
795 10
796 617
797 598
798 338
799 713
800 567
801 193
802 586
803 191
804 498
805 387
806 364
807 631
808 5
809 591
810 760
811 466
812 123
813 541
814 226
815 602
816 305
817 604
818 3
819 104
820 519
821 192
822 577
823 374
824 527
825 509
826 508
827 304
828 262
829 262
830 471
831 715
832 340
833 780
834 826
835 555
836 428
837 295
838 135
839 678
840 60
841 462
842 482
843 816
844 305
845 281
846 596
847 556
848 409
849 812
850 699
851 592
852 92
853 229
854 407
855 277
856 163
857 687
858 259
859 702
860 800
861 734
862 235
863 433
864 638
865 386
866 712
867 858
868 10
869 848
870 744
871 318
872 584
873 132
874 67
875 549
876 769
877 719
878 714
879 479
880 728
881 507
882 353
883 398
884 131
885 798
886 43
887 27
888 605
889 162
890 137
891 297
892 7
893 315
894 874
895 467
896 661
897 419
898 307
899 6
900 654
901 817
902 208
903 798
904 407
905 670
906 540
907 393
908 507
909 274
910 53
911 525
912 732
913 761
914 667
915 450
916 806
917 648
918 47
919 75
920 742
921 526
922 391
923 879
924 166
925 433
926 450
927 323
928 659
929 702
930 871
931 110
932 37
933 426
934 361
935 479
936 372
937 83
938 420
939 474
940 857
941 822
942 937
943 655
944 215
945 192
946 574
947 501
948 772
949 570
950 431
951 885
952 242
953 380
954 630
955 382
956 635
957 205
958 289
959 303
960 588
961 945
962 626
963 510
964 465
965 540
966 602
967 227
968 338
969 237
970 152
971 924
972 704
973 172
974 715
975 331
976 527
977 914
978 857
979 767
980 482
981 550
982 398
983 433
984 456
985 963
986 864
987 486
988 401
989 440
990 505
991 372
992 197
993 981
994 321
995 125
996 867
997 637
998 173
999 500
1000 109