1000 1000 500
192455 869682 465268 713794 634473 972831 901443 177878 770703 364382 590824 237024 179596 169328 42311 182059 926488 670529 651259 213861 783287 742611 472129 434842 718504 867866 938882 257751 614599 458662 63757 807279 489436 365076 586387 833361 330049 928493 433841 766736 810600 837893 982329 352370 244795 608253 647433 535209 264498 243650 15842 189101 812649 523852 474634 891201 854991 697920 780579 931545 340488 899526 483539 492194 252012 560835 840498 785530 540806 791393 210550 578980 971278 73194 620498 826277 790583 578160 418490 159450 924073 380009 967209 477504 370608 196075 722612 19762 56891 163684 716933 452742 954814 862397 460616 904600 136681 198033 387585 240518 6671 241883 249524 758106 621096 296917 678179 579059 577751 7730 81996 678677 753900 784566 93609 172244 929515 168056 191974 922749 651987 144447 577518 629917 874792 469913 146694 91816 949858 640053 236552 487227 162956 183395 180098 65066 513262 578079 878141 611948 445171 975490 750150 333866 214283 7433 896368 522883 810642 231188 705480 321539 351448 208647 276760 189423 666487 455029 614861 253778 348504 861432 82456 197107 752822 296282 21456 947125 318136 376775 859999 74254 922636 643889 153233 747681 926679 450802 961200 855364 716574 561246 473275 550354 181288 699111 643466 172530 981113 476382 247891 671806 372033 989321 165432 658294 206579 948207 171167 396698 20695 529789 109985 969979 617016 626685 168907 928098 118391 199786 486200 420711 271814 415086 318581 331268 387445 186508 360828 74432 152272 268694 885338 311605 677407 768023 413001 542538 38389 355290 647182 93585 987762 493218 501483 447666 753105 84096 525222 964782 872107 656344 593081 80869 411714 968252 216080 768041 531934 779664 259654 936096 365875 720836 680977 455726 71809 559157 602833 905441 375563 885963 80837 797203 508081 340077 58494 740547 474774 97881 335073 400708 955667 141589 481169 315397 225010 12137 455763 43743 21923 512249 18369 717715 650291 335760 169896 303641 979200 105792 661682 652754 33030 987043 253084 420815 718245 63230 652865 769471 5048 594488 326277 323541 679991 588711 271946 221471 183590 955979 779007 262136 487197 33089 935780 993791 962966 1106 807568 669135 671458 998546 597219 838845 372564 28265 801724 490605 601228 197693 771364 301364 721566 421446 610496 741023 812152 15056 393739 279883 608655 822708 245339 144291 339155 604624 225079 724982 330734 223595 130847 987446 805617 750490 338964 135698 209631 224909 737475 920373 293856 734562 56607 184076 382120 741433 684780 279284 667837 125119 737029 119578 737092 556796 60902 793433 136581 875908 184075 719791 476042 351330 290975 72592 189788 490240 893054 63682 903006 176480 695140 468999 83640 515622 993827 722839 828582 399979 891024 943835 243350 702708 502142 687347 891638 413401 816691 162936 126411 877383 260190 705875 663723 195567 360039 588812 245468 425868 189543 63548 502618 99024 226204 48052 570637 458968 456406 531963 819976 556532 495045 591804 388916 450320 272792 383134 775643 569301 954079 585258 333894 490104 750234 722272 611991 338642 258048 352659 479303 683991 2569 422896 135009 361743 194700 188179 42358 941848 469346 380914 964711 61386 73505 462704 102070 154530 552075 149731 244845 49119 65364 552774 470732 747512 869399 498104 352680 53044 522089 563835 850023 240912 492652 580478 616877 178221 615349 798180 635858 883663 902263 420771 22274 841687 888918 717893 698268 749066 389933 619082 3131 28632 589153 630173 864408 295429 681491 610178 71237 459644 840634 37894 630275 993783 203462 290663 307998 151424 890718 640704 566884 661660 245387 651766 601841 209498 283251 58422 175582 787272 288000 504980 138701 530462 118206 540829 459623 398761 98936 481615 567494 596162 746539 670539 476556 917372 760753 758434 255066 726402 34760 393549 273793 193934 137104 690212 694669 627499 989249 879648 149932 669876 598450 436600 123444 731155 861435 385968 816394 704867 953309 223685 792668 48470 930812 814091 427744 604600 474196 506159 589859 809890 447041 818365 975027 89504 66413 840571 676396 641987 651110 187084 85391 250687 755382 128503 277863 424566 872833 885429 646890 478884 925266 260046 778822 855521 927774 134252 675337 334002 737311 974591 356072 80936 145283 825719 573713 37999 905163 717693 539048 946104 231116 839859 829646 394200 645273 675863 72774 480239 897543 608204 277126 134402 78383 169737 478940 138722 426664 677576 724982 700962 862003 448096 684017 137508 993285 944260 821059 643669 677120 857042 891265 623916 72930 841716 615537 957760 700453 93242 829449 227799 224325 274134 885039 170863 629085 909879 923086 400025 193106 412766 767408 677785 704791 834892 621086 734191 542999 86019 621425 597377 254670 108928 493069 366103 438601 819319 290985 339557 808633 478815 787240 74021 827555 988442 798643 2322 104947 56510 833709 761534 686805 385143 842261 161621 343579 187114 63592 934416 656762 12412 959252 738371 124508 7585 951102 489959 441791 13413 855061 93473 402677 543374 266652 275529 532762 469504 729108 892452 953393 570520 472408 494506 440384 262410 607039 360472 171655 947515 523230 489767 887757 632471 739667 522284 160554 705092 259387 687630 42318 45357 388453 154467 833761 919632 738268 776099 314321 53008 469217 722843 7464 260948 793631 717044 376315 626118 334621 171793 964155 866694 664776 213 100552 476380 943878 789362 385273 434145 561564 504947 888309 157431 123465 74347 837982 318612 292592 832124 461992 461331 498370 291401 179118 317915 595442 936868 28454 909974 981504 569817 883368 385403 230158 681568 310867 687172 477246 764239 671048 115593 311658 405054 171581 740531 675321 790378 998587 604490 631745 388611 718920 259928 609120 479717 300397 853459 830594 806850 854273 160295 54334 146230 471429 559242 421689 366034 685271 329262 860209 982163 506879 979898 887539 469784 540796 266634 509558 317135 53136 258594 843694 466952 140095 937175 512098 551696 817493 292238 530614 296711 389629 809787 744841 182570 120394 292963 214528 807195 705714 11914 693665 203996 762382 946910 48769 624512 954236 127634 240863 127578 817341 142101 400559 476155 935431 831296 537624 922928 29212 211755 880254 293322 785529 443001 555672 270453 375632 640935 40987 834249 539766 796313 262053 731988 464558 248557 170451 182302 293100 332045 331076 4051 26067 738802 623844 441381 695919 659364 628330 88855 613980 569667 679578 837403 115293 723873 448324 153949 395198 508909 411994 665782 202611 828257 705966 23770 715254 805685 478146 840834 285901 968995 633886 348282 32257 910873 982902 306636 860472 527138 343769 233996 171604 942012 879035 512594 530162 234259 926907 191444 188228 719485 224094 435225 94583 867628 5147 686590 540238 850760 578957 677404 42301 811226 143596 16616 804007 368642 335699 325314 23313 618458 396340 86095 846044 522912 280456 358848 870991 873328 413455 896473 450242 641647 525214 824930 695404 594994