999 790071349 876905939 593248735 73691300 665048132 744704048 240289833 894343046 527165939 583646531 813004315 627205489 233501332 777893050 772305990 746171458 828058011 214446547 74501864 956120405 999852415 639738567 485877413 658126774 480047499 252432327 309779272 666725918 540723515 340624096 703640834 314180401 5475358 204512878 456554356 851975614 897878387 727063201 292601577 934253035 767049155 637126994 917271586 880990874 256083266 199287572 90534947 562974149 683382145 99475488 734628629 607718729 974252849 218635393 91411785 907934581 945831602 810532039 284806436 826840770 522967513 230835256 442081261 799807359 395086462 752858154 220460991 668606451 141354040 280211722 933253263 102888607 395222559 731264026 643755671 77914554 427136406 985043944 887835210 626676748 930608092 849254563 862824778 927156789 410197541 995320195 974294306 808770960 485846693 710227963 503228861 539260921 201149684 898756439 97546766 275820389 747858074 869347339 255301419 675550477 970904725 397696468 471148103 533843425 497254042 674525201 115886455 923731202 793869346 876835910 280257791 96674014 30903831 57308110 254064267 7474814 556104178 846355453 892894998 140069680 279405385 593612724 662717881 859788463 14067447 177465962 360960573 401680903 14472232 209988282 90737584 94142812 630866617 447959837 333461766 229166982 144088495 947673066 41142206 243095706 308814089 683907493 612486042 822555602 602649077 572699622 522102714 175352265 91521330 536720596 504934457 959935141 443221866 730319881 291565497 121499349 612789139 129717806 880285468 517968010 117354044 545783812 804244 474364388 824814137 515198816 654299467 559351319 556936213 255283517 399895657 325460549 440421396 921595108 483724907 841255539 414920608 228920689 414949953 118696174 632104117 498097418 748625664 235128673 461180413 199653033 67398688 542211941 528026198 867622558 234238442 490685971 283230006 99882693 54974171 329604265 285831622 966231460 596804534 278121433 911501865 209013488 174339880 45873872 910675729 383946162 297790031 731117450 674488331 398560186 342661872 700840966 320713548 912398060 491406133 585228079 596050273 532681424 163787720 182899286 606915857 337335951 13874891 197529331 27182677 112132683 311269957 164306837 164893846 857789140 3036843 944809076 813069700 149570019 171002070 436198743 805835175 643666543 481788719 823571471 331103242 312761314 315045893 138502867 119930845 947205739 73807718 46298282 771077975 726137349 130539159 823156132 540916016 136934856 814225903 673227126 149317774 848476650 460180032 294775165 632197081 79118382 125822042 291364088 694063352 782953845 58513895 209615168 821784629 257414579 808924415 454829066 270776842 227899465 347455501 553668060 903719280 511000602 462933304 91604151 432214592 120897651 183847774 216993006 584652760 452135161 108849768 211629194 831887754 727005573 415267341 860339278 380494312 682946043 258386425 59373399 518252395 221238850 690599537 753135391 255106433 692126702 431396239 429244772 411735602 385390709 560513346 581256626 455449682 902938043 898337055 824602941 82889395 692885661 145317598 332026255 161390430 412224909 409724744 56110406 273759575 731344028 522989212 219911593 578582307 247516017 521553139 304339823 334871136 538634825 460231034 80052447 369382112 800545984 612957846 517736936 981101380 86084993 104513340 188259291 37254667 607214948 34911942 354095245 117654321 69038323 885168559 886241909 975526642 875060278 42549951 120270460 530738256 571688945 82705143 827529020 949817494 159372337 763549580 585518748 103459051 111459582 843077855 827621994 343073694 684898376 828714704 512997161 137742751 241771165 349296412 104849097 561868652 310482512 737368124 353953836 412599146 451136874 930620203 585988678 387940915 441735570 31836466 238144069 289378637 360035577 674363124 70697975 746914992 356068108 552492862 20542285 702853643 960596225 83109116 625146803 407671288 944867516 590798677 92119972 97237316 182613803 324878856 128182578 61669338 308182772 253402623 100521404 241257127 663296558 217534057 286570609 567811172 854668286 32462353 65750093 255781477 759003641 40465577 113059500 742244816 320285976 70508647 579741492 998022836 542319377 621310891 498714484 662318891 946027977 48462556 175339599 600044684 919095781 44894037 488406961 355263586 124837960 177161893 578732148 308016937 818248179 424638911 840942559 303721534 141705044 94660520 165887859 979300119 404232440 295193318 41603948 443663629 259336210 113340209 984856630 990005530 847482711 25083439 756729860 875340872 470824346 388859184 634421778 15746276 771491350 467554931 919958796 595815921 606725429 905877462 858041969 160756146 828623250 95006005 89533757 96677637 633557305 595079541 951045726 59349080 813879535 49558906 242170262 520505941 257236405 531875769 83745577 778303638 163367141 47496234 813954430 179075028 765153795 632372200 316350798 459765577 327345528 249151498 121411251 445990409 203264248 638463798 236285441 332712669 259978606 561334000 182162899 514757534 699760826 690637768 554908010 255710174 669601342 804540404 228392390 770354062 317801232 182799870 618906512 105313231 904523779 598437046 608565637 826647525 852094331 893834533 723029202 640036151 165113786 114559707 343314249 291456797 682744789 115035286 197205003 761751557 791281210 124032586 863638772 701685535 213415612 872151623 655768208 645678469 254343701 327710582 555957190 840673756 59468034 84566399 411372945 443825669 775085808 70167306 35770839 238052505 817997134 44520239 66186625 195888807 424891161 343708869 743583979 307577452 680465080 541630535 823230921 821532245 444908532 628592670 927821387 123474271 990991235 835815524 822694982 799358803 819296984 867904387 104708569 505515430 669197620 615048288 994231661 713829516 944222404 52649803 770621249 195376535 686889767 268726523 666237639 45716230 979563432 167155511 168363150 92779113 558219066 777978141 631448536 368898842 263718673 138313547 523103631 263068299 125980290 314574600 402173792 883611061 871641045 90072412 516827015 148154335 362502151 142743698 318065097 706303805 944313840 583056970 182114790 462355444 969492855 548485073 111884751 212094451 911603959 517264879 889353081 994815184 551739353 128039471 467217242 776745522 271411851 766473894 639414849 391846109 5682747 569451961 75981848 785894555 271454384 789238427 307598432 489018085 145674257 523096711 631801888 820508612 338421102 49517805 210261777 984881139 709530736 821587165 874698258 8499588 738003128 28094037 810199303 963052823 188940 35652429 62401940 682002295 42667228 601686812 320472429 822256495 237294612 895858319 946035660 410425179 77884860 527249292 848249991 856828264 88536059 181997464 583916979 204566689 131830406 172805550 803526810 800940107 495658902 915133425 865739976 94424586 987616124 633888551 847974192 36773854 148396865 118099562 659458099 924209505 396380176 219083059 584111131 543372210 209187357 850075580 351337174 62694828 10229615 854553871 818452673 540293705 822431761 398574785 709015434 563465010 781145203 224890872 634008131 370878957 966834472 538891503 20817526 740593703 541578443 149681491 773283798 608800552 753872467 980947727 789939840 441435818 447965292 224807359 554700412 752678713 105984530 776414764 165957741 706509030 116687731 348112358 655772318 676882535 611522444 122386207 151454483 747568333 687230344 133444599 547865542 646507142 33392535 405371639 870690796 646686995 522433123 859040806 156471391 336608881 677287056 594760914 12715454 307339096 789989527 738748497 884784947 904734585 134974157 534632907 412019718 690598415 954558939 903055711 741663722 230517746 184165985 210083387 388423906 86191714 599233386 620314854 730089229 560336465 798918832 487493326 580817191 422868804 561515843 122683043 243511247 731356205 308208896 359238650 593511555 870308455 315840115 510141422 106773444 622320207 664416409 915946796 951879628 267521517 230871693 240431320 130821813 645464736 248435389 182505362 363792863 875717189 121396030 814907076 295064382 613541807 838342354 129309374 497577713 580594047 55128214 391601714 964126097 218812107 226127318 349640401 407488163 770538162 181651859 850408079 925055854 112894786 599086313 127470617 227171075 938932734 241483463 568624973 739286721 939249780 453646506 341436686 811266669 641484448 807827688 547161795 175822075 334115571 527741321 574537625 354701060 826536509 807327688 500598100 900698226 744892714 696210873 636775927 36662287 794592569 476962123 112156892 781281823 152921023 240975687 927210836 508057080 994402658 641578834 282059237 976002366 774559717 538932611 490146677 16857048 83282782 722568950 182440756 573359674 883413 488280188 443552152 195673775 854570716 66895597 207199336 905082168 489061062 361371191 770365073 269117454 617195181 999877836 514497764 199634472 205610171 875740634 746819936 120589811 281768628 847309039 671795856 775751460 132980499 760920482 962556008 990556725 920591833 586710499 633231341 786093092 735170834 155728052 69484068 970909287 160132055 587497582 9267009 761537397 173711640 15501365 190735873 618356828 515694283 475708709 451911181 728608313 759180536 839292546 746598518 114580130 511036511 175886381 914899388 281578830 371722100 652084656 137652247 422567641 612410334 5716234 912295416 898816398 973699290 217777329 67052273 725422195 123587296 267471050 431360065 263758523 733045447 863907512 159012003 749614451 713408354 914993556 785993639 911323690 964635076 65311241 783851375 34376712 639507571 909437384 237082959 222252870 311222515 225556647 942054386 472872591 426561842 508322343 575329328 64956595 5406306 848286673 705745093 566107414 625208715 580169185 553423000 399523611 530772225 997772453 434550999 47056510 803613326 205139719 202981137 830777106 812852607 473579408 689099938 906027279 234678594 170889698 189698873 110942462 753187950 983565997 39178989 10 575 10 214 10 566 575 27 10 908 10 105 214 969 27 428 969 71 214 543 10 803 71 54 969 592 803 317 54 306 27 718 54 871 969 955 10 88 718 229 718 824 803 442 803 943 575 883 306 121 718 665 824 180 575 837 428 95 54 68 229 690 180 961 575 801 442 637 883 100 10 556 88 136 88 131 306 24 566 102 543 66 68 186 883 509 68 404 229 771 100 433 136 984 433 250 871 352 180 271 433 832 229 336 24 110 88 820 433 691 131 337 908 296 575 283 68 834 803 115 115 721 691 347 592 338 115 133 121 872 296 790 543 603 71 290 509 953 338 828 543 243 543 468 908 619 428 233 306 166 872 16 296 611 801 833 872 90 352 403 955 532 871 571 115 973 969 997 95 287 566 995 133 783 186 354 592 494 306 978 133 829 131 822 229 362 290 711 592 252 833 739 619 671 637 547 711 424 822 802 336 913 803 713 337 847 955 38 690 108 828 999 433 937 713 2 428 875 100 728 871 272 166 91 424 579 579 507 592 519 38 971 803 740 243 434 713 294 579 101 973 816 166 455 2 866 713 221 455 555 995 775 71 30 637 156 718 96 337 310 790 152 16 219 403 297 519 415 547 712 575 620 27 521 995 635 221 825 740 84 971 288 338 766 272 704 999 140 833 612 740 884 766 160 721 885 66 645 160 625 66 129 294 774 645 7 140 371 362 738 543 616 690 958 108 587 625 474 219 458 2 67 728 887 102 572 133 500 30 826 136 776 68 843 214 301 774 132 834 811 999 373 997 321 297 348 620 945 95 518 287 193 521 929 140 991 571 230 121 341 984 800 283 75 887 437 984 312 186 52 115 191 341 470 433 699 233 675 221 757 875 76 52 6 415 563 822 652 587 567 129 32 131 114 611 438 52 537 100 905 38 870 27 259 824 311 665 59 537 674 371 501 509 286 543 222 290 476 348 758 352 204 438 634 563 85 790 159 476 426 159 942 191 77 84 251 336 696 635 94 219 475 100 203 872 413 775 418 825 450 428 702 283 794 929 861 85 305 518 898 803 358 88 69 500 744 88 868 532 613 875 680 68 444 203 278 272 60 95 660 272 73 2 401 942 760 219 388 129 926 160 86 620 207 129 725 955 234 725 239 898 762 358 383 866 643 674 970 476 819 861 62 468 586 521 194 740 604 744 33 133 628 833 220 32 402 868 578 362 40 362 200 843 878 783 763 52 478 822 623 878 773 84 998 794 985 969 681 776 707 90 946 509 447 758 391 702 240 2 280 362 135 383 697 428 727 945 889 91 414 660 242 760 789 108 679 803 851 509 540 697 53 240 792 800 781 613 429 240 907 781 646 478 416 186 659 643 147 242 11 872 916 942 372 824 544 711 248 283 569 60 685 579 880 438 602 91 877 681 151 868 57 794 895 403 940 604 581 108 495 73 143 337 841 68 821 725 8 718 512 474 663 721 174 191 257 348 323 883 64 821 724 16 573 563 787 288 784 802 497 675 264 660 439 916 202 204 928 352 123 744 807 945 688 294 387 940 733 712 683 348 398 995 595 403 593 604 303 100 597 794 26 725 261 875 906 671 526 998 747 913 489 219 925 928 511 191 192 474 754 286 106 889 35 819 710 747 742 415 346 160 982 271 617 681 187 754 951 398 183 573 723 696 277 738 538 592 705 221 585 792 975 115 729 602 334 239 655 675 741 136 983 438 79 108 967 707 621 758 768 771 546 621 340 207 919 476 386 581 909 690 750 33 523 800 422 428 339 742 627 297 589 280 686 371 157 194 374 725 667 820 224 470 701 433 677 422 481 183 838 643 726 79 127 428 253 114 576 321 119 991 798 337 492 754 638 625 380 729 164 760 848 67 245 843 753 68 577 301 5 164 846 5 382 760 769 753 720 221 748 790 365 613 583 838 483 183 624 67 47 704 82 627 682 623 654 848 772 792 594 478 279 38 499 725 852 73 960 887 232 501 608 152 503 136 298 287 21 885 467 474 210 391 644 340 788 680 448 437 256 110 330 495 717 252 319 984 376 492 722 191 479 877 806 729 749 337 324 685 453 511 751 852 181 983 120 671 703 280 548 889 125 634 28 398 981 52 395 33 761 317 238 587 171 761 356 10 195 925 692 751 570 340 390 418 81 67 484 774 609 96 393 766 457 680 385 769 695 286 322 794 92 433 227 478 941 79 335 123 461 33 235 468 669 301 939 76 270 433 425 2 293 183 255 699 80 40 15 106 116 422 397 663 34 608 810 24 853 283 150 951 309 467 20 663 184 385 31 929 879 202 228 579 672 24 780 909 50 362 662 951 817 192 513 820 764 461 213 186 111 705 29 159 104 758 454 847 793 194 650 509 799 356 797 28 498 294 209 157 779 479 661 509 304 742 12 8 606 194 41 832 545 573 596 286 258 125 745 35 124 96 463 725 359 495 223 30 262 940 411 463 281 442 580 928 155 713 22 34 419 800 524 183 176 180 607 298 400 28 719 586 381 928 956 186 900 573 161 422 3 512 618 973 559 209 770 458 231 518 529 975 647 544 17 429 375 85 954 383 514 467 420 682 791 181 932 926 487 157 901 733 165 848 175 372 874 822 888 356 285 733 316 729 469 616 831 738 860 594 83 618 508 577 436 679 56 874 582 94 460 83 506 860 384 261 562 702 795 183 58 729 535 476 268 728 471 811 948 956 449 321 46 995 432 787 217 852 349 204 830 192 406 17 25 387 44 768 275 8 850 747 1 984 446 96 864 718 935 28 49 322 601 753 109 984 976 24 364 248 805 494 867 165 477 334 308 783 561 463 737 983 666 193 148 885 778 695 145 400 394 81 641 880 355 11 466 230 493 749 48 585 363 641 332 578 664 10 344 12 366 967 138 105 320 192 502 985 534 335 812 871 491 336 178 183 327 874 950 279 343 382 936 298 421 729 452 227 630 297 89 832 61 586 326 769 98 223 598 233 141 883 873 44 631 797 325 774 185 644 198 234 636 198 342 981 292 750 212 30 933 571 541 848 923 219 315 98 263 114 986 52 302 807 430 76 827 29 823 875 153 5 584 790 746 44 993 681 357 180 274 429 786 148 735 358 924 129 588 191 134 851 445 404 412 776 911 985 45 907 782 82 218 580 378 699 549 702 857 105 882 696 211 823 267 764 254 449 485 926 574 218 818 997 930 252 13 460 201 634 947 476 599 493 756 311 653 559 409 556 962 631 968 923 858 857 473 930 269 81 456 183 510 802 876 975 65 895 629 433 318 306 167 535 897 526 99 8 554 793 869 775 266 77 435 811 78 12 144 939 715 679 126 134 130 925 74 770 215 102 520 748 291 790 241 283 63 602 246 174 640 1 777 61 614 174 987 619 216 500 854 380 979 166 360 471 670 848 14 719 93 895 72 380 989 78 694 544 112 563 408 580 551 973 952 82 863 791 972 508 4 823 142 983 517 592 206 712 996 178 938 880 431 321 23 762 289 74 244 645 480 20 804 707 462 380 965 468 558 390 188 971 949 74 39 833 533 420 396 339 542 998 632 116 170 239 814 33 459 780 353 132 836 879 369 185 539 320 199 738 809 751 709 574 944 683 894 185 605 324 247 144 51 254 190 95 552 819 676 288 963 455 550 93 974 315 610 434 482 681 649 192 668 140 531 798 37 291 527 611 700 519 920 397 736 161 902 768 917 188 815 572 351 83 698 141 865 885 651 951 988 355 189 680 915 115 118 674 488 935 642 562 249 814 591 877 284 478 350 120 516 629 276 111 590 351 389 982 451 171 55 596 399 403 149 230 427 1 903 665 994 967 957 290 314 675 881 246 964 936 313 155 862 82 18 180 87 897 407 357 464 799 196 21 808 874 162 552 236 143 732 540 169 846 465 777 42 161 839 911 743 936 914 513 177 155 765 450 525 268 639 250 208 127 553 274 910 463 472 45 966 531 560 869 859 727 536 100 440 142 226 88 43 941 886 477 922 647 918 888 168 979 530 843 70 472 648 889 368 125 856 436 992 963 977 897 626 199 282 823 849 58 706 699 122 820 237 366 921 64 893 84 36 492 496 40 813 994 328 416 329 915 568 518 179 977 785 630 931 12 379 609 844 800 146 17 657 264 367 424 693 750 912 586 486 629 19 854 490 598 687 131 522 902 331 567 154 993 980 555 345 82 137 877 405 572 392 792 678 911 205 650 300 151 892 111 443 170 410 793 842 250 716 245 734 770 9 817 730 707 714 164 182 23 759 609 139 939 835 704 899 62 990 915 855 407 633 284 441 80 97 262 361 532 934 14 504 657 840 405 225 938 103 141 890 735 689 376 767 37 684 503 377 821 113 536 896 410 173 560 845 607 307 979 158 68 752 231 265 508 557 569 622 8 417 245 273 974 796 298 295 112 423 412 117 334 658 37 128 307 163 971 891 5 959 270 615 314 904 865 673 776 197 957 260 825 370 610 528 210 299 651 755 314 505 728 172 725 731 30 107 833 600 989 564 742 708 239 565 757 515 699 333 174 656 359 927