1000
678 270 896331130
568 270 205971581
147 678 311565755
152 147 723058916
451 678 284307402
616 147 927946050
563 270 140522074
225 563 93099252
621 270 962042551
853 225 224299552
582 853 580378544
175 147 591300166
335 678 119737915
890 678 952886060
340 853 517970560
413 225 287435364
803 175 152024015
461 568 616779869
533 270 264113469
787 451 299413905
513 147 296751587
217 563 899445925
984 890 18809620
532 568 574344479
363 451 732096854
673 413 221849631
867 984 962793350
947 451 987105118
296 532 652432238
596 787 910726634
12 673 235518803
715 175 452779382
1 621 296514385
35 890 921390621
789 715 590691852
932 596 630567133
347 363 296021455
948 621 381974425
466 867 25023058
574 466 67278441
316 152 639351221
708 316 253710936
473 789 583302645
257 35 990538988
877 296 877784498
575 563 37086311
889 621 209727105
751 787 688134046
860 347 621684911
61 1 925888929
723 867 756986520
70 984 846053177
871 568 282948263
13 860 165436639
905 61 37227930
859 451 277901236
829 789 742601561
569 12 335469471
6 877 189135370
392 152 929280361
763 947 413693441
58 35 206261962
960 889 122552236
426 61 252919688
262 596 818772710
497 13 670158357
539 497 128663109
965 787 810304491
158 413 602964020
170 497 386279895
667 932 709937698
622 569 311529814
937 667 838357955
605 965 181022544
699 871 460261036
823 699 419959253
966 715 695011823
51 363 811239816
404 678 821899874
374 363 31221879
322 363 21100850
898 860 974517178
856 262 738339934
319 960 270463643
649 322 473563365
256 225 636763370
90 296 450917394
915 621 437513987
691 322 408239588
227 823 432174006
377 582 463581786
110 932 188413973
967 569 764988137
694 984 187472085
506 823 106710831
235 532 604896453
957 789 793645601
73 867 56911598
480 340 102061268
731 363 773801938
996 225 625324006
505 497 809702838
441 426 673500054
878 621 601458498
471 61 217863760
339 678 531870316
472 890 162708025
650 90 475086136
958 889 345877125
185 235 890742009
698 532 677422375
975 339 616406573
299 878 803758466
368 673 51658310
291 889 345499491
71 582 980359665
721 152 663244700
538 175 288479346
706 915 24008183
171 158 963579869
625 650 778318294
72 984 755756274
490 533 502429280
914 787 588953062
612 533 963853953
876 856 179945017
415 616 390617691
64 170 272868776
665 257 50063298
642 616 550795413
1000 984 996578064
545 505 131623712
245 225 146865579
847 110 528463486
439 960 719131616
630 235 30020164
74 256 982968588
442 152 957257136
640 582 83322731
861 147 100382163
998 975 981865644
266 35 623429220
704 622 639001934
410 319 19859946
512 723 819012026
866 856 446249523
909 965 460376469
735 706 540457472
740 270 721151522
767 563 713083560
659 171 176650650
469 876 887314118
369 1000 793020554
749 473 553088601
478 751 796739104
929 339 785558686
101 612 296616857
848 861 342441090
757 185 862968275
726 110 568030712
144 630 942909206
555 569 607133867
2 937 120851509
102 257 838140014
826 596 264351875
160 319 982750498
518 640 536389539
666 876 440992686
212 866 737911546
952 58 810323030
907 185 225444404
98 70 502035062
636 898 655975827
389 473 922312441
96 363 481368047
651 853 61962917
730 929 585697376
638 947 43109692
589 937 320815245
117 71 302086580
489 102 448229061
542 569 120330538
137 322 496124882
84 513 194586319
75 721 437350459
550 74 125998190
875 616 9023112
874 442 16802008
884 622 104832599
521 937 221166863
777 706 461476366
974 875 604447623
220 589 901227090
758 539 392218596
384 35 148736027
609 227 895238562
807 147 587019618
773 853 907955532
540 605 659554518
941 171 7409971
978 555 963971800
345 871 353608974
618 235 144786346
311 6 174870677
869 144 527048723
976 638 239119399
338 518 131088550
940 480 630784116
83 12 941917286
792 338 749354669
11 345 373172506
93 335 84750075
935 392 145672958
361 158 489864317
519 497 77974276
435 93 882131354
886 678 640642256
479 582 562024085
222 1000 171888180
945 71 630807937
597 616 654159491
202 51 360775585
926 773 548071087
995 6 706076221
393 369 768082111
520 147 604528853
150 338 745570877
294 984 348778624
115 848 553106514
644 102 14502329
873 890 467850723
261 220 668753349
953 665 245889436
561 965 185358526
496 461 950392766
186 823 407399121
430 1000 642034820
371 807 129479859
690 497 879796513
782 496 952640500
470 338 54450671
972 649 690801827
599 497 510256346
969 575 951388499
9 787 170816870
701 340 13569816
548 721 505848891
692 856 176526769
320 171 760341762
15 70 592948123
631 929 957929280
300 909 941522585
118 616 471992582
459 430 130585716
933 1000 781697772
492 889 848640475
500 905 289016478
391 599 397462631
163 659 691101487
652 740 349230331
818 926 148298663
695 466 377140542
123 782 567521590
934 340 900429389
343 296 234725465
488 170 163203706
47 952 931612683
348 345 132530869
382 320 686924554
350 929 297667292
676 473 578882336
168 555 189067052
367 574 963030544
534 612 537781267
951 651 635588023
671 575 430289836
793 469 536657042
432 698 528733369
670 706 797843703
7 932 856418246
346 671 293973598
663 84 446110908
696 426 433690320
416 867 916524115
362 469 183770358
386 439 826588078
337 723 47641213
833 538 242872863
55 101 646180209
375 319 396514635
24 84 537152857
624 701 173938200
648 726 68130848
775 73 966972785
167 694 411592764
30 749 955402769
182 730 583689622
481 856 331245351
714 666 613160422
893 185 951224462
702 905 291588745
172 539 610736491
3 299 201048155
263 416 681310985
613 875 269618897
199 339 543383658
285 856 220077154
607 568 374751332
358 61 688628929
587 222 343743805
143 666 962777922
864 803 270187454
32 11 706790464
303 256 824514747
178 701 65003284
328 829 155327756
464 340 392877584
510 984 356783066
434 650 550396715
849 339 482982684
771 345 719142947
850 929 526920668
329 538 21163786
395 650 993547900
365 803 314987321
63 256 505694614
786 829 922471311
45 217 739992544
403 702 661095456
571 343 625405594
768 345 193794327
689 548 674752736
433 83 703170158
174 285 176358696
444 666 775706430
968 803 372838098
899 375 341586522
221 441 685078056
852 876 807802591
277 506 398203938
732 221 700172968
766 689 274394869
619 393 601977109
581 64 126320066
295 867 253898267
855 70 419574791
846 702 103610042
912 363 593455785
697 285 464407624
312 850 591168403
839 30 149251927
438 933 324408670
508 850 556698518
674 575 636435863
956 714 379069319
193 874 963892865
475 975 539473206
990 666 88376367
127 676 151667649
802 375 521469076
166 934 964937301
894 671 934850641
722 674 507644537
181 671 806742494
406 508 209006754
232 652 760862509
119 665 723348431
380 692 279589475
604 348 139728557
927 71 102974976
111 320 529597751
290 607 4459013
196 966 845019394
677 277 61811676
620 235 556478211
298 365 516973026
132 665 661008230
353 489 635674786
104 178 660162602
727 291 771894728
895 2 828978445
460 927 725209858
858 196 24444901
288 512 803190495
308 298 929525405
712 166 823359284
425 295 820976643
449 361 294662380
511 185 898811048
879 1000 324117846
882 721 880557581
756 642 273337652
306 947 274336751
269 506 576289456
65 695 721744459
114 533 30390937
584 521 652646961
963 571 382828061
634 874 435704552
297 932 680518482
419 638 198998749
203 869 801837648
711 697 692114196
22 958 280398896
537 7 576551303
617 7 126507422
40 978 84246117
788 294 460586496
429 667 666482490
332 438 625072524
815 701 675909436
824 75 383159465
971 960 61565774
177 648 154016942
603 667 654769806
195 163 825763243
838 374 504952610
293 886 202071256
868 659 217329918
498 569 15730552
254 329 961678598
276 489 803279495
50 694 285121318
994 793 524481123
920 631 703106321
39 382 448017927
592 644 302237380
600 969 746409160
231 118 113530618
924 621 746783475
522 858 730623932
463 174 555112859
333 691 599016675
431 563 255146119
97 143 131704508
428 369 914263767
448 395 344119028
517 929 415414206
641 332 59375286
710 698 77941119
570 500 763862102
675 634 641241177
188 335 622281414
483 582 175129088
615 426 996479063
779 63 191126321
130 945 206011491
31 123 872944876
629 622 827745256
608 634 468918151
902 13 37930131
66 369 275165935
526 871 257110307
760 350 643727147
549 130 41252678
399 641 474256070
892 93 212342
919 434 776895175
131 850 609045009
36 617 707850726
237 855 572368106
683 978 506951001
477 237 665789436
558 760 707953735
801 496 999091953
180 864 144586680
258 589 640781312
514 852 766647321
309 225 149856103
208 948 405408921
812 391 376391541
148 295 342283588
679 890 797667700
857 195 630089686
247 410 733097193
138 893 239220764
499 815 52533968
452 674 866540979
844 673 371350600
716 231 97209406
400 367 216097870
59 701 452252432
560 195 170731200
783 171 356797670
352 295 900602873
465 460 949823249
422 448 368208204
323 581 446684830
226 670 593760511
753 975 51110616
688 158 321273537
531 35 414303288
248 846 207930095
331 97 559071786
718 299 406905619
943 365 802230509
387 143 920778432
529 489 735070193
42 226 46584481
159 786 109678788
709 650 207022462
901 449 28988812
48 879 665392812
903 393 675809100
554 912 401428863
94 369 909859449
593 186 252423352
982 470 59358727
280 757 52950563
747 571 951405377
809 51 11927030
80 111 816730320
746 558 179987698
523 499 116453944
811 984 743688376
724 175 411815907
543 953 853779463
647 163 447433987
559 974 464473055
541 877 700272053
60 74 354522047
557 757 401758807
457 395 399413914
964 294 78025647
725 159 416885994
594 568 240282235
409 444 399012070
525 811 758774055
881 59 837523063
578 619 463778188
854 996 294119756
813 71 212026540
238 331 147409651
917 203 122717810
991 909 504680969
834 561 923353819
243 984 587440236
729 894 616218742
841 295 956763206
633 63 550511871
214 416 438251453
252 847 169740787
68 488 763277173
81 389 247406159
381 860 104648795
780 30 445435881
169 694 350247480
397 61 364867586
660 753 592684085
91 666 104107063
643 619 822452905
351 698 613897527
680 615 487617282
344 864 122874908
161 343 896871249
887 696 816130788
928 400 455446680
752 84 276808486
77 337 747979473
598 511 38285528
980 543 304613249
207 308 725127513
720 490 394633836
916 670 693178620
407 608 185050534
923 697 987490724
120 864 517060427
821 858 98299625
57 475 876739955
106 766 686588726
267 331 702249310
748 915 926634775
870 666 602076250
764 499 589238296
865 948 848822978
795 214 728333250
645 522 695663817
87 498 353646273
112 615 414361158
567 839 203208582
842 471 131190152
421 510 422737849
46 309 179257427
993 746 566208898
817 81 559442002
565 636 963596155
728 886 155072907
936 84 700823210
577 701 120670680
717 735 7395937
836 406 858349748
251 7 124938468
959 159 364499949
379 111 681682750
189 117 162464408
837 425 992066494
408 363 6888070
317 171 276263787
133 339 170456153
970 853 862131097
601 549 274235294
240 620 239496590
794 842 804217523
191 643 823211623
390 660 333985160
455 32 171084775
602 673 709758687
282 175 725042714
456 438 398814038
962 203 200816444
229 199 283545811
388 64 267387316
16 481 591407120
25 306 783933170
355 633 96279327
5 554 875617996
872 68 176324337
162 421 929217436
784 225 348620301
402 543 335083612
28 353 666089308
888 470 41951327
931 191 710602771
810 967 902391321
904 882 658193737
412 991 681633388
121 120 653670051
999 410 977554624
140 70 872847881
682 169 564517030
822 160 600166763
495 663 779347907
142 815 955840474
805 451 704267499
774 888 363841818
53 308 680604077
146 879 933248482
21 207 866347875
950 577 85073976
737 715 469406475
918 676 719628429
977 161 76516926
770 848 396639249
580 240 54388189
450 87 177312808
165 331 185373253
411 533 28011634
979 773 236939756
206 812 44923883
681 431 107244188
925 948 897982789
938 47 903263626
205 83 819499911
49 962 30319193
719 212 410481206
754 673 801510962
610 823 849269596
357 181 631987507
62 333 431443456
830 442 794026435
305 982 894781618
401 549 477712102
19 522 471525993
922 84 438853945
372 677 570042526
772 441 541853585
330 477 31467581
349 5 444852336
56 947 798847357
544 382 938773577
145 140 452216501
562 399 223487960
658 137 526470217
623 815 114725385
8 710 22483873
310 589 936487951
536 708 609402914
946 631 793490855
586 35 676589396
827 368 934864016
289 389 640920346
765 593 617405578
863 719 441849442
453 909 773295746
260 658 570091203
314 539 235135167
790 377 140612462
239 60 286080736
769 993 479689083
27 754 978075671
259 790 160919677
845 237 474336355
417 688 34079969
124 350 903918154
989 879 419190619
454 98 660160361
364 118 384167004
113 922 844780098
201 537 550293312
284 387 252477982
268 689 612006660
778 452 617995766
655 836 667210965
446 202 57915248
547 288 118938825
467 523 175087894
85 46 921037445
253 133 522025955
336 425 446500376
988 933 368074678
183 51 973310071
981 817 793206241
18 887 884212864
326 748 8583682
215 483 620386873
632 112 261206424
230 454 968936911
155 601 89518314
418 964 868433123
588 575 311775948
546 879 360425498
88 976 199894698
797 607 116912686
10 976 335486051
210 716 375450950
271 58 446110585
194 252 713354899
669 858 382381593
76 722 643060965
832 917 318523428
241 740 366344217
703 188 872711569
684 545 240907323
804 998 586208250
139 317 223326976
662 114 925379583
373 506 851406526
135 64 5561746
151 610 316777831
414 473 989786119
742 587 562875461
200 407 352318605
342 912 822791989
122 439 883911314
799 430 876536572
614 298 895588363
693 709 792663667
246 721 148773789
424 182 828189478
491 801 591854946
885 659 702334673
973 185 773762117
572 799 669435617
672 422 365890511
264 941 721944217
244 652 59085850
54 18 756850896
281 990 815721032
734 602 377419777
983 391 929241784
4 418 572086961
611 326 610278403
808 706 667936538
198 533 588360885
657 361 355029492
891 676 659077011
255 671 274578528
476 581 47837506
394 747 482299988
825 76 705735783
136 980 579231824
462 362 905143294
134 784 696328792
437 361 585977388
900 361 277316786
468 425 427067272
798 328 987620268
304 581 131492536
528 546 899759509
89 931 937354480
503 980 401039435
576 991 856263232
218 387 757913115
781 783 611219705
213 94 321255068
880 118 968818095
154 252 575748831
179 465 978696148
944 4 759387794
713 972 871571607
566 571 57740677
501 725 417398731
761 711 6951069
487 478 964422646
67 57 827874308
686 967 228609936
535 16 412342147
961 446 205502012
278 861 643118776
524 391 43006144
986 199 990745683
897 749 565211015
573 681 801915533
485 839 907017025
116 971 917996602
515 787 619290786
273 885 595429993
910 650 67315712
685 614 954610649
474 991 750009812
156 571 844799143
250 870 80393144
100 642 540526086
750 497 363388278
29 519 230019737
173 907 431523669
509 858 841683578
190 933 590174808
954 713 312006412
494 765 793550855
370 158 645293026
228 901 855394891
14 538 860950816
366 63 56042738
327 554 21839534
484 213 819517239
86 620 182783081
516 117 294904501
128 926 948066579
851 422 365043591
141 902 530530107
739 936 946968183
274 363 954342887
700 98 305127030
233 841 695693847
733 566 230880264
37 865 879401612
939 163 558872148
354 510 208867338
325 715 472487300
41 489 64049883
420 281 580597625
26 674 642748376
896 622 533821708
34 614 587489263
504 215 502361702
378 473 413536721
109 431 144949646
906 115 335874437
17 251 968823168
627 531 355974335
105 241 22855632
668 989 635242035
216 588 47953664
443 769 349929010
744 511 350340867
440 346 530596288
664 763 197809733
279 972 543988816
840 395 534680136
656 190 776150144
272 543 48695808
637 702 548937627
95 964 818929940
321 389 308410519
921 147 269396260
806 702 527867509
315 970 700377037
992 534 863508025
405 861 513168097
157 1000 371354345
755 162 802701050
556 143 865896806
126 91 310702662
831 159 176152072
78 237 128272262
275 957 572065022
527 62 512172644
79 947 88579342
52 193 396426068
814 297 614416114
265 781 9460010
209 86 461966787
20 546 18103993
493 848 263755191
313 586 636741822
628 537 593311127
82 434 506409443
646 338 190425158
743 860 78255529
223 71 829517122
507 87 872001768
224 220 957066565
942 322 986882669
639 770 724702074
302 508 400893148
234 931 561736102
334 798 594744102
595 935 227597053
458 542 259410316
820 826 181166391
552 834 990790577
949 399 498200917
283 575 531574376
862 417 712234619
249 600 16772664
436 45 1772341
69 845 99031254
318 552 715988088
762 613 896827575
292 82 612017673
583 19 777870451
654 351 756074707
653 929 931116275
819 97 500888070
211 456 971169135
423 638 90712754
324 588 844736378
192 209 384325502
626 714 155623046
591 352 256643776
741 380 736283472
738 948 283803306
359 575 489791459
23 550 193372276
383 406 37215635
92 63 465651173
800 443 258844139
164 758 962484624
43 826 278595388
796 346 246324091
187 786 530959923
930 619 359223424
301 809 215148634
103 877 18708369
125 25 644994628
396 600 860153600
445 986 440213426
38 130 417869661
835 496 946618100
149 535 813392750
590 834 940219744
911 479 829596612
108 753 756581067
606 425 978902281
564 651 841350563
356 488 472997252
376 377 228595419
791 884 842710831
307 297 690109444
908 414 994339518
987 291 642734645
828 476 261468732
759 844 796009857
33 546 741681729
427 659 666583274
286 986 401674649
585 59 526454181
736 762 508799417
553 430 470395909
579 911 900854449
745 722 933026346
153 69 541515088
341 948 476335042
635 779 147669584
44 74 219811852
99 977 871297489
776 381 50063187
360 121 14514969
398 292 7754208
129 477 334380845
707 188 996660420
486 361 671106348
184 761 268973488
551 544 286003969
913 858 719393203
705 127 30979129
385 503 916519094
785 52 884139883
843 446 390350105
997 720 529703414
236 906 135247352
816 409 151259186
883 53 718174211
985 468 484429794
176 51 870681272
242 476 965469137
287 29 600087312
687 605 607232026
197 463 237576007
482 908 451982535
530 142 282721172
955 366 702039253
502 755 884235586
107 200 429222236
447 267 489193661
204 518 332274694
219 191 55632547
661 501 978711404