1000
355 864 174057965
836 864 502447917
601 836 515262681
712 601 430851544
968 601 269138366
811 355 717997327
444 601 507899466
264 864 7198356
751 444 476450125
619 751 984223880
910 836 613434912
239 968 276977412
117 864 888380968
724 444 426031587
880 264 770641489
76 601 182553991
781 811 32027168
10 880 518558283
754 117 206778472
579 811 527448271
361 781 134243720
684 781 24725647
765 684 183771255
490 864 460642573
332 910 744648481
187 781 761876396
640 619 756480733
721 10 8270738
133 864 711398626
274 910 65762397
899 910 898582749
862 899 607902500
78 754 150033098
285 619 512826156
926 76 104595597
537 910 174875511
669 899 91797618
846 880 314414536
110 361 489597303
997 836 690803243
190 836 646432816
999 997 521695386
966 640 471454053
69 669 262261202
302 811 138674068
813 619 56864567
944 862 613229095
126 601 757147379
789 332 417340352
896 880 425684756
978 997 292261791
333 640 830625000
207 926 451306521
518 846 196271554
319 332 448172775
965 999 781073654
676 207 640052125
86 190 245890291
410 302 32521761
900 78 452911127
454 410 355151139
93 896 123013268
359 518 147474551
635 361 284084344
167 640 438093054
803 518 250257782
656 332 668852016
949 332 891698541
693 190 282535000
366 965 908255056
493 635 296953034
617 93 948681258
425 944 270623491
132 69 925342382
562 712 801540893
291 846 499328674
912 712 557160905
457 721 260081334
26 846 210045956
416 69 639454545
941 966 661432168
666 366 197093727
275 966 846144729
660 86 337327113
452 899 123087469
116 416 810003168
322 10 90304581
234 126 504117298
514 537 292435666
278 896 544890942
182 319 77529119
904 78 831760025
243 999 509202371
194 86 696551234
547 454 302931391
317 640 422188195
927 444 807761637
235 754 869359025
427 965 538258057
770 676 470069971
91 656 280215506
49 117 639203271
462 781 642263120
709 754 10926529
202 770 107016267
682 235 25738655
271 457 268656728
38 754 600987061
739 86 99495833
610 656 588062384
692 10 216201672
465 635 661103380
822 235 938921513
616 93 921542097
564 803 546313934
802 359 357247249
683 682 65602077
99 235 749832143
158 271 230603392
368 493 163727299
918 425 576612796
875 76 662533259
206 69 334748387
784 666 252340628
119 682 631613644
898 319 747798806
377 190 272440333
247 333 595232851
472 709 54930751
201 754 901299325
480 896 871049333
671 822 579275572
400 864 163548984
680 285 610742332
103 949 894450940
220 683 655066023
136 368 230014288
386 158 294415427
744 271 600852887
459 377 220723727
134 271 182283876
258 93 336588544
842 751 750835046
702 562 113698506
916 784 853625287
560 899 927761475
780 640 277075617
716 802 502959488
713 361 969333641
855 739 766358674
627 490 495372613
854 880 518250276
293 480 796008592
273 285 903446005
642 724 593343245
393 910 3394569
808 875 708516240
833 116 64041699
177 275 484735639
479 999 48286406
150 918 466103625
122 10 593995038
31 136 909790822
140 781 76047697
502 493 932840111
397 49 840607044
897 291 111401441
48 465 553422360
613 765 337848566
572 454 930492112
352 899 276792194
205 134 646246048
151 941 271480408
127 275 356766097
869 291 618339793
804 754 85730132
231 332 64499883
748 702 833151314
487 514 761299729
723 965 975212002
219 459 162625606
614 457 454600451
541 333 541016005
94 854 764350432
732 864 389051334
28 127 232555400
343 134 653224676
74 167 220243143
65 693 2112257
800 723 301364898
193 537 145772948
938 547 230882608
164 219 535816630
176 319 275488016
528 231 32753370
1 547 882166337
695 462 265037109
203 842 524149815
279 167 920043621
40 802 601990028
561 10 76752598
636 487 785532588
559 93 350924477
345 425 493869842
974 926 83534341
144 243 433231815
27 541 248863707
990 669 810881453
248 709 411282635
378 800 612575792
649 480 216103237
46 537 818887136
542 748 980941841
232 151 946841312
72 103 565468523
41 910 939373001
805 789 607517652
863 803 524427904
960 164 135461312
659 926 671247917
405 465 345963431
729 490 568948892
743 459 937958508
501 846 918733656
259 748 959644014
107 490 448282660
883 72 875246423
719 206 112631464
304 134 876484217
484 293 689679443
282 649 198259445
60 562 332957070
445 960 899351547
868 136 156114196
599 202 765913928
794 518 852577604
934 751 782330222
212 537 157441807
308 352 636792951
663 78 372099039
87 140 550514828
959 966 310030861
810 275 926237802
737 465 855968123
474 202 998308894
834 103 438636992
715 397 660465586
223 317 779886614
417 345 133254893
633 855 706806422
251 465 174767385
577 76 872118315
689 635 668024678
367 232 196396806
241 542 535409983
508 834 75656181
29 187 393041405
415 751 461499351
998 501 433712345
994 285 355239248
895 997 605477123
84 822 463572796
585 91 492027309
362 275 624414927
795 405 971954774
646 193 160525931
955 926 944920956
515 136 829546966
609 559 852375604
338 912 887099899
726 721 398286355
96 729 661395679
296 231 927363788
914 541 498430855
686 490 576773856
529 914 569141750
66 72 664030087
843 278 992306902
882 352 803436568
250 836 662679740
101 26 494073801
266 332 694991087
236 343 101988689
735 855 120285685
530 751 922279285
525 732 645177307
441 692 789389777
906 27 337098710
204 362 312442728
827 715 118824679
350 547 775797234
791 577 511733336
589 386 18322617
481 27 689280891
148 724 134619854
395 784 441475306
881 236 611986143
24 136 29952058
857 959 618570370
492 359 711504385
360 140 293495287
222 148 73501693
429 695 630964454
335 222 599472424
936 617 801692559
286 713 534090377
752 601 23108345
145 914 352095053
6 207 12555298
756 416 426873559
612 343 677516252
879 693 854329875
30 739 126160957
987 770 808677986
504 944 823882626
82 117 884341818
128 735 241968000
422 633 937234682
453 846 637045781
696 177 23281413
637 441 916767274
47 990 372289900
249 302 384314005
961 997 720034506
349 164 179700768
595 145 664899915
948 72 916468873
33 914 445053309
63 842 281225167
516 33 465102977
414 126 141835583
583 151 782107659
467 48 139392025
654 827 259173885
214 472 624632062
777 472 277001674
165 122 434548144
911 69 603535980
954 444 106320938
268 751 778187633
178 862 18406528
256 400 646716728
381 231 28445203
221 635 353916402
535 666 309427944
821 998 985668157
536 577 701670944
858 454 950403556
7 66 223607781
486 78 593363108
775 577 365092835
373 282 631344880
301 49 290788911
289 76 52418104
694 47 105201317
569 723 440230803
45 795 395098582
295 126 817415556
878 308 88832871
790 393 485458887
109 202 668647192
246 684 3128850
371 961 795740877
475 319 325544314
458 813 204987388
766 729 27235677
717 480 411437602
988 234 886716817
872 619 900459631
973 599 165657877
594 934 433802627
443 445 645585300
244 256 800404781
967 683 830406850
489 393 829695393
37 927 155629390
991 724 753692492
141 765 770527444
645 973 257142698
957 680 247673780
845 101 219936865
893 805 387539032
767 145 69051219
209 516 567415942
995 31 7576275
901 716 205647129
339 31 215537424
797 128 885563779
491 811 956035532
191 501 939811505
306 381 75848765
611 204 297964269
303 855 484210534
185 361 822283594
593 41 222695424
778 194 982369781
718 46 33695035
820 185 658911521
622 303 963807948
730 304 868649139
929 454 643121658
51 579 515409722
705 368 752677958
384 916 481950760
923 151 115993961
935 167 129733731
830 275 542666781
404 944 736568307
23 429 917808516
309 487 341714548
889 122 599336086
269 676 485777624
208 775 585809695
18 443 222375321
511 613 942140616
921 235 36620024
14 765 163797115
871 84 816952277
449 716 164951204
641 244 771012434
320 537 48602856
89 997 879043007
701 465 321706389
665 754 571705696
951 713 453400220
105 264 894228751
884 802 657274869
237 462 544277862
557 352 713277277
876 601 132169095
734 18 728858166
497 929 318279589
548 404 165722985
793 49 955912204
943 339 378999621
989 63 953909612
673 30 100980879
567 234 777255248
123 793 392760303
114 444 84437674
582 405 952257315
450 167 326482317
856 191 645860782
483 916 510090181
598 235 83172141
809 622 984332416
519 187 289355788
691 830 504786932
389 278 892142992
626 955 61984079
704 954 314241104
506 997 535779886
615 24 410943532
817 536 427760595
706 656 976028611
848 808 363215436
618 836 82503850
812 695 294720364
662 836 969855139
174 151 743698536
420 116 900011002
687 693 519449192
905 453 9323146
138 378 613263565
874 617 309684018
263 427 121644141
523 692 302630524
866 895 19336571
915 682 665292525
853 481 645995303
255 842 927012372
644 444 807971294
399 959 940025385
179 23 924651643
284 988 802552897
835 219 851316321
403 93 649117965
229 775 248074913
230 626 203377160
972 386 859719789
391 72 501630334
861 582 171625139
545 87 645965592
270 821 974622900
162 38 699404040
815 162 125455886
720 94 22028017
652 18 547795909
534 101 641102166
106 897 144746969
825 203 860051647
287 404 370527388
799 809 123129703
553 721 28357141
353 209 651130944
85 800 694373292
142 855 283805812
761 926 962388847
546 997 117267114
531 649 754527656
963 866 613672685
327 345 237174974
976 236 678134530
714 231 473902195
53 820 126698631
877 583 215358027
631 301 806225551
186 397 225872969
318 302 958839475
408 322 91794668
840 317 110499528
3 862 651359072
70 457 258872805
690 577 969446070
924 27 314887128
460 405 293025670
245 371 663326026
314 694 960529335
476 481 404978192
125 999 503757245
39 134 275814285
423 125 634981048
746 94 576029541
629 846 955225112
175 187 422760734
215 884 642577571
315 720 703558158
725 393 669491630
253 613 895497166
154 935 527465858
575 583 87241607
688 706 604594547
312 718 857593986
728 987 287617626
958 656 654950452
867 3 12644414
22 291 274553807
554 719 24471332
947 458 154760332
4 951 201451537
428 530 616538221
471 972 609660402
313 269 921196311
581 511 927046073
143 72 468934054
171 502 474546183
56 399 342578735
100 231 308638595
664 483 878468877
602 243 246342742
464 263 363094724
565 6 454185162
168 136 762043711
139 569 81515925
447 967 757077113
634 497 450193014
792 245 971187451
272 10 706924488
679 746 210163398
388 268 467891302
522 207 228695786
439 237 563459014
394 884 26414585
885 239 542483402
226 522 729150741
668 654 465306785
261 447 469852042
195 203 374819960
81 459 920924362
749 235 344837743
372 688 816955793
628 582 452276940
517 746 162396425
828 767 774391904
334 38 378590678
762 110 166406366
80 723 574669068
73 30 751187134
888 123 756477469
969 914 4832229
982 716 778293129
952 349 259428872
742 516 235405837
184 691 297992050
587 669 921255099
342 713 831806394
555 14 942115961
135 100 701288994
950 730 166332968
539 567 833508947
970 493 138494590
277 534 362574409
254 893 625260320
83 629 854587591
456 748 752912281
850 790 76709844
771 287 110667887
348 38 493452829
213 874 523689126
283 955 176417541
699 136 70382685
933 6 289037617
887 171 683768539
300 690 798819790
90 746 323749393
657 966 827908235
288 720 113766905
852 232 254615846
468 410 743241843
9 732 578135450
242 85 481747756
964 897 478817325
321 215 633172498
509 33 752514803
380 493 125510996
832 381 651884455
43 208 320848233
571 236 826646738
550 761 658914562
939 868 308746987
757 248 668847990
591 491 73499225
540 219 223967533
903 449 744571800
15 583 340325613
188 213 809034365
152 474 761174822
298 48 246498875
674 490 682354533
753 245 837029291
707 926 286149605
440 221 928920823
32 94 175389641
597 82 734055552
64 497 201679403
398 221 470063096
71 322 865474193
418 73 807497825
297 777 197468015
849 458 130041286
469 652 727262438
354 94 625903877
369 213 673458002
975 214 660746742
841 219 752577983
971 519 51591140
625 481 429751818
890 855 425900535
513 296 632841915
485 972 837111292
783 890 739013099
210 270 735435053
299 690 113309097
940 190 540800220
632 109 826690853
779 589 136500186
77 540 975064639
538 123 867456345
323 350 966048933
434 825 863791591
678 251 438831776
120 109 759745562
433 614 317021320
331 343 986686655
370 864 991000499
436 269 869727367
826 746 18103927
731 69 254587826
576 388 542193863
435 631 341330496
62 69 765805294
356 164 838696620
837 250 693508485
512 705 657009993
986 352 184639510
782 679 590579663
533 117 274336601
281 29 358975225
341 790 430067711
823 538 230207683
170 279 962401684
375 810 301302673
12 271 280885380
847 77 390692334
407 368 455046681
776 969 490487123
608 24 761297822
448 964 921965123
267 158 773357802
655 435 735188417
424 320 128516896
351 474 457427477
160 864 587504568
364 961 752540020
280 332 750372108
311 186 994708122
118 720 468401352
189 459 248144925
604 867 772761585
859 41 800887013
227 399 904900550
703 89 371373624
796 863 781702624
570 152 528392633
672 815 208605447
374 790 944374706
54 975 582632673
829 362 364347165
324 80 785500471
95 15 995624449
451 881 224517743
156 323 900719057
727 237 918676254
482 988 623348462
233 410 462224748
252 362 679728882
909 749 435682921
638 934 172544277
981 152 416314500
192 988 988427226
681 941 79743811
588 123 348979615
50 482 552293258
276 929 932152607
16 349 597532112
922 62 412211288
325 632 930654381
526 456 975013321
788 443 60383223
983 832 259762370
639 812 155275093
759 249 429249535
409 761 514941675
310 204 428436367
745 872 864389214
446 748 543599224
698 209 466404020
685 948 127127559
586 731 695951919
238 515 595420024
262 707 697451197
61 586 342376417
466 95 951806682
807 595 754774043
217 914 961698091
600 253 460211066
648 139 623064207
552 95 811237208
340 950 511952905
455 474 252700498
461 587 703477427
946 139 374113143
431 545 108779682
670 812 870246883
169 160 765378508
768 593 897323029
667 255 808410064
98 684 413434365
382 515 578666592
838 964 612616681
159 26 411777174
336 690 805087356
385 910 72383754
507 490 263560275
225 586 557934696
111 272 620416911
419 884 760283750
894 397 400807576
173 627 243406426
624 639 954306276
390 841 353681507
870 997 20114030
124 923 108749518
819 450 308513379
532 869 47200045
708 288 577790717
563 311 235896860
733 655 534545884
357 825 256734175
919 889 649189403
603 768 300616117
473 533 82246713
763 269 346082262
401 604 978272474
851 370 931612002
494 671 924589994
346 986 474298993
521 808 321255775
697 176 130790364
798 800 833452065
20 788 624405366
860 322 483347555
925 914 840177283
520 78 640025418
786 788 587631673
750 680 181798058
383 936 567906848
161 400 654332367
677 298 564009940
920 838 561824372
149 958 964553220
831 479 738251866
396 357 280993305
42 479 611969312
764 447 592481808
886 634 530508250
79 404 831218087
549 518 438924274
147 70 790974345
558 949 449754168
13 492 384960897
977 1 660252173
478 202 270706624
129 796 846043494
816 676 892392585
470 743 395418507
412 965 553672222
52 140 926605984
75 243 598158980
413 30 524010604
643 80 447997450
543 262 412194629
630 889 600747855
907 518 524449006
758 393 891429505
574 64 382008716
130 195 570604771
430 244 154772754
620 345 135469150
108 7 317148429
102 782 959955763
216 795 374762260
316 972 227741138
930 124 175909142
980 646 504993554
146 906 553020397
92 79 784138224
772 302 799526181
292 535 989191805
556 759 293361059
8 476 164738548
438 391 545676448
218 813 676984265
34 467 507595887
344 489 899331431
67 778 95381171
844 654 662570052
942 9 964786345
121 788 262534357
137 622 577360346
57 583 247486927
653 128 138396359
774 125 938208860
747 759 534809935
573 84 630697053
760 252 225376543
818 830 336251875
658 545 639012532
741 543 730287048
58 419 610441256
773 67 708857116
932 770 434872829
839 54 244200208
937 133 833482578
892 449 653954906
224 750 351009197
44 41 151723491
166 277 510459814
908 926 848433111
421 20 467629100
711 812 224726903
500 24 26034657
891 126 455187851
183 886 717310140
544 120 160568778
650 667 115361976
984 33 57221738
505 490 650597362
68 254 571934718
917 451 684643970
700 799 547555034
153 867 368420657
738 168 781466458
584 831 750742852
596 574 304837043
392 94 757537417
437 915 940175454
996 812 365394923
260 230 934276129
307 788 96012434
199 944 571082152
330 335 738650137
112 287 743995936
328 542 726712944
11 343 294678245
5 707 295997609
787 547 26588264
524 153 442921092
568 770 819869073
228 247 417868017
814 223 971302557
661 480 164182114
566 674 919080494
290 898 554568154
510 852 616544509
97 437 218646830
376 680 720317486
463 616 335324370
257 566 258977603
769 404 382023462
19 194 687299342
21 982 401964463
499 997 342516115
197 942 963072704
477 544 650109921
578 963 491800367
363 999 26970268
17 33 1682100
873 569 490046148
496 78 17681547
411 203 163366197
647 476 354621061
931 640 519069222
35 166 211833417
592 803 349032488
155 485 282111317
590 784 568441546
181 262 712318830
240 732 971785435
387 286 207515821
172 277 997603918
985 199 669922457
785 45 466263559
503 714 533679172
379 35 431527758
337 378 838260218
928 210 937161121
605 991 555953819
113 575 985288688
527 876 259589983
962 864 172576435
806 238 851256056
651 716 27031840
25 839 720928055
211 330 698963377
498 60 462080577
607 886 649220793
992 533 256364541
36 260 726043933
551 754 686308234
1000 848 34070437
358 190 455164632
865 998 693639209
993 389 310849036
488 870 524517259
824 449 965817978
442 140 182692320
115 678 504459895
722 232 219773537
902 208 3781769
265 331 95874351
406 949 999488643
953 795 410695351
710 129 888532104
956 374 327377980
200 120 780501279
131 110 460380014
736 640 145887931
157 133 422536470
801 79 536696741
580 209 687671517
88 284 379689935
294 121 610843421
979 247 995739271
59 181 917643040
305 4 151680482
945 199 360865583
913 774 329922584
163 586 950614560
675 70 617566733
426 333 344403645
740 393 361454457
180 472 461332055
326 887 645358241
329 811 540679868
755 404 716818719
104 676 608085343
402 287 295189782
365 981 113364406
495 366 220295283
623 257 391457291
196 481 327636664
606 630 168334524
621 882 116163365
2 495 386427380
55 956 222327079
432 389 330391732
347 390 261114293
198 466 938253503