215 432 795887943 670001098 242155937 81062183 144 188179256 993992449 838054435 613086508 270583318 34 454754675 -1 11 280690667 391102363 556 68093116 361421364 816872695 231401159 932611793 236229513 329 498 937385093 177017039 20125390 54723614 93282954 432 267 948127215 212505301 762866431 628772869 716432033 498327150 673466602 287 254091185 504209596 970062456 469 236229513 254091185 376 236229513 954103169 640257700 723551462 301101064 445796727 409 914247224 647 832 204 309746518 520808770 94411085 477086746 954103169 347155090 192939551 27992190 638 560456543 799158428 464289454 710290423 156764 470045024 899959027 457215301 398584008 239 336751640 738115841 106932205 512 818405241 898 746 983456086 274974844 774565069 98073919 752470678 398584008 279664671 84475147 236229513 121 212612975 27992190 517422940 562596936 269985850 563428748 269 630 463 972514823 355039913 145941098 91208198 710108943 177017039 124549126 618298540 873087829 242155937 21263601 825958247 392850273 178934187 339 813178718 178934187 807949290 943056984 789473416 635 479006197 30 116647042 37895355 455 200 393256312 463472330 269083857 166057448 612484774 206054045 493576353 -1 271011833 742044103 4 517422940 576377966 565 841425041 966358951 862281989 124415720 666 921154357 101265212 732929057 967468092 174767359 612484774 913 943056984 235518089 495 398584008 624 319572321 272792024 78859502 725310670 742044103 9965165 84521425 106932205 41904208 832566170 927467800 384248590 788 384678538 63 259347596 474538470 8813051 527 868201351 410364233 76887994 780369952 219957318 270583318 409454013 961 429436449 732038509 772 173195557 675041776 415 601085021 895123768 116647042 791881390 489837102 280483850 704 927 798 291638371 825958247 170962622 927467800 279480133 715073642 276 683506145 309 435 250136885 654439786 982190248 384339361 239 809475291 923742125 818405241 584 10 30247738 493576353 427124378 886934838 651 167540046 287 468168409 854 759518315 622 613 28635126 996542074 127 656326405 350 650326726 527507141 873900773 170962622 644768132 342185429 841425041 764096728 995573041 901332937 537780009 231412948 180019963 145941098 428 599484641 538 813178718 95 952175062 772335588 225318291 308431084 489231836 525 80418266 429436449 153599292 945471160 20125390 227052116 923742125 411736794 794667434 637150199 677644631 194562916 26754255 597532459 378154747 885617968 774773656 950 612484774 187928226 554 849294793 586 86567488 863734093 673282909 779364609 336822513 974 227052116 196994946 68469980 832566170 702 509 494 100373969 256860909 709968046 517422940 607179645 215438568 310905896 566138605 320 624301926 161571478 955 604978051 262918725 774773656 873900773 767171602 305326269 873900773 310905896 215438568 538 120882525 799459255 625 720876584 587821314 495 587633677 537180003 130600813 279480133 849294793 993992449 453021299 967468092 342185429 208115388 169272946 271 732038509 779349988 254091185 849064100 258183223 781958720 964665256 695617531 118125217 248292386 80998348 972514823 352 335303255 563359293 819 215362606 71287988 688865271 629344246 914768354 509911814 643835833 832566170 486026824 899959027 69984825 692312576 645727331 599484641 65132084 729156523 430840670 781958720 818405241 274853174 88251046 465385250 789894369 720876584 630 816872695 642 587 108494849 985523575 280 321518363 11 143500123 921154357 402 709 208115388 187282466 150411702 931687951 664745814 650 758 937385093 84708556 402560617 370415433 441 29 340 110561899 82 86868526 124549126 548 533 743946854 150 323655646 809475291 510192994 826 873900773 852 393218410 928229728 18 546075498 471611905 170962622 749597500 149893081 637150199 499368958 337 613706907 682 613706907 971779741 234 109 241 577 323655646 80418266 535 234533156 754087296 411806530 7285952 605616025 365871502 799 860806653 813178718 375927789 316 510192994 587633677 615551819 646 675041776 63064402 567432934 941794856 670001098 817 666573288 272792024 458 680232134 913715131 457882206 478 597532459 419 866 2591083 584474774 695617531 41904208 -1 27992190 612792481 879021283 838054435 160678923 624990630 215362606 775809585 290432813 519 6620902 243345425 721958784 11295424 476787818 163024964 523742857 945471160 147375074 209769922 548045151 417 9965165 473653705 575033536 195 542 68093116 412973000 710108943 329920251 923 879021283 987130097 69614183 155731220 211137295 321518363 392467605 351984045 817 664745814 219 546075498 512533542 846410693 122256557 681582058 797149661 989 645779254 513025460 209769922 631496855 801 939907162 881 417141792 69 166057448 182333045 738077433 487736353 760 374605067 246 115917228 357 760303484 121 187257798 700476452 15 37301769 767171602 934 433290682 355087736 859 552724692 430865747 613 584790396 623 274853174 242099507 443471521 321518363 511 867017453 384678538 33 901332937 156764 524 323655646 615 154 867017453 809475291 468 403 531442354 401341976 405 551 102990494 584474774 135565213 554658412 448 607720488 112066211 592566788 341 91 314 732 938496097 712335838 24059943 342518623 650326726 32 713041886 692312576 854745611 203725867 670001098 793826951 978 668 8692268 296 173803659 212 615551819 95023636 659245009 838054435 284 757370606 372 912 680695712 950757313 4 724345037 9200261 625701809 136391292 417287838 886934838 710108943 607179645 327 370347248 448 236 80998348 473653705 78859502 565 111760960 256305753 126963422 637150199 759518315 191 805704091 23 243 634938630 734266402 823518565 575033536 732929057 140631476 500094404 972514823 296 584474774 272792024 98971813 964665256 47434338 369264804 170962622 568 567282677 250136885 916943464 310905896 419247204 976380303 856 930690244 714 294207194 797149661 254 285475432 640257700 357735711 565 581955618 681582058 259347596 161426036 65 957 294 816 318353561 715 318353561 9200261 21263601 77732266 247279147 786 390232483 79 864 505604507 235 162088232 274853174 438981204 654439786 304566371 723551462 176 763 280483850 27992190 889 215362606 76887994 612484774 567972641 393256312 476787818 46410727 833 789157270 21716059 954 224207218 748779499 737076138 903 550 890237000 84708556 252153132 940965261 140631476 232553236 205018974 791881390 872174286 868201351 487736353 951966857 336822513 700560202 726 283283198 120882525 801594169 601085021 920440338 952865008 829 624 832566170 885617968 66842524 567816714 93282954 883394947 189721383 658 153733117 718129899 499316672 240 263 273 738115841 465385250 335303255 439 743946854 408619248 567282677 325019009 461634197 869329021 170962622 38526569 100742911 419 242099507 31 567972641 883394947 562596936 393 323655646 356982167 300666789 749717630 746213531 958834567 437719154 321518363 153733117 904461495 614149143 828896080 271011833 930690244 643 141 538096002 80 477830025 238308414 842041675 405127266 984629297 385 -1 605616025 291638371 203725867 20125390 605288864 78944071 305326269 709968046 424 408187156 80418266 135565213 304566371 934 446145948 543930181 546075498 720876584 455 32021993 305326269 219 427380314 561873263 185030419 832566170 887859867 920 692 474538470 713041886 729156523 976380303 616 30247738 588023548 177017039 101265212 867495149 657153133 854745611 116647042 629344246 24059943 684444395 988872191 727725878 105 941794856 727725878 203725867 209769922 857630218 794 795 799158428 537525569 355732561 689523292 657153133 714506326 534477464 943056984 889076216 78 958834567 618849633 208606010 270 584790396 980 644712801 435345309 374 476601142 429436449 836 35616762 832191033 117 873 43 606252818 46 674 984 384339361 269083857 311294439 997837191 687851530 115 -1 679974875 811333453 565866719 972295874 315 535 39 142141502 796550976 497 243621556 839 725310670 205018974 832191033 579 102860860 477830025 468168409 653010341 772335588 690619816 351984045 582 282692654 7537862 319 847 202 800923723 419247204 833 450 71287988 47434338 298 252153132 289690023 562 409 849064100 603706365 344303507 147331218 421884304 895 378154747 157 1861620 795398160 793126210 154 7537862 10545 656389084 666633123 393495221 421 105297890 638 890237000 342827008 198621884 785025451 457215301 629344246 356473154 575268466 206054045 215362606 752470678 760657421 342185429 501255084 557613887 972514823 567432934 609213723 694 832566170 492205882 537016815 297901069 754334092 624189998 462590682 600479810 402080873 47434338 888462586 761 852 198035066 265307442 527507141 521674165 64044003 192 206088997 198986228 436414064 163024964 993992449 69984825 297 598640728 137 679974875 540130780 723551462 306 607179645 37 795398160 84475147 788150883 461634197 285475432 940965261 832191033 351 417287838 149893081 199 805049067 466 384339361 112187572 332 372999620 616 486026824 33903462 607807067 295 552724692 207 849 212612975 761 76887994 796550976 470045024 754891992 378154747 599523332 96443153 989754188 967468092 300 105297890 754 895086985 294696626 967468092 21110038 177 24 717909925 719639741 369424280 692312576 795887943 290432813 237 357735711 574 310905896 664745814 742044103 289690023 644768132 496 33053098 612792481 382765550 692312576 906763981 410364233 38442167 734448264 780 805049067 989754188 278 937385093 503 356 734362113 356534892 626 378126062 497565877 375496397 928229728 854745611 69614183 688542728 557019352 691 303 462 634883913 501 751791188 92 94406529 59 878366736 553736420 159 2591083 553736420 825958247 520808770 880098006 9200261 612484774 141 69614183 338 333081593 96443153 717 102990494 548045151 794 599484641 440028642 402 739730662 901332937 922062638 437719154 147219198 149893081 309746518 609213723 773 84475147 105297890 679974875 487736353 594 635 131 402560617 565677864 235518089 817690053 624189998 985523575 536 124415720 919693970 961 895123768 294207194 461634197 361421364 268 677644631 242 596942770 874 264 497565877 481095768 552724692 952 474538470 346128706 78859502 427380314 684734627 828896080 927467800 470045024 294696626 360648201 567282677 895086985 791881390 657153133 347589470 590 605616025 417141792 280947786 714 432653384 234 42 463 173803659 66842524 762866431 552 696538826 705014348 819242395 548045151 457215301 371803472 587633677 845 863734093 145941098 996448486 819242395 914768354 11295424 363 412973000 163024964 86868526 880098006 490 116647042 163024964 542927779 745196112 860760417 54826492 13 639435507 198621884 592566788 457882206 926 540359278 718129899 807949290 982 356534892 554 258183223 589075597 697029907 269 206121309 705014348 174767359 277 920440338 825 69984825 338837126 94406529 177 725845416 39048172 21110038 228 832191033 108494849 629344246 979 648669542 887859867 567282677 727761698 360151898 905 725 569197642 922550791 920440338 231288389 721 105 128 489231836 664 700560202 363 360584203 849294793 294696626 904461495 697351024 684734627 304566371 719639741 316 831 945 556167411 360151898 697 125 599738581 832566170 811333453 872174286 930690244 828105104 393495221 130188717 718129899 182333045 551238034 404 540359278 618298540 967 187 101265212 331824546 242099507 259347596 54826492 842 922062638 108 698 754334092 363567713 76887994 329920251 505604507 81062183 243 815 940965261 732038509 15558196 979 997837191 340 729156523 978164011 39919329 408619248 686541684 140631476 640 551238034 175261027 347589470 470045024 236929594 38442167 907301325 77732266 263198329 559397285 441955509 173 8813051 430865747 645199066 687851530 775809585 489671699 624189998 933507092 820462779 673282909 112 253516569 185940227 321518363 79599416 108430558 551238034 435345309 861956207 772698388 974 336751640 42 360 506 371185370 683110217 737507051 506 324 861 296356322 294207194 571 689523292 325 841 976380303 883394947 969676773 551592960 383443224 112187572 871435007 219 98971813 203725867 20683010 963 33 356534892 767171602 891 839 479661466 197 183 880 81 363290231 217 253 686541684 954 779349988 165 235151274 9965165 475757272 392850273 717909925 718129899 663879567 951966857 645199066 853772148 935152487 731 465385250 560196332 566138605 799158428 509911814 796550976 211137295 499316672 637150199 627105627 182333045 872174286 873462667 842041675 180348334 969485187 70 486026824 185030419 183259116 402005161 787 152585716 612484774 198986228 577007952 873 7846637 738077433 952865008 625701809 329 486026824 122256557 680695712 185940227 310905896 527507141 406 592 997837191 775809585 9 738 741658807 584790396 310136979 54723614 520808770 402080873 875236313 105 224487240 28929767 738115841 982714779 744 368704676 674 360584203 43591040 883394947 673 268 752470678 735249489 577007952 561 120882525 255 328 471966566 219957318 90621422 996506222 542514996 551592960 867495149 562 666573288 846 823518565 206 626 971 183908093 157 188179256 779364609 879 762341708 890165630 996448486 268 374605067 375869002 384678538 307414947 289690023 173803659 291638371 479006197 183908093 632544208 380075508 259347596 789476776 673 410364233 633034791 937701908 9200261 590 594280111 553 537525569 873462667 664 365871502 764096728 510140564 370857163 475757272 943008950 43591040 283 260 422666120 587633677 310905896 852 727725878 182333045 412973000 717909925 907301325 530 158 560456543 600479810 225318291 656389084 11295424 466 754334092 269985850 149 741 278901824 434396593 330 63064402 809475291 943008950 820462779 151 276900387 848181926 712 131 93282954 561873263 88198072 247395365 529679406 688 311554006 166 224207218 432 555644669 325432259 982 8813051 664745814 300643186 59098079 794667434 134 142610325 581 838054435 371 860760417 670001098 889076216 528 427380314 599523332 583928003 300666789 65132084 273 605616025 105297890 71287988 355732561 571812901 712 565677864 733 777 412973000 470611082 93282954 645727331 205018974 634883913 738115841 849064100 659245009 789476776 291638371 557014053 132 357735711 196994946 708 26754255 100373969 417141792 20125390 308431084 263198329 296356322 885 760303484 624990630 914967290 370857163 460 392850273 565866719 948127215 112187572 187342644 921154357 291638371 342827008 527507141 653010341 441224254 828 457882206 374937360 279877374 409454013 519 760303484 95023636 64044003 575268466 88251046 248292386 505977928 809475291 368 331 368704676 86 945471160 903226349 475757272 247279147 923 935152487 945471160 901 715073642 735205243 297901069 785 589075597 208115388 561873263 231288389 209721596 372999620 554658412 84708556 878366736 978 417 679974875 600479810 898102333 845 961 999889600 933 160678923 818 246 219957318 749597500 347155090 344303507 904461495 615551819 468168409 65111958 935152487 989754188 205018974 20125390 859 438981204 952272551 505977928 372676097 762946187 361421364 700476452 281676935 559397285 832566170 801260973 547 493 263628924 931687951 256860909 142384508 301101064 793126210 732038509 125 730496353 754334092 183908093 975 734713993 631496855 402005161 88205199 793826951 142384508 91995194 531442354 68 794 265307442 451 48819428 15558196 8 459 183259116 8692268 604978051 982190248 13841380 665229761 567816714 206088997 919693970 964 921154357 708 33 41904208 331824546 300666789 181 690 789473416 565677864 325910984 130600813 9200261 279480133 473653705 796550976 906763981 115917228 38 24059943 776 847 234 807949290 738115841 901 153 7537862 89 254 135 157487018 112 305326269 402005161 219957318 956632420 997837191 988872191 865 407566380 567816714 471 887032969 506 130188717 947 180019963 823 88198072 263198329 326 122651017 981 346128706 242155937 444 985085442 338837126 719 510140564 187928226 520808770 976684614 605288864 901332937 745196112 775 861169280 645779254 537525569 845 567 155731220 109 774565069 801594169 542927779 949 438981204 287460887 838054435 888462586 542514996 289690023 993992449 913715131 108494849 114 632544208 605616025 801260973 116 279480133 235 451 213 231288389 218373067 371803472 118125217 185940227 641372285 79599416 547 695 564159615 587821314 860760417 716432033 789157270 26754255 664745814 50 405127266 538096002 725 861956207 122256557 215362606 716225287 564159615 958834567 819242395 112066211 102 33903462 300643186 496 289 604 645199066 84708556 160678923 202 547193379 904461495 259347596 890 457882206 409454013 167540046 513025460 868488629 285475432 687851530 563 474538470 386 13841380 885 281 613522780 780369952 943056984 310905896 192 486026824 32021993 192939551 978164011 821712677 463 300666789 410364233 216 679974875 767171602 7 182 880098006 601085021 441224254 47173681 718636351 227052116 907950446 114 640257700 133845054 2591083 244208872 721 1488804 872 280947786 570 937385093 875596010 907301325 441224254 69984825 688865271 832191033 680 862281989 569 24059943 556 384678538 740 446 931 33903462 567282677 484 692312576 290432813 683364021 482199719 208606010 449 710290423 122651017 559397285 65111958 411806530 123 664 365871502 883394947 849294793 604978051 749597500 253516569 50548018 465423715 34 883 -1 417 473304340 764096728 665229761 372999620 920 374323399 520808770 333 746 789473416 740738219 659216109 105297890 961692520 187 112 363290231 475757272 331824546 619 454 746 69 631496855 88 873 270583318 599523332 509 203725867 318353561 734266402 166415923 848 670001098 151 414057053 581 48819428 198986228 78944071 916624283 183259116 867495149 513025460 243621556 86567488 374937360 417141792 850 719 142392058 284 451 21716059 809475291 398584008 819242395 943056984 506119814 153733117 659216109 453021299 772698388 982190248 734266402 422666120 199 477337284 774773656 693 954103169 890165630 948127215 714506326 493576353 895086985 557019352 78944071 930 386 205018974 374738151 27 145941098 181011230 480 750470605 687851530 972514823 599484641 18 94411085 50548018 861956207 408187156 659245009 978164011 268 513025460 461 299357940 539 136248093 190323346 86868526 325432259 384678538 495 637150199 212612975 563428748 776 384678538 475757272 319 806 63064402 374605067 374605067 182333045 954103169 475 173958780 190323346 745196112 657 680 903226349 879021283 14 885617968 487736353 857 238 542514996 37895355 690619816 101265212 155731220 828896080 848181926 10 679974875 658 919693970 449762261 95023636 100373969 976 382765550 901 692312576 724 909 48086638 28929767 582 379021826 306 654439786 738115841 785 117633124 457908107 122651017 31 31562571 190513116 751791188 713 180348334 175261027 486 791881390 729320492 868488629 24596432 842041675 558900214 236229513 231412948 110561899 94094977 90621422 489671699 610 345 419247204 807949290 55 59098079 695617531 943056984 799158428 754087296 574 995573041 285475432 961692520 587 310136979 933507092 203725867 490 310 253516569 612501617 869195525 933507092 177017039 635 913 486026824 601 405 714506326 60 381 622014449 972514823 291638371 319572321 502516676 411806530 538096002 182333045 271 30247738 657153133 796 360584203 936 5403924 789157270 945471160 169272946 319572321 325536833 139 91995194 128 299357940 13841380 190896064 307650057 61 482145421 734266402 862281989 297 371209335 735205243 671 253 612792481 456905914 115917228 438 670 730496353 65 624990630 932611793 801594169 958834567 935152487 250136885 308431084 370686813 363567713 949 478 94 737507051 170962622 529679406 884 681582058 375927789 738077433 242155937 86567488 368704676 701056542 537780009 479661466 265347784 212612975 158 203 265347784 898 787 365871502 634938630 899959027 895123768 98073919 760657421 357735711 149893081 2591083 219951578 563359293 520808770 559397285 177017039 746213531 641372285 231412948 588 842041675 72 543930181 809684001 735161947 928229728 157435453 503 913242550 842041675 964665256 679974875 537525569 117633124 390232483 329920251 -1 930 964665256 497041626 563428748 607720488 821 411806530 274853174 624 269083857 235 153599292 695617531 157435453 408619248 452 242897422 363567713 849 368382661 325 147219198 78859502 500094404 158 227052116 267 794667434 729320492 842041675 818405241 931687951 46410727 873462667 791 454754675 807949290 864 737654628 610 473304340 458 634938630 10 336822513 579 813178718 355732561 457908107 979963115 823518565 35616762 962 368382661 860806653 875236313 208606010 760303484 383443224 209721596 48218162 181 811333453 551238034 347155090 634883913 54 799 593084528 164 923742125 310136979 54723614 897354169 789157270 19 931687951 474538470 922550791 936 509911814 724345037 853772148 89073464 450 342185429 873462667 756418971 124 941 180348334 64 899959027 606984444 906 161571478 683 537016815 500 922062638 962 861956207 789894369 136391292 789 118125217 331824546 301101064 477086746 190323346 237 849 589075597 449762261 901400271 88198072 219951578 657153133 958 739730662 231412948 279 346128706 807949290 159 724345037 842041675 256860909 194 614149143 24596432 160678923 178934187 786 854745611 368382661 848 24596432 363567713 115 26754255 94411085 793126210 826 41582470 371209335 540359278 421884304 88198072 607807067 67003584 265 405127266 150411702 860 128309313 196 575033536 791881390 170962622 231401159 591 366256794 764096728 120882525 866816759 429 41 443471521 390232483 290432813 102990494 535335054 145941098 729320492 625701809 506119814 482199719 627105627 996542074 468662786 175057436 77732266 382 370347248 825958247 629 206133076 407 388 461634197 391102363 -1 688542728 913715131 846 732 238308414 915 215438568 640257700 738 979963115 512533542 564159615 279 698 290432813 69 572 846410693 657 437719154 517422940 781958720 283283198 451 108430558 399 155731220 227052116 914768354 476787818 939458768 748529163 817074075 791881390 483 713041886 700476452 687851530 445796727 150 140 865 136391292 371209335 247279147 607807067 841 554 611 120 881 9965165 323 278901824 6620902 263 263628924 287460887 263 280947786 817690053 976380303 774565069 590730703 91995194 467322083 392049320 294207194 468168409 215362606 198986228 922062638 176 454671349 21716059 488355649 671 667 130188717 449762261 323655646 372999620 309746518 737076138 598640728 624301926 5 889 206121309 781958720 785025451 117633124 529 495893906 122651017 208606010 473304340 760303484 775809585 967468092 793126210 656326405 196994946 374114531 940965261 427124378 697 270583318 524 446145948 397 789473416 325910984 122651017 605288864 640257700 169272946 180019963 480 398584008 443471521 199 79 124549126 106932205 982190248 63064402 83 355039913 370686813 725310670 929 203725867 689523292 250 534477464 190513116 480737544 564159615 289690023 325910984 751865562 967468092 355039913 650326726 136391292 29387516 205018974 17 196994946 119 257003592 215362606 954 331824546 179 901400271 645199066 952535151 452 939907162 490 949 33903462 492205882 937385093 142 39048172 331824546 296 645779254 499232662 401 259 622 242155937 596942770 599738581 128309313 856 157487018 343 799459255 751865562 457908107 211137295 510192994 48 785025451 438 259347596 242099507 485631084 819 492205882 160678923 499368958 941 757578230 774773656 750470605 613086508 943056984 983456086 804816501 634938630 540130780 895086985 290 949 760303484 774773656 142392058 761 906763981 457215301 571812901 242155937 219957318 599738581 355039913 937 688542728 342185429 140631476 328 408187156 486026824 952535151 785025451 355087736 177017039 434479191 746213531 116647042 556167411 185030419 607720488 571 505604507 429436449 956632420 762946187 986365957 691 261 948127215 842 889076216 739730662 967468092 989754188 624301926 78859502 701056542 98073919 34 219951578 76887994 800923723 287082385 356982167 608 772335588 -1 147375074 39048172 488355649 907301325 253516569 825958247 505604507 251 126 155731220 645779254 795 933507092 150 235151274 557014053 701056542 19232251 454671349 633034791 348 106932205 173803659 603706365 156764 297 140 392049320 185 69 95023636 577007952 68 970 311294439 43318401 529679406 81062183 146 434 48086638 907950446 633034791 735161947 899959027 311294439 570 232553236 136248093 8550863 873462667 11295424 979578913 613522780 200 774565069 401341976 280 719 271011833 774773656 811 374738151 914967290 767171602 366256794 133 261 718129899 844 567432934 845 860760417 916624283 41582470 6999164 194562916 535335054 607 774773656 685446819 732038509 409 226772138 828105104 713196042 633 318353561 28 265 472892556 300643186 985 531442354 988872191 986365957 809684001 564 247 931687951 922550791 12741541 606252818 430974086 897354169 231412948 867495149 543930181 243 541035280 214 150411702 339999570 654439786 681 378126062 392049320 597532459 362 735161947 301101064 889076216 493576353 106932205 534 666633123 263628924 799158428 754030551 837 677644631 46410727 114 419 540425911 307650057 50 740738219 238308414 923742125 694 527507141 69614183 708001977 525 427380314 417141792 356534892 695617531 841425041 537780009 919693970 883 402560617 140631476 840 724345037 400752854 185940227 982190248 133845054 80998348 618 861956207 259347596 663879567 126963422 64044003 95 925 181011230 454754675 890237000 273109631 218502949 618298540 866816759 828896080 416 296356322 152 537 374323399 33903462 901332937 683110217 375 289690023 375927789 639 816 723551462 29387516 296356322 612484774 318 407566380 823518565 605491815 754030551 930674943 618 914 212612975 979 142384508 562 115917228 629344246 313868888 261 941794856 574 356982167 666633123 759518315 641372285 725845416 477830025 692312576 384678538 20683010 91 12741541 499232662 369264804 24059943 613522780 697029907 652114327 215438568 716432033 48677072 552724692 390232483 842041675 259347596 599738581 329920251 187342644 838054435 613086508 645727331 952175062 8550863 47434338 814 468168409 13841380 67 979 819242395 287 719639741 427124378 575268466 732929057 421 252 479 485631084 218373067 106932205 472892556 799459255 738115841 676 510140564 895 244208872 813178718 436414064 13841380 936 885617968 489837102 224207218 615551819 701056542 574 139 739730662 256860909 126963422 699212976 8813051 50 599 308431084 673466602 296356322 904461495 961692520 443471521 338837126 724345037 563428748 263198329 182333045 794667434 548045151 914967290 253516569 461634197 846 279 190323346 310136979 501255084 457215301 881 427380314 280483850 374605067 577 951197672 185030419 928229728 88198072 818405241 861 335303255 880098006 688865271 380075508 435345309 759518315 776 307414947 585 128 712335838 895086985 257003592 838 471 832 465385250 259347596 80418266 149893081 509911814 103 411736794 596942770 860 170 780369952 461634197 200 620 380075508 580 263198329 560 631 984629297 63 347 279664671 187928226 453 434479191 738115841 184 479006197 142 544 851 344303507 327 33903462 366256794 230 434396593 347589470 444 360151898 92 534477464 76887994 651 552724692 644712801 203725867 675431728 29 772698388 719639741 961 46410727 305326269 632 789 890 683110217 735161947 648669542 867495149 746213531 615551819 273109631 670001098 754334092 760657421 286 920440338 189 737507051 254091185 333143333 130600813 21166510 999889600 392049320 939907162 788150883 48 576377966 562596936 796550976 729320492 208009449 596942770 391102363 178934187 356473154 748529163 490 692312576 590730703 259 1454227 215362606 629344246 795398160 473653705 368382661 531442354 98 115 392850273 985523575 490259472 575268466 753 262918725 767171602 294207194 489671699 771 292 751791188 972295874 499443963 361421364 434579431 935152487 166415923 597532459 864 644712801 639522229 179980555 565677864 905561198 563428748 573 676 842 427380314 461634197 489231836 584790396 305326269 681582058 873900773 273109631 716432033 893 411736794 412973000 828105104 215113193 614149143 938 476601142 450 265347784 709 885617968 238308414 414057053 599523332 453021299 370857163 325432259 979963115 1454227 713041886 88198072 72 670001098 21716059 15558196 289690023 354 198035066 272792024 378154747 897354169 673466602 878 263198329 20125390 684734627 883394947 950757313 821 762341708 526 54045945 1861620 492205882 149893081 540 131 875306288 868 170962622 497041626 108494849 683364021 841 142392058 752470678 68 226772138 612792481 701056542 652902050 729156523 809684001 972514823 923742125 212505301 138 513025460 767171602 679 206121309 601085021 854745611 135565213 775809585 881 914967290 750272869 69614183 77732266 866816759 116647042 228 625701809 665 521674165 369424280 875236313 276900387 350 460 756882312 547193379 23 887032969 618849633 861956207 656389084 629344246 122 813178718 393256312 457908107 564 497 283283198 999889600 907631891 8813051 716225287 102860860 51932307 381 801 891 392850273 811333453 756418971 749597500 412 140631476 760657421 818405241 208009449 772335588 663879567 252153132 643 890 599738581 325910984 177017039 885617968 384248590 680695712 443471521 445 289 64044003 473653705 517422940 557014053 883394947 336822513 828896080 707046643 40 327 203725867 898102333 641372285 274853174 782395438 686541684 363290231 167 792 976380303 930674943 348 325555210 311294439 680 988 356982167 375496397 366256794 287082385 206088997 372999620 422666120 6620902 635 490259472 198986228 596942770 522 523742857 958834567 645779254 192939551 681582058 737654628 718636351 867495149 656389084 950757313 725845416 888462586 304566371 66842524 918 575268466 180019963 193 898 916943464 618298540 360648201 723551462 932 489671699 94406529 883394947 68093116 288 907631891 677644631 916943464 265 457882206 54 677 780369952 631496855 889076216 612484774 375496397 567 433290682 989754188 226772138 15558196 11295424 39523837 542514996 86567488 916943464 558900214 666633123 913715131 191 509911814 407566380 295 335303255 283283198 589 644768132 371185370 279936610 79599416 227052116 177017039 78859502 270583318 587633677 140631476 928229728 700476452 256305753 780 392049320 431879635 774565069 913242550 354 54 59 688542728 869 457215301 160678923 663879567 39919329 708001977 256860909 591 575268466 336 670001098 705014348 754 986365957 495893906 592 370857163 258183223 976380303 166057448 392850273 498 523742857 581955618 329 987130097 8813051 795887943 755 948127215 112 582 795 338837126 327 80418266 715073642 772698388 583928003 641 480737544 567282677 405 737654628 71287988 511 933507092 561873263 212612975 624189998 361421364 625791403 71287988 141 279936610 537525569 852 378778863 606252818 412973000 677644631 887032969 907950446 356982167 1861620 772335588 634883913 641372285 860806653 9 242099507 109 657788742 402560617 585 454754675 527507141 632 1861620 697351024 71 163 909 82 675041776 305326269 718129899 799 145162288 204 651 631496855 938440973 154 774565069 2 336751640 351984045 705014348 80418266 299357940 535335054 257003592 527507141 54826492 601085021 575033536 417141792 183259116 27992190 430840670 681582058 952 108494849 106932205 155731220 612484774 509 828105104 505604507 385 32 402080873 360584203 565677864 339999570 12 128309313 436709999 1488804 510140564 231412948 729156523 131 512533542 325555210 378778863 820462779 604 699212976 465385250 166415923 820462779 495893906 885617968 344303507 690 920308421 538096002 351984045 971916852 863734093 21166510 410364233 679 399 727761698 973 371803472 258183223 456 211137295 652 966 332 705014348 755 218502949 846 645199066 371803472 467322083 487736353 446145948 708001977 369424280 639435507 654439786 905561198 50548018 607807067 363290231 914247224 670001098 579 784 898102333 1827168 250 757578230 258183223 526 966358951 392049320 896 588023548 612484774 996048841 932285673 278901824 108494849 828896080 789157270 372999620 380075508 346128706 719639741 781958720 15558196 912 978933184 354 41904208 738077433 570388236 173803659 510140564 940 316 480737544 732929057 913242550 731128332 461634197 4 206121309 280483850 791881390 160 811333453 173958780 624189998 982714779 923742125 436 729320492 906 983456086 242897422 935152487 869195525 921 466 106 956632420 948127215 859899645 207 813178718 961692520 63064402 797 311 208009449 817690053 186 257003592 499316672 460 333143333 708001977 943008950 743946854 441224254 677644631 28929767 574 688542728 393218410 754891992 425927291 989754188 738077433 943 699212976 401 236929594 402080873 88198072 355 849 800923723 939458768 600479810 224207218 12741541 514 624990630 876 54826492 477 577007952 813178718 618849633 645727331 300666789 185940227 935835714 541035280 8550863 754891992 861956207 937701908 967 215362606 774565069 422666120 250136885 964665256 403740650 426 1827168 941794856 378 921154357 587633677 816872695 876 81 263628924 659245009 448 43 774773656 224487240 402005161 941794856 357735711 441955509 671 434579431 218373067 534477464 505604507 546075498 175261027 257 923 142 252153132 319 673282909 46 895123768 361 648669542 447 579 317 497041626 126963422 842041675 197 562596936 43318401 468662786 454754675 215113193 206088997 342518623 816872695 378778863 550 699212976 294207194 145162288 983 248292386 432653384 370686813 430974086 175261027 828896080 518 853772148 482145421 43 913242550 96443153 640 915 751865562 560196332 772335588 816872695 594 434396593 928229728 520808770 477830025 748779499 436709999 692 907950446 495893906 945 282 821 276 725845416 548045151 839 893 242155937 380075508 33053098 590730703 695617531 117 227052116 235151274 757506952 169272946 904461495 215113193 960525987 464289454 124549126 632 757578230 807949290 102990494 538096002 735249489 37895355 329920251 443471521 879 748529163 93 487736353 198986228 169578121 847 433290682 384340708 950757313 913242550 434396593 325910984 897354169 46410727 535335054 427124378 369424280 610 789 681582058 295 169 69614183 756882312 593084528 209769922 499368958 391102363 980 695925644 390232483 66842524 150411702 690 887859867 932611793 162088232 89 696272847 737654628 587633677 472892556 273109631 39048172 822 557014053 276900387 163 861169280 384678538 634883913 517422940 117633124 846410693 801260973 582 982714779 402005161 7285952 540130780 789894369 80998348 551592960 342827008 24596432 951197672 325019009 27992190 524 542 265347784 136248093 903226349 581955618 670001098 384248590 942 120882525 499232662 510192994 485631084 269083857 433290682 854745611 588023548 372999620 338 471966566 143500123 505945203 813178718 764096728 639435507 745196112 142141502 635 972514823 208606010 33903462 612484774 548045151 684444395 401 606984444 305326269 670001098 608 542927779 118 558900214 989754188 361421364 905561198 661 951966857 75 622014449 262918725 938440973 600479810 538 969676773 214515745 535 318353561 90713262 921154357 333 951197672 774773656 194562916 645199066 488355649 328 55 651 739730662 48218162 607179645 923742125 880098006 555644669 309746518 412973000 427 987130097 675041776 738115841 129473913 65132084 786 727 378126062 842041675 297901069 187 979578913 487 398584008 148343784 132 142 401341976 656389084 27 351984045 363290231 433290682 734713993 557 670 819 54826492 285475432 117633124 737076138 427380314 517422940 886934838 48 465423715 564159615 596942770 546075498 305 697029907 989754188 366256794 629344246 424 734713993 930690244 952535151 481095768 434362954 489837102 596942770 21166510 869329021 474 976684614 877 885617968 943008950 273 206121309 384248590 878366736 13841380 517 7537862 16 767171602 577007952 206831541 98971813 995573041 479006197 761 502516676 523 665 66842524 821712677 537525569 625 504209596 36 47173681 236 236229513 205 102990494 130188717 856 756418971 883394947 177017039 198986228 499316672 405127266 779364609 28635126 243345425 652902050 931687951 567432934 618849633 648669542 154 258 988872191 453021299 937385093 634938630 310905896 660 59098079 84475147 794667434 174767359 509 430840670 974 937 269 938 683210834 32 26754255 495893906 210 366256794 374738151 903 84708556 183259116 699212976 50548018 980 746213531 247 161571478 743946854 489231836 735249489 95023636 737076138 759518315 713041886 77732266 177 283283198 134 11295424 875306288 105 715045953 887032969 815 984629297 182333045 480 356473154 722 163024964 390232483 453021299 489837102 347155090 192939551 481095768 576 756418971 6999164 718129899 576377966 886934838 488355649 505977928 679974875 899959027 873087829 637150199 435345309 328 103 112066211 716432033 853772148 971916852 130188717 98971813 919693970 623 644712801 624990630 427124378 269083857 683462460 829 366256794 48819428 761 600479810 169 534477464 281676935 734713993 972295874 903226349 545 361421364 124415720 492205882 39919329 33903462 436709999 938440973 688542728 947634121 215438568 212505301 634938630 625791403 41582470 480259433 433290682 384678538 372999620 785025451 695925644 217 321518363 390232483 471611905 935152487 692312576 819242395 961692520 835 384678538 80 876 688865271 555603904 235518089 361 453021299 152585716 448 715073642 163024964 279936610 713196042 94406529 799 598 402560617 632544208 904461495 341 313868888 86567488 349 313868888 370347248 7537862 340 236929594 173803659 47 263628924 404009803 966 227052116 734448264 524 841425041 645199066 857 551238034 54045945 701056542 223 499368958 115917228 695925644 281676935 941794856 1488804 969485187 94 914967290 220 47173681 832566170 794667434 474538470 734713993 717909925 303 971916852 493 460 325019009 310136979 750 764096728 939907162 940965261 866816759 895086985 989754188 417141792 398584008 742044103 861 952865008 152585716 567282677 841 7846637 50 370686813 648669542 895123768 772698388 890165630 502516676 622014449 868201351 407566380 754334092 142610325 737507051 142392058 701056542 729156523 907950446 844 978164011 609 309 564159615 480737544 713041886 360151898 198986228 86567488 789157270 838 985523575 932611793 732929057 994912259 414057053 897354169 134 438981204 982714779 482199719 590 631 170962622 835 108430558 357735711 531442354 166 660 996542074 438 422666120 652265348 849294793 365871502 854 604978051 -1 558 601085021 483 933507092 541035280 987130097 218502949 613086508 291638371 872174286 697351024 323655646 697 39523837 177 576377966 788 390232483 948 540130780 392850273 80998348 21166510 500094404 454671349 707046643 534 451 80 250136885 305326269 525843580 425 127532808 491789143 807949290 592566788 182333045 645779254 901332937 727761698 799158428 676 732929057 269083857 304566371 166415923 740738219 101265212 925 533 799158428 265347784 768 195 357 434479191 112 442431820 59098079 659245009 313868888 610 565866719 442431820 355087736 894 993992449 112066211 215438568 9200261 939458768 159 658076052 250136885 524 820462779 954103169 513025460 838054435 242155937 652265348 799158428 969676773 339999570 477 206133076 542927779 24059943 748529163 594280111 506119814 390232483 847 759518315 557671641 867017453 372999620 643 205018974 875236313 375869002 374323399 54826492 683462460 643835833 901332937 242155937 899 65111958 108494849 419247204 91995194 374937360 881 529679406 437719154 343962987 567282677 498327150 731128332 219957318 351 689523292 932611793 238308414 372 145336938 256305753 442431820 363567713 891103799 828896080 411806530 219957318 982190248 46410727 886934838 224207218 480737544 675431728 417287838 962 848181926 494 434396593 876 22 371 772 39523837 349 919 47434338 807949290 361 848 187257798 27992190 664745814 505977928 12741541 599 162088232 89073464 271 412973000 265347784 834 622014449 352 37301769 719 15558196 636 510140564 832566170 931687951 883394947 826 807949290 294207194 341 851 781958720 557613887 873087829 403740650 906763981 576377966 933 253 663879567 754334092 833 215362606 145941098 890165630 421884304 265347784 346 619 681582058 472892556 501255084 673466602 398584008 368704676 145941098 867017453 681582058 837 499 27992190 627 601085021 90713262 571 924 943056984 28635126 346128706 971779741 535 630 291638371 18 804816501 584474774 370686813 254091185 325910984 90621422 720876584 999889600 427 547193379 66842524 1861620 657 7537862 756882312 806 813 696538826 331824546 430840670 541035280 614 952865008 198986228 477086746 614149143 59 670001098 182333045 656389084 388 796550976 219957318 895086985 189 63064402 932611793 513 417287838 449762261 683210834 39 828105104 700476452 854745611 868201351 588 375869002 269985850 495893906 875306288 750272869 247 771 407566380 898102333 666573288 880 355039913 248 972514823 81062183 392049320 793826951 313868888 175057436 130600813 133845054 954103169 467322083 161426036 779349988 198986228 112187572 315 566138605 951197672 272792024 668 402 541 449762261 791881390 405 529 132567905 957 125 899 384678538 41582470 784 754030551 321 413591339 425927291 152 921154357 71287988 325910984 124549126 563428748 520808770 487 370347248 874 626 398584008 501255084 257 747 778 26754255 398584008 51932307 606252818 390232483 427380314 38526569 984629297 190513116 255 232553236 84475147 145941098 604 65111958 446145948 64044003 816872695 113 78944071 276900387 407566380 355 166415923 666633123 208606010 789473416 587633677 976380303 886934838 181011230 170962622 786 730 213 823518565 947634121 331 250136885 748529163 659 789894369 59098079 22 98073919 601085021 248292386 846410693 231412948 444922450 331824546 857630218 789473416 34 88205199 145941098 863734093 460 645727331 886 124415720 497041626 897354169 169 725310670 51932307 46410727 107147247 290432813 713196042 312 954 270583318 41582470 278901824 209721596 907301325 360 772335588 160678923 539 673 431879635 390 869 132567905 444922450 64044003 39919329 609213054 780369952 525843580 190 476601142 982714779 558900214 215438568 142610325 54826492 59098079 101265212 236 480737544 559 112187572 789473416 369362289 620 504108341 41582470 523 117 470611082 760657421 427380314 405127266 37895355 563359293 417287838 788150883 170 278 599738581 657153133 117 374605067 429436449 35616762 224487240 177017039 701056542 367883729 33903462 430840670 147375074 209721596 254091185 687 739730662 116647042 487736353 883394947 903226349 157487018 903226349 683506145 659245009 30247738 112187572 639 762341708 605616025 98971813 206054045 679974875 2591083 279877374 259 21716059 903226349 877 653010341 891103799 35616762 173195557 206 409454013 254 262 311554006 899959027 178934187 379021826 19232251 20683010 869329021 816872695 557019352 521674165 455 745196112 789157270 566138605 39048172 53 351984045 607807067 589 477830025 749597500 369362289 76887994 759 639435507 913242550 192 707 235518089 894 631496855 480737544 27992190 -1 658076052 382765550 299 979963115 697 899959027 512 84521425 198621884 505977928 185 557613887 121075473 224207218 445796727 807 90713262 144 347 90600712 832566170 571812901 280690667 525843580 756882312 854745611 365871502 325910984 379021826 381 489671699 821 374 964665256 807949290 356 825 735161947 457215301 33903462 848 37895355 280947786 577 21263601 723 657153133 738115841 684734627 526 340 551238034 557671641 398 351984045 682 442 248292386 607720488 613522780 167540046 587633677 308431084 441224254 636 328 947634121 857630218 719639741 719639741 683110217 601085021 375927789 157435453 969485187 683364021 489231836 367 380075508 215113193 978528800 38526569 219957318 325555210 557014053 730 898102333 979963115 90600712 622014449 873462667 24596432 601085021 879021283 979963115 695617531 312 147219198 39919329 373 485631084 849064100 979578913 875306288 775809585 475 624990630 958 958834567 652902050 750 759518315 548045151 625791403 183908093 383 581955618 360151898 519 342185429 741 510140564 889076216 730496353 584790396 832191033 94 943056984 860 346128706 421884304 647 375496397 471966566 939458768 347589470 738115841 33 995573041 954103169 54723614 8692268 916624283 707046643 654 625791403 965 972514823 82 276900387 20 554658412 386 846410693 721958784 1575559 48677072 521674165 135565213 203725867 941794856 970062456 47434338 464289454 398584008 477086746 344 828896080 280483850 301 801 209769922 750470605 453021299 907 -1 789894369 457908107 813178718 560456543 566 257003592 59098079 153 235151274 247395365 681 890 520808770 634883913 352118545 80 707046643 84708556 39523837 746213531 629 885617968 741 670001098 530 467322083 481 901332937 632544208 760303484 995573041 745196112 347589470 555603904 100373969 394 81 274974844 928229728 427124378 988 842041675 741658807 240 756 867495149 169272946 571 371803472 236229513 423 431879635 444922450 148 665229761 475757272 76887994 190513116 291638371 734713993 969676773 577007952 8 735143631 206 166415923 385 863734093 339999570 339 294207194 407566380 283 637150199 781958720 772698388 692312576 287460887 282 411 50548018 436414064 372676097 580 285475432 100373969 637150199 7285952 411806530 804816501 206121309 175261027 479 102860860 355039913 357735711 872174286 347155090 966358951 13 593 822 212505301 489231836 547193379 762946187 155 77732266 524 828105104 309746518 750233156 785025451 41582470 143500123 311554006 499232662 211137295 467322083 71287988 112066211 783 24 988872191 713196042 828896080 757 880098006 881 299357940 1827168 825958247 732929057 846410693 618849633 259347596 644712801 713196042 970 363567713 467322083 12741541 611 725845416 625701809 750233156 169272946 782395438 88198072 393256312 709968046 809684001 138 412 304 729320492 840 153733117 66842524 832566170 785025451 434362954 595 65132084 756882312 885617968 157 54045945 670 5403924 95 31562571 712 807949290 269083857 335 922 259347596 110561899 710108943 683506145 353 603706365 285475432 757370606 941794856 757506952 540425911 594280111 961692520 265347784 369264804 308431084 192 206088997 748779499 939458768 457908107 28929767 226772138 108494849 -1 211137295 767171602 541035280 850 262918725 470611082 697351024 577007952 688 920 540359278 521674165 372676097 780369952 208009449 43 414057053 124549126 652 721958784 990 756418971 656 173195557 525 173803659 382765550 743946854 411736794 906763981 493576353 157487018 279480133 91208198 452 461634197 79599416 817690053 960525987 569 127532808 687851530 63064402 752 215438568 999889600 612 970062456 734 7537862 24059943 430974086 632 78859502 457215301 470611082 406 547 570388236 785025451 182333045 266 750272869 869195525 983 885617968 279877374 140631476 618298540 156764 542 6620902 281676935 589075597 355732561 772698388 564159615 895123768 280483850 529679406 123 618849633 899959027 468662786 206054045 161426036 252153132 486026824 508 372676097 20 820462779 467 613522780 365871502 474538470 609213054 263 598640728 681 198 967468092 477086746 861169280 520808770 789473416 417287838 567972641 84475147 436414064 742044103 325 920 57 318353561 371803472 465 299 115917228 618849633 686541684 663879567 482145421 336822513 449762261 542688502 922 118125217 513025460 269083857 130188717 626 859899645 606984444 527507141 343962987 665341877 811 479661466 229 746213531 542514996 269 639522229 77732266 570388236 287082385 23 657153133 153733117 607807067 443471521 538096002 982190248 915 913242550 644712801 816872695 946 434362954 386 352813421 993992449 797149661 785025451 845 887859867 932285673 374323399 223 914768354 857 116647042 190896064 577007952 206133076 142141502 203725867 821712677 604978051 392467605 325910984 922550791 819242395 436709999 343962987 152585716 53 596 760303484 729 332 947 629344246 824 715 116647042 11295424 878 945471160 655 775809585 725845416 250136885 605616025 476787818 391102363 674 985085442 774773656 352813421 786 757578230 152585716 534477464 368382661 758 296356322 901332937 320 432653384 140631476 529 645779254 86567488 920440338 793014352 258183223 461634197 15558196 733 982714779 832566170 206 13 365871502 108494849 430865747 66842524 605288864 723551462 -1 958834567 442431820 737076138 985 619 579 599484641 363567713 291638371 732038509 754334092 889076216 849294793 745196112 512533542 557019352 890165630 567282677 427380314 43318401 652114327 11 609213723 495893906 219951578 654 -1 658076052 163 68469980 212612975 222 145 142141502 86868526 754087296 205018974 947634121 84 967468092 258 688 540359278 311 408619248 793826951 979578913 247 188 982714779 549 797 471966566 417141792 634883913 697029907 215438568 378154747 853772148 535335054 51 708001977 899959027 142384508 13841380 480737544 730496353 876 567432934 841425041 59098079 938637117 218373067 978164011 607179645 805704091 374605067 609213723 236929594 505604507 69614183 77732266 41582470 312 844 520808770 375496397 148343784 173195557 432653384 257003592 310136979 59 152585716 767171602 607807067 485 782395438 820 363290231 749597500 470045024 958834567 995573041 434579431 432653384 880098006 2591083 791881390 59098079 247395365 932285673 236929594 683364021 749597500 371209335 212505301 175057436 979963115 754030551 504 339999570 50548018 270 939907162 988872191 333143333 540130780 714506326 760657421 947634121 547 586 849294793 774773656 799 568 842041675 622014449 716225287 28929767 283283198 78 274974844 229 64044003 495893906 754891992 342827008 402005161 10545 680228173 477830025 971574946 111760960 33903462 575268466 685446819 327 712335838 68469980 21166510 140631476 1488804 379021826 748779499 541035280 716432033 696272847 339999570 883394947 194562916 469 289690023 993992449 706781241 384678538 67 603706365 988872191 832566170 454671349 712 411806530 401 54723614 684444395 869195525 510192994 127532808 370 468168409 932285673 571812901 176 752470678 614149143 607807067 5403924 275 140631476 169272946 93 118 278 711 795887943 592566788 421884304 51932307 913 203725867 434579431 430974086 7 375869002 318353561 37301769 790 510192994 867495149 766 440028642 473653705 701 794 183259116 817 684444395 156764 794667434 472 632544208 166 958834567 49 545 271 652902050 961692520 574 291638371 653010341 663879567 764096728 208 253 551238034 961692520 212612975 374 134 750470605 631 663879567 433290682 706781241 807949290 128309313 485631084 785 809684001 242155937 677644631 340 648 218502949 88198072 68 287460887 540425911 656326405 664745814 256305753 192939551 39523837 660 729320492 342185429 885617968 551592960 591 618298540 542 47434338 206133076 520808770 765 480737544 603 234 370857163 35616762 530 663 415 374937360 117 914 247279147 325432259 257003592 996506222 405127266 904 486026824 181 173195557 380075508 472892556 849 501255084 556167411 774 356473154 505945203 411736794 632544208 436709999 7537862 371185370 637150199 500094404 33053098 345 279936610 243345425 789894369 759518315 78944071 890237000 665229761 612501617 411806530 187342644 705014348 402080873 788150883 726 64044003 356473154 68093116 36 875306288 425927291 8550863 958834567 355 922550791 805049067 71287988 959 557014053 47 66842524 930674943 113 41582470 613706907 867727273 417287838 838054435 132567905 427124378 652902050 81062183 461634197 311554006 187928226 99 826 966358951 607720488 265347784 136 913242550 577007952 982190248 838054435 368704676 495893906 767171602 -1 365871502 531442354 725845416 914967290 101265212 69614183 889076216 283283198 860806653 447 986365957 132567905 1454227 634883913 35616762 369424280 951966857 529679406 487736353 244208872 793 305 63064402 343 879021283 601085021 453 206054045 738115841 599484641 388 143500123 368704676 365871502 311554006 683364021 587633677 122256557 180 143500123 411806530 152585716 565866719 537780009 211137295 912 126963422 130188717 189721383 175261027 537016815 916624283 789473416 525 761 121075473 609213723 417141792 615551819 639 828896080 555644669 259 684734627 772335588 647 162088232 436 271011833 624 280483850 180019963 688865271 932285673 93282954 383443224 194562916 335303255 697029907 378778863 958834567 491789143 779349988 507 940965261 742044103 625701809 500 80998348 553736420 985 971916852 382 437719154 577007952 687851530 501255084 380075508 793014352 309746518 718129899 713 432653384 750470605 212505301 527507141 749717630 659245009 371185370 958834567 828105104 656326405 548045151 556167411 374114531 250136885 142610325 570388236 274853174 612792481 254091185 185940227 639435507 820 609213723 370857163 153733117 166057448 369 417287838 241 663 622014449 308431084 943056984 939907162 683506145 625791403 208115388 947634121 480259433 434579431 964665256 203725867 652114327 969485187 751865562 324 697029907 37895355 528 182333045 352813421 227052116 454 583928003 670001098 767171602 155731220 708001977 107147247 45 482145421 289690023 752470678 160678923 355732561 25 227052116 13841380 498565394 81062183 185940227 157 124 805704091 239 235518089 330 570338115 427380314 852 793826951 104 940 524 39 905561198 893 706781241 554658412 665341877 272792024 779364609 65 563428748 115 801260973 482199719 945471160 827 860760417 846410693 463472330 779364609 342827008 -1 386 935835714 361 247395365 20683010 6 612 116647042 615551819 474538470 237 305326269 155731220 767171602 849294793 938 380 28635126 426 311294439 181011230 108494849 577007952 894 65 737 43591040 999889600 363290231 121 632544208 734 187342644 208115388 110561899 129 102990494 791881390 571 932285673 527507141 289 895086985 356534892 796550976 480259433 624990630 129473913 371209335 587633677 499368958 453021299 706781241 1454227 479006197 468168409 817690053 457215301 471966566 331 750272869 577007952 795398160 262 2591083 93282954 437719154 513025460 657 604978051 225318291 347589470 764 449762261 979578913 629344246 612501617 154 187257798 429436449 442 356534892 143500123 825958247 560196332 697029907 242099507 557019352 401 88 599738581 491789143 68469980 194 370415433 794 476601142 136 512533542 926 789326205 752360903 958834567 969485187 268 577007952 198986228 190896064 699212976 853772148 85 656 80 136 265347784 639 7537862 652265348 309746518 558900214 182333045 960525987 828105104 559397285 206133076 551238034 198621884 740 710290423 130188717 975 749 981 844 408619248 875236313 491789143 551238034 189721383 825958247 319572321 795398160 898553 683506145 299357940 848181926 84 996506222 370686813 118125217 663879567 735 800 587821314 887859867 922550791 667 378126062 211137295 244208872 493576353 495893906 543 233 126963422 995573041 497 898102333 185030419 265 360648201 555644669 252153132 532 408 749597500 506119814 644712801 967468092 69984825 342518623 984 347589470 370347248 262918725 683210834 233 374937360 992 308431084 215438568 406 832566170 129 710 735 498327150 606252818 318353561 136248093 570338115 581955618 854745611 566138605 324 39919329 717 54045945 781958720 866816759 88205199 19232251 880098006 160 9965165 348 52 258183223 991 895123768 206133076 294207194 588023548 978 839 263628924 553736420 846410693 701056542 653010341 654439786 279480133 54723614 624189998 670001098 143500123 661 96443153 96443153 724345037 410 878366736 624189998 516 846 675 8550863 979963115 735205243 470611082 784 596942770 891 924 612 592 276900387 729 754030551 433290682 94406529 122651017 236 985 411806530 2591083 166415923 173 402560617 899959027 96443153 252 162088232 625701809 666633123 68469980 247279147 64 978528800 749717630 602 657 869195525 919 659 392850273 343 910 287 136391292 652902050 203725867 182333045 752470678 90713262 252153132 88198072 136248093 510 278901824 329920251 265307442 950 686541684 356982167 570338115 901332937 393495221 224487240 68 26754255 628772869 112 796550976 142392058 495893906 32 752360903 880098006 -1 346128706 694 479006197 754030551 686541684 562596936 838054435 571812901 63064402 930 501255084 304566371 613706907 384248590 184 746213531 113 136248093 754891992 675041776 319572321 819 280483850 799 274974844 690 463472330 631496855 164 565866719 425 59098079 235518089 895086985 576 390232483 147219198 364 267 54045945 786 203725867 372999620 392850273 499316672 84475147 566 791 846410693 760303484 471966566 605616025 150411702 713041886 916943464 659 525843580 173958780 932285673 236929594 825 319572321 658076052 710 149 427380314 841425041 500094404 750470605 487736353 905561198 107147247 77732266 635 368382661 305326269 901400271 504 960 643835833 512533542 208009449 240 993992449 187928226 289690023 490259472 842041675 792 194562916 240 183908093 482199719 605 954 613 775809585 418 789326205 566138605 203725867 710290423 779349988 1861620 182333045 760303484 392049320 63 491789143 112187572 631496855 390 619 308431084 402 863734093 697351024 488355649 492205882 408 713041886 849064100 705014348 556167411 687851530 961692520 124415720 832191033 751865562 6 537180003 148343784 602 983456086 263198329 248 295 368704676 209 263628924 677644631 502 714506326 675 94094977 683506145 863734093 446145948 419247204 735205243 374114531 202 951 759518315 379021826 713041886 624990630 429436449 7285952 49 143500123 444922450 775809585 252153132 439854551 32021993 887032969 982190248 434479191 115917228 408 477830025 727761698 906763981 337 411736794 347589470 718636351 604 154 600479810 801260973 402005161 914967290 163024964 410364233 615551819 473304340 548045151 338837126 78859502 793826951 152585716 951 624301926 392049320 285 689523292 557671641 849294793 686986728 48819428 414057053 523742857 247 782395438 -1 370415433 404009803 585 584474774 253516569 15558196 775809585 697351024 785025451 956632420 715073642 279480133 581 817 -1 212612975 790 291 846410693 112187572 140631476 461 684734627 581955618 842041675 66842524 46410727 756882312 760303484 355087736 850 831 360648201 147375074 772 989754188 686986728 242155937 501 730496353 757578230 970 243345425 875306288 307 996048841 845 854745611 849294793 254091185 547 883 243345425 9 906 987130097 162088232 555644669 319572321 907301325 91208198 716225287 34 400752854 167 402 401341976 98073919 701056542 7846637 644768132 539 537180003 105297890 231288389 679974875 473653705 996506222 937701908 828105104 517422940 33 928229728 398584008 335303255 584474774 479006197 79 51932307 10 66842524 231412948 859899645 392 552724692 173 179980555 142392058 290432813 731 412973000 896 809684001 304566371 716432033 360584203 5403924 495893906 612501617 248292386 100742911 634883913 775809585 300643186 649 416 410364233 716225287 521674165 493576353 198986228 805704091 816872695 851 251 936 206054045 978164011 304566371 522 814 -1 688 93282954 59098079 779364609 378154747 838054435 427380314 54826492 360584203 136248093 619 1861620 374114531 392467605 69984825 318 6620902 854745611 605491815 849064100 884 880098006 31562571 653010341 190896064 609213723 112187572 813178718 895123768 502 39523837 265347784 145941098 43 259347596 408 531442354 408187156 215438568 895086985 288 680228173 357735711 661 807949290 307 952175062 952175062 842041675 537780009 164 81062183 663940847 159 219957318 574 187928226 643835833 891103799 683110217 48819428 537525569 28635126 725310670 863734093 338837126 978933184 656326405 158 923742125 356473154 473304340 24059943 373 166057448 218373067 384678538 556 863734093 901332937 605616025 244208872 525843580 278901824 986365957 361421364 723 262918725 941794856 360151898 293 670001098 793126210 985085442 7285952 666633123 685446819 860760417 20125390 842 924 519 301101064 360648201 731128332 686541684 263628924 542514996 725310670 875 972514823 372 895123768 710290423 665341877 462 454671349 384678538 552724692 871435007 314 701 933507092 871435007 810 873900773 570388236 112187572 242099507 39919329 890 673282909 482199719 913242550 182333045 735249489 973 177017039 198986228 775809585 161426036 898102333 321518363 457908107 50548018 804816501 238 273109631 714506326 499316672 622 657 446145948 795398160 227052116 789 38526569 652114327 283283198 28635126 935835714 950757313 65111958 531 613086508 849294793 985523575 145941098 456905914 727 716432033 179980555 599738581 951 269985850 124549126 937385093 474538470 8550863 262918725 325910984 624990630 952865008 904461495 553 325019009 748779499 360584203 20125390 918 612484774 842 313 47173681 98073919 329 563428748 208 716225287 71287988 624 294696626 905561198 136248093 147219198 338837126 323655646 603706365 26754255 722 9 875 263628924 849 279936610 867 225318291 506 152585716 613706907 634938630 78859502 132 437719154 709968046 101265212 637150199 405127266 190896064 372676097 474538470 453 449 695617531 333143333 747 61 640257700 649 636 438981204 189721383 78944071 166415923 433290682 198035066 136248093 517422940 352118545 642 200 787 540130780 280947786 490259472 224487240 861169280 966358951 892 257003592 672 664745814 32 242099507 888 922550791 497 48819428 809 290 313868888 714506326 66 654439786 442 472 48218162 774565069 654 94411085 325536833 265307442 188179256 754334092 964665256 215438568 278 914247224 537180003 890237000 76 293 179 145941098 560196332 178934187 100373969 788 542514996 296356322 710 967 883394947 170962622 266 561873263 804816501 352813421 100373969 790 100373969 206054045 634883913 878366736 296 820332202 343962987 398584008 748529163 934 555644669 21 279936610 108430558 157487018 80 311554006 304 5403924 509911814 98971813 65111958 505977928 509911814 390232483 274974844 311294439 270583318 709968046 577007952 821712677 742044103 923742125 785025451 393495221 132567905 274853174 384339361 946 112 555644669 675 750272869 471 102860860 575268466 231412948 280947786 601085021 145941098 40 951966857 754891992 952272551 607720488 558900214 907 243345425 673466602 265307442 19232251 624189998 941794856 48819428 730496353 208 805 152585716 400 677644631 567432934 663879567 419247204 887032969 540359278 226772138 939398799 30247738 510 224207218 930674943 537180003 877 91 58 659245009 444922450 254091185 157487018 183908093 740738219 280690667 239 960525987 480737544 370347248 717909925 757370606 26754255 982190248 680695712 935152487 181011230 346128706 149893081 173195557 505604507 591 752470678 129473913 852 903226349 408619248 495893906 427380314 525843580 471611905 643835833 975 236929594 838054435 80418266 871435007 211137295 751 746 863734093 985 416 489231836 20125390 15558196 650326726 419247204 166057448 461634197 477830025 94 343962987 69984825 205018974 757370606 283283198 993992449 919 873087829 447 92 398584008 157 129473913 297901069 504108341 442 214515745 799 739 823518565 262918725 794667434 457908107 454754675 615551819 145336938 999889600 473304340 495893906 762 940965261 817074075 93282954 411806530 869329021 206054045 801260973 652114327 433 672 323655646 762866431 219951578 686541684 730496353 481095768 637150199 669 659245009 278901824 470045024 196994946 593084528 746213531 69984825 634883913 883394947 986 94406529 855 719 737654628 37301769 169 212505301 795706128 566138605 613706907 921 788150883 861 231288389 232553236 947634121 384678538 948 644712801 657153133 263198329 372999620 5403924 937385093 471 542 795398160 367883729 939 384678538 242099507 263 618849633 370686813 231288389 613706907 368704676 209769922 687851530 203725867 347155090 38442167 770 404009803 108494849 804816501 898102333 592566788 836 612484774 715045953 390232483 406 434579431 978164011 211137295 219957318 524 422 843 691 850 788150883 838054435 510140564 281 583928003 670 542 -1 194 939458768 411736794 185030419 592566788 143500123 629344246 231 966358951 208115388 100742911 1861620 265347784 903226349 33053098 689523292 645199066 873900773 640418711 805704091 476601142 784 365871502 472892556 517422940 31 430974086 429436449 31562571 828896080 418 776 365871502 960525987 422666120 714506326 932611793 402005161 889 105 90600712 551592960 353 796 919693970 996448486 387 456905914 153599292 150411702 71287988 670001098 939458768 447 878366736 198621884 423 764096728 393495221 780369952 867495149 307650057 906763981 828105104 179980555 313868888 801260973 727725878 259347596 271011833 446145948 738115841 534477464 733 301101064 964665256 583928003 991 366256794 978933184 524 27 700 875306288 384340708 134 188179256 28635126 169272946 91995194 725845416 947634121 339 912 145162288 35616762 423 37895355 374937360 43318401 64 12741541 868201351 392049320 145941098 941 280690667 805049067 754030551 618298540 209769922 632544208 696 607179645 247395365 979578913 329920251 319572321 101265212 914247224 429436449 100742911 336751640 206133076 193 576377966 560196332 11295424 481095768 801 402005161 609213054 592566788 399 287 229 954103169 735249489 20125390 436709999 794 519 355087736 190323346 696272847 91995194 901400271 250136885 861956207 347589470 367883729 401 552724692 142141502 460 374323399 323655646 10545 958834567 335303255 839 19232251 614149143 775809585 652902050 926 538096002 873462667 51932307 735143631 613522780 224207218 607720488 597532459 800923723 203725867 697351024 208606010 468168409 634 311294439 797149661 462590682 652114327 708001977 180348334 524 889 374605067 96443153 142392058 24596432 978528800 454671349 190323346 355039913 745196112 218373067 805704091 240 536 490259472 219957318 969485187 724345037 7537862 69614183 738077433 789326205 88251046 861169280 984629297 854 789157270 355039913 522 780369952 867727273 259 737076138 672 468168409 212505301 762866431 242 1861620 570338115 622014449 344 169272946 464289454 798 7846637 465 406 86868526 76887994 71 793014352 147219198 9 153 393 627 696538826 562596936 629344246 427380314 537525569 749717630 627 861169280 394 48218162 102 530 783 921 918 960 338837126 363290231 628772869 751865562 756882312 355087736 336822513 637150199 732038509 587633677 50548018 953 157487018 163024964 872174286 603706365 883 741 439854551 748529163 725310670 927467800 640 405127266 225 762866431 94411085 906763981 551 952535151 164 26754255 594 921154357 358 759518315 181011230 273 634883913 84521425 90600712 658076052 374323399 837 -1 699 454671349 441224254 825958247 491789143 938440973 985 402 305326269 252 250136885 581955618 351984045 128 988872191 355039913 985523575 772335588 11295424 526 93282954 557014053 289 175261027 -1 136391292 152 411736794 735417053 543930181 198986228 699 639522229 173 811333453 521 379 529679406 907301325 311 892 540425911 163024964 570 966358951 984629297 520808770 423 948127215 477830025 185030419 842 218502949 972295874 254 293 196994946 970062456 863 450 854745611 206831541 153733117 67003584 53 242155937 906 914768354 124415720 575033536 217 398584008 913715131 69984825 35616762 659216109 279 673 767171602 875306288 675431728 740 665229761 751865562 370686813 986365957 94094977 697029907 296 581955618 705014348 325555210 355087736 883394947 869195525 208606010 838 400752854 102990494 842041675 135565213 996448486 48819428 1454227 641372285 338837126 115917228 801 71287988 164 885617968 259347596 486026824 582 124549126 304566371 240 651 48218162 479661466 575033536 567972641 430865747 140 28635126 688 272 392850273 793826951 555644669 706 365871502 832566170 470045024 971574946 441955509 891103799 15558196 360648201 504209596 939458768 155 361356699 398584008 231412948 93 713041886 308431084 789476776 997837191 637150199 907950446 415 50548018 454671349 205 522 48218162 895086985 247279147 979578913 750233156 779364609 68 153599292 907631891 370686813 872174286 644768132 48086638 305326269 379021826 945471160 446145948 206831541 142610325 976380303 88198072 842041675 781958720 607807067 900 294696626 473653705 38 559397285 782 482 292 625791403 841 314 325910984 41904208 211137295 296356322 755 820462779 153733117 939398799 170 801594169 587821314 510140564 375869002 690039293 265307442 853772148 542514996 319572321 157435453 206121309 219951578 408187156 297 7537862 557019352 950757313 132567905 838054435 716432033 547193379 707046643 453021299 939458768 696538826 648669542 976 130188717 551592960 606984444 155731220 538096002 804816501 7846637 500094404 905 325910984 355039913 971779741 873087829 433290682 90621422 665229761 853 509911814 37895355 368382661 853772148 639435507 160 325555210 508 672 59 2591083 20125390 734448264 458 684734627 916943464 246 825958247 219957318 162088232 775809585 943008950 312 145336938 374605067 80418266 569197642 21716059 371185370 256 954103169 210 651 764 774 170962622 659245009 446 699212976 1454227 976684614 471 461634197 1827168 76887994 -1 315 570388236 555603904 775809585 735205243 913715131 45 923 793126210 592566788 808 941 392850273 960525987 352813421 952535151 280 117633124 188179256 100 820332202 756882312 950757313 369264804 443471521 782395438 919693970 476601142 978528800 124549126 241 290 751791188 414057053 540425911 88205199 767171602 873462667 303 461634197 33 343962987 127532808 986365957 230 933507092 986365957 749597500 993992449 196994946 818405241 721958784 518 633 71287988 938496097 553736420 263198329 366256794 683364021 115917228 951966857 570388236 435345309 157 227052116 817690053 895086985 684444395 234533156 142610325 498327150 489671699 562 187257798 7537862 875596010 214515745 727 555603904 737507051 499443963 952175062 945471160 503 192939551 487736353 338837126 371209335 270583318 337 86567488 422666120 437719154 31562571 137 401341976 710108943 854745611 125 785025451 24596432 33 235 47173681 408 739 135 294696626 928229728 433290682 254 38442167 69 675431728 558900214 816872695 799158428 122651017 393256312 828105104 124549126 325910984 818405241 631496855 784 153733117 681582058 787 857630218 434579431 94406529 290432813 402560617 880098006 501255084 615551819 79 436414064 224207218 33053098 715045953 921 130188717 564159615 15 391102363 888 214515745 188179256 344303507 496 215 126963422 673282909 457908107 12 537016815 39919329 150411702 282692654 700476452 970 231288389 391 732 937385093 372676097 622014449 899 319572321 296 161571478 654439786 606 670001098 384248590 422666120 71287988 707046643 17 705 890237000 54723614 256305753 901332937 497041626 407566380 52 157435453 592566788 941 425927291 265347784 77732266 63064402 683110217 37301769 242155937 248292386 80418266 800 149893081 7846637 280947786 147 380 341 290432813 725 169272946 231288389 950757313 425927291 705 938637117 791 903 543930181 732038509 624189998 121075473 211 852 505604507 591 958834567 306 463472330 468168409 250136885 370415433 89073464 1827168 848181926 542 695617531 772335588 883394947 480259433 633034791 652265348 367883729 308431084 860806653 641372285 147219198 114 365 551238034 510192994 161571478 169578121 732038509 913 430865747 351984045 59 334 132567905 820462779 600479810 24 297 424 913715131 471611905 121075473 971 452 80998348 584790396 155731220 576377966 131 804816501 988 690039293 129 164 263198329 746213531 419247204 304566371 94411085 48 972295874 264 454754675 818405241 116647042 181011230 868201351 999889600 64044003 774565069 804 343962987 683 95023636 529679406 173958780 86868526 696272847 153733117 809684001 752360903 2591083 891103799 195 281676935 54 775809585 95023636 640418711 695925644 183259116 311554006 357735711 780369952 905 748529163 588 147 366 441 150 887032969 471611905 557014053 510140564 751791188 78944071 175057436 427124378 307414947 685446819 821712677 392467605 935 468 419247204 823518565 571812901 604978051 828896080 336 186 898102333 482199719 988 614149143 587633677 279664671 90621422 430840670 557019352 567 612484774 793826951 163 37895355 894 227052116 720876584 94411085 642 191 187342644 9200261 716432033 826 613706907 683364021 593084528 453 133845054 279877374 524 978933184 39523837 208606010 278901824 505977928 198035066 15558196 183259116 490259472 652265348 86868526 313 732929057 670001098 971574946 465385250 107147247 963 355087736 34 236929594 774565069 477086746 84708556 860806653 400752854 355087736 231412948 449762261 863734093 259347596 809 745196112 774773656 589 895086985 565677864 547193379 979578913 609213723 581955618 86567488 359 308431084 961692520 197 465423715 441224254 347589470 111 789894369 68469980 301101064 851 20125390 262 95 429436449 950757313 44 977 454671349 488 939458768 648669542 500094404 593084528 650 39523837 838054435 105297890 227052116 745196112 555644669 513 609213054 817 318353561 209721596 723551462 761 956632420 325910984 162 48819428 588023548 185 392467605 868201351 854 156 38442167 938496097 163024964 351984045 430974086 430865747 173195557 696272847 875 308431084 493576353 64044003 890237000 157435453 436414064 945471160 633 839 405127266 878366736 591 377 861956207 378154747 805704091 26754255 339999570 898 32021993 938440973 565677864 506119814 656326405 88251046 289690023 971916852 165 754334092 371185370 372999620 907 331 127 94094977 832566170 343962987 153733117 734266402 325019009 889076216 339999570 470611082 465423715 690 256 140631476 445 861169280 347155090 535335054 762341708 91208198 272792024 15558196 301101064 542 191 231412948 229 365871502 613706907 128 750233156 955 108 750272869 657788742 520808770 358 538096002 260 997837191 685 988872191 670 652902050 474538470 877 281676935 427380314 393256312 878366736 773 310905896 774773656 355087736 166 857630218 460 660 263198329 258183223 79599416 652114327 160678923 857630218 455 893 84475147 914768354 813178718 873900773 907950446 647 978528800 234 8550863 734713993 654439786 624990630 734713993 293 854 347155090 150411702 816872695 548045151 294207194 444922450 375869002 595 697351024 725845416 32021993 898102333 10545 789326205 81062183 695617531 333143333 566 232553236 235151274 634938630 24 570338115 145336938 838054435 913242550 378778863 664745814 196994946 1827168 665341877 634 198621884 545 746213531 243345425 849064100 625701809 393218410 958834567 140631476 623 299357940 161 179980555 85 989 235151274 764096728 306 716432033 618298540 404009803 276900387 493576353 670001098 133 554658412 788 734448264 446145948 624 375927789 34301237 185030419 875236313 738 853772148 363290231 797149661 269985850 705014348 98971813 996048841 809475291 232 172 19232251 927467800 145941098 378778863 355039913 954103169 48677072 612792481 335303255 129473913 252153132 491 212505301 331 502516676 145336938 589 952272551 975 81062183 414057053 490259472 387 298 943008950 98971813 441 182333045 458 331824546 688542728 231 820332202 280947786 155731220 325536833 723551462 702 577007952 338837126 909 171 646 7537862 417287838 361421364 835 8813051 439854551 594 427380314 564159615 413 -1 718129899 252153132 131 993992449 342827008 201 367883729 13841380 681582058 861169280 190 384678538 48086638 725 869195525 652902050 805 375496397 679 294207194 520 183259116 972514823 713196042 825958247 907950446 596942770 718636351 847 107147247 166 33903462 805049067 710290423 784 477337284 333081593 66842524 869329021 270583318 444922450 54045945 183908093 915 867727273 738115841 748529163 91208198 800923723 626 860 439854551 880098006 227052116 232553236 434579431 407566380 659245009 795398160 982 142610325 699212976 816872695 280947786 643 757506952 688865271 751791188 296 372999620 14 553736420 110561899 287082385 560 398584008 988872191 752360903 138 567432934 127532808 75 20 269083857 825 800923723 807949290 438981204 504209596 567432934 805049067 618849633 454754675 255 517422940 663940847 939398799 479006197 432653384 347 33053098 943056984 745196112 688542728 799459255 276900387 263198329 15558196 615551819 219951578 657788742 369362289 564 663940847 745196112 256860909 24596432 756 531442354 322 569 100373969 849064100 871435007 147219198 716432033 989754188 68093116 668 639522229 142141502 120882525 41 564159615 205 866816759 491789143 262918725 710290423 513025460 952865008 922062638 721958784 996048841 253516569 326 434479191 674 54723614 978528800 101 965 613086508 108430558 691 721958784 951197672 863734093 873900773 800 637150199 940 56 506119814 842 972514823 595 253 817074075 162088232 436414064 701056542 307414947 166415923 67 332 487736353 886934838 594280111 741658807 737507051 499443963 395 952535151 93282954 37895355 609213054 111 674 684444395 145336938 622014449 551592960 204 932285673 851 417 1575559 867727273 422666120 371185370 421884304 577007952 222 339 477086746 818405241 923742125 333081593 11 122256557 996048841 597532459 427124378 380075508 467 43591040 580 554 122256557 454754675 455 173 145336938 170962622 642 148343784 727725878 867017453 379021826 297901069 392049320 218373067 759518315 499368958 477337284 479661466 407 313 393 481 47434338 218502949 422666120 175057436 928229728 517422940 869329021 235151274 622014449 136248093 79599416 624301926 38526569 685446819 890165630 517422940 581955618 723551462 903226349 313868888 675041776 940 219 732929057 459 680 477337284 248 552 108494849 470045024 205018974 816872695 941 108 65111958 124549126 810 335 754334092 907950446 873087829 800 7846637 145941098 798 531442354 739730662 271 734448264 284 548045151 393256312 232553236 167540046 700476452 88205199 612484774 919693970 158 943056984 467322083 513025460 907631891 145336938 645779254 650 464289454 552724692 645779254 33903462 615551819 936 759518315 677644631 145336938 196994946 576377966 589075597 585 83 294207194 762341708 655 28635126 576 688865271 334 318353561 477 513025460 903226349 436 471966566 846410693 309746518 695925644 813178718 797149661 298 375869002 730496353 491789143 411736794 417287838 734266402 650326726 32021993 457908107 720876584 745196112 666 355732561 297901069 999889600 282692654 600479810 300643186 801260973 279664671 941794856 966358951 77 588023548 541035280 112187572 279480133 887859867 729320492 385 468662786 848181926 363290231 710290423 226772138 799158428 223 39919329 764096728 6999164 146 372676097 372676097 48677072 933507092 757506952 378778863 382765550 325019009 365 596942770 565677864 253516569 252 956 265307442 153599292 418 670001098 792 679 9 666633123 989754188 943 513025460 886934838 811333453 891103799 78859502 548045151 603706365 559397285 969485187 65132084 606984444 529679406 756418971 848 948 499368958 520808770 978933184 487736353 871435007 90713262 64044003 77732266 296356322 384678538 434479191 645779254 531442354 493576353 540425911 913242550 242099507 441224254 280690667 46410727 205 24596432 80998348 442431820 916 996506222 374 799 904461495 774 123 309746518 400 801260973 276900387 129473913 561873263 219951578 987 750272869 13 762 548 832566170 884 141 298 680232134 238308414 170962622 217 30247738 43318401 163 520808770 50548018 548045151 439854551 59098079 390 659245009 90600712 960525987 336822513 976380303 996048841 548045151 905561198 153599292 178 938637117 313 90713262 529679406 53 242897422 795706128 985 688 477337284 774773656 405127266 807949290 467 198986228 829 729320492 716225287 895 366256794 774565069 565866719 61 187928226 1827168 374738151 9 747 928229728 409454013 413591339 832566170 994912259 250136885 799158428 875236313 867495149 283283198 970 307414947 551238034 937385093 690619816 188179256 785025451 779349988 493576353 976684614 188179256 198986228 290432813 124549126 95023636 98971813 927467800 587 392850273 999889600 356534892 743946854 243345425 540130780 490259472 557671641 1861620 54826492 369424280 511 523742857 907301325 397 80418266 645779254 782395438 563428748 774565069 498327150 615 957 738 412973000 590 685446819 400 806 943056984 618849633 178934187 21110038 701 242 24596432 577 732038509 388 196994946 102860860 366256794 553736420 531442354 757506952 959 273 559397285 74 299357940 122256557 982190248 360584203 126963422 504108341 408619248 690619816 232553236 88198072 283283198 526 543 520808770 655 878366736 747 346128706 626 235518089 78 279664671 599738581 640257700 828896080 110561899 735417053 402 101265212 6999164 789473416 740738219 509911814 315 203725867 133 185940227 98073919 456 371803472 465423715 746213531 735143631 179 901400271 897354169 983 180 422 102860860 378778863 683506145 530 883 555603904 374114531 809684001 423 954103169 976684614 946 609 624990630 190513116 32021993 265347784 993992449 219957318 531442354 500094404 952175062 410364233 153733117 878366736 11295424 454671349 114 206831541 891103799 987130097 365871502 198986228 218373067 173958780 478 45 153733117 856 878366736 767171602 645199066 873900773 807949290 393256312 135565213 1575559 20125390 294207194 471966566 208606010 294696626 517422940 866816759 505977928 492 441955509 916943464 323655646 706781241 387 879021283 644768132 347589470 717909925 821712677 710 71287988 772335588 931687951 952865008 938496097 372676097 812 3 93282954 105297890 828105104 63 414057053 297901069 692 88251046 215113193 438981204 280947786 374738151 476 288 183908093 809684001 958 725310670 110561899 157 457908107 818405241 817690053 688542728 928229728 219957318 48086638 460 467322083 47434338 21716059 338837126 439 673 215362606 243345425 27992190 587633677 730496353 214 681582058 278 302 547193379 370686813 489 941794856 615551819 615551819 276 897354169 449762261 866816759 392467605 601085021 790 84708556 425 59098079 208 323 269083857 129 251 449762261 789157270 732929057 465385250 206054045 423 534477464 911 206133076 274974844 688542728 378 537016815 156764 124 611 307414947 791881390 287082385 185 402005161 907301325 719639741 342827008 415 875 396 442431820 639 522 461634197 414057053 523742857 335303255 860760417 785025451 718129899 318353561 817074075 40 981 888 942 605491815 718129899 232 945471160 378126062 329920251 734266402 895123768 883394947 542514996 129473913 990 599738581 916624283 352813421 762341708 378154747 259347596 384340708 745196112 425927291 393218410 428 935835714 84 177017039 939458768 355087736 887859867 89073464 659216109 110561899 727725878 816872695 789157270 712335838 472892556 333143333 331824546 154 644712801 355087736 734266402 307650057 456 584790396 517422940 683506145 644712801 601085021 504108341 793126210 258183223 407566380 51932307 860 622014449 325432259 368382661 760303484 383443224 593084528 405 897354169 705014348 534477464 941 751865562 393495221 148343784 481095768 807 745196112 605288864 849294793 37301769 730496353 436414064 390232483 26 334 553736420 116647042 599523332 523742857 8692268 493576353 714506326 589 39048172 781 464 180019963 695617531 645779254 547193379 871 294207194 428 537180003 21263601 813178718 710108943 738 866816759 88198072 607179645 690619816 564159615 654 627105627 482199719 545 477337284 51932307 117 666633123 518 281676935 571812901 553736420 -1 637150199 784 713041886 869329021 441224254 875596010 251 621 609213723 789326205 479006197 427 325019009 983 566138605 775809585 48677072 708 269083857 185940227 124 530 903226349 823518565 319572321 423 492205882 878 477337284 402 198986228 147219198 390232483 313 867495149 664745814 875596010 686541684 437 609 810 266 782395438 748 520808770 758 696272847 499443963 77732266 67 81062183 886934838 181 665 179 402005161 680228173 147331218 59098079 371185370 471966566 832191033 628772869 482145421 -1 106932205 577007952 947634121 51932307 734266402 951197672 409 98073919 699212976 384678538 809475291 552724692 370347248 744 218373067 78859502 118125217 732038509 35616762 427124378 987 613522780 2591083 807949290 142141502 684734627 922550791 166057448 817074075 889076216 670 713196042 511 937385093 566138605 754030551 336751640 894 42 128309313 378154747 419247204 491789143 607179645 976380303 664745814 338 231412948 801594169 536 165 821712677 313868888 716432033 817074075 867495149 951966857 906763981 939458768 495893906 468662786 564159615 548045151 795398160 86868526 234 325910984 612501617 817690053 294696626 772335588 194562916 505 121075473 308431084 919 862281989 78859502 180019963 218373067 252153132 467 65111958 36 420 307650057 287082385 596942770 379021826 142610325 673282909 147375074 372676097 697351024 305326269 187282466 216 457882206 789157270 48677072 950757313 33 647 279936610 809684001 185030419 332 54 601085021 688542728 379021826 132567905 342827008 857630218 919693970 231401159 996048841 69614183 800 872174286 89073464 640418711 319 384 913715131 551592960 740738219 659216109 488355649 274853174 244208872 570388236 99 276900387 447 754030551 603706365 34 907301325 723 31562571 430840670 951 967468092 474 312 774773656 147331218 563428748 933507092 941794856 517422940 705014348 692312576 219957318 671 173803659 645727331 376 365 88198072 718636351 438981204 339999570 19 823518565 280690667 41582470 430840670 333143333 444922450 883 656326405 37301769 716432033 214515745 232553236 231412948 306 982714779 144 445796727 148343784 854745611 434362954 50548018 474538470 417141792 279936610 530 762866431 471611905 430840670 89073464 187257798 677644631 47434338 948127215 603706365 63064402 98073919 923742125 785025451 734713993 735143631 813178718 20125390 238308414 541035280 710108943 651 220 173 789894369 145336938 557019352 390232483 587 140631476 737654628 650326726 712335838 554 613522780 166415923 343962987 412973000 209769922 471611905 209721596 640418711 690619816 570 710290423 421 520 624990630 667 400752854 542514996 618298540 912 316 557014053 932285673 225 1827168 692 80998348 149893081 875236313 161571478 431879635 713196042 279664671 157487018 680 105297890 729156523 38526569 492205882 873462667 215113193 599 545 250136885 727761698 235 332 398584008 37301769 93282954 463472330 527507141 368704676 113 65132084 607807067 622014449 650 339999570 690619816 393495221 60 38442167 219957318 701056542 150411702 206088997 121 111760960 130188717 827 923742125 235 677644631 366256794 969 97 880 238308414 613522780 347 988872191 961692520 564159615 438981204 618849633 930690244 201 695925644 506 842041675 927467800 470611082 821712677 119 706 634883913 767171602 832566170 190513116 878366736 21716059 81062183 688 779349988 898553 273109631 577007952 538096002 945471160 317 789326205 652 224207218 472 553736420 210 409454013 609 995573041 304 177017039 959 208115388 930690244 677644631 471966566 279664671 456905914 21110038 459 993992449 236929594 6999164 666633123 374738151 238308414 897 366256794 697351024 576377966 59098079 775809585 422666120 39523837 959 664 432653384 371803472 809684001 69614183 297901069 709968046 978164011 86868526 301101064 253 781958720 634883913 550 308431084 871435007 789157270 928229728 195 366256794 356982167 898553 952865008 378778863 248292386 848 379021826 898553 960525987 371209335 311 456905914 477337284 512533542 370347248 48677072 886 100433187 122256557 411806530 183908093 318 566138605 527507141 972295874 889076216 897354169 684444395 482199719 413591339 222 125 817074075 789473416 970062456 953 384340708 848181926 676 374937360 666573288 21716059 223 939398799 96 651 592 379021826 434479191 6620902 94 480737544 160678923 617 683462460 520808770 305326269 710 735143631 35616762 263628924 123 895123768 28929767 -1 878366736 751791188 805704091 371803472 988 323655646 247279147 510140564 257 529679406 294207194 517422940 206088997 269083857 645779254 996448486 723 43591040 566138605 728 68469980 742044103 280947786 916943464 274974844 932611793 680695712 142392058 725845416 27992190 472892556 937385093 685446819 542927779 106932205 304 111760960 321518363 719639741 384339361 35616762 964665256 719639741 762 286 390232483 288 665341877 180019963 967 799459255 485631084 485631084 584474774 424 206121309 471611905 493576353 43591040 405127266 392467605 552724692 339999570 939458768 478 380075508 81062183 593084528 347589470 94406529 183259116 430840670 525843580 943008950 2591083 625791403 697351024 647 65111958 696272847 331824546 6999164 554658412 333081593 307414947 554658412 119 69614183 157435453 713196042 369362289 783 510192994 976380303 454754675 754 648669542 465423715 259347596 434579431 81062183 313 234 730496353 873 811333453 809475291 457908107 627 969676773 175261027 497041626 464 954103169 989754188 540130780 714 254091185 640 721958784 875 265347784 529 402080873 517422940 -1 274853174 117 705014348 920308421 301101064 884 705014348 297 690619816 844 431879635 279877374 598640728 868488629 751 -1 5403924 563 432653384 906763981 336751640 419 650326726 437719154 157 209769922 634938630 913242550 269083857 577007952 51932307 606 750470605 74 907631891 192939551 953 477 888462586 50548018 825958247 579 716432033 921154357 203 818405241 47434338 102 219957318 513 253 13841380 65111958 204 648669542 996048841 50548018 392850273 89073464 243345425 240 307414947 718636351 107147247 857630218 677644631 629 793126210 502516676 206054045 517422940 723551462 739730662 96443153 636 84475147 983456086 853772148 24059943 742044103 615551819 563428748 110561899 805 49 464289454 203725867 402560617 499368958 555603904 115917228 315 746 305326269 20125390 752470678 952865008 22 331824546 21 652902050 22 66842524 716432033 465385250 656389084 102860860 166057448 652902050 603706365 479006197 402560617 562596936 630 360 128 363567713 325555210 849064100 315 480259433 553736420 334 541035280 408 932285673 208 198621884 841425041 190896064 616 956632420 948127215 119 605288864 244208872 612484774 718129899 594 497565877 212612975 383443224 994912259 214515745 95 35616762 487736353 959 756882312 505945203 823518565 708001977 735143631 907950446 780369952 270583318 489837102 792 805049067 594280111 809684001 878366736 480 958834567 90600712 980 641372285 487 743946854 537016815 427380314 258 188179256 438981204 166057448 473 605616025 126963422 509911814 76 781958720 95023636 764096728 209769922 589075597 861956207 463472330 678 676 271011833 35616762 607720488 462590682 149893081 799158428 480737544 -1 90713262 31562571 520 979578913 799 628772869 801594169 996542074 804816501 932611793 657788742 69614183 408187156 352813421 751865562 817074075 593084528 357 685 575033536 374323399 599484641 520808770 985523575 211137295 628772869 39523837 959 465423715 169578121 329920251 677644631 991 505945203 641372285 741 291 361421364 304566371 325019009 81062183 115917228 499443963 336 505604507 365871502 140 641 948127215 525843580 875306288 513025460 710108943 24059943 643835833 845 315 419247204 895086985 724345037 33 658076052 379021826 279480133 29 732 960525987 690619816 673466602 153599292 644 190896064 873462667 142384508 490259472 338837126 774773656 311294439 206831541 828105104 916943464 819242395 905561198 645 63064402 352813421 351984045 435 43318401 537016815 294207194 652 314 468168409 449762261 555603904 647 111760960 284 411736794 248292386 887032969 745196112 333143333 537180003 178934187 683364021 451 641372285 212612975 923742125 819242395 873900773 166415923 90621422 127532808 437719154 227052116 430974086 111760960 542688502 169272946 891103799 515 157435453 325019009 51 299357940 434479191 540425911 159 538096002 535335054 414057053 329920251 898 390232483 467322083 214515745 552724692 145 993 592566788 564 737654628 922 342518623 816872695 224207218 231288389 274853174 444922450 46410727 315 607720488 91995194 961692520 523742857 867727273 663940847 759518315 939907162 94094977 983456086 699212976 385 932611793 146 245 641372285 136391292 664745814 190323346 50548018 849294793 331824546 609213054 486026824 124415720 118125217 175057436 993992449 997837191 341 639435507 321 505604507 187282466 695617531 188 743946854 15 846410693 801594169 821 584 375869002 356473154 412973000 53 531442354 993992449 94 23 111760960 248292386 381 169272946 673 440028642 784 557 457215301 525843580 588023548 194562916 592 169578121 709968046 732038509 497041626 321518363 920308421 100 54045945 517422940 580 211137295 188179256 523742857 890165630 209769922 234533156 584790396 612792481 408619248 836 904 775809585 142141502 579 609213723 147219198 714 976380303 943056984 560456543 311554006 135565213 430840670 875236313 804816501 607720488 618298540 262 825958247 120882525 8813051 719639741 318353561 679974875 767 135565213 471966566 279936610 336822513 795887943 840 477830025 523 832566170 143500123 732038509 206133076 546075498 388 173195557 794667434 130188717 677644631 290432813 961692520 970062456 323655646 819242395 919 169 542514996 456905914 404 857630218 680695712 145162288 644768132 641 445 297901069 214515745 875 321518363 695617531 820 247395365 817690053 729 499443963 311 212612975 90713262 425927291 802 785 565866719 300643186 856 182333045 219957318 219957318 809475291 454671349 278901824 120 249 880098006 872 664745814 187928226 677644631 490259472 488355649 559397285 196 680695712 157487018 161 124415720 499316672 555644669 378154747 909 895123768 697029907 907950446 133 823518565 174767359 746213531 823518565 937701908 492205882 365 713196042 751865562 333 401341976 972514823 86567488 26 301 65111958 665341877 438981204 188179256 8550863 813178718 490259472 662 464289454 276900387 695925644 413591339 663879567 65132084 457882206 91208198 107147247 631496855 254091185 499443963 727761698 435345309 680232134 572 577007952 132 160 652114327 335303255 788 745196112 499232662 11295424 90713262 922062638 296 253 759518315 807949290 577007952 930690244 938440973 410 457215301 167540046 934 108494849 98971813 939458768 375869002 860 142392058 473653705 422666120 645779254 378126062 640 352118545 945471160 441955509 417 659216109 749717630 307650057 363567713 976 817 24 252153132 612792481 325536833 325910984 495893906 325 177017039 311 581955618 666573288 919693970 551592960 319 930674943 190323346 534477464 593084528 414057053 588023548 642 444 756882312 804816501 579 115917228 192939551 880098006 952175062 474 505945203 51932307 76887994 717909925 353 170 356534892 697351024 305326269 371185370 396 601 500 679974875 76887994 120882525 243 264 853772148 372676097 354 907950446 951966857 413591339 731128332 849064100 54723614 971779741 701056542 866 208115388 133845054 407566380 889 631 956632420 690039293 482199719 878366736 940965261 493576353 218 17 584474774 989754188 269083857 100742911 628772869 664 101 218373067 721 938496097 520808770 112187572 120 122651017 122 39919329 80 571 613522780 224207218 583 278901824 634883913 720876584 785025451 636 398584008 174767359 967 331824546 279664671 444922450 71287988 800 553736420 32 223 356534892 639435507 255 577 46410727 473 954103169 970062456 309746518 760657421 700476452 115 734448264 352118545 437719154 577007952 956632420 90713262 583928003 201 860760417 437 624990630 76887994 745 145162288 183 789473416 287460887 361421364 700476452 500094404 336822513 787 198035066 860760417 920440338 63064402 166415923 675431728 400752854 410364233 913242550 46 618298540 885617968 198035066 252153132 613706907 101265212 523742857 886934838 860806653 774565069 795887943 737076138 599 104 451 6999164 697029907 336751640 923742125 623 283283198 686541684 830 774773656 897354169 986365957 177017039 477086746 177017039 996448486 713 28635126 541035280 224487240 801 633034791 526 314 801594169 854 55 838054435 143500123 365871502 409454013 335303255 403740650 609213054 316 890237000 318 564159615 156764 804816501 729156523 715073642 625701809 422666120 564159615 357735711 842041675 382765550 719639741 650326726 416 48 289690023 581955618 23 100433187 386 47173681 164 796550976 571812901 727725878 750272869 467322083 190323346 969485187 690619816 160678923 974 283 93282954 206133076 638 314 543930181 369264804 789157270 37895355 31562571 236929594 547193379 581955618 541035280 257 370347248 996542074 560456543 117633124 374937360 685446819 425927291 209721596 11 895 127532808 713041886 680695712 263628924 470611082 512533542 491789143 861956207 837 394 658 762866431 984629297 907950446 692312576 374323399 498327150 219951578 421 488355649 398 89 974 325910984 541035280 145941098 88198072 181011230 906763981 465423715 471611905 456905914 584790396 274853174 607720488 907950446 622 124549126 968 242897422 169272946 683364021 504108341 718 789 163 740 614149143 375927789 477337284 683110217 584474774 898553 887859867 605 898553 198986228 932611793 265347784 251 371185370 621 431879635 142392058 555603904 537180003 493576353 347 265307442 430840670 890237000 331824546 76887994 954 614 838 604 801260973 789476776 479006197 163024964 363290231 540359278 627105627 863734093 422 167540046 899959027 880098006 886 65111958 467322083 198621884 666573288 817690053 391102363 237 461634197 140631476 9200261 775 84475147 342185429 126963422 51932307 534 628 291638371 932285673 624990630 47173681 504209596 739730662 280690667 480737544 719639741 108494849 414057053 639522229 80 55 166057448 145941098 547 806 59098079 335303255 817074075 512533542 238308414 976684614 65132084 175057436 846 890165630 374114531 436709999 408187156 663879567 235518089 601085021 997837191 930690244 708001977 817074075 1488804 732038509 748529163 987130097 557019352 710108943 257003592 994912259 470045024 709968046 392850273 555603904 35616762 135565213 69984825 886 269083857 -1 857630218 841 915 374738151 19232251 311294439 920308421 626 446145948 576377966 33903462 329920251 43318401 422666120 629344246 487736353 482145421 951197672 612 570388236 727761698 59098079 84521425 746213531 759518315 781958720 470611082 183908093 612484774 -1 538096002 648669542 31 868201351 656326405 294207194 41904208 465423715 697029907 362 467 399 244 993992449 764096728 970 887032969 614149143 564159615 875306288 145 169272946 928229728 35616762 367883729 206121309 536 817 54045945 506119814 718 215113193 734 321518363 525843580 111 218373067 532 547 446145948 523742857 127532808 9 510192994 857630218 31 837 812 47434338 679974875 96443153 970062456 342827008 872174286 325019009 741 107147247 721958784 90713262 675431728 122256557 120882525 553736420 842041675 43591040 238308414 988 561873263 473304340 873462667 187257798 278 987130097 7 542927779 28929767 356 738077433 914768354 828896080 236229513 907950446 717909925 622014449 321518363 411806530 897354169 765 657153133 585 457215301 161571478 342827008 759 378126062 617 331 718129899 827 149893081 263628924 142141502 732929057 160678923 174767359 347589470 690039293 187282466 145941098 256305753 346128706 422 559397285 224207218 712 209769922 279936610 534477464 764096728 734713993 38526569 346128706 21110038 29387516 370347248 806 342185429 759 142384508 380075508 680232134 252153132 732929057 299 601085021 185940227 625 504209596 832566170 464 754891992 610 113 393 581955618 654 779349988 66842524 100373969 124415720 901400271 91208198 21716059 556 190 912 489231836 465423715 875236313 600479810 796550976 27992190 374738151 940965261 51932307 785025451 434362954 501255084 612484774 477337284 794 534477464 719 198035066 932285673 983456086 378154747 916624283 986365957 452 9 733 971916852 24059943 762341708 258 368382661 968 347589470 772698388 795398160 861169280 95023636 718636351 693 697351024 673282909 124415720 318353561 797 618849633 287082385 926 189721383 294207194 720876584 945471160 294207194 418 231288389 901400271 54045945 885 873 136391292 670001098 680228173 648 72 30247738 898553 617 860806653 263198329 527507141 174767359 111760960 723 497 21716059 71 759 274853174 43318401 127532808 659 566138605 169578121 822 84475147 729156523 745196112 937385093 215362606 948127215 310905896 652902050 218373067 659245009 280690667 366256794 695617531 48677072 840 149 537180003 454754675 242099507 942 517422940 461634197 825958247 380075508 323655646 279664671 15558196 877 187928226 463472330 886 453021299 577007952 208009449 772698388 631496855 374 325 31562571 136391292 370686813 444922450 344303507 866816759 690619816 407566380 801594169 599484641 355087736 134 94406529 956 587633677 677644631 767171602 539 652114327 815 914 280 280690667 441955509 938496097 436414064 877 203725867 561873263 599523332 867 158 878 732929057 739730662 325432259 956632420 993992449 689523292 32021993 39523837 133845054 659245009 679974875 100 370686813 824 409454013 287082385 918 737076138 78859502 930674943 680695712 683462460 281676935 510 261 472892556 166 933507092 461634197 615551819 408187156 849294793 597532459 685446819 8 618849633 823518565 464289454 954103169 107147247 863734093 541035280 914247224 681 287082385 465423715 517 531442354 964665256 504108341 779349988 407566380 565866719 477830025 117633124 916943464 960 854745611 605616025 903 879 615 555 868488629 947 664745814 948127215 809684001 982190248 488 652265348 182 28635126 392049320 457908107 248292386 227052116 213 774773656 713 750 796550976 742044103 372999620 198986228 854745611 205018974 612484774 939398799 100373969 144 952175062 460 656389084 51 282692654 108494849 417287838 19232251 391102363 547193379 311554006 457908107 657 172 208009449 920440338 922550791 122651017 402080873 250136885 637150199 789476776 700476452 432653384 734713993 493576353 252153132 659245009 563428748 590730703 194562916 497041626 951 6620902 772335588 890165630 697 46 673 675431728 634 198035066 419247204 115917228 44 323655646 318353561 433290682 445796727 555603904 609213054 67003584 511 986365957 427380314 400752854 310136979 299 482145421 411806530 964 473 215362606 670001098 175057436 250136885 760657421 616 641372285 713 445 207 979578913 523742857 907950446 952 927467800 422666120 18 384248590 869195525 521 688865271 38442167 531442354 789894369 780369952 795398160 398 601085021 86868526 867017453 879021283 115917228 838054435 224207218 750 794667434 861169280 90621422 457 816872695 562596936 757 498327150 299357940 644712801 499316672 504209596 734448264 555644669 723551462 663 232553236 816872695 556167411 27992190 124549126 979578913 33053098 25 529679406 527 54826492 145162288 542 272792024 717909925 663879567 553736420 631496855 331 849294793 -1 935 564159615 24 235518089 659 214515745 128 351984045 214515745 662 80 504209596 740738219 374323399 86868526 525 427 714506326 852 361356699 413591339 21166510 715073642 150 696272847 371803472 352118545 820332202 126963422 153599292 -1 768 804816501 707 37895355 706781241 922550791 72 793126210 715045953 140631476 765 601 699212976 28929767 848181926 790 553 871435007 603706365 361356699 572 577007952 13 152585716 540 959 65111958 168 631 159 367883729 299357940 91995194 705 724345037 732038509 378154747 631496855 945471160 916624283 864 363290231 987130097 848181926 551238034 296 531442354 614149143 772335588 527 703 889076216 116 454754675 491789143 401341976 969676773 280483850 116647042 90600712 166415923 518 828896080 935835714 639522229 127532808 719639741 279877374 594280111 513025460 297901069 203725867 130 131 737076138 982190248 570338115 436414064 30247738 256 32021993 795398160 211137295 206831541 517422940 370857163 205018974 279 656389084 218373067 350 429436449 926 487736353 657153133 322 634938630 338837126 666633123 987130097 218502949 247279147 421884304 48819428 613 870 -1 291638371 277 244208872 498565394 594280111 472892556 675 969485187 583 675 252153132 807949290 173195557 675431728 206133076 68469980 13841380 206133076 577007952 271011833 634938630 750470605 121075473 971574946 482199719 412973000 325432259 512533542 24596432 130188717 650 363567713 500094404 303 542514996 227052116 145336938 219957318 236229513 329920251 749597500 55 280947786 568 894 117633124 372 79 709968046 378778863 166415923 964665256 31562571 761 939458768 325432259 52 895086985 102990494 725845416 600479810 464289454 567282677 453 643 156764 849294793 35616762 35616762 965 71287988 -1 746213531 639435507 971779741 933507092 699212976 567816714 250 8813051 47 144 729156523 215438568 502516676 601085021 493576353 7846637 743 793826951 212612975 59098079 941 180348334 352813421 136248093 828896080 467322083 135 680695712 259 214515745 380075508 37 201 333143333 253516569 708 6999164 692312576 901332937 859 37895355 742 625701809 413 175261027 38526569 71287988 422666120 322 333143333 656389084 333 480259433 347155090 888 501 720876584 634883913 446 593084528 48086638 497041626 955 193 127532808 857630218 922550791 538 442431820 214515745 321518363 48819428 24059943 174767359 34 393495221 866816759 156764 198 454754675 278901824 601 322 402005161 360151898 505977928 150411702 117633124 311 648669542 50548018 983456086 182333045 129473913 26 710 71287988 779349988 28929767 260 670001098 686541684 314 740738219 961692520 310905896 441224254 862281989 536 355039913 953 435345309 64044003 545 169578121 794667434 849294793 296356322 5403924 31562571 978 740738219 126963422 168 917 218373067 709968046 848181926 696538826 972514823 828105104 68 596942770 585 311294439 44 283 518 737 677644631 24059943 799459255 345 875306288 279877374 436709999 255 654439786 198986228 481095768 972295874 649 791881390 122256557 273 848 157 818405241 383 537525569 909 105297890 752360903 945 410364233 523742857 297901069 989754188 95023636 253516569 808 401341976 936 214515745 128309313 435345309 174767359 835 971779741 559 844 748529163 954103169 948127215 587 -1 785 313868888 712 531 540425911 238308414 96443153 421884304 346128706 247395365 893 891103799 903 756418971 502516676 575 776 642 485 602 780369952 32021993 384248590 760657421 163024964 8813051 166415923 520808770 485631084 8692268 110561899 901 126963422 284 793014352 196 995573041 419 943056984 564 712335838 752470678 398584008 7285952 795 97 246 689523292 71287988 707046643 174767359 863734093 812 417287838 110561899 789894369 243345425 735249489 323 607179645 727 419 828896080 308431084 155731220 101265212 861956207 24059943 727725878 895086985 737076138 644712801 374114531 939 970062456 477830025 495893906 607720488 609213054 538096002 434396593 767171602 732038509 299357940 71 999889600 927467800 554658412 353 450 558 764096728 136391292 20683010 587 51932307 735161947 789157270 133845054 427380314 314 659 985085442 206121309 919693970 718129899 576 15558196 27992190 236929594 698 63064402 242099507 853772148 890165630 375 453021299 746 762341708 713041886 904461495 278901824 961692520 489231836 411806530 710290423 273109631 -1 701056542 979578913 476601142 740 838054435 890165630 969485187 914 634883913 63064402 791881390 859899645 243621556 897354169 502516676 306 173958780 482199719 688 390232483 -1 628 567282677 280483850 978528800 758 561873263 729156523 840 686541684 393495221 605491815 305326269 8550863 584474774 75 203 906763981 482199719 118125217 227052116 624189998 680695712 93282954 457908107 490259472 105297890 392467605 346128706 47434338 970062456 105297890 310905896 32021993 13 374323399 917 173958780 603706365 241 367883729 579 140631476 95023636 639435507 729 618849633 417141792 8692268 499368958 699212976 710290423 922062638 814 243621556 443471521 434396593 978164011 198986228 569197642 100742911 177017039 868201351 887859867 941794856 378154747 600479810 789894369 820332202 208606010 472892556 828105104 505977928 739 356473154 607807067 715045953 907631891 276900387 618849633 961692520 578 325910984 443471521 398584008 593084528 282692654 488 523742857 120882525 324 342827008 214515745 425927291 616 80 731 978164011 754030551 510 921154357 8550863 548045151 240 468 63 897354169 757506952 285475432 384 393495221 968 743946854 601085021 729156523 904461495 551592960 548045151 563428748 665341877 187282466 804816501 175057436 754087296 705014348 939907162 943008950 553736420 855 738077433 561873263 59 243621556 820332202 859 891103799 914967290 461634197 292 716225287 754030551 799158428 352 665229761 548045151 78859502 24 13841380 468168409 938440973 570388236 805704091 540130780 801594169 759518315 194562916 740738219 250136885 928229728 132567905 566138605 697029907 21110038 88205199 549 491789143 48677072 140631476 474538470 565866719 964665256 537016815 857 269083857 730496353 555603904 799 907631891 491789143 754891992 243345425 878 181 301101064 347589470 7846637 485631084 409454013 506119814 411736794 905 987130097 779364609 839 965 169272946 648669542 981 741658807 247279147 28929767 366256794 71287988 271011833 244208872 231401159 866816759 960525987 88 342185429 862281989 700560202 624990630 301101064 557613887 446 537016815 688865271 7846637 785025451 652 132567905 468168409 271011833 847 420 928229728 166415923 368382661 849294793 374738151 187282466 576377966 325019009 654439786 966358951 735417053 769 969485187 449762261 708001977 367883729 548045151 113 28635126 403740650 764096728 39919329 993992449 498327150 243621556 146 468168409 352118545 166057448 683210834 733 594 360648201 166415923 84 392049320 320 895086985 640257700 112066211 335303255 486026824 861169280 421884304 380 243 285475432 633 449762261 985085442 945 79 449762261 240 613086508 282692654 567816714 421884304 976380303 971574946 951197672 540425911 837 63 486 124549126 8813051 639522229 269083857 789473416 172 263628924 613086508 751791188 280690667 982 670001098 21263601 943056984 194 208115388 642 349 465385250 335303255 895086985 639435507 461634197 688542728 68469980 297 268 650 950 89 101265212 90621422 48677072 244208872 126963422 557671641 304566371 907950446 903226349 825958247 331 30247738 651 868488629 801260973 127532808 215438568 975 985085442 774773656 180019963 473653705 5403924 246 563359293 666 291638371 776 952175062 984629297 513025460 198035066 690 577007952 254091185 645 561873263 366256794 273109631 967468092 820462779 361356699 819242395 594280111 124 406 785025451 402560617 102990494 122256557 124549126 285475432 509 361356699 160678923 828896080 389 291638371 952175062 54045945 548 789326205 20683010 939458768 873087829 805049067 832566170 594 904461495 633 263 414057053 838 740738219 875306288 231412948 759 490 779 282692654 279936610 100433187 796 260 13841380 964665256 788 242155937 2 142384508 983 760657421 941794856 435345309 904 274 557014053 310136979 785025451 300666789 609 311554006 112066211 445796727 795398160 828105104 947634121 580 570338115 77732266 612484774 199 754891992 489671699 360151898 567282677 142610325 294696626 588023548 804816501 360151898 238308414 285 308431084 730496353 268 721958784 594 627105627 276900387 888462586 772698388 612792481 627 96443153 965 89073464 100373969 765 732038509 609213723 624990630 583 232553236 878366736 838054435 187257798 625791403 9965165 272792024 353 923742125 408 433290682 368382661 612501617 401 351984045 754030551 700476452 136391292 231288389 933 789473416 767171602 592566788 352118545 242099507 167 570388236 695925644 966 903226349 725310670 334 54045945 709 941794856 181011230 690619816 762341708 268 39919329 716225287 142384508 458 952865008 854745611 554 384678538 289690023 972514823 257003592 996506222 380 979963115 139 443 122256557 198621884 106 849294793 756882312 398584008 764 239 517422940 715073642 644 657788742 796550976 7846637 637150199 270583318 659245009 938 239 727761698 832566170 607720488 507 471966566 73 989 709 194562916 901400271 734448264 502516676 126 576377966 172 802 43 848 820332202 932611793 95023636 124549126 215438568 324 547 903226349 355087736 260 638 969676773 782395438 607807067 333081593 232553236 639522229 873900773 863 772 321 623 391102363 441955509 41904208 823518565 677644631 939398799 243 691 939 129 699212976 10 923742125 696272847 876 914247224 486 108430558 628772869 21263601 650 474538470 612501617 400752854 169578121 940965261 793826951 923742125 24596432 308431084 258 274853174 493576353 573 762341708 309746518 160 265307442 147219198 958834567 610 402080873 641372285 163 371803472 979963115 509911814 699212976 84521425 892 866816759 90 132 427124378 225318291 967468092 868201351 731128332 329920251 492205882 853 259 523742857 879 8813051 609213054 235 801594169 495 735161947 174767359 789473416 697351024 411736794 371185370 756882312 108430558 943 943056984 500094404 988872191 972 342518623 281676935 8550863 352813421 710108943 681582058 935152487 970062456 875596010 128309313 196994946 659216109 969 475757272 969 361356699 913 590730703 739730662 10545 -1 569 797149661 919693970 176 19232251 645727331 51932307 368382661 584790396 269985850 310905896 683364021 420 256 477830025 754891992 102860860 477086746 8813051 735205243 589075597 985523575 183259116 431 779349988 688542728 105297890 945471160 839 366256794 111760960 702 102860860 727 659216109 862281989 100433187 764096728 581955618 680232134 413 930690244 664745814 437719154 598 489231836 726 261 336751640 779349988 901332937 283283198 440 329 811 707 136248093 657153133 902 883 112066211 368704676 112066211 785025451 118125217 357735711 191 914967290 799459255 438981204 767171602 978528800 898102333 751791188 157435453 657788742 498327150 751791188 919693970 224207218 820332202 907301325 605491815 402080873 542514996 185940227 155731220 243345425 319572321 468168409 526 490259472 948 555644669 454754675 663940847 94406529 477 254091185 295 788150883 116647042 69 357735711 142392058 735417053 658076052 656326405 799158428 365871502 749597500 307414947 754030551 215113193 550 19232251 259347596 903226349 707046643 28929767 155731220 442 177 336 679974875 413591339 906763981 368382661 384678538 793826951 336822513 757506952 937385093 886934838 827 701056542 13 867495149 652902050 495893906 41904208 673466602 592566788 828896080 571812901 599484641 556167411 933 256305753 804816501 548045151 443471521 804816501 575033536 480737544 799158428 622014449 736 641372285 356534892 775809585 356473154 614149143 948127215 890165630 28929767 548 583928003 996506222 866816759 319 697029907 920308421 489 209769922 218502949 985523575 468168409 302 784 705 618298540 979578913 368704676 224207218 265 611 871435007 247395365 890237000 162 457908107 275 28635126 952535151 115917228 997837191 223 263198329 215362606 737076138 310905896 866816759 51932307 94406529 357735711 271 819242395 895123768 534477464 136391292 71287988 169578121 329920251 266 485631084 838054435 860806653 777 86567488 189721383 574 115917228 342 499443963 739730662 875306288 383 950 112187572 37895355 462590682 390232483 886934838 752470678 356982167 271011833 206831541 487736353 517422940 236929594 219957318 481 190896064 492205882 799158428 395 597 658076052 20683010 785025451 247 627105627 430865747 282692654 344303507 76887994 813178718 609213054 136391292 809 101265212 541035280 943008950 813178718 612792481 969 512533542 545 546075498 206831541 598640728 44 51932307 197 607720488 873462667 122651017 179 153733117 124549126 699212976 542514996 713041886 64044003 725845416 26754255 893 133 804816501 917 242897422 198035066 748529163 903226349 704 430 175057436 147375074 392049320 294696626 287460887 945471160 398584008 763 789157270 505977928 209721596 738115841 760 903226349 375496397 301101064 625701809 746213531 169272946 13 323655646 971574946 914247224 565866719 627 281676935 39048172 531 680228173 215113193 793126210 300666789 730496353 941 767171602 690 841425041 383443224 181011230 759518315 930674943 179980555 449762261 319572321 287460887 504108341 243345425 448 790 854 43318401 282692654 262 434396593 150411702 84708556 700560202 849 267 677644631 422666120 546075498 325536833 823 959 609213054 457908107 143500123 670001098 749597500 142610325 645 560456543 407566380 502516676 523742857 197 618298540 793 718636351 828 188179256 540130780 378778863 883394947 93282954 849294793 244208872 78 393495221 215438568 985085442 604 959 65132084 964665256 633034791 690 112 943 705014348 548045151 566 786 831 468168409 546075498 351984045 624189998 648669542 371803472 860 952865008 409454013 282 21716059 652265348 468168409 732929057 275 36 643835833 951197672 402005161 606984444 122651017 690619816 543 361356699 161426036 166057448 240 434479191 50548018 422666120 265307442 72 419 735161947 99 823518565 825958247 116647042 561873263 312 258 951966857 392850273 607807067 102990494 721958784 86868526 613706907 868 203725867 457882206 670 462590682 923 422 746213531 603706365 495893906 847 675041776 284 788 734266402 609213723 525 242099507 59 461634197 357735711 677644631 564159615 599738581 903 615551819 677644631 869 525843580 587821314 967468092 617 338 842 901400271 577007952 479 451 853772148 545 628772869 789476776 767171602 772335588 231 388 329920251 161571478 148343784 269985850 825958247 613522780 240 29387516 689523292 35616762 421 69984825 523 59098079 756882312 866816759 21166510 356534892 100742911 262 397 561873263 346 970 867017453 891103799 565677864 39523837 490259472 -1 138 8550863 678 150411702 791881390 994912259 155 546075498 729156523 81062183 512533542 402080873 366256794 89073464 314 895086985 117633124 211 187928226 677644631 124415720 417141792 521674165 118125217 356982167 192939551 916943464 499316672 147375074 916943464 805704091 538096002 593084528 242099507 472892556 708001977 235518089 644768132 430974086 335303255 393495221 342185429 378126062 867 751791188 10545 564159615 628772869 41904208 66 841425041 371 206088997 163024964 392850273 762946187 853 868488629 365871502 432653384 27992190 685446819 430840670 645199066 583928003 54826492 987130097 553736420 99 557613887 300 299357940 134 931687951 996048841 975 320 96443153 169272946 887859867 515 276900387 875236313 680228173 145336938 32021993 677644631 709968046 411736794 841425041 187928226 873900773 8813051 310136979 2 473304340 440028642 939458768 505604507 730 414057053 446145948 714506326 888 546075498 793826951 231412948 872174286 774773656 599484641 136391292 428 135 737654628 471966566 175261027 319572321 683364021 588023548 333 6999164 952535151 374323399 289690023 922 68 784 793826951 18 819242395 94094977 357 327 278901824 417141792 13841380 542 521674165 332 321518363 565677864 283 190 333081593 192939551 614149143 147375074 782395438 422 274974844 190896064 225 528 130188717 242155937 297901069 54826492 131 7846637 911 265307442 979963115 81062183 890165630 683110217 441224254 925 919693970 592566788 563428748 21716059 648669542 169272946 211137295 945471160 13841380 707046643 473304340 95023636 192939551 282692654 283283198 958834567 562 231401159 357 132567905 799 978528800 374937360 581955618 821712677 490 7 417141792 253516569 978528800 303 235151274 596 680232134 862281989 242099507 607179645 750233156 108494849 384678538 885617968 273109631 444922450 315 521674165 461634197 454671349 663940847 827 958834567 333143333 774565069 414057053 287460887 818405241 698 198986228 48677072 795398160 2591083 836 920440338 817690053 996448486 374605067 313868888 311554006 681582058 687851530 721958784 263 495893906 809684001 177017039 986365957 441955509 679974875 751791188 891103799 803 670001098 885617968 629344246 599484641 46410727 868488629 336822513 677 692312576 253516569 380075508 242155937 242897422 452 23 379 209769922 153 69984825 763 384340708 987130097 338837126 625701809 251 932 640257700 258183223 372676097 596942770 705014348 885617968 108494849 423 607 756882312 670 112 785 229 405127266 240 489837102 224207218 760657421 624990630 453021299 551238034 231401159 583 33 329920251 145941098 594 347589470 627105627 868 605491815 954103169 224487240 208 663879567 546075498 463472330 832566170 894 948 290 652114327 690039293 720876584 499316672 779349988 330 100742911 457 454 801260973 132567905 577007952 810 333081593 296356322 886 84708556 860806653 553736420 716225287 54826492 431879635 731128332 915 117633124 187342644 393 242099507 237 380075508 193 686541684 243345425 629 819242395 723551462 539 547 482199719 436709999 758 528 555644669 867495149 126963422 473304340 31 772698388 54045945 583928003 389 189 163024964 469 799158428 673 710290423 980 168 828896080 338 666573288 675041776 594 561873263 203725867 916943464 801260973 76887994 227 746213531 346128706 480259433 76887994 737076138 666633123 468662786 243621556 675041776 425927291 300666789 552 20125390 149893081 634 875306288 932285673 152585716 871435007 187928226 162088232 967468092 26754255 607179645 921154357 456905914 360648201 355039913 11 938637117 299357940 294207194 744 898553 344303507 688865271 939458768 613706907 310 91995194 442431820 160 461634197 779349988 6620902 212505301 401 367883729 920 871435007 6999164 344 400752854 50548018 366256794 491 117 132 972295874 224207218 252153132 175261027 369264804 740 629344246 50548018 140631476 919 51932307 351 897 6999164 417287838 205018974 736 269985850 935152487 715045953 910 263198329 618298540 472 825958247 212612975 785025451 907301325 817074075 226772138 370415433 192939551 579 569197642 347589470 474538470 602 748779499 670001098 313868888 669 258183223 773 976684614 526 821712677 -1 9965165 570388236 738115841 537180003 258183223 274974844 681582058 294207194 930674943 599484641 360648201 690619816 54826492 493 716432033 652265348 861956207 791881390 832191033 952175062 20683010 477337284 848181926 624301926 757506952 476601142 757578230 686 449762261 393495221 105297890 150 331824546 325910984 280947786 173 490259472 933507092 201 555603904 218373067 270583318 552724692 449 480737544 513025460 417287838 639 609213054 307 732038509 883394947 754891992 9200261 853772148 731128332 665341877 917 281 94094977 441 799158428 734448264 10545 596942770 664745814 695925644 408619248 551 605491815 879 401341976 133845054 720876584 59 274 907631891 964665256 300 504108341 999889600 180348334 179980555 473653705 489837102 575033536 448 358 799459255 834 795887943 312 665 745196112 537780009 272792024 878 976684614 31 465423715 292 581955618 54045945 920440338 352813421 398584008 958834567 876 515 525843580 356473154 657153133 789326205 738 901400271 187257798 795398160 100433187 929 887032969 329920251 971574946 81062183 323 674 383 982714779 629344246 688 101 796550976 793 605 564159615 299357940 352813421 21166510 781958720 679 140631476 35616762 746213531 978933184 489231836 576377966 940965261 212612975 643835833 68093116 857630218 211137295 160678923 832 242099507 612792481 862281989 343 956632420 783 547193379 242897422 152585716 158 487736353 577007952 558900214 727 865 365871502 278901824 347589470 978933184 161426036 907950446 910 922062638 762946187 832191033 651 226772138 613086508 890165630 512533542 589075597 886934838 933507092 847 39919329 513025460 166057448 935152487 136 529 356534892 468662786 350 122651017 695617531 996448486 421884304 107147247 673466602 475757272 477830025 713 927467800 265307442 106932205 252153132 39 904461495 879021283 202 417287838 989 734448264 565677864 999889600 391 675041776 880098006 603706365 982190248 673466602 231288389 890237000 700560202 705014348 695617531 939398799 27992190 29 987130097 54045945 692312576 741658807 989754188 754891992 607807067 966358951 64044003 335303255 235 370415433 368 567282677 915 709968046 984629297 102990494 903226349 658076052 27 161426036 142 63064402 730496353 995573041 479661466 421884304 631496855 780369952 311294439 505945203 931687951 761 686 417141792 645779254 21263601 951 690039293 212505301 50548018 287460887 68093116 858 922062638 755 411736794 760657421 363290231 278901824 1488804 217 853 398 63064402 84475147 566 98073919 557014053 740738219 643835833 797 342518623 554658412 542514996 383443224 273109631 120882525 71287988 850 540425911 236229513 759518315 429436449 94411085 157487018 789157270 347589470 614149143 425 700476452 828 381 546 488 313868888 102 756 683462460 540359278 419247204 570338115 205 995573041 861956207 552724692 367883729 489837102 757506952 234533156 105 738115841 24 557613887 259347596 520808770 188179256 199 98971813 848181926 278901824 678 910 860760417 948 198621884 603706365 675 356982167 283283198 606252818 801 752470678 437719154 10545 435345309 231 584474774 680232134 360648201 470611082 407 555644669 670001098 372676097 692312576 673282909 48086638 483 581955618 323 157435453 237 735205243 898102333 310905896 760657421 981 457882206 314 684444395 153733117 593084528 436414064 689523292 695925644 517422940 548045151 814 624 190513116 535335054 760657421 347155090 86 878366736 873900773 112066211 288 361421364 959 170962622 805704091 555603904 5 283283198 48819428 686 493576353 987130097 573 999889600 633034791 309 346128706 575268466 972 442431820 529 417141792 493 758 670001098 374114531 71287988 922550791 124415720 76887994 748529163 593 706781241 280483850 946 677644631 551238034 395 501255084 142610325 937701908 542688502 122256557 181 804816501 456 715045953 521 111760960 883394947 834 471 462 703 456905914 136248093 933507092 869195525 700 378154747 96443153 846 355732561 39919329 425 173803659 21716059 913242550 263198329 645779254 66842524 102990494 567282677 465 552724692 351 866816759 664745814 185030419 762 683210834 737654628 152585716 227052116 417141792 311294439 677644631 390232483 287460887 316 81 900 325019009 424 7285952 725310670 64044003 128309313 479006197 875 861169280 -1 203725867 944 401 933507092 922062638 789894369 331 8 479 392 405127266 155731220 464289454 971916852 190896064 285475432 305326269 64 98971813 859899645 639435507 920308421 448 -1 244208872 682 375869002 458 804 811333453 451 94411085 166 247395365 685446819 138 351984045 227052116 472892556 593 752470678 921154357 849294793 729156523 48819428 236929594 398584008 157 816872695 831 710290423 970062456 272792024 198621884 571 339999570 823 333081593 738 779364609 48086638 901332937 715 34301237 532 885617968 236929594 779364609 454671349 336822513 391102363 427124378 170962622 737507051 832566170 455 457215301 978528800 80998348 873087829 996048841 643835833 883394947 307 547 805704091 421884304 342827008 823518565 339 613522780 713196042 779349988 219951578 599523332 889076216 709 287460887 357735711 989 607179645 787 500094404 37301769 546075498 675431728 161426036 948 95 393218410 772698388 552724692 231288389 779349988 589 989754188 525843580 601085021 887859867 557019352 839 28635126 212505301 611 331 291638371 84708556 2591083 310905896 873462667 436709999 721958784 7537862 645199066 278901824 575033536 169578121 505977928 521 440028642 191 791 321 310136979 983456086 313868888 604 187342644 51932307 987130097 93282954 624189998 769 190896064 838054435 500 526 407566380 538096002 41904208 353 674 979963115 565866719 534 46410727 772335588 547193379 30247738 122651017 757506952 757578230 393495221 609213054 828896080 689523292 294207194 155731220 311554006 479661466 970062456 634938630 971779741 601085021 485631084 198986228 157435453 584 46410727 820 345 823518565 609 392467605 868201351 241 329920251 605288864 24 904461495 734 65111958 692312576 627 543930181 398584008 471966566 21263601 760657421 512533542 80418266 786 941794856 535335054 670 391102363 173195557 464289454 931687951 140631476 549 875236313 384678538 505945203 384678538 754891992 185 6620902 599484641 748529163 715045953 198986228 985523575 9965165 945471160 346128706 30247738 978164011 421884304 719639741 869 188179256 21 654439786 130600813 234533156 39919329 750233156 78859502 393218410 549 895086985 436414064 382765550 541 355732561 356473154 211137295 585 993992449 629344246 541035280 613086508 697351024 607720488 254091185 281676935 853772148 687851530 880098006 305 368382661 908 132567905 555 662 430840670 375 9200261 328 90713262 102860860 697029907 952865008 215438568 107147247 175261027 854745611 752360903 145941098 762946187 927467800 904461495 673466602 351984045 961692520 217 8692268 520 988872191 641 296 825958247 292 857630218 313868888 209769922 482145421 823 205 750272869 258183223 118125217 897354169 819 432 695925644 107 795887943 956 384678538 206054045 235 952535151 410364233 583 145162288 735161947 377 384 717909925 39048172 347 117 187342644 392850273 63064402 786 547193379 551238034 47434338 304566371 697029907 504 913242550 333081593 206088997 605 603 757506952 624 459 369362289 90600712 163024964 88198072 387 352813421 187257798 548045151 323655646 679974875 984629297 307 331824546 258183223 461634197 692312576 186 66842524 14 199 492205882 666573288 529 122651017 122256557 482145421 927467800 613086508 675041776 993992449 607720488 11295424 490259472 384248590 841 169578121 372676097 779364609 875 904461495 527 510 983456086 365871502 427380314 259347596 289690023 725310670 774565069 257003592 745196112 329920251 576377966 236 624990630 978164011 80418266 147375074 301101064 982190248 81062183 176 529 54723614 153599292 609213054 12741541 427124378 436 567282677 838054435 487736353 169272946 449762261 250136885 244208872 429436449 318353561 930 268 706781241 517422940 867495149 218373067 801594169 54723614 145 613706907 352118545 98073919 979963115 263628924 135 706781241 48819428 206831541 507 421884304 899959027 688865271 94411085 271011833 19232251 368704676 542688502 429436449 6620902 754891992 964665256 272792024 19 782395438 381 333143333 214515745 421884304 537180003 300643186 734448264 421 33053098 731128332 311294439 173803659 870 603706365 59098079 1575559 307650057 294696626 867495149 325555210 571812901 527 127532808 7285952 723551462 537525569 629344246 196994946 566138605 782 523742857 684444395 815 439854551 190513116 309746518 361421364 188179256 785025451 906763981 875596010 705014348 136391292 900 205018974 535335054 310136979 555644669 773 855 198621884 258183223 6620902 656326405 280947786 370 391102363 177 713196042 898102333 541035280 468662786 907301325 734362113 713196042 10 748779499 631496855 604978051 486026824 525 820 311294439 112187572 347155090 846410693 855 521674165 818405241 643835833 263628924 36 943056984 571 937385093 605616025 731 526 352813421 130188717 818405241 951966857 161426036 705014348 741 438981204 69614183 325536833 501255084 219957318 654439786 804816501 916943464 603706365 708001977 517422940 416 670001098 624301926 39523837 831 89073464 304566371 683364021 613086508 979963115 801594169 432653384 414057053 527 745196112 916624283 91995194 625 290432813 523742857 491789143 495 346128706 69614183 663879567 931687951 809684001 219951578 767171602 355 265347784 253516569 751 757578230 224207218 567816714 258183223 982190248 589 226772138 930690244 670 862 24596432 432653384 735417053 250136885 756882312 374738151 165 533 347589470 360648201 556167411 754334092 181011230 64 561 100742911 716 120882525 427 463472330 844 368704676 393495221 96443153 408187156 675041776 643835833 263 363 920440338 624189998 938637117 695 205 771 375496397 853772148 754030551 907950446 664745814 811333453 380075508 120882525 799459255 190896064 50548018 624189998 506 517422940 811 274974844 356473154 730496353 84708556 168 647 697 325019009 995573041 759518315 295 748779499 767171602 474 986 789476776 760657421 805704091 313868888 172 589075597 295 250136885 885617968 551238034 512533542 248292386 972514823 958834567 795706128 930690244 128309313 257003592 482145421 869195525 919693970 875306288 432 50548018 273109631 269083857 47 437719154 236 538096002 392 520808770 108494849 68469980 950757313 248292386 101 84708556 629344246 650 573 932611793 24059943 489231836 206133076 130188717 587821314 231412948 986365957 868488629 732929057 189721383 131 895123768 124415720 344303507 684444395 384678538 190896064 623 470 879021283 543930181 639435507 356 543 554658412 615551819 547193379 816872695 828105104 232553236 1 716 923742125 163024964 18 604978051 430974086 846410693 976380303 888462586 665229761 675431728 548045151 846 -1 869329021 505945203 971574946 618849633 390232483 752470678 803 701056542 603706365 134 246 746213531 922062638 102990494 717909925 526 983456086 309746518 779349988 498565394 407566380 733 699212976 71287988 622014449 707046643 806 844 60 361356699 492205882 205018974 537180003 593084528 576377966 623 265347784 567816714 849 961692520 276900387 379021826 36 562 889 118125217 785025451 629344246 -1 162 838054435 501255084 785025451 666633123 710290423 98073919 684 356534892 628772869 213 659245009 94094977 774565069 375927789 604978051 678 809684001 603706365 677644631 74 5403924 287460887 335 928 952865008 69 560456543 646 580 370415433 668 208009449 476 499 247279147 482199719 436709999 594280111 491789143 411736794 649 625701809 729 475757272 325432259 779349988 224207218 203725867 127532808 547 537780009 333143333 360648201 554 942 442431820 449762261 497565877 805049067 914967290 772335588 715045953 541 551 963 987130097 748529163 157435453 721958784 260 390232483 167540046 781 111760960 318353561 908 212505301 474 670001098 738077433 734448264 883394947 161571478 578 984629297 87 618849633 390232483 215362606 113 131 610 816872695 489837102 333 351984045 832566170 665 347 540 248292386 644712801 148 181011230 543930181 793126210 891103799 325019009 883394947 878366736 2591083 879021283 449762261 378154747 421884304 861 752470678 12741541 935835714 441955509 309746518 477830025 139 498327150 604 86868526 789894369 599484641 705014348 395 905561198 725310670 809475291 895123768 495 594280111 391 734266402 700560202 861 567282677 673282909 716432033 363290231 618849633 130600813 820462779 380075508 68093116 417 809684001 818405241 849294793 497041626 801 564159615 347589470 779349988 128309313 838054435 537525569 795887943 498 470045024 827 496 727 294696626 517422940 793826951 535335054 647 360 458 169 796 801260973 923742125 648669542 218502949 692312576 335303255 935835714 774565069 208115388 153599292 614149143 446 782395438 41582470 438 265347784 524 347589470 692312576 809684001 274974844 764096728 -1 512533542 817690053 235518089 657788742 47173681 738 183 847 675431728 718636351 854745611 542688502 120 696538826 -1 43591040 231 767171602 357 817690053 479006197 523 254 500094404 310905896 867727273 427380314 371803472 491 470045024 860 639435507 319572321 73 880098006 895086985 8813051 846410693 705014348 408187156 116 142141502 434 567 269985850 417287838 570388236 224207218 584790396 541035280 283283198 970062456 325555210 653010341 156764 775809585 557019352 198035066 567972641 140631476 280483850 954103169 265307442 640418711 305326269 590730703 291638371 970 675041776 163024964 734 515 81062183 489671699 432653384 526 729156523 331824546 607720488 727725878 289690023 719639741 67003584 612792481 759518315 664745814 499 645 67003584 898102333 907631891 398584008 926 69614183 730496353 280947786 446145948 899 153599292 235 770 -1 629344246 648669542 633 892 662 226772138 489 198986228 888 632544208 265347784 620 563359293 378778863 754891992 620 325432259 461634197 710290423 310136979 743946854 192939551 542927779 875596010 374323399 754 988872191 173195557 274974844 673 788150883 393218410 219951578 956632420 431879635 86 10545 953 37301769 767171602 84521425 78944071 978933184 512 883394947 525 248292386 972 729156523 839 686986728 498327150 88198072 453 361356699 824 198986228 518 976380303 414057053 411736794 304566371 313868888 189 548045151 654439786 504 801594169 878366736 586 878366736 888 124549126 567972641 537180003 490259472 599738581 920440338 441955509 436414064 434396593 961692520 930690244 696538826 251 976380303 588023548 5403924 314 712335838 546075498 173958780 995573041 796550976 898102333 218 23 686541684 124549126 383443224 198035066 932285673 860806653 956632420 379021826 157 699212976 652114327 815 544 928 873087829 211137295 793014352 525843580 378778863 774 9200261 227052116 218502949 43318401 982190248 793826951 945 691 30 378778863 231288389 732038509 873462667 94 559397285 309746518 128309313 361421364 369264804 505945203 558900214 802 360584203 589075597 148343784 130600813 555603904 243 577007952 664745814 772335588 37895355 163024964 730496353 110561899 606 675431728 38526569 869195525 360151898 597532459 930690244 446145948 652902050 382765550 434579431 68 325019009 377 883394947 158 919693970 12741541 189 183908093 612484774 707046643 486026824 271011833 699 551592960 90621422 641372285 231412948 443471521 799459255 781958720 640418711 732038509 599484641 701056542 211137295 69614183 247279147 817074075 556167411 941794856 145162288 675431728 124 242155937 21263601 499316672 243 135565213 -1 192 686 607179645 279664671 26754255 906763981 956632420 353 324 614149143 607807067 54045945 43318401 629 38 187282466 276900387 937385093 68469980 531442354 785 85 488355649 725845416 85 618298540 78944071 327 129 220 852 41582470 846410693 557 473 876 296356322 958834567 540359278 873 713041886 150411702 209769922 307414947 721958784 38526569 380 417141792 854745611 939907162 1454227 493576353 605616025 204 443471521 6 801594169 799158428 681582058 725845416 505977928 190896064 186 463472330 182333045 813178718 700 907 500094404 443471521 606984444 300666789 207 609213723 301 641372285 30247738 93282954 155731220 208 319 707046643 101265212 613086508 986365957 411736794 282692654 434396593 295 419247204 895 411806530 795398160 774 867495149 111760960 22 126963422 993992449 252153132 443 788150883 363567713 689523292 542927779 295 952865008 784 988872191 576 183908093 586 627105627 20125390 603706365 44 464 132567905 392850273 380075508 757578230 880098006 360151898 888462586 640257700 95023636 841425041 752470678 898553 716225287 303 513025460 718129899 958834567 12741541 542688502 135565213 -1 264 537180003 135 789476776 361356699 867017453 31562571 945471160 527 232 950 520808770 33053098 342518623 390232483 309 289690023 419 309746518 180019963 549 807949290 41904208 987 463472330 177 486 739730662 440028642 485631084 411806530 449762261 757 68469980 12741541 374937360 932285673 970062456 590730703 931687951 779349988 290432813 561873263 556167411 115917228 996542074 265307442 506119814 666633123 806 543930181 27992190 305326269 432653384 816 659245009 458 263 673 513025460 985085442 527 823 610 291638371 517 868201351 723 982714779 107147247 177017039 219957318 904461495 217 700 12741541 686986728 663879567 581955618 370 160678923 943056984 24059943 570338115 684734627 632544208 729320492 820 412973000 557613887 94411085 553 357 987130097 577007952 510192994 31562571 276900387 417141792 374 938496097 143 596942770 680 886934838 628 857630218 127532808 360648201 343962987 801594169 920440338 705 984 37895355 198986228 681 684444395 858 805704091 666 732038509 239 754 873087829 846 287082385 436709999 9200261 124415720 505604507 240 262918725 367883729 11295424 777 842041675 734 369424280 527 145336938 895123768 477086746 252153132 987130097 243345425 468168409 853772148 402560617 571812901 796550976 901400271 695925644 224207218 170962622 404 677644631 509911814 333 263 772335588 338837126 686541684 449762261 131 218373067 393256312 87 718636351 398584008 279 985085442 943008950 279936610 973 325910984 710290423 843 400752854 581 505604507 215362606 597532459 794667434 567282677 806 746213531 355039913 336822513 730496353 604978051 901400271 739 335303255 707046643 122651017 225318291 89 190323346 871435007 88198072 683110217 217 441 781958720 707046643 793014352 427124378 177017039 502516676 913715131 960525987 650326726 59098079 132567905 76 325555210 131 187928226 563359293 825 29387516 369424280 715 993992449 557613887 933507092 773 126963422 737076138 576 831 279480133 893 422 914 5403924 208606010 922550791 408619248 453021299 879021283 227 510 565677864 352813421 180348334 1827168 402005161 723 640257700 809475291 624 537016815 937385093 751865562 93 351984045 641 51932307 419247204 482145421 478 399 584790396 179980555 734448264 342185429 952175062 644712801 832191033 490259472 81062183 184 422 430865747 587 122651017 419247204 69 183908093 124415720 468662786 982714779 843 8550863 474538470 157435453 970062456 41582470 677644631 732929057 653010341 196994946 32021993 607179645 639435507 823 65132084 96443153 269985850 54045945 984629297 155731220 762866431 528 142141502 639522229 749597500 982190248 51932307 509911814 685446819 296356322 96443153 218373067 734266402 475757272 921 533 236 982714779 449762261 471611905 414057053 531 592566788 828105104 520808770 774773656 78 932611793 600 820 817074075 297901069 749717630 634 735143631 819242395 203725867 542514996 983 526 145 440028642 2591083 737654628 253516569 133845054 430840670 907950446 782395438 591 443471521 188 898553 94094977 868201351 869 846410693 401341976 564159615 292 120 500094404 117633124 972295874 867017453 363290231 939398799 685446819 935152487 738077433 374605067 91995194 940 162 37895355 939458768 860806653 688865271 449762261 517 430 713196042 94406529 190513116 627105627 930690244 54723614 311554006 363567713 997837191 548045151 861956207 921 825958247 828896080 453021299 869329021 492205882 278901824 956 548045151 436709999 648669542 80 699212976 633 163024964 20683010 558900214 853772148 995573041 490 887859867 160 478 108494849 670001098 780 66842524 633 996542074 24596432 297 361 413 644 212 648669542 577007952 895123768 365871502 368382661 247395365 922550791 221 67 68469980 695925644 757506952 823 565677864 449762261 310905896 967468092 710108943 825 311294439 78944071 482199719 190896064 506119814 393495221 445796727 978 615551819 488355649 841425041 997837191 485631084 78944071 6999164 212612975 546075498 592566788 828896080 989754188 575033536 439854551 570 378126062 304566371 541035280 583928003 593084528 325555210 247279147 84 77732266 468 457908107 752360903 557671641 250136885 497041626 982714779 597532459 920440338 541035280 685 445796727 525843580 419 24059943 279480133 169578121 729320492 372676097 189 905561198 454754675 645 247395365 133845054 809475291 756418971 112066211 994912259 744 547193379 77732266 477337284 553736420 913242550 68093116 131 947634121 183908093 8692268 645199066 325910984 540130780 589075597 145941098 352 675041776 887 927467800 748779499 418 956632420 747 177 476787818 789473416 675041776 112066211 898102333 964665256 506119814 976380303 180348334 91208198 262918725 560196332 477086746 735417053 628772869 710 242 218 739 382765550 542 675 854745611 838 76887994 690039293 181011230 356534892 560456543 190513116 365871502 403740650 754334092 751791188 890165630 252153132 180348334 860760417 985523575 66842524 613 269985850 689523292 347 940965261 763 735417053 727761698 304 108430558 72 231288389 613086508 112066211 11295424 666573288 403740650 631 920440338 132567905 67003584 581955618 754891992 338 711 289690023 440028642 838054435 737 551592960 299357940 825958247 136248093 735 878 584790396 989 868488629 841425041 705 757578230 369362289 557014053 220 587633677 398584008 67003584 939458768 914967290 522 128309313 945471160 557014053 349 967468092 209769922 713 513025460 190323346 194562916 305326269 708001977 414057053 169578121 490 840 979578913 111760960 520808770 407566380 625701809 869195525 185940227 907301325 716 824 101265212 29387516 258183223 789894369 168 700560202 384678538 888 387 1827168 434579431 167540046 294696626 849064100 474538470 461634197 801594169 126963422 135565213 21263601 891103799 658076052 497565877 242897422 645 150 227052116 715073642 999889600 652902050 51932307 726 347589470 167540046 680228173 346 259347596 842041675 319572321 274 932285673 68093116 575268466 564 7 751865562 439 714 898553 416 737076138 280947786 622014449 399 419247204 850 680232134 739730662 490 516 696538826 329920251 29387516 390232483 362 656326405 425927291 417287838 419 537780009 208115388 681582058 985523575 797149661 374738151 974 996448486 39523837 631496855 928229728 800923723 742044103 543930181 430865747 707046643 500 705014348 908 907301325 430840670 153599292 583 956632420 499232662 652902050 915 269083857 54723614 930674943 449762261 401341976 419 484 229 427124378 147219198 689523292 887859867 9200261 975 393495221 124415720 390232483 637150199 33053098 797 368382661 26754255 247 517 485 356473154 347589470 510140564 380075508 675431728 676 730496353 143500123 640418711 434396593 176 136248093 538096002 966358951 187257798 591 943 785025451 477830025 542927779 960 670001098 570338115 276900387 984629297 283283198 575033536 797149661 979578913 468662786 851 741658807 725845416 941 892 920440338 274853174 51932307 224487240 758 86567488 726 695 571812901 750470605 517422940 499 289690023 10545 54045945 716225287 454671349 961692520 250136885 902 454671349 308431084 887032969 94411085 247279147 38526569 402005161 966 91995194 431879635 749717630 63064402 290432813 863734093 215113193 947634121 357735711 709968046 917 497565877 521 889 734713993 421884304 987130097 256860909 274 325019009 483 497041626 606252818 622014449 231288389 206054045 501255084 209769922 834 907950446 988872191 470045024 107147247 750470605 307414947 945471160 923742125 361421364 234 640257700 497041626 274974844 422666120 727 967 190513116 576377966 122256557 972295874 760657421 12741541 909 442431820 194562916 198986228 77732266 791881390 971 203725867 964665256 639 548045151 156 150411702 869 721958784 479661466 273109631 969485187 556167411 608 391102363 972514823 645199066 407566380 175057436 205 283283198 132567905 675041776 999889600 229 576377966 54045945 590730703 290432813 361421364 534477464 825958247 30 310905896 422 94411085 162088232 563428748 554658412 115917228 540130780 985523575 926 388 -1 148343784 497041626 688542728 189 931687951 182333045 6999164 205 593 313868888 939907162 360648201 583 943008950 612501617 370 869329021 576377966 227052116 212612975 861956207 21716059 654439786 242 849294793 389 470045024 859899645 393218410 357735711 625791403 493576353 374323399 19232251 711 163 1827168 752360903 734448264 390232483 209721596 954103169 637150199 664745814 173803659 527 790 312 952865008 198986228 214 263 625 627 434 654439786 624189998 91995194 359 905561198 571812901 615 11295424 411736794 437719154 796550976 299357940 20683010 535335054 914967290 404009803 828105104 734362113 677644631 122651017 546 978164011 581955618 713196042 679 375927789 603 813178718 41 434396593 551592960 405127266 215362606 126963422 481095768 173803659 756882312 47173681 436414064 567282677 361421364 169578121 781958720 190323346 449 304566371 435345309 700560202 720876584 313 663879567 884 938496097 762 20 563 756882312 76887994 468168409 67003584 273109631 206133076 425927291 -1 143500123 32021993 624301926 279936610 965 222 107147247 26754255 956632420 945471160 618849633 130188717 1454227 801260973 567432934 950757313 250136885 844 398584008 897354169 263198329 782395438 513 311 960525987 130188717 -1 679974875 149893081 490259472 878 799158428 618849633 596942770 425927291 780369952 677644631 644768132 723551462 943056984 263198329 562596936 280483850 48819428 510192994 592566788 107 422666120 829 526 587821314 746213531 141 12741541 497041626 266 916624283 392 673282909 908 951197672 490 436414064 153733117 462590682 613706907 762946187 260 319 700560202 939398799 479006197 890237000 250136885 231412948 129473913 352813421 448 571 970062456 439854551 187257798 809475291 923742125 279 56 966 115917228 594 542514996 33053098 883394947 370857163 234533156 183908093 735205243 337 952865008 500094404 914247224 380075508 832566170 583928003 7285952 505604507 996448486 963 480259433 472 463472330 1861620 443471521 407566380 325555210 971 485631084 378154747 432653384 35616762 963 333 266 864 429436449 807 145 932611793 849064100 392 632544208 20125390 159 551592960 271011833 558 393495221 189721383 39 153733117 77732266 67003584 115 374 400752854 782395438 556 907950446 879021283 330 499368958 39048172 136248093 701056542 639522229 577007952 336822513 168 105297890 157487018 502516676 311554006 313 695925644 47173681 903226349 419247204 457215301 750233156 492 785025451 462590682 492205882 111760960 609213054 276900387 789894369 488355649 707 73 607179645 650326726 375927789 925 555603904 719 493 26754255 219957318 913242550 975 725 349 336822513 735143631 318353561 163 68093116 782395438 178934187 453021299 90621422 393495221 342518623 136391292 931 224207218 206121309 269 688865271 509911814 857630218 369362289 5403924 744 421884304 31562571 850 757578230 809475291 810 350 508 380075508 644712801 269083857 325019009 509911814 614149143 628 126963422 393 689523292 366256794 952175062 1454227 65111958 20125390 136 178 198035066 471 500094404 79599416 838054435 384678538 556 31 183908093 869329021 751865562 479661466 263198329 112066211 7846637 308 309746518 101265212 964665256 618298540 664 370347248 91995194 417 813178718 93 867495149 797149661 735 930674943 155731220 428 270 150 551238034 656326405 847 271011833 169272946 558900214 555644669 269083857 263628924 632544208 749597500 904461495 489231836 205018974 928229728 510 938 419247204 971779741 901 721 325555210 751791188 371803472 972295874 294 227052116 100742911 996048841 795887943 382765550 274853174 482199719 880 537525569 361356699 365871502 124 372 750470605 429436449 879021283 142384508 531 175261027 235518089 843 107 823518565 883394947 645199066 609213054 178934187 907631891 474538470 276900387 380075508 161571478 408 653010341 437719154 945 369264804 594280111 224 1454227 905561198 173958780 289 639435507 499316672 69984825 644712801 711 -1 371209335 58 958834567 325536833 281 873087829 984 110561899 817074075 21716059 422 370857163 683462460 296 67 625701809 971779741 271 459 51932307 598 517422940 -1 265347784 696538826 11295424 895086985 785025451 914967290 108430558 278901824 491789143 443471521 793 182333045 5403924 136391292 971574946 921154357 673466602 460 842041675 8813051 133845054 439854551 767171602 145941098 811333453 557014053 229 415 764096728 175 41904208 371209335 178934187 408619248 76887994 37 344303507 540130780 203725867 913242550 921154357 256305753 368704676 960525987 384339361 948 -1 583928003 506119814 853772148 343 231288389 363290231 706 842 15558196 752360903 278901824 970062456 734713993 37895355 183 485631084 484 849294793 238308414 41582470 916943464 953 338837126 12741541 952272551 33903462 19232251 442431820 -1 688542728 259347596 132567905 238308414 906 183259116 624189998 422 29387516 80 70 333143333 557014053 731128332 347155090 136248093 524 813178718 510192994 192939551 348 558900214 756418971 325019009 715045953 208606010 39 243621556 470611082 347589470 497041626 231288389 1827168 737076138 412973000 750470605 713041886 434396593 956 734713993 84708556 26754255 94411085 242155937 581955618 931687951 1454227 795887943 952 342827008 444 866816759 457 607807067 464289454 20125390 413591339 705014348 78 482 581955618 565866719 985085442 623 748779499 371 352118545 54045945 451 979963115 901 355087736 274974844 551592960 575033536 706781241 818 921154357 441224254 8692268 854745611 907950446 429436449 627 821712677 399 96443153 867017453 306 30247738 950757313 904461495 140631476 384678538 77732266 20683010 658076052 811333453 324 225318291 370686813 714506326 600 435345309 380075508 540359278 12741541 713196042 106932205 369 445796727 984629297 473304340 759518315 523742857 799459255 526 347155090 734362113 -1 368382661 719639741 760303484 479006197 1575559 29387516 180019963 956632420 422 429 680228173 177017039 183 162088232 477086746 512533542 124415720 224 996048841 481095768 807949290 725310670 168 863734093 789157270 253516569 788150883 179 20 618298540 734266402 166415923 725310670 245 43318401 243345425 653010341 789 979578913 311294439 242 886934838 935 470045024 984 136391292 433290682 464289454 627105627 889 873900773 625701809 964665256 741658807 434479191 785 477337284 539 683210834 967468092 39919329 457215301 648669542 208 202 153 546075498 903226349 859 739730662 565866719 612484774 937701908 497041626 15558196 923742125 950757313 749597500 84475147 646 956632420 51932307 634883913 133 869195525 742044103 215 735205243 431879635 605491815 556167411 110561899 738115841 793826951 276 542688502 110561899 319572321 360584203 937 501255084 512533542 567972641 401 920440338 930674943 12741541 71287988 384 203725867 748529163 628 8813051 632544208 750233156 299 978933184 135565213 323655646 557019352 63064402 618849633 380075508 663 231412948 477830025 327 411 737654628 853772148 43318401 442431820 794667434 978 945471160 873462667 247279147 700 417141792 795398160 140631476 143500123 247279147 887032969 360584203 81062183 549 665229761 77732266 659245009 684734627 86868526 542927779 21716059 458 921154357 218373067 112187572 938637117 547 480 904461495 741658807 37301769 215438568 612792481 769 600479810 563359293 727761698 695925644 442431820 387 943056984 448 860806653 67003584 457 705014348 163024964 11 311554006 568 705014348 823518565 756882312 402560617 24059943 577007952 228 528 942 637 583 493576353 198035066 285475432 492205882 462590682 904461495 284 645779254 118125217 888 91995194 952865008 818405241 76887994 169578121 622014449 821712677 182333045 956632420 365871502 880 321 911 913242550 402560617 432 422666120 685446819 809475291 6 656326405 520808770 11295424 621 68093116 206831541 209769922 467322083 329 675041776 948127215 324 679974875 658 418 939458768 63064402 651 800923723 198986228 370347248 737 862281989 462590682 697 232 872174286 147331218 19232251 407566380 897354169 291638371 989754188 35616762 819242395 246 514 80 965 581955618 940965261 873 832566170 374114531 989 887032969 294 697351024 756418971 371185370 177017039 893 342827008 235518089 765 167540046 880 47 928 966358951 947 54826492 419247204 331824546 401341976 254091185 524 725 10545 575268466 101265212 126963422 797149661 609213723 116 599523332 880098006 262918725 178 414057053 289690023 737654628 828896080 208009449 102990494 846410693 54826492 613522780 300666789 139 375927789 654439786 951197672 504209596 310136979 746213531 15558196 495893906 457882206 657788742 291638371 294207194 648669542 699212976 760 793826951 215362606 859899645 194 370415433 221 583928003 631496855 247279147 149 64044003 311294439 32021993 841425041 485631084 585 996448486 257003592 759518315 540425911 484 941794856 185 609213054 88 603706365 696272847 849064100 823 781958720 402080873 110561899 683506145 527507141 101265212 757578230 262 734713993 988872191 937701908 1861620 854745611 1575559 11295424 952272551 219957318 719639741 537780009 598640728 325432259 688542728 590 933 13841380 489837102 402005161 375927789 683210834 680232134 111760960 922062638 801594169 995573041 36 189 873087829 148343784 457882206 509911814 76887994 821712677 329920251 842041675 263628924 169578121 752470678 177017039 972295874 718129899 716432033 663940847 650326726 614 888 800 874 569197642 203725867 759518315 709968046 411806530 19232251 771 369 48819428 33053098 927467800 978164011 762341708 697029907 98971813 329920251 2591083 175261027 247395365 453021299 983456086 756882312 133845054 659245009 470 869195525 173195557 888 280947786 590730703 930674943 628772869 729156523 903 795398160 434579431 767171602 738077433 427124378 748779499 196994946 673 259347596 151 540425911 907950446 772335588 372 977 5 612484774 21716059 839 296356322 723 147219198 299357940 259347596 750233156 80418266 269083857 504209596 625791403 153733117 224207218 20683010 536 441224254 103 136248093 279664671 520808770 192939551 43 473653705 476 674 772698388 935835714 807949290 111760960 825958247 232553236 695617531 785025451 161571478 308431084 12741541 63 479006197 48218162 279 457215301 499 605288864 339999570 513025460 430974086 133 380 259 779349988 280690667 506119814 750470605 187342644 602 274 265307442 274974844 366256794 670001098 618298540 695925644 913242550 838054435 124 265347784 895123768 665229761 923742125 91208198 700560202 386 76887994 163 697029907 206 319572321 911 521674165 142141502 672 127 644 68469980 68 485631084 796550976 976684614 479006197 26754255 634883913 562596936 262918725 545 269083857 740738219 804 588023548 517422940 498565394 224487240 429436449 22 48819428 619 976684614 276900387 39523837 259 846410693 378126062 108430558 436709999 492 822 216 982 801 477 860 21716059 700476452 523742857 916624283 567972641 717909925 613086508 448 180019963 323655646 231288389 555 -1 185 7285952 446145948 100742911 279664671 280 183259116 632544208 883 970062456 719639741 775809585 347 145162288 895086985 329920251 624189998 6999164 300666789 571812901 801594169 727761698 360648201 695617531 142384508 470045024 798 15558196 537180003 449762261 446145948 273109631 351 279936610 679 618298540 748529163 374605067 291638371 248292386 785025451 115917228 913242550 745196112 927467800 988872191 161426036 571 488355649 643835833 947 622014449 468168409 569197642 780369952 633034791 203725867 791881390 411736794 724 436414064 355039913 788150883 11295424 624990630 764096728 745196112 139 641372285 157487018 513025460 683364021 932285673 648669542 32 39048172 430840670 995573041 562596936 979963115 754891992 280690667 979 948127215 906 667 895123768 7846637 501 960525987 958834567 80998348 652114327 7846637 318353561 23 797149661 849294793 752470678 528 203725867 817690053 541035280 345 130600813 528 218502949 272 631496855 653010341 54723614 135 208606010 204 203725867 127532808 870 373 224 568 832566170 941794856 976684614 710290423 242155937 279664671 532 710108943 50548018 995573041 735205243 212505301 689 143 695617531 47173681 576377966 565 939907162 713041886 307414947 319572321 208606010 110561899 805704091 454 794667434 21166510 937385093 901332937 217 776 694 342827008 206088997 231 65111958 713041886 913242550 538096002 238308414 447 461634197 305 956632420 961692520 481 260 628 161571478 654 841425041 367883729 355732561 961692520 170962622 435345309 979 101265212 957 234 799459255 697351024 862281989 546075498 509911814 939907162 567432934 950757313 169578121 506119814 289690023 312 37895355 497041626 795887943 443471521 426 652114327 997837191 767171602 537525569 633034791 571 356982167 797149661 218502949 383 132567905 904461495 43591040 355732561 802 98971813 462 356534892 430974086 496 48819428 169 953 34 970062456 50 68093116 449762261 67003584 338837126 506119814 180 717 403 467322083 21716059 185030419 491789143 370 979963115 269985850 297901069 183908093 347589470 378154747 90713262 502516676 853 969485187 408 689 194562916 371185370 391102363 939907162 370 725310670 152585716 865 615551819 105297890 157 599523332 869 398 526 152585716 818405241 447 788150883 115917228 54826492 952175062 464289454 452 920308421 15558196 269083857 71287988 287460887 542688502 877 509 209721596 323655646 734266402 177017039 453 63 594280111 732038509 126963422 477830025 961692520 262918725 421 318353561 734713993 27992190 291 10545 986365957 719639741 346128706 853772148 605491815 444922450 425 414057053 642 357735711 671 195 927467800 391 695 218373067 203 932611793 11295424 422666120 449762261 913242550 289 85 555 305326269 215113193 347155090 437719154 402 764096728 379021826 980 712335838 606984444 645199066 30247738 259347596 716 9 606984444 187342644 488355649 993992449 63064402 699212976 932285673 160 211137295 982714779 151 436709999 65111958 91995194 551592960 90621422 639435507 361356699 88205199 235518089 356982167 849294793 919 648 581 738115841 750233156 520 512 44 672 554658412 706781241 970 586 995573041 718 279877374 741658807 276 640257700 320 893 214515745 481095768 126 335 978528800 294696626 894 775 551592960 357 65132084 321518363 751791188 214515745 62 129473913 648669542 575268466 171 14 531442354 860806653 837 463472330 862 442 206133076 775809585 19232251 21716059 38526569 274853174 654439786 296356322 142610325 206088997 186 649 650326726 429436449 499443963 436414064 325555210 499232662 785025451 336751640 173958780 542688502 853772148 11295424 505604507 464289454 190896064 640257700 821712677 752360903 375496397 434479191 793826951 605616025 551238034 906763981 308431084 419 208115388 485631084 975 441955509 964665256 639435507 47434338 24059943 913242550 243 502516676 525843580 194562916 779349988 438981204 561 885617968 287460887 370686813 785025451 263 121075473 98 798 813 710290423 342185429 873087829 54826492 853772148 311554006 995573041 71287988 789326205 520 919 968 231412948 795398160 300666789 725310670 590730703 852 78859502 276 849294793 355732561 499368958 425927291 727725878 136391292 79599416 150411702 404009803 724345037 688542728 644712801 497041626 562 553736420