1000
111 668 447016799
607 111 787945211
279 668 123431252
747 111 927926410
48 279 423218664
495 48 134099896
148 747 868266490
112 495 111711567
641 279 360109967
116 112 836913281
136 116 148739692
961 48 914865930
978 116 967624504
960 116 314746801
783 960 289927262
935 783 125899777
895 607 624476302
183 668 942028102
189 183 41934183
766 641 920482998
599 48 173295696
841 668 212178576
618 935 317085138
312 607 650654015
560 48 816315624
696 618 371965528
808 279 405626391
681 766 458499910
949 560 472147851
300 189 126631580
122 116 870863311
625 935 385024813
939 696 422748318
204 978 184352772
824 747 808474031
86 696 47761608
259 312 412307826
871 148 90472186
402 183 127347882
913 116 432249358
468 48 358105780
202 696 280663280
786 895 590297294
727 204 249569110
79 808 16783910
609 116 235891689
134 824 538039020
315 134 863149709
742 625 886064887
545 939 260978339
114 48 100689055
992 913 281474829
165 468 233628907
688 960 957788920
433 279 207376951
720 696 937480656
154 824 564655112
437 189 48307669
303 468 430262125
575 609 79039460
399 116 170428301
733 895 663611755
694 733 205272833
218 202 656304434
776 189 586782402
887 747 942075515
452 747 852812213
151 122 8334075
5 841 402397807
214 5 37621685
635 165 868202352
406 48 274748448
928 961 80674833
712 148 942409164
606 939 558005857
172 48 605566366
528 606 603964802
483 766 94314897
392 887 744966554
439 452 298166161
345 606 876288100
157 345 503073779
314 895 404181775
267 766 268951159
760 528 571062548
415 625 688238571
547 259 409089314
252 114 844221968
674 439 783475577
590 439 745107980
250 760 190829093
327 913 260321991
74 696 11855859
562 399 16925971
365 742 605742677
186 625 879677097
47 79 368325563
667 786 434356064
269 345 741847939
891 913 686803464
255 134 67198362
703 528 496489208
350 545 577727165
820 590 239496237
903 214 951230110
565 74 411851160
911 312 451646002
12 202 297462005
123 712 795828321
963 439 876976921
836 202 166354644
14 609 737738582
449 674 606724672
807 891 365530576
858 992 34243590
749 259 565257531
367 116 693662861
659 963 183264092
416 279 780526861
110 635 13459067
89 433 876145829
53 807 513796406
347 742 409457767
857 111 692771011
642 300 181513473
894 575 236329046
173 252 60555645
139 836 471458625
639 165 592059494
519 416 778063900
445 172 670129163
856 445 683289917
527 674 890647895
879 824 961135810
319 992 665144432
213 547 702789822
351 53 211530960
487 776 351399456
605 776 667510445
818 415 52440747
201 961 928768676
359 527 820310739
602 139 389659596
998 399 562211555
188 903 57148480
118 319 169110757
64 857 936862890
897 607 563194397
7 841 206183458
474 315 289929973
413 48 192739314
811 528 176070252
914 452 189727224
35 402 994004782
854 642 300460474
756 413 931614115
453 157 758217582
247 165 140604744
420 606 283488400
569 415 245920122
743 681 606838702
784 949 968731524
161 111 921695016
592 148 865781113
324 157 760082007
673 562 441894310
884 641 396311892
443 172 977735282
855 811 556172949
91 415 403348830
924 202 788460451
611 345 612669025
164 818 494581918
295 139 763767126
726 449 397642047
790 5 509636477
589 673 42790630
758 605 572130411
883 569 549544000
230 91 991583457
524 783 842477254
422 720 835528739
469 747 670310346
421 406 427581943
290 188 919280735
222 855 145631932
306 758 695748628
268 230 321205841
633 172 762910629
999 978 947847309
98 818 626495714
293 960 734014391
434 895 210551565
680 836 846787811
798 64 135751099
512 98 182194443
806 784 798784101
902 136 995803313
261 134 273109486
598 895 685696993
825 295 273416323
732 895 702094314
666 667 823932502
840 598 732998457
175 856 762418096
168 173 686200331
772 949 434785073
750 469 639970554
716 811 131692890
193 91 959978428
199 512 327713972
198 255 497154472
226 139 252561514
751 315 987556397
881 999 232917897
338 935 307379247
301 871 761091791
62 902 264508028
228 139 298899005
770 252 769262705
514 575 476568880
990 749 55464409
827 12 257629468
435 883 70312283
401 327 956374679
976 290 209494218
582 939 997805518
805 565 983351373
511 742 980003917
685 228 329193614
709 399 174559480
701 201 207031503
54 524 809071089
321 261 261858713
744 401 901123349
2 161 551268176
778 514 41325294
458 902 144444481
292 157 919866467
66 487 305965906
704 172 362493106
28 778 242195725
604 359 620313524
930 226 159862783
462 749 703396985
404 602 90291936
718 268 79214171
845 154 602352318
546 172 157910427
121 122 298274186
991 295 156191278
256 406 992920116
944 367 793314013
951 858 193140144
4 592 800271919
52 641 750632345
125 367 590390278
796 401 356990095
535 468 659830793
531 301 275843067
207 122 877049068
242 154 71127507
488 306 993002295
779 696 591356953
366 750 947673378
386 589 35527490
491 312 758920541
862 314 415251942
150 681 456848492
932 366 166289380
861 350 833229497
481 666 54090707
56 168 132167666
500 546 650328200
3 386 299928728
284 306 31620022
713 228 234139404
801 198 808549680
509 199 89728928
129 786 151445787
817 4 183033747
24 511 172345303
833 836 520277177
441 186 364068615
973 401 965043149
832 928 244981119
113 402 352663177
307 944 915319100
476 531 197231271
588 744 456104798
135 269 978511552
867 157 116650007
768 213 762772266
391 625 120691806
917 776 690335737
581 439 997742042
880 913 391401985
915 443 665283236
780 449 257355881
647 562 419903450
948 569 380469628
816 123 407879243
538 825 508022900
455 24 922913976
337 832 225178897
220 611 153207465
584 56 303458253
236 230 857890482
691 607 194931744
554 7 255044231
860 113 291865330
640 314 612566060
505 54 296962207
431 884 946831030
682 581 806576525
280 845 249419825
996 228 135004428
461 391 815375435
357 639 972168318
51 701 698546315
383 113 487863795
159 766 558889870
104 611 235287471
326 996 727505886
847 433 524239861
285 758 215569823
740 891 98151295
372 24 695802730
211 718 787416318
450 383 69732579
42 680 359610670
394 701 653188283
107 157 6738991
71 42 112651457
974 453 140572440
457 930 468026500
25 825 199494496
21 883 202651478
385 790 998716879
370 74 619989240
769 554 329822011
349 796 376340521
75 841 173006490
597 867 121411325
821 913 793122716
405 349 741092605
536 716 502197601
571 911 490500706
814 770 417750470
475 193 121393238
181 814 860262312
634 481 424410785
644 642 673436585
849 110 202399956
361 306 916693829
328 420 687465218
206 123 628099140
683 858 332144937
39 122 525716095
18 602 396477523
451 181 283111632
741 495 948817060
364 79 443374963
555 709 124657006
237 495 343916628
448 811 884345881
37 807 468685843
677 701 585018972
45 611 272852308
288 633 336067734
558 546 137171866
723 581 280417444
672 978 93559083
430 801 110230049
67 644 782456190
579 91 495488715
358 935 981032000
145 79 48099979
739 25 360478980
517 861 184163769
520 453 290884559
240 476 882565315
529 45 297535782
542 285 23194779
331 89 396599713
371 448 999579382
627 451 439250914
479 495 415511258
389 935 673456392
530 776 471260562
221 751 766460735
971 915 188057427
567 256 58999899
46 682 824271610
224 113 346744799
274 538 379109541
787 256 724965723
44 928 734492579
993 255 601742186
839 820 296636183
977 67 807249053
573 75 436967827
124 999 272654616
330 811 362455000
717 475 733317932
6 597 688235655
17 821 858750054
664 743 371337170
33 683 477566230
504 255 406303304
566 439 628928593
411 845 840205466
544 536 83241830
675 221 465951255
447 717 928316706
619 37 658994768
190 879 759243286
947 295 794279608
767 28 939661148
492 110 951313770
119 198 642656055
16 579 678394231
835 129 276697291
59 389 174736137
785 218 927816768
909 668 873220718
661 447 332626288
232 971 788853285
174 915 780540846
686 359 979416844
354 751 451366538
829 161 380770817
904 514 783943147
574 971 396244535
265 973 129100981
369 458 819696941
70 750 535038073
398 538 230560300
251 150 667648492
465 488 480081464
738 740 562421352
774 784 728644754
761 3 842239583
99 123 164225690
526 744 113822820
556 136 410313308
865 66 611750134
830 779 403915256
187 668 566219137
243 274 905604871
485 581 408295571
355 228 644921118
69 644 865346462
419 862 497017161
238 193 337815283
585 206 297972801
687 79 223952449
660 392 208552351
162 402 160611189
731 829 155022788
375 139 197243734
630 204 535273721
953 369 283355065
551 173 534820942
506 462 188756696
794 641 413592667
710 881 725061757
299 358 895229285
85 206 997325451
837 806 772336637
810 315 657252007
192 581 52906676
1000 199 330462033
775 439 104768447
205 402 748200438
133 774 630317359
962 867 176713297
163 228 906225196
941 4 985376439
170 883 298223371
287 314 680182219
874 566 803538548
689 716 564869901
638 85 406442753
802 971 287318876
516 419 393530304
429 857 593688452
339 430 409055250
478 504 537892052
595 747 591891180
950 62 919383451
40 562 84317352
692 181 798385165
471 495 48661252
940 324 991300278
580 836 808768696
87 107 222221512
20 733 688287070
850 581 27334217
380 475 275454130
912 604 601880092
352 303 372095335
612 641 260302039
432 358 211219503
156 814 889258324
464 214 625786770
748 148 92638982
160 535 43770964
502 790 859419256
534 630 787364007
576 692 939396893
210 769 105658006
969 881 679981007
684 545 235480113
843 165 202317345
196 411 121140443
93 887 393085641
572 104 485351146
549 760 143970082
651 324 33980119
294 495 535959086
626 505 246621839
444 430 270794788
115 232 491435661
715 295 992173637
132 89 60715419
94 639 458475447
670 174 214260974
586 350 110567848
800 401 769941643
100 288 937157083
859 691 355298307
938 635 172158318
870 252 687176533
460 268 525248035
283 858 888240910
153 391 707693449
746 843 986017523
34 854 322151677
363 452 723986175
494 950 812206195
986 327 501676601
896 150 559219570
281 315 207947365
831 251 964867811
931 122 803295309
482 1000 371251655
649 435 557429094
15 375 111227215
203 948 737589229
96 210 584645175
890 883 805054087
493 123 433979488
77 89 344117276
499 580 683026795
729 148 198624752
813 218 912761544
892 255 100286136
276 96 34467838
353 491 996593887
498 364 798542689
557 339 304908471
137 584 490317749
532 111 901036489
102 962 692432484
396 718 785527548
910 940 172348640
336 883 288953000
654 367 291276882
376 609 104468497
970 51 432794705
617 509 156486905
55 974 409599628
927 54 97717716
577 89 256803604
959 716 290825988
734 647 741852472
197 805 227946592
537 761 84490529
601 672 14956675
791 396 738655656
552 640 96089254
304 86 118910234
762 124 821381127
80 917 72308471
141 673 44481084
258 769 888341077
459 351 601840615
231 962 616282203
313 385 229508234
690 129 930480855
943 584 152800428
257 585 868279346
853 385 610826304
553 833 993037640
559 204 190360048
518 145 210069936
8 618 512260310
548 836 740238798
851 572 222211652
622 404 22299921
872 684 594566203
143 359 465490460
937 218 602883102
933 129 410470664
497 831 373420599
956 402 544848164
65 268 345060796
863 86 458458197
322 434 838289598
215 931 369273949
621 953 769593662
608 962 206077514
984 843 46771048
95 894 867273926
41 837 175955042
823 284 853200199
809 452 949543323
263 500 180843237
377 664 9236146
755 775 326494905
423 52 765608108
706 935 959539040
864 720 474809410
719 743 949515705
979 843 490035484
120 569 116950219
679 181 915693534
503 228 25113362
428 845 355380515
920 659 589897909
49 396 686430748
967 865 643854837
395 931 348075929
989 712 27703927
570 712 668188631
78 274 83138861
918 597 720820171
36 751 128002313
792 619 479697665
533 802 360437839
777 89 313170870
489 391 56815077
334 597 196366006
180 129 472047840
438 287 686462330
329 562 806183810
10 912 643069775
988 35 636782155
387 569 935182027
648 369 920437827
246 439 975432217
194 474 416436830
208 86 890233093
763 462 133584933
477 895 849995041
271 802 715690772
200 70 801257082
81 4 910937690
277 488 723846996
343 979 635350618
650 93 748122686
106 443 237937859
470 299 968110998
472 79 666753494
264 77 185340267
82 89 858213837
523 917 379661559
958 277 627148774
563 589 718094306
877 447 218622713
109 87 504279212
583 755 367898120
737 839 473408994
591 277 768124747
789 642 359786769
407 948 243669208
561 625 836858436
144 3 324704955
614 52 673240777
309 459 617566642
88 123 984012873
955 303 805110475
61 551 782822890
19 491 206721729
149 370 209891221
388 35 13466370
127 472 660928706
68 180 619493255
390 230 375182972
60 237 41641989
773 220 443259611
225 461 27252633
624 746 323088418
209 960 204784249
83 236 517025303
362 684 759793216
400 203 9700925
278 87 685007691
908 847 407247114
418 274 169586182
724 133 281473558
707 330 942143377
427 666 461307609
286 644 464082450
541 567 107341315
316 595 626974925
945 59 152112988
623 306 401211050
539 188 628455944
942 940 394182294
901 468 568678831
957 40 252077806
848 870 127097343
31 221 813673628
711 583 260847512
636 111 571333491
946 352 547412221
262 119 774125631
130 817 291063658
356 607 439439661
29 211 788674144
954 707 597564823
131 979 944713877
282 334 131167180
929 780 472528813
700 542 447482638
964 989 382251398
501 441 579106136
702 264 177212099
486 556 179922613
184 276 171190563
889 959 157003896
564 683 617340063
272 479 295598104
669 689 867315894
379 918 841560250
446 680 497815349
234 612 930705605
952 988 660425318
658 62 342338465
217 946 880576854
466 582 40956217
826 932 196294673
155 687 236926956
297 592 329347852
888 200 82554968
697 535 395048677
515 210 556913194
975 607 813132440
409 175 218775841
216 911 656689334
138 731 143558566
603 324 962217433
815 407 279836286
291 792 856287873
484 211 683047190
730 139 239423480
982 825 594205416
966 351 685758441
803 372 174081953
101 500 670240672
38 585 674085271
600 592 162908099
171 59 463778865
596 224 894635828
72 580 245783937
253 306 93089310
332 42 591138730
568 738 731794623
846 481 216813319
178 716 193562844
305 75 629412994
934 455 758131137
414 33 665037659
757 452 553831216
550 433 671335980
397 314 733324442
923 196 827459393
248 668 747948459
76 155 214604071
302 606 565701432
239 76 77469046
360 483 199978919
629 100 931858733
587 783 766284576
191 636 908483112
177 4 422248329
852 56 656747060
275 982 41199281
873 453 375585869
103 61 483507392
410 401 918455886
32 363 191725032
631 314 968901444
781 830 587612844
426 734 825592536
463 570 155672353
13 375 993647422
73 879 233923622
753 277 268775622
663 255 539957942
578 908 649847901
227 755 292805340
610 115 527782489
179 827 532712233
92 851 11539344
182 880 390816767
147 947 100544222
223 7 137223827
799 600 97258922
671 205 478286867
260 272 77365301
229 163 913073344
819 518 970499408
921 927 589885638
735 962 500932210
765 4 113604720
384 134 344646930
905 41 492387242
373 133 435569677
838 887 899387225
510 570 930109052
454 35 638806815
637 748 541830348
620 772 52037826
828 192 974843395
771 756 963008640
235 561 137214746
657 258 349780698
456 94 408478150
320 422 730645982
381 841 101208653
656 320 957543132
254 843 786141048
58 213 982405483
665 446 532080786
725 839 122405774
662 494 48291656
926 726 55306637
513 799 523713198
176 56 771553037
335 697 608762284
645 413 656529985
90 377 510646409
594 945 805564728
84 459 588895742
11 301 135413070
745 861 832511715
869 953 107501825
844 717 567335109
995 203 695298532
140 204 63265396
994 684 199405315
632 947 587963861
30 7 498802920
893 622 606710352
346 546 644933557
9 638 719962971
195 250 479113704
97 369 499277337
158 498 977143223
128 560 697939038
378 272 959374281
249 651 491203758
655 396 781107670
714 541 772220928
440 969 80776428
876 545 776018895
521 38 949667053
698 432 114475199
885 462 297566819
900 806 191396334
117 565 212911871
245 545 330004653
340 973 607002239
868 825 365896218
219 202 957190859
368 262 352200533
244 409 518222268
63 725 626842315
344 277 406168450
169 642 313218909
793 304 867652777
342 326 210413635
424 719 832841799
490 538 484909850
341 95 666893209
722 930 151004709
318 378 389266417
108 420 93405288
442 92 678908733
393 860 626455628
507 70 90656004
233 59 978744816
834 743 688358522
906 295 209030455
241 755 464997386
142 969 486855076
842 117 211672569
643 20 490502941
676 512 363853786
467 370 865491834
898 640 413229061
678 634 505959808
296 649 656866219
57 694 744324289
907 351 988636133
496 518 406483599
965 271 808226127
795 394 276612488
968 943 775844890
298 862 331594696
981 631 538161212
797 549 430999742
615 841 164789928
699 136 312262519
1 924 894652531
653 793 652124773
27 526 628880143
543 377 463640300
289 694 337976606
22 196 361747619
311 943 298329289
417 78 83846097
325 651 3017215
270 268 925494658
593 271 778940272
146 499 391190802
436 341 243266349
878 236 853349197
613 518 539202030
936 229 655352114
972 758 724318930
695 816 303135302
167 406 667105673
997 650 904211800
646 316 311618331
540 122 159625722
782 490 780414071
185 1000 433418667
983 260 844440273
899 646 896725359
764 574 600205403
473 278 97961542
348 381 218053774
43 503 786814552
652 407 746398773
754 227 329653333
50 880 807599728
403 932 859029639
333 742 614305991
882 21 447016808
23 556 246412518
752 429 53569408
310 327 137874359
919 71 688586785
374 337 658259356
866 463 172809001
425 213 795123202
705 388 410225290
788 215 230820554
728 517 547023590
273 457 208353294
822 213 208504838
616 452 383141033
708 561 301694844
987 376 401330985
759 675 189842512
736 902 626723835
166 579 762169743
985 871 667640912
152 239 283143689
804 345 946253209
812 442 271311217
480 958 615672961
925 617 938406626
875 598 491704101
916 683 400517939
628 4 462457352
522 513 892528342
408 947 142395823
693 432 632840453
323 161 997080079
308 443 640745082
508 274 401574948
26 269 290661522
126 187 743311687
886 201 118831280
922 151 469107812
317 779 856103428
382 227 514107073
525 661 784831541
721 914 882544973
266 250 310311240
105 770 631012124
412 542 208488773
212 37 739856279
980 605 793907634