1000 10000 2 1 139293809 3 1 191782259 4 3 545251943 5 2 463458362 6 4 744811616 7 1 504663546 8 5 468376688 9 6 211522662 10 4 872917717 11 3 554262078 12 2 329618457 13 2 34841326 14 13 902331253 15 9 817061886 16 10 415138654 17 7 166129953 18 17 582953514 19 13 629998245 20 12 272876945 21 19 869480931 22 21 809997083 23 13 202449237 24 15 120659361 25 1 513496497 26 18 151360665 27 11 940878975 28 20 503744815 29 27 238418672 30 13 779866651 31 27 295659765 32 8 428983393 33 4 725725001 34 5 391662610 35 21 670406336 36 27 636829561 37 16 536401270 38 11 385266830 39 36 657654172 40 30 105306181 41 1 263267712 42 27 219443961 43 4 489829478 44 23 683908711 45 11 605647797 46 3 923872710 47 45 916416482 48 4 670200677 49 29 949836785 50 25 125877521 51 3 77983631 52 8 987237719 53 5 992232468 54 16 667326535 55 35 853087237 56 41 238698965 57 48 261962928 58 29 757927569 59 26 326241203 60 53 381296083 61 58 544163690 62 54 612145707 63 17 385635111 64 25 493765728 65 17 810176624 66 30 573413624 67 24 103162716 68 28 65681107 69 23 328694878 70 4 219584488 71 44 327989774 72 52 226913854 73 42 732497533 74 62 356627559 75 36 414894330 76 62 518317059 77 37 344070792 78 67 628624581 79 12 421681206 80 3 297837332 81 36 579548087 82 26 42377512 83 1 287371726 84 66 306491500 85 28 426639922 86 60 749327406 87 8 421546345 88 39 273891313 89 20 958899627 90 37 157755688 91 65 897686095 92 74 478296288 93 25 522177469 94 30 264279063 95 91 964568746 96 67 695221337 97 45 829524956 98 7 376817330 99 5 426370971 100 4 277598702 101 3 539167899 102 97 241789640 103 71 495877060 104 24 77167898 105 83 939791868 106 8 21512967 107 39 533569517 108 68 22871643 109 23 437957182 110 7 41055832 111 10 535919168 112 84 490757544 113 84 486428978 114 82 781565589 115 27 25486187 116 21 540100608 117 22 942224715 118 7 490575047 119 71 268112659 120 88 723602235 121 62 64551359 122 76 692496179 123 18 897566067 124 99 357209612 125 86 282964494 126 90 546919531 127 114 490684613 128 106 100407064 129 39 238487732 130 110 287661206 131 2 936408360 132 97 928580096 133 129 853212738 134 112 117238899 135 56 881092849 136 94 809739908 137 49 110811710 138 8 844847499 139 116 624470421 140 31 143344299 141 96 96765818 142 29 856390530 143 38 786565009 144 4 174515578 145 17 693096160 146 25 250733950 147 103 344989397 148 89 915789777 149 71 226304077 150 84 423830288 151 86 745112597 152 100 56766484 153 74 852147500 154 94 837497148 155 77 625004507 156 136 287893123 157 104 45734323 158 29 420109374 159 77 654524102 160 5 522812511 161 127 203440868 162 29 558103887 163 102 387801682 164 53 649097107 165 129 646275207 166 102 101597512 167 127 572074881 168 138 352258553 169 37 33055194 170 58 969833276 171 25 812283613 172 1 249505911 173 131 794661585 174 7 482664817 175 21 761876257 176 12 903758397 177 175 941705536 178 59 752813322 179 36 807990600 180 114 947374947 181 41 319221400 182 81 280056021 183 129 195020468 184 15 425636237 185 26 250845018 186 24 49298697 187 119 494280954 188 77 549262087 189 171 480195581 190 127 488073335 191 188 906947349 192 96 25037301 193 11 333605635 194 5 820328070 195 82 965069324 196 10 18767133 197 47 851238482 198 22 259303587 199 27 387938664 200 151 857439737 201 200 144285306 202 103 617824103 203 95 49470516 204 203 999718092 205 9 852878151 206 24 392722628 207 176 571046510 208 70 876323454 209 68 244664310 210 164 780614560 211 44 810033021 212 40 462712861 213 70 521821 214 163 520724840 215 125 62596528 216 28 373749819 217 150 756926195 218 58 318909348 219 208 12501659 220 154 133983747 221 156 32909517 222 119 119534689 223 63 244438882 224 83 360466717 225 224 449683403 226 170 300061930 227 192 865349165 228 141 527690043 229 13 479062671 230 7 523164252 231 106 253139430 232 113 794439848 233 172 464280466 234 204 994946970 235 100 50804816 236 194 358601583 237 147 743798510 238 65 152250803 239 13 324979662 240 75 622797556 241 201 342216762 242 48 8083253 243 28 159983077 244 156 42656223 245 150 634082992 246 137 529814100 247 64 697999025 248 114 295232511 249 204 640017967 250 136 27083994 251 36 865082125 252 205 346218576 253 227 374630403 254 198 307621179 255 182 789135280 256 60 835579173 257 190 397475790 258 251 999388711 259 167 24119000 260 93 537689108 261 141 707347412 262 106 798812164 263 250 175578964 264 105 370186872 265 146 955916795 266 66 920173933 267 41 960626895 268 219 673003310 269 231 12608541 270 141 937815185 271 27 823361170 272 93 994493194 273 219 585348884 274 140 733137163 275 240 53796573 276 14 748871115 277 70 97258024 278 163 730998363 279 53 29600751 280 184 987450871 281 47 575143100 282 116 723906647 283 175 467468527 284 267 838368472 285 262 968226806 286 226 316055062 287 84 186672343 288 97 881582066 289 265 495025844 290 259 876764484 291 95 917915579 292 45 187220671 293 132 762035217 294 173 61517268 295 155 860825260 296 108 520469109 297 264 943914163 298 275 164437146 299 280 842337358 300 139 167015953 301 128 779881821 302 234 308917369 303 294 743425185 304 153 629384102 305 126 304719763 306 193 882857052 307 3 857333550 308 52 81425792 309 169 853245686 310 53 60670146 311 94 347072873 312 45 329899181 313 191 877963785 314 219 366066237 315 15 329829448 316 300 724570359 317 24 992294031 318 129 685164251 319 6 412955863 320 293 851249510 321 88 630323436 322 96 535007996 323 197 307689661 324 322 20517386 325 78 653698718 326 305 742527951 327 90 992210176 328 22 850991128 329 262 82593282 330 237 550880531 331 31 960031826 332 72 341994122 333 105 98670207 334 329 136165456 335 173 299440830 336 101 393002145 337 239 387172244 338 225 951006382 339 184 740807223 340 2 896019731 341 139 504488302 342 53 754408643 343 220 607146134 344 259 542515627 345 59 879764037 346 248 541286542 347 177 404757954 348 278 502414292 349 45 93586548 350 13 61299982 351 72 612853540 352 114 206551600 353 208 694135917 354 332 710944127 355 203 902497125 356 117 144060066 357 85 748956716 358 17 466397043 359 110 868442553 360 138 370500975 361 2 799380482 362 63 92870418 363 241 862566545 364 309 701551777 365 163 772394643 366 287 919521109 367 355 753346517 368 49 779405939 369 317 124543012 370 363 957724070 371 73 793236722 372 127 614215101 373 32 276129466 374 7 653096617 375 270 762140887 376 278 228239076 377 148 54296920 378 221 229386396 379 364 138737256 380 311 5141717 381 113 95373469 382 117 864229424 383 293 294724176 384 354 830472028 385 164 866968283 386 364 561044898 387 16 526227114 388 162 903888913 389 245 447847442 390 201 294547776 391 243 621214729 392 42 244310877 393 214 347917146 394 201 204396729 395 295 776349447 396 178 255851764 397 2 477358738 398 289 620368893 399 235 884299164 400 205 190411711 401 392 482094107 402 18 676761665 403 240 453170533 404 331 937525267 405 172 682738177 406 257 842511311 407 15 17678721 408 178 673472400 409 240 260803828 410 174 442883119 411 154 310585570 412 340 868540909 413 55 475114942 414 224 883465610 415 163 214299865 416 67 898179631 417 376 940920016 418 70 360700154 419 161 761684161 420 185 229032524 421 93 815325303 422 61 742522960 423 407 960750624 424 170 173486034 425 424 311508595 426 367 138913871 427 280 680215769 428 423 807699087 429 401 453307443 430 201 704489474 431 421 635313919 432 409 811134056 433 315 201421975 434 341 522288199 435 219 121723480 436 414 193469618 437 389 774409895 438 138 741905985 439 206 299218647 440 130 463343888 441 305 843901102 442 220 9751908 443 156 54502690 444 69 327872352 445 73 614820038 446 243 8764148 447 276 638551224 448 138 335430233 449 107 810675821 450 263 695480546 451 332 986447942 452 225 556309274 453 429 183656629 454 284 832602272 455 238 430629686 456 5 313737182 457 65 507291751 458 184 66611085 459 55 555878339 460 416 473888361 461 196 82486383 462 389 807047345 463 283 422944088 464 225 484798058 465 317 556567487 466 42 449854451 467 377 747621021 468 87 126368158 469 302 887956932 470 437 845938731 471 345 527835239 472 443 362040266 473 245 398600757 474 231 90485154 475 131 841729526 476 10 138486871 477 344 750116551 478 209 260298532 479 166 145240295 480 321 740603882 481 361 231496794 482 217 562234602 483 373 220980402 484 405 922164690 485 407 323332554 486 48 502393574 487 29 736518501 488 371 932343352 489 55 133525016 490 218 20036445 491 8 416183934 492 41 823207107 493 39 296805217 494 251 315761706 495 180 946788095 496 300 491863374 497 41 564169829 498 260 800611848 499 416 419773920 500 331 183076566 501 435 21153828 502 385 47101227 503 480 606883281 504 136 940464751 505 267 751544951 506 83 308762714 507 218 155032268 508 430 688892518 509 86 274765241 510 439 722456886 511 370 556702605 512 306 127464061 513 425 547499887 514 246 390469509 515 429 402546729 516 509 193868987 517 374 75452406 518 24 124357401 519 423 709857590 520 31 419435823 521 386 400097166 522 73 534288057 523 157 287743668 524 32 759020424 525 427 54355696 526 263 189299325 527 293 603202645 528 60 793804686 529 361 944915709 530 453 791492531 531 54 120710208 532 434 722369698 533 263 335547210 534 398 425125774 535 414 423957838 536 322 503164059 537 282 986613877 538 92 35514156 539 146 991302625 540 206 500849644 541 495 206661269 542 508 712107307 543 315 370508804 544 448 934458166 545 20 796504800 546 60 474901727 547 255 415103154 548 303 8447637 549 238 77034398 550 24 484933063 551 344 899865860 552 407 194886050 553 295 296809698 554 68 807716109 555 423 161847625 556 41 513119108 557 315 311708056 558 308 632020953 559 89 538349931 560 59 493257319 561 119 214176078 562 235 182856335 563 63 190103268 564 390 526014291 565 174 896721398 566 136 928666173 567 493 186167127 568 299 273737544 569 497 461008054 570 360 993015982 571 535 829156134 572 13 267299966 573 178 747821839 574 561 934975256 575 567 2349151 576 378 218429444 577 254 920314113 578 425 80554509 579 384 742328922 580 6 956520357 581 22 681396150 582 85 960253727 583 386 745874144 584 306 588952371 585 33 639581394 586 81 37951295 587 123 759014059 588 169 641307718 589 558 154467370 590 331 211466961 591 222 797206842 592 398 439611086 593 437 935753744 594 486 273451013 595 566 322839936 596 192 482022750 597 87 950563312 598 474 793831691 599 301 957497821 600 117 657167646 601 149 567549829 602 54 871722824 603 66 928212500 604 3 511657893 605 309 226388650 606 211 813364528 607 120 805315648 608 474 32430521 609 546 288030886 610 187 206088995 611 111 571557691 612 429 841509228 613 251 698978151 614 101 117792416 615 355 691139565 616 362 626067690 617 66 536070092 618 352 142174128 619 392 16251534 620 379 179780683 621 487 108097986 622 495 397042082 623 5 841036310 624 286 619508980 625 366 993370871 626 523 474658490 627 394 756256935 628 553 105824234 629 114 207260395 630 286 286054339 631 319 59137822 632 536 707224518 633 62 47281208 634 179 14871195 635 272 334281218 636 584 242051706 637 300 689722565 638 449 782765345 639 407 153131823 640 603 292906812 641 466 501123135 642 229 208639303 643 419 688118769 644 376 8519164 645 628 836126293 646 356 750623078 647 39 715670419 648 545 603245480 649 3 516549556 650 237 296690325 651 64 185148085 652 87 179294950 653 446 168335301 654 612 858971829 655 558 733389538 656 610 798446792 657 196 315460786 658 507 877346893 659 164 266206093 660 268 162202619 661 449 99397840 662 298 106434770 663 15 178687203 664 366 76105633 665 412 496940229 666 383 262177435 667 606 34580625 668 196 771290405 669 438 676632390 670 334 648690815 671 56 382743087 672 7 312344989 673 613 633542612 674 122 858588442 675 634 389170794 676 646 864587744 677 204 41233317 678 638 713710736 679 462 425601766 680 468 137532561 681 389 811783818 682 206 845521932 683 166 889241820 684 196 754350290 685 229 50230026 686 116 477010393 687 385 156753288 688 267 149700036 689 340 851984293 690 262 304759404 691 220 153509805 692 99 278519393 693 455 441849470 694 326 73690866 695 611 342340486 696 136 64627478 697 297 259173369 698 527 982517990 699 389 666161006 700 13 65992778 701 494 463262731 702 87 950322297 703 213 324592514 704 265 578712082 705 133 3168114 706 317 634350854 707 484 10429833 708 33 548281225 709 630 959155708 710 111 282924206 711 237 169299966 712 396 305193885 713 636 385479743 714 149 743088723 715 230 7951343 716 613 861088838 717 494 579224824 718 563 759443171 719 490 322007498 720 395 398107524 721 674 731405381 722 37 541676671 723 29 800534371 724 331 171312842 725 419 708321556 726 347 691356792 727 197 882377086 728 602 381612408 729 62 142088701 730 445 382008569 731 70 204712460 732 215 332293886 733 533 462283756 734 59 809276435 735 494 267265103 736 299 570989226 737 316 688592133 738 3 341673448 739 26 439494018 740 300 3135421 741 87 600390281 742 76 792949395 743 168 253235791 744 318 509637957 745 251 859974676 746 458 90895855 747 606 907918143 748 502 398166696 749 555 626399363 750 39 634002711 751 416 620479018 752 382 884014357 753 202 659375605 754 540 108190005 755 718 618710635 756 640 778483310 757 29 934430344 758 21 134854286 759 197 443810754 760 521 335044859 761 249 565175482 762 734 968753577 763 379 705014247 764 142 132949684 765 468 614685480 766 195 438327450 767 213 574869866 768 451 649899822 769 509 507933193 770 761 894043146 771 283 743228152 772 291 26975610 773 153 469748623 774 739 949244180 775 51 789965418 776 595 984084245 777 715 568240273 778 706 452864010 779 532 101844971 780 435 268221127 781 719 936018964 782 692 398608487 783 720 923020296 784 515 439525200 785 736 897950796 786 676 674368306 787 60 944033994 788 279 699795879 789 656 84280689 790 79 318364831 791 341 444900721 792 131 590954925 793 308 935144511 794 527 962294644 795 77 659128218 796 320 746864930 797 138 789130128 798 56 234344453 799 688 363772713 800 363 231954430 801 95 564484522 802 560 848820723 803 583 532764545 804 689 446916536 805 374 642573736 806 312 77718314 807 605 330252549 808 388 74205178 809 394 285857232 810 743 823564329 811 96 481841775 812 273 977356161 813 32 644994081 814 362 41198482 815 359 503617921 816 572 321417324 817 532 896238162 818 78 188898558 819 708 35907629 820 108 75962096 821 607 25478438 822 665 32734092 823 591 842169751 824 641 874839191 825 96 998522334 826 661 210402241 827 561 847797678 828 38 963449948 829 8 274930825 830 208 664982803 831 748 150621377 832 751 8653390 833 210 425385624 834 26 222768455 835 736 483830459 836 107 876701451 837 629 222608644 838 161 851093929 839 581 598967977 840 627 315833621 841 450 558675571 842 695 417757137 843 656 138160574 844 323 712131948 845 611 451872986 846 600 160829794 847 99 679441316 848 6 310498026 849 760 45702626 850 61 463454227 851 798 572423205 852 645 683398970 853 527 945699446 854 439 164211977 855 316 377148059 856 825 574633413 857 678 429342843 858 749 528781798 859 811 659960941 860 189 598732107 861 293 41533845 862 363 988927960 863 14 664449682 864 465 786701567 865 402 423488942 866 11 292424610 867 100 747825285 868 825 142446773 869 238 46677252 870 184 739850036 871 402 287847104 872 64 414771750 873 604 939104341 874 283 400856801 875 852 85222187 876 660 798437483 877 691 585122861 878 506 680294900 879 870 520435527 880 797 373777608 881 508 408042983 882 641 567428930 883 124 415643507 884 693 771965274 885 213 28184122 886 288 184306560 887 783 479132190 888 573 378904031 889 836 637566952 890 819 995634964 891 477 462616621 892 772 835103924 893 723 543831813 894 226 235121513 895 288 993587673 896 108 938153230 897 633 802122729 898 166 843565160 899 776 290058440 900 798 130979250 901 364 404948176 902 852 989561871 903 219 445740196 904 246 331520007 905 313 110163577 906 852 383559190 907 280 682685562 908 148 505674547 909 369 483656271 910 909 654094159 911 757 626100242 912 561 978667008 913 564 157786487 914 378 298238057 915 349 356744366 916 178 496534357 917 354 163303662 918 520 395086461 919 135 778056520 920 59 873312764 921 527 994006960 922 693 33965432 923 626 301446253 924 754 900635029 925 422 278613207 926 846 106414692 927 344 694650570 928 211 50459210 929 59 402677267 930 416 648738908 931 626 601905122 932 912 776559299 933 163 574940533 934 159 588040348 935 441 145101275 936 290 794101263 937 178 51820085 938 334 561366890 939 370 251002693 940 743 125335135 941 834 654230782 942 837 467645637 943 766 103022316 944 556 597342391 945 351 75815863 946 643 536900536 947 418 15738421 948 794 737538965 949 561 848881954 950 349 680961713 951 795 421368975 952 740 125912139 953 99 195218961 954 502 830856587 955 489 778122057 956 884 516468876 957 433 603138079 958 215 786048348 959 294 764845187 960 189 693063775 961 165 747855313 962 524 699648429 963 199 330494628 964 297 516605819 965 794 878904621 966 739 1195232 967 425 583721795 968 718 412144113 969 417 91941349 970 294 792906149 971 450 602774619 972 81 780149048 973 576 458571635 974 255 408802731 975 71 154092794 976 95 914467576 977 260 527252319 978 841 206371705 979 237 706350155 980 253 434994304 981 124 496303175 982 193 243269387 983 69 393619998 984 455 799207351 985 62 823957920 986 829 490917902 987 601 186264746 988 556 57584239 989 99 950837880 990 722 329576757 991 469 861271474 992 895 541310890 993 187 5407896 994 354 116992205 995 153 900876659 996 524 355942521 997 687 883686496 998 443 165624968 999 703 402678147 1000 932 28696845 576 966 289903780 180 906 975651539 466 813 745315508 807 294 980903510 406 667 708769739 977 650 913024382 157 436 115273573 382 560 454561868 1 720 732882960 617 615 65275811 703 336 167158659 530 945 897976454 528 387 754661982 701 944 506679012 338 291 340037430 60 445 824859669 538 106 864000136 489 176 208658972 635 702 837152092 444 8 729640943 665 657 975383224 897 581 833347884 505 290 717494180 387 189 132907790 670 970 55095539 481 351 410360462 450 499 667937191 201 521 669207607 831 315 881271404 184 775 39513289 70 907 588022845 612 629 160621789 242 947 454772089 989 999 788332692 541 293 660193083 368 433 416440008 856 975 549128853 299 586 252560816 783 159 465333142 861 751 163267933 322 277 665135808 278 10 898775664 525 709 687050456 30 524 313074389 508 371 939451898 910 881 378589009 733 959 806598909 553 506 887711574 200 134 452810530 151 470 664504689 596 940 802311681 89 491 49542097 451 70 99893886 409 455 866426618 991 17 965923098 613 553 657762644 666 966 34558086 166 962 776450350 959 322 701112737 823 186 272879252 724 24 230074980 390 357 355836180 790 882 924216663 5 577 911175627 669 823 29920570 855 851 67601978 689 497 8398976 344 286 421650927 242 195 861097616 28 417 303796324 887 245 598682378 281 506 889851699 424 814 749659386 988 27 795285284 384 714 9295172 94 29 146974699 470 686 191152907 412 163 104232205 275 623 78462666 535 745 451837670 299 175 203522774 105 705 781904203 845 165 405734320 496 229 220778542 451 108 418358878 135 345 871351656 680 34 503697343 393 730 257995496 336 200 69259301 863 487 113168388 895 622 686608467 160 931 440824515 253 109 536989179 820 353 421786341 821 209 242977392 920 432 722524092 886 749 669930889 969 310 461534215 589 374 648724361 262 375 272713517 392 781 234835138 645 101 737060841 557 412 468580504 644 738 254296953 5 507 769520406 570 199 141744970 217 253 934044645 604 786 340695062 244 422 710873445 668 481 29180856 370 271 804941276 959 611 733457304 849 217 841053524 542 903 779091361 532 443 345050334 231 173 135502693 132 722 127814277 159 644 124926304 615 334 437037213 703 131 803408488 903 978 186971314 315 520 150115927 319 64 588128223 343 523 586259328 33 112 114718367 267 472 595968502 737 348 45079103 98 32 678116783 847 782 719145935 586 542 771314368 992 775 260966964 205 822 614457205 745 885 243900284 466 713 931289655 252 12 824832575 133 914 952188952 909 614 689177652 566 235 414813809 85 429 512402040 244 850 75236292 518 625 806320484 176 46 567131324 533 543 957166042 852 450 725177309 829 608 926740065 81 43 473649326 412 903 902274988 532 757 516333790 742 436 251503455 897 752 742749511 727 475 570801309 861 761 760770773 409 309 797769991 750 543 345730757 276 297 486068138 401 993 585157010 770 526 874354393 223 562 788788822 934 902 153202664 428 293 206886286 673 405 754522047 707 67 841541755 96 910 643325656 758 899 750022887 690 474 270045597 780 8 746984625 87 542 133033438 270 929 389175196 490 37 832062718 999 595 506363732 60 233 523378044 807 960 893830699 132 616 562690780 522 637 891261672 88 384 867706238 608 625 444911045 21 885 341124398 379 436 60522527 87 708 952483973 288 646 177033895 617 320 508042761 472 752 932630336 122 888 232836620 315 417 580971479 802 71 2731466 187 494 476759479 811 302 639131415 808 253 158139869 326 664 337215546 864 294 937567881 132 286 963720289 92 56 122266984 83 301 496822833 674 799 277439216 550 698 552212336 420 803 947838491 106 220 269878264 243 112 189162371 364 236 239837753 932 680 273504707 343 979 603534597 216 925 761456693 630 135 544684024 86 476 458382626 564 867 293394057 595 845 55215613 553 978 372115332 130 362 827113155 365 297 872941247 66 986 532292895 926 937 305893757 168 2 666307202 683 862 808295992 669 915 56163908 952 576 814563463 705 977 716343404 282 16 156068728 10 533 163566175 472 357 86721420 863 216 242564436 755 659 826334519 834 571 112549881 896 315 81133020 940 650 907377184 800 664 776941172 699 725 79195758 275 725 429879893 234 187 310626194 584 118 695173716 244 996 910210189 483 236 94628717 975 961 422464900 350 140 937225901 374 916 904174724 592 454 491120808 736 30 854452893 359 875 544419813 171 614 815552604 150 843 401844202 914 687 445277861 610 857 220999787 731 745 5398917 456 426 625480267 69 674 679149180 623 613 261564197 230 136 147342596 206 434 78328325 605 366 904106105 211 1 351161522 345 962 69789004 130 72 474571413 321 732 531105726 696 761 286339186 706 677 111148721 917 664 411869918 758 483 248911311 922 566 70760280 157 668 967396941 62 789 376646325 77 820 941283048 521 656 245919461 588 264 862971357 522 999 658967342 572 589 771301099 975 405 500266086 755 492 213732480 109 326 75571468 170 870 582553139 199 354 671687520 251 524 600064637 112 845 768840283 499 694 795437150 450 328 440363492 306 435 179222568 71 876 350877825 415 260 296886401 450 257 4351564 537 786 803824897 810 320 248960895 161 185 294964640 765 593 496702991 789 296 193488329 802 951 130816262 457 335 419850915 823 500 982048151 35 296 765709692 383 61 720470075 516 220 784435299 960 995 667230772 147 744 284405995 71 443 268414563 395 628 314938416 172 859 931770579 958 205 246365629 951 764 28606253 483 323 286776422 67 536 76771787 3 186 218176251 489 542 693683025 954 632 39692502 922 971 238265548 413 285 348338017 909 924 757749740 709 252 638276787 630 580 710707074 817 762 717073474 392 199 716350906 74 224 85103496 799 881 261864861 374 699 679290080 173 522 201998138 829 182 2086102 891 997 658515419 281 828 403647088 647 444 849045411 654 349 225445484 490 671 173610947 810 264 146194255 303 14 870144283 104 419 846325754 864 215 4781274 23 348 490253639 858 129 678936402 76 718 103065981 12 148 156742876 239 808 917884216 586 150 172316946 476 482 676210146 355 102 538983788 269 106 428627549 15 401 136222474 518 352 932064369 35 535 635765822 621 107 370913784 604 430 852589775 387 716 349287038 685 895 107105739 883 875 208573374 758 127 434595014 612 404 171509867 994 13 901637714 720 728 815437851 519 926 525442899 306 664 198362083 516 230 191628302 78 64 815826761 158 702 324620174 725 794 493177427 767 852 852679339 144 536 528857693 390 24 234170667 933 828 104539072 784 256 988063713 100 211 966437235 287 704 493674083 698 719 81578144 864 467 629703686 109 655 796905454 761 665 176216161 905 880 791920388 812 666 24619513 211 460 983146964 724 414 72752999 880 664 595590488 202 512 413050660 293 299 933913753 930 981 39773123 259 143 871496862 140 950 458841439 744 882 69759018 618 203 234652255 121 234 881508783 789 224 196890137 695 535 433230802 530 261 509606224 375 533 784461978 883 804 54695488 12 171 526360221 913 7 777643979 150 222 719655183 599 829 85578042 715 681 911105137 243 874 167347265 726 923 33857824 248 912 79525682 562 787 128506703 5 973 676574466 471 586 779425532 942 925 748100638 912 978 476271950 80 361 862672470 471 384 376030601 83 872 51891124 758 286 692262636 307 356 783977126 393 103 886688645 11 359 105936593 521 455 14929952 967 80 125686623 852 661 525833430 676 278 634543171 384 916 731121041 231 25 223324598 638 815 210905085 873 806 483528456 561 12 506870304 620 502 874871212 784 827 591770286 369 702 929782732 241 544 337130939 277 694 400112379 325 316 377666126 268 864 553196961 256 535 211509953 408 899 607021771 842 883 890393359 782 929 705729449 617 740 108555290 220 209 593436630 397 516 729682206 353 593 576466636 194 604 31040971 938 370 773104504 355 409 756338656 509 484 352324292 835 289 185088341 873 420 292182729 392 15 242036352 198 392 499795265 368 782 276837767 660 452 594036795 18 212 570204346 561 564 805341454 135 32 413572556 728 917 420619253 367 460 531356875 594 109 977591054 7 686 560685865 148 182 716159494 104 627 46127916 267 170 667859620 664 308 147260031 607 366 961126263 167 377 898380019 217 670 329640771 166 115 27852073 103 360 330110266 813 418 954493642 234 831 962126757 848 503 370642893 779 282 925669787 615 831 876770113 486 353 902068664 992 597 908920409 328 386 813602154 559 644 621915196 316 470 634266342 129 415 333964573 170 581 296591673 862 765 498134637 667 393 542750565 832 684 620960845 447 261 501365897 169 963 420094564 644 136 473508758 245 308 181548019 842 451 226384175 329 751 175025565 635 45 41437595 449 952 846421987 405 982 120032727 98 962 13960837 51 956 287547200 364 882 671999354 146 303 450317095 767 366 327365555 329 332 596392798 198 893 946973631 12 262 435925598 945 440 992693003 342 117 986466557 328 895 919690136 733 477 162913756 417 293 32827124 164 189 954497043 776 133 848478313 174 718 348783533 795 358 237979015 579 256 422562521 357 182 634429331 646 35 120586857 865 846 236135867 183 556 707561373 625 466 257332057 369 359 117116637 766 859 56343440 39 887 219323261 330 15 34656266 552 284 336107024 124 505 763245565 560 645 80601818 553 807 714129968 314 243 730834673 785 719 890108547 984 129 418568662 691 837 255457521 825 790 459776115 13 632 823924088 403 929 750475690 32 472 913165003 661 640 705476889 54 411 654189988 67 204 93275305 936 517 303627798 259 858 597372540 559 901 965169260 554 233 87339964 937 926 415549726 128 800 13610117 444 784 9564689 705 757 69691155 274 62 452398184 996 814 615857971 966 17 564798014 561 552 958054843 478 777 407185937 865 334 253669590 8 669 293294429 977 36 226953236 794 295 920649162 509 55 776119598 422 566 704144792 282 999 511952279 564 489 215524555 276 33 916090937 986 774 571060781 134 369 857336398 617 124 501008791 290 38 181533067 174 660 283078778 335 43 714173157 48 503 658657025 394 341 258179576 56 497 626296734 492 862 936987072 410 567 761021573 196 32 971073548 947 901 806845875 604 554 593937785 880 278 528943616 95 43 978318813 890 342 23844795 589 378 916975698 139 22 230184586 470 94 211035805 602 485 945070869 181 751 559111522 654 59 755082211 202 229 156139731 839 934 144384113 425 813 108106126 190 401 664714764 850 710 233852345 572 418 623795434 223 510 493803743 888 816 942745517 519 296 450936345 585 779 660027718 170 178 947791333 958 465 486766029 130 528 949483339 521 830 872912189 252 459 388957063 962 528 681457702 462 209 506984390 479 617 751484961 8 868 737872036 822 571 716032039 108 484 789489182 169 194 178304172 605 861 596422278 344 553 742855762 706 301 900150529 875 912 235743045 87 39 898784435 643 293 624260092 483 561 887397730 90 172 107612253 140 422 158611846 792 219 251481757 142 765 681150309 804 172 453572484 733 535 636722876 633 828 716315408 848 660 990784538 966 224 959162050 912 494 420695812 254 904 725885970 127 531 35099029 978 351 962047074 880 839 967852513 830 216 528090200 367 683 433903477 635 587 797215378 682 971 948240437 472 613 589448043 88 727 289360349 397 81 441029991 301 774 41689227 484 501 355197330 3 805 870266634 731 337 616870373 869 254 249414593 71 187 451954253 708 445 308227356 626 32 27638712 243 751 975151629 545 720 898445791 754 731 464055331 125 897 120077168 554 254 726244500 203 172 531112327 405 782 465332024 97 107 193948219 586 467 179861054 935 875 366445168 466 886 34897671 731 551 372012106 941 812 234158501 460 141 254212928 899 787 150947140 725 938 284161502 245 489 395378157 686 253 632805820 670 994 368001306 438 736 593496524 127 188 534106887 286 126 484069578 168 405 695514109 706 42 524034906 294 515 862638106 355 738 201330186 59 575 637877998 171 727 501661563 931 680 134981226 904 304 73948078 33 83 195943517 96 829 702693063 462 34 644712703 983 819 794244372 94 704 575663117 403 752 676728665 513 504 275214087 143 871 867299460 326 652 468104569 386 403 922377340 739 135 577909550 545 594 853365306 761 619 996337852 886 117 867964907 263 223 587177662 820 627 567480444 436 235 446574432 972 18 963545410 610 941 816066985 926 862 923184740 552 296 959753800 817 179 983688987 98 218 911772165 837 243 479434644 771 366 493331204 754 821 378977895 701 897 416930925 550 101 314537216 809 107 8719439 924 726 226003987 63 242 248155545 685 69 469714846 910 339 883092121 729 304 635545647 531 753 705316150 457 826 294907926 975 243 113111640 633 201 682555153 847 851 609685998 326 638 159222650 313 272 667149640 17 796 124569218 191 723 924165823 440 925 767830159 550 539 816320244 564 787 322167669 896 743 288679556 940 853 603060763 646 195 671438118 433 327 190456553 196 260 520932695 809 985 293808111 537 496 463608231 849 556 486777736 313 596 360596654 879 795 583382259 45 701 531290259 896 280 285883665 463 332 891277452 212 317 78845795 607 236 980135429 2 401 348166878 593 889 405664562 707 447 970041385 305 169 199227765 596 758 202361748 293 672 446659412 627 57 18025459 390 148 356865627 469 616 619513090 238 94 995589319 712 672 164801189 12 104 335646634 116 764 910384813 753 888 349447749 88 774 908729191 513 244 745006555 570 805 852541415 379 759 561756102 474 433 881273377 785 253 508954834 548 111 667077003 945 697 652130046 29 246 40075311 555 61 880456263 987 893 313501981 764 484 368611147 301 34 904653228 924 638 649291462 789 46 529578387 620 289 595886950 569 772 775576945 220 991 398162806 53 844 886967768 908 672 59317410 921 312 612153682 85 545 269257456 829 160 735050212 522 877 923597863 428 467 586285727 619 274 547321306 871 271 162834040 958 799 971879847 995 118 47420360 162 901 590458953 266 892 45103451 194 14 437400171 620 921 939409034 693 414 905107838 537 916 242256898 706 49 288050431 611 593 285497678 941 419 223666288 604 725 628454415 862 4 167185853 659 268 649591733 533 38 402125137 987 507 404238768 906 149 745209037 771 357 169207313 255 496 575576368 971 688 287764934 13 954 534646859 707 492 928258792 309 644 84933326 702 902 701567865 898 495 595715914 866 329 306468462 301 787 509379950 823 771 971143873 452 384 165328062 113 352 977578250 706 573 615071045 237 735 171608759 151 167 527883986 531 453 902244313 406 455 988508425 336 276 412172903 64 866 414149656 58 135 903029561 868 479 869181766 1 321 399257141 372 681 416307777 589 509 79489419 28 436 666399739 630 244 167194907 407 431 591808507 972 949 995309530 665 996 252907164 664 96 75086868 257 529 54175026 717 636 791874544 632 344 944444409 458 863 890157152 468 247 423241803 900 198 314043260 25 150 140317008 82 633 708557257 216 217 174274234 110 4 452751826 706 755 467147697 147 507 380244945 666 900 298516588 452 638 45603666 217 210 227070787 861 949 892941714 871 547 923065655 839 6 808739438 179 189 753810602 963 445 595513605 100 209 83037901 765 693 823880726 983 249 543842040 547 362 472623905 226 404 360037216 683 642 545323312 446 555 872436133 422 589 171648296 814 823 263447071 16 650 237028010 985 41 862419277 246 245 782824450 89 283 670427648 601 968 457617018 727 753 882738285 254 952 993013779 972 526 682949079 857 470 380269819 209 74 256052472 52 909 490675983 949 397 13152408 130 434 115145331 406 273 789823298 591 792 98060748 661 799 946955109 125 175 756943748 980 447 697349031 163 408 211617999 439 615 933068079 177 26 741750490 239 912 754864558 185 598 284208201 988 644 198924377 644 176 819809593 495 833 235823982 181 965 527453522 847 504 205571004 887 745 927474987 370 68 332202520 605 569 118907142 635 899 940710428 499 184 919836835 962 455 390448 285 990 430623696 82 450 764833329 869 564 251345866 803 928 946240054 7 845 875833137 62 818 496940202 419 509 909181607 762 569 897924731 434 797 52088292 110 564 796368782 519 994 261048615 154 26 620956701 724 391 690069684 530 580 625976080 422 921 33309805 296 818 828991646 367 561 891330012 879 532 229086198 607 101 366459260 766 135 965955911 346 775 891626278 346 164 954922754 637 16 554064446 560 758 225640747 571 306 446410874 901 537 377983864 256 910 722799354 137 63 610637764 943 227 612413039 739 453 142289147 891 133 921213443 364 679 386494586 711 194 5827225 812 849 95980467 142 652 290275041 220 56 450492562 468 654 568332916 498 28 499293023 272 189 460336211 194 114 771082729 879 685 994610016 124 952 701247668 820 617 567201067 812 165 302896288 237 996 173885786 37 979 845077139 686 298 936331957 64 10 72125858 832 386 560684440 651 304 782173701 505 366 332608253 247 432 4968466 641 856 626598404 36 474 375525963 221 648 522854578 70 439 52070221 558 249 475263971 8 617 11522404 77 590 761034793 413 568 97835202 53 672 468155149 555 584 967993795 855 73 623595076 560 164 670607707 350 975 679535465 219 628 581422270 968 318 567378250 787 199 903588290 246 503 477265864 471 159 633652359 940 59 232832534 263 491 118755752 736 122 935277404 316 969 2028533 229 412 294246174 323 226 56163829 465 681 444433809 91 461 915401767 673 350 733160449 658 209 554784721 517 890 206965401 103 235 956022637 591 421 677618243 15 697 955872046 922 998 112189187 594 688 261261713 297 687 926466225 326 626 346325614 360 769 974647065 595 605 479324565 437 743 193342199 377 293 542161814 962 526 906390339 498 452 480984786 917 708 285761193 632 94 502447502 648 155 457742296 782 63 218249018 64 676 480961888 256 531 639619768 808 739 710475403 316 762 179663745 276 819 148137706 147 861 367095711 846 1000 526888966 265 42 950805742 484 384 905851292 156 400 25769947 280 778 990629075 441 361 241249613 17 606 826369697 445 650 513867677 398 619 43162711 142 333 564566335 99 64 141917223 766 783 54661337 263 475 295413934 829 938 976727310 869 612 764504276 642 13 571037409 911 468 98077467 690 393 154179375 721 581 179617762 797 751 190156826 95 460 784374529 469 677 556540658 478 797 883235083 987 416 790653948 850 148 663014742 385 761 155814966 813 210 154879514 808 856 228145812 847 447 428837405 384 829 414495973 215 116 986114422 702 481 521887377 372 165 18620844 555 447 569303053 139 120 888986022 409 382 155470694 306 702 310266517 407 882 455566899 95 656 227803796 279 11 390954419 95 390 388547506 158 999 234877371 838 98 119190293 732 699 392643352 712 327 330696993 750 647 167344438 178 799 618213673 257 159 570862116 560 104 243798114 926 357 819017867 742 334 303889727 676 174 500103917 897 857 190084963 942 960 386922265 925 822 345727551 358 370 218730534 120 927 765971584 71 942 403108637 199 745 616653909 618 474 820725392 732 346 835497325 792 465 115447885 706 596 795379845 862 235 444073441 604 803 48393155 25 933 147349508 228 417 202333046 977 264 796614312 553 711 629415401 143 254 420626809 842 432 920947507 593 982 441937567 822 618 48417033 647 540 9654247 794 852 634019979 963 684 764085475 483 845 952418707 546 95 780366879 215 521 420871870 5 910 266077723 847 670 298295552 200 946 189001373 37 938 457417682 852 84 140413587 664 775 766801735 657 380 151851513 461 217 281047534 611 242 745615127 586 270 297387313 954 204 414997377 446 742 734472918 282 573 680957962 530 788 653885935 967 821 110441029 231 11 222242895 346 257 174274791 963 276 526837763 574 756 433851973 913 105 916669037 699 924 501982894 726 75 478179620 968 906 761498525 454 383 924910001 859 328 201736517 965 602 47470134 621 310 30500695 343 519 728960547 861 463 337602911 685 287 411723523 735 325 786143201 833 495 618430318 929 621 401634397 650 422 995038883 277 368 180499302 121 279 404689557 670 177 884137122 165 923 865155254 883 975 554309652 967 757 298794138 837 784 66909772 835 29 34119806 569 567 47312910 115 366 809108625 188 455 277131806 272 854 172654600 998 914 862560727 514 414 48649013 236 196 157588851 259 871 859339488 350 892 462148412 644 730 820827200 78 874 899257728 532 438 510847040 819 439 82598195 876 489 847888491 4 909 711226381 510 488 393330860 200 254 452776918 899 571 199115610 953 752 369811089 576 775 277400638 878 848 807776911 960 212 139053503 985 741 436374095 746 336 897735748 138 964 906628267 584 720 509593632 595 446 504056942 24 223 473964470 403 596 995633714 492 676 803751608 762 736 629285395 69 27 915060742 613 946 556921118 328 543 763268813 620 510 539099804 403 284 543318086 769 876 678374830 689 426 762776284 60 184 276959965 438 138 577649509 223 569 265506784 847 10 470233694 550 13 27872686 46 874 764773544 441 301 707133254 312 192 262908836 669 266 827685420 595 176 569505471 876 791 571422973 596 680 587019889 849 229 179621701 919 856 111605010 78 84 945206395 545 30 723007865 151 351 195490310 811 96 254124275 917 28 492867781 811 987 722153136 883 932 29842618 934 215 708971378 987 953 613526746 374 952 698987863 341 637 5644293 202 326 789840940 987 798 838437017 14 577 767933109 188 288 924983278 661 38 951344775 365 293 356749647 482 334 486433358 540 832 970620565 913 442 193559986 965 903 464267816 786 605 652615653 512 111 696731634 584 965 797994839 967 458 199968333 669 33 197736187 496 155 835513972 134 840 449729236 577 1000 480541007 962 82 124263905 87 696 447007834 373 71 310286151 319 412 99506792 85 633 487891775 610 668 289611489 602 882 485825364 804 782 204623370 678 765 216268861 427 832 322836722 180 925 636756005 118 557 267095538 67 33 737385573 748 521 489380195 551 180 760880893 777 244 65784724 97 692 17298634 468 655 54582010 92 225 68783472 19 775 987295749 558 365 166432806 872 65 511192643 839 653 167583102 675 513 157041777 295 257 529775172 259 513 848262637 781 640 562973206 72 894 751651182 171 366 372526288 749 189 77606978 454 526 739753418 317 656 889104759 159 513 700912883 409 994 269535909 450 312 987513418 854 448 974722472 329 539 94924513 193 406 365951098 556 403 459175525 648 862 191293382 675 41 489616479 372 889 493619533 339 607 449500077 682 984 907555079 230 35 229965362 646 829 415836190 812 848 201978291 852 135 664537825 470 779 942592744 601 268 352162385 985 838 937508651 595 569 15701708 535 726 886677868 282 548 720664666 487 237 213319388 438 52 136888176 464 915 872280965 925 948 852034730 449 26 761822799 96 650 258763718 989 673 578099141 238 25 426220886 424 871 25699046 835 703 434981368 29 772 881663352 947 921 411854360 359 721 169027288 660 719 746677805 443 782 311057575 697 433 347102064 289 326 391541621 193 911 707138889 522 487 761099024 721 135 552097993 851 48 758701916 833 21 824405649 79 11 733159346 265 822 990493271 463 369 412602046 944 766 260429693 617 169 481310024 408 632 458509459 171 225 335804429 962 730 805674213 509 505 916661963 4 302 182336200 753 431 370373945 176 789 806094297 685 360 38337776 578 691 474355952 908 424 956958820 891 94 597974389 242 643 386215560 568 536 42599759 588 710 268715687 555 396 328854848 370 346 877553038 603 455 610410473 760 332 863685147 723 606 19442235 820 463 25224870 599 275 277093434 208 795 954786629 701 888 628369363 519 663 807807928 146 322 541783389 350 255 499704354 84 80 622457461 582 238 636902320 472 119 965921667 508 219 53656214 870 399 265043049 996 1000 740562124 863 518 725603043 832 108 230958997 870 999 106982879 727 597 676712797 561 456 135050416 294 929 977512297 430 511 953593085 737 18 367858392 130 80 850438110 995 330 707232623 174 810 921356612 25 53 846452869 600 806 907853417 73 639 523946624 495 796 745447865 871 254 502738311 718 9 121020280 160 212 211141627 8 683 30383 157 97 441591103 126 566 664879253 103 365 734194026 432 726 426568212 971 563 943859085 641 90 162432729 625 998 318555137 659 306 30091862 554 196 452604933 971 8 432193355 348 198 862275208 77 970 266235099 604 159 449064761 887 556 70672038 387 781 251208297 712 181 574532126 667 110 472308886 847 521 803378109 988 338 961552468 993 200 737631454 319 441 858980838 934 870 966628809 256 210 814691375 953 271 216646866 763 173 685312089 215 176 612472862 444 727 821184761 735 685 670912972 277 235 880461275 978 910 860947643 745 947 68287099 778 471 662441553 531 57 870443946 813 450 697462665 510 26 187172470 979 553 413008249 176 55 664691159 257 275 371633076 209 455 986672971 715 952 876111450 123 622 587080744 626 406 167006213 103 786 44826436 88 782 369216091 498 426 874147352 768 403 328214300 649 21 980120166 972 538 279444536 470 41 958400057 611 832 420204877 638 529 38989404 213 716 94189027 294 516 728801531 806 879 99070975 352 339 539065367 625 520 696044334 98 707 683796926 799 307 142854593 304 19 904680660 357 515 746267570 542 243 93538235 405 112 395163283 804 629 19036792 414 46 772073361 274 337 843916859 983 596 333370396 738 601 223843859 677 691 936174686 754 682 131963915 435 868 39022814 438 228 389095631 131 529 790210686 70 810 298715207 52 222 647772421 730 126 739491629 875 602 784073371 472 40 469790439 382 293 878580121 616 327 483885168 162 957 498753236 77 80 583153190 873 537 765380686 2 281 762969467 612 839 356836681 271 946 550763921 691 372 146799616 18 860 260540533 994 189 113984034 372 143 579489197 352 533 347926117 621 218 345068265 829 955 488301031 223 149 179080870 438 61 602040498 116 1 804758209 629 193 559879042 64 669 869365308 241 664 302758043 689 443 223001240 58 761 315909224 863 741 399882494 90 916 12080930 601 786 433007268 825 605 108846282 314 519 417107022 475 258 134372752 232 226 655090585 716 544 517765090 736 863 526674620 757 823 567597871 123 896 856972636 965 395 590133371 521 302 351522614 366 429 985393162 170 792 739368016 90 116 818223922 235 481 528659794 833 332 551103659 188 294 803593394 612 229 895824569 124 833 651382565 836 365 519480851 68 17 641690243 204 322 96283095 293 716 748155079 217 215 28147906 202 870 711610309 626 621 801543769 693 427 505867011 434 356 551778274 227 706 800130123 485 446 893968693 445 561 970831545 657 145 32602411 222 211 272336265 309 773 341904115 739 943 227624791 788 685 286699372 508 811 436481077 978 712 198946614 917 315 84029891 703 879 222953257 115 895 435960480 488 712 268278534 878 616 623679487 584 709 977206253 725 487 366633020 785 295 345011639 92 418 246977659 948 825 621956505 647 421 928835619 169 52 569822481 211 545 607142510 153 417 669215125 83 606 374868935 921 678 288429837 486 269 548415678 910 345 929297625 915 158 619366608 816 581 880526095 177 21 600015307 212 973 276401443 527 917 601787229 49 891 263790021 423 580 150530380 13 915 881939935 426 815 206756451 710 792 197782498 665 116 355776136 465 95 631610496 187 246 754049046 628 38 176390668 407 932 294611954 846 108 98360302 79 627 78093853 290 477 336075600 971 94 647038293 412 538 546274031 928 740 538332222 124 78 801860915 537 137 16441180 969 461 390733222 675 284 873214918 292 668 897536782 812 986 771617344 90 192 679663981 546 324 881780159 708 379 585141212 78 816 458433325 800 318 28116492 126 90 23027138 204 763 941278591 325 937 254886683 444 6 954519371 432 753 437023171 426 885 897278844 110 159 825374798 184 470 64850183 65 125 259618394 521 218 781788976 811 757 942075474 405 439 263394099 928 574 421895521 932 453 390654097 744 796 648243825 941 721 163372566 709 563 967459153 973 58 164276562 6 896 211292137 922 629 772889335 323 328 797356826 416 92 776400676 666 274 154945927 635 518 752097193 686 579 939863271 74 507 774878509 332 339 395067171 632 152 861873708 290 279 777511887 992 101 527583354 116 59 511674977 704 358 795414057 232 610 151885982 729 702 499647096 157 651 752043019 69 172 674422995 765 77 573788919 244 687 10880405 84 403 320223001 710 119 362242409 20 860 955765696 804 885 131436955 643 152 525609698 955 938 34837828 621 868 830981343 44 170 241036854 815 736 243582706 178 475 864610740 301 559 360949460 427 380 830708298 630 491 150705504 301 479 32992299 319 166 679731898 911 531 83417474 979 720 886085892 159 410 615163403 241 382 202981630 549 542 519630930 619 514 403582221 778 474 307682982 269 452 382001284 719 68 58703598 534 49 86489020 174 936 656721043 520 732 218777251 244 302 368057059 714 359 75344829 653 43 448061177 195 274 296502278 27 446 347915665 656 596 479673314 577 433 712527002 930 809 270430737 305 794 769014360 663 74 964831591 755 18 310163106 399 326 958461857 416 4 658416469 913 763 399933194 935 458 3325932 618 572 755808405 32 71 282166088 793 982 611856094 453 294 206052132 124 35 977313063 825 855 739191917 147 773 652691930 615 11 508412884 996 518 784786123 427 172 404831662 41 469 402912689 44 657 405946875 795 839 101094810 224 301 34952313 172 621 827469215 862 577 136444049 922 652 767079847 966 443 342474491 65 974 918481761 637 399 497629972 245 477 891938040 10 572 575906182 358 96 249465137 480 550 21285561 516 484 240911807 205 503 441479444 552 530 566172814 323 413 706906053 551 869 883053202 455 979 365785308 855 828 925874809 49 771 15539661 148 312 980077875 822 854 166910997 609 482 930758044 350 693 66725530 448 120 243491714 178 589 824391863 532 252 110408248 882 832 806626720 424 696 441109204 490 603 995840372 432 604 728613777 853 712 122989470 375 742 752680390 340 702 352982540 511 734 594875232 7 80 803293826 942 118 55471054 700 817 721186967 81 418 329686035 940 64 288828974 129 439 85576693 569 338 965513521 67 991 732652260 850 226 88770840 884 553 665941184 547 181 153134429 832 922 701502686 319 87 466470739 133 528 917098567 398 135 310171454 607 326 298143936 879 931 18681122 865 339 849926229 102 624 194987956 792 982 367470536 642 779 856775319 464 939 521029363 941 277 945753152 236 196 282702313 600 620 506840168 671 351 82912150 239 856 843484988 452 462 209779984 567 349 421359448 233 584 12914534 990 674 921450569 929 331 914489880 753 406 295999092 599 92 654601233 462 228 780120860 41 333 56275021 105 389 367715746 720 722 80389470 358 710 727894663 460 920 772394687 642 718 322514688 442 681 607712926 918 86 789892677 918 62 502408360 311 677 496409904 757 754 635956389 818 605 173187287 343 771 280959927 86 281 278154133 517 822 435230693 456 296 85495986 620 751 3025554 790 625 29757750 733 332 353386446 149 745 812719764 227 438 985178314 276 887 65799689 849 348 887889867 893 463 897121310 288 444 203600741 983 832 932260035 695 490 109563699 368 747 368327674 457 517 956078227 532 122 258207930 945 535 438835812 613 175 386149550 355 613 157462836 572 628 430828316 138 64 832374935 198 256 402836923 387 95 784252899 966 983 966475505 815 945 599397194 294 717 487507268 2 549 163835547 939 638 12277337 953 592 895892232 726 220 701589317 100 929 950660047 400 552 239144291 529 2 681852225 819 367 244256906 74 48 759466390 559 27 518939780 739 856 679315678 872 937 162170647 294 394 217776270 815 296 335722671 744 903 147046637 984 651 986665680 368 576 459236820 785 286 538132539 694 588 981129180 766 480 723296809 94 228 643056056 364 156 976151145 491 467 187211605 177 127 204894200 983 407 190227963 302 281 995650614 944 425 887296333 128 166 631776755 344 952 965273093 693 995 355557410 918 193 661767809 645 494 861110780 60 864 80611783 947 538 589385967 130 921 354955589 437 239 29803100 362 978 477689360 404 684 222910147 75 765 82592791 876 90 605031428 121 787 553217108 318 221 267852573 342 102 757920920 661 321 509950368 649 545 71391291 470 788 943195397 19 278 695824641 761 100 824005800 315 770 324050840 104 537 243261621 554 908 125440015 302 435 285740772 434 592 359465258 699 626 527733024 572 142 176302376 188 537 124253414 449 868 716914446 84 575 565237151 693 335 572296263 904 523 396599870 497 235 197069406 568 896 319575622 865 517 352120579 534 161 81419695 395 186 690474205 927 914 486733149 55 319 263680666 538 754 30103831 278 181 3957454 484 562 473167650 474 274 280605116 268 729 518661581 434 830 968246181 296 11 494022830 923 241 326293481 660 23 334677442 358 915 982937244 909 933 503138016 315 359 572141520 142 655 329914355 187 538 359496966 957 219 292988360 500 655 23262541 927 214 677278048 891 220 469679246 284 399 184067510 37 803 851703887 610 838 17893697 320 226 275109538 131 572 809556035 474 982 955235266 258 414 86253238 575 731 653353671 648 613 769832501 765 357 202769868 197 776 984136564 657 281 126744178 377 494 374538705 749 71 195798774 354 768 361532693 70 585 165107997 125 405 564994778 622 614 301930068 281 334 37304022 716 576 331104541 555 530 151587678 244 920 935193773 640 378 387855900 963 832 8395079 25 271 817178359 103 421 241732067 600 838 393844798 841 814 345805954 252 525 233511349 857 430 92266024 276 376 392625128 610 433 794989261 923 176 102520196 572 281 351480404 62 420 676378794 570 713 342899497 731 99 115777339 446 473 195503268 468 305 55878735 995 475 10241747 408 339 762265464 55 435 114712085 772 233 906375956 656 693 99459413 658 562 884685190 313 891 723013229 924 8 475854000 469 981 384147253 655 227 318418217 291 742 992955009 170 618 796413526 539 873 646591025 923 513 239187120 210 843 415144649 393 461 376033669 24 622 261134169 671 108 759684554 928 914 168385648 844 278 847416996 80 43 709263844 597 16 906553813 240 440 667761739 254 795 501110435 83 642 787926762 240 330 819221894 484 90 751367119 341 391 298169266 376 263 32140591 652 769 769815646 122 913 29010664 733 622 565477602 561 878 349493464 665 456 288247068 658 746 711398747 444 570 740384722 526 534 191891319 376 288 53971983 411 306 560049918 213 102 356415273 69 276 664323651 335 52 855059841 469 508 819079021 976 943 915662882 623 657 629029279 941 191 860019338 14 48 889981206 781 208 117008541 526 576 222405042 477 450 233811313 920 869 175377905 639 416 72608123 9 345 55975467 832 626 114688200 286 764 619844456 872 42 363838044 679 103 648055571 876 255 651145784 783 757 913148049 528 214 187425089 622 812 584531901 797 672 728401901 175 178 875140242 458 173 658179407 900 871 858420229 647 124 511151809 714 855 273583714 986 933 642317192 839 473 469131202 643 435 793407456 766 963 574969142 945 459 833696930 927 396 217582272 694 911 132061651 943 373 962205879 230 632 539349728 402 307 148722516 899 270 781408966 620 214 535564387 622 423 666353971 414 329 67073726 483 660 708846484 274 479 54456641 953 774 674501308 191 425 741989041 913 381 992294020 358 355 437901020 709 625 655914257 384 942 807607642 852 847 238110087 315 609 521659599 501 747 867401480 898 544 713550076 40 672 227457201 764 248 589395912 355 504 498956748 5 111 372130389 201 306 558638463 741 503 996007962 21 963 396681896 897 372 480502306 982 146 548578846 841 85 510813885 732 658 155559926 394 522 349813609 225 479 2008310 388 537 436646070 338 162 469837551 364 523 650087199 668 41 67221440 291 688 756226978 609 378 514698610 823 230 419956570 24 367 12115207 118 585 45967554 84 208 250048460 641 410 631917883 763 781 732038202 908 385 887385488 883 525 334878262 701 496 223290237 143 990 482840342 363 863 384363974 256 882 548050169 653 249 881689892 867 63 494312862 268 303 114734402 611 584 266233185 505 473 658552385 265 656 721811476 469 266 721563168 17 435 290473656 535 845 631483641 533 397 343458507 116 826 961921425 64 777 207238610 619 788 889508831 411 331 329509808 300 39 703828719 271 734 167514264 836 323 742029566 599 360 112280410 591 835 612207524 482 295 581446245 6 157 608691910 3 921 769428997 226 217 204355774 208 205 136839050 11 688 214032828 824 853 927109428 11 643 848660718 180 887 842045719 11 110 220164845 85 772 516727800 899 634 420890827 215 498 375238963 361 736 860950940 616 949 355905081 828 402 327380142 322 495 948580765 319 448 330283009 810 41 30564092 601 645 729785387 376 390 255465533 737 139 370630447 232 310 13282158 232 593 684051342 124 753 814960730 108 420 451499289 335 864 958924694 66 545 30051076 89 634 246818506 776 394 282479386 223 925 626819577 926 455 474085232 219 44 35882162 580 958 334656535 397 20 965127514 336 146 803712193 319 248 198600779 954 760 735986594 295 799 276655245 639 264 657124994 710 65 605863159 505 609 466140705 663 345 692392987 406 941 255447543 458 324 153948965 716 593 556238754 207 447 28955828 237 963 718133458 114 494 379211104 359 511 763069874 324 912 103934576 631 582 503162484 896 312 119474770 74 509 522097355 977 988 553783199 476 733 658152578 522 208 233319077 161 657 729937050 4 390 418663653 235 989 174005008 55 365 856026870 881 376 874789268 399 941 563174721 655 151 911120104 312 102 482147940 287 774 826164685 200 976 953338499 10 480 221028935 849 732 568702068 526 992 784905597 739 691 826071859 819 592 988810225 223 374 869474104 797 971 653993372 494 443 494985652 495 358 125979271 496 893 176532319 210 601 711071221 648 393 86283878 278 540 532519891 119 47 360284682 955 908 42296319 46 791 225575992 935 457 714657676 915 811 464266094 27 493 511952758 402 520 395637737 143 955 769697861 440 323 34219414 106 574 454154565 985 114 695761906 569 94 172809286 384 707 29158755 725 712 338773830 954 119 280438063 443 389 829560837 397 612 917728347 342 898 839262701 493 64 945362985 981 704 405407524 437 50 379449950 657 53 4979003 599 506 900165892 952 442 645867575 91 560 676240596 664 423 457304833 498 522 423458356 953 325 288047967 375 837 88067590 210 239 144232529 928 472 762346636 565 704 388009424 712 346 137794414 5 138 361027286 692 812 882467060 759 432 443988880 703 638 372388218 325 763 854224130 921 112 166997612 609 786 405831225 818 82 417372098 435 523 83984840 526 364 917466967 687 72 954792002 840 244 704377526 188 806 962717390 518 205 960636511 838 426 654660652 797 61 588874829 449 2 372736440 188 403 59304423 972 346 792134745 452 980 721748942 187 924 69552048 377 16 725220758 577 564 431852688 607 599 431719876 714 243 963949152 790 422 835656055 768 490 690564443 42 567 522709918 845 268 273874758 606 847 503616931 275 647 93853997 814 628 162242118 11 938 74356170 891 696 504847297 773 546 898021411 586 603 347642180 365 865 352430135 255 529 470944851 466 941 756184936 767 123 621042880 395 515 73433120 640 153 246222142 220 203 931474587 102 37 651765767 533 837 226201550 494 74 681628531 821 549 875498204 455 654 33888829 149 617 824451177 593 703 418930404 529 370 674736803 462 57 972135561 855 500 805292598 708 263 443996784 69 705 284762253 203 630 510014847 369 147 369246276 695 514 92788763 178 103 749021294 934 682 565518648 85 519 203966195 121 10 159658158 491 824 556752752 781 516 278188896 90 523 984683378 22 189 72260723 296 875 389691365 671 902 391260064 340 483 354447548 937 256 132941777 647 846 323533366 234 205 264178413 137 655 890758341 583 907 66460935 163 813 226636104 872 853 748098389 550 449 944363814 247 206 662124123 615 536 115527407 297 766 144301001 133 821 389679210 948 519 771885350 489 989 20837899 581 756 172841955 719 792 439688239 706 501 782121955 843 718 628148366 250 138 151390782 63 470 681976800 654 345 387697869 556 889 568100048 277 80 702597380 227 946 472324323 720 568 507517720 915 877 40683141 790 144 882487475 467 107 866910651 260 729 352632459 294 589 531021372 469 783 104919081 179 1 959110925 553 809 689028363 1 365 737002084 24 67 354518952 531 863 422875116 278 669 48929015 718 481 570864045 342 300 718169393 449 937 248158663 239 241 967721443 869 845 605567562 342 571 864374498 918 376 173204027 637 601 792320988 70 515 910740968 891 599 934807688 1000 191 275527851 374 596 845878691 109 553 630619422 440 427 600800763 31 105 1466685 591 61 263344171 159 672 476802102 379 367 164218335 839 572 437962329 838 744 27254721 345 549 439727992 303 428 420719255 183 343 107627586 109 152 938931054 134 482 583446270 305 595 239947792 329 979 194299472 54 913 501141484 97 312 277062884 405 753 655256117 629 69 205893805 161 994 651124867 540 880 848619122 604 428 997304766 8 161 755856858 503 787 977766092 989 351 246355108 623 411 241066941 470 519 889539939 412 21 816494790 383 680 649616660 915 406 680646965 514 463 148963543 742 140 68843197 550 760 17312516 840 267 13611734 625 631 438511341 37 938 941745924 745 897 602702730 68 827 917056380 886 71 474937134 53 711 909238829 608 605 905692656 106 861 652042937 324 207 250426020 850 254 705261597 838 668 487750146 746 135 387565561 773 755 153573931 575 594 553877407 728 329 739039376 951 911 832696792 954 799 457721514 208 701 713212611 154 434 548713384 425 807 25858932 153 732 26666944 902 720 62413604 684 288 601680693 955 927 892318359 522 396 41184719 457 917 697924856 829 864 36681301 169 886 524845934 122 317 27788701 401 16 566267651 951 874 458954036 813 927 441322210 674 456 603040740 371 574 943266408 707 959 522092887 142 248 934898791 610 600 42808361 250 425 271859934 290 586 792523204 772 60 817986408 521 187 959292246 311 800 48199971 238 384 123471588 151 593 247209502 407 55 343187842 878 768 903819451 295 134 166714326 456 714 944949903 96 744 414030524 310 95 840665673 560 222 121507721 80 805 339214585 846 918 993364211 838 444 744620013 874 581 511184374 673 836 541446280 214 628 741593534 362 750 54282235 234 291 360227636 47 521 963770654 270 794 151891309 743 24 222010331 145 740 341690094 811 327 785542562 702 135 212298026 627 930 507709554 752 529 645933545 490 143 148155677 321 694 290411972 746 459 251464167 279 217 753081546 154 467 783411177 354 71 969687994 177 804 472971799 952 461 349805774 354 219 708358958 398 647 147492660 270 761 477959186 775 31 360551362 236 332 636612924 698 388 219781211 448 454 10113018 593 926 634068501 274 400 281743706 86 847 978300908 952 422 801468095 233 731 134033451 285 335 808952421 250 518 644056065 697 481 343614937 754 82 757585244 992 832 170786402 837 413 614732179 599 38 326604709 700 271 796193065 948 254 815638913 975 611 368828180 560 39 311581588 773 801 529949484 787 980 504002699 286 576 625343353 300 605 459497238 20 285 989268731 807 386 582984580 154 140 93093495 360 282 921044867 639 175 621831441 862 243 925656594 756 440 14171601 619 672 887554524 964 751 760402360 611 706 865780658 670 390 96454802 174 484 184195498 153 465 956529146 525 649 21031148 585 861 156562930 571 52 416331335 413 576 852716730 685 868 114682334 526 491 369307832 702 630 495068521 254 12 34629907 191 715 676701082 413 699 196489375 679 84 656062617 709 819 707502845 500 577 957507296 302 715 320701049 404 817 359853397 911 470 523756133 635 465 514323430 651 951 979604443 191 585 113955157 775 229 965571764 694 568 923169857 253 81 541418574 192 303 465536633 435 903 195802573 248 283 933676154 99 504 694628523 861 775 182407708 566 618 361587635 975 91 927757338 203 353 603615291 501 672 67110410 123 222 22641299 760 967 699943059 821 755 262836131 906 410 136960078 54 74 892596078 785 223 195116391 95 953 678248589 57 204 127440957 694 699 844786967 231 793 142354091 588 340 433441190 899 755 298681049 215 978 884242819 187 338 725543837 620 383 243503531 686 779 131153061 408 171 158954614 995 539 235266539 570 745 903828777 482 916 836610477 964 251 32753354 8 939 370493632 808 935 932154987 669 37 742835682 858 835 780119517 4 788 172695307 685 95 168615393 90 480 849571397 812 155 63990410 854 358 739743256 24 566 401226719 25 621 542409388 784 133 286216058 375 331 574777901 324 74 770358868 363 464 477846853 958 443 763872243 668 844 858997400 596 141 404620470 417 290 935037085 944 940 380179587 518 961 296369832 909 541 556727964 441 242 511299629 999 455 173890424 655 394 388796154 249 833 324823480 432 820 953811873 943 969 239683841 551 8 546827365 200 28 865400647 488 790 935061470 168 989 403622554 200 902 608571586 684 980 791107849 889 692 875768000 981 252 944602442 685 405 328231252 497 630 445636534 897 690 84708726 67 447 842692502 156 588 170258814 764 567 146268733 987 820 13615281 632 266 866941390 876 245 226067028 657 981 902529065 647 978 745789339 737 421 617425022 537 896 52754687 369 639 193351587 372 605 82125013 653 576 58429201 720 522 481653197 96 736 177781317 217 862 2942334 572 914 224877423 407 751 870211337 518 193 109331609 530 256 180981227 715 847 702380390 272 164 363688781 791 370 62332971 392 189 933961840 749 146 346880374 436 963 269263326 487 864 531980481 811 777 48309554 525 355 563623062 257 55 546995821 310 672 751200866 103 757 324714185 277 191 645678442 773 938 947667664 566 174 949556628 787 914 904274822 959 410 860002990 746 583 667639752 833 827 587464302 83 334 190315432 805 355 71366556 931 975 188528962 522 363 555201660 554 682 849065741 453 506 79661096 711 87 649886079 204 779 881024010 992 83 642820729 972 580 975826779 249 636 33228554 64 977 699705100 903 527 575566476 617 324 793066461 987 299 106210929 614 454 390687983 269 550 532533231 187 601 559361148 137 5 405012313 977 231 724311508 708 244 872156230 203 117 139149558 51 894 500987798 318 871 771231978 973 906 150671720 675 327 653572151 652 903 33771872 401 165 940705126 344 538 383206800 829 561 913493856 741 711 431127796 306 524 453413295 201 108 804382714 673 595 65492542 647 101 272638671 636 279 608264735 11 415 321310318 723 991 552650071 113 386 610068314 255 798 463008197 429 571 358245281 74 481 643146264 472 40 87367793 740 210 797742685 978 958 669939630 993 323 707724388 42 101 149440336 298 670 299144579 92 775 255579344 151 626 106437475 951 25 536328753 430 629 911047748 901 789 407925253 670 875 453672281 900 583 683249160 794 553 732034154 162 266 106614484 852 383 997562402 213 113 432518225 260 226 374916792 463 249 426482413 547 152 576919770 269 585 554409211 348 889 94358599 4 923 442771953 954 548 491302540 897 754 641154651 298 57 678581731 907 468 803339326 127 777 353058091 550 270 747488324 256 109 857420251 219 93 713878252 626 256 121099365 295 927 770577010 175 340 964999713 64 795 215848033 660 685 45913579 255 857 945690401 239 596 672402676 742 101 127977595 61 365 691997508 726 60 571415792 589 690 630059469 120 804 966746656 936 272 616709274 615 174 382574691 861 458 317271800 660 831 888303796 931 419 234963544 422 882 968859523 316 106 192824414 915 343 856266155 755 936 247699617 715 836 860149868 601 718 162769606 638 252 287805764 555 111 240568761 997 356 171779613 517 688 782676982 963 336 159633411 207 323 353519185 508 255 926309641 223 409 635216474 679 140 117432022 497 368 26061190 148 85 335241000 688 878 180828463 961 741 218125004 93 736 946456952 948 421 324328769 755 319 127320143 401 160 222500509 175 774 211060273 674 432 590310798 645 317 106505697 513 860 412360035 375 130 287480822 776 456 180666839 941 582 47837788 723 388 112892004 524 407 141926167 933 782 760600853 175 329 905959684 834 293 7978614 450 261 381886484 544 866 188722772 109 984 34902119 732 686 797255334 542 358 265724304 365 396 540014470 272 711 364204968 735 214 46462320 294 531 897632475 385 7 20852922 489 593 367439376 787 303 150650365 501 892 701100757 357 506 341375391 549 898 136117751 305 503 684506654 585 302 466221449 920 426 674551835 700 232 693554886 569 761 687557420 899 94 218183278 937 898 538496368 264 16 121704306 455 240 87475647 414 802 501846152 896 399 792195593 742 843 391643161 772 296 800083143 790 116 281064641 782 461 407843055 697 876 277821892 89 293 666836545 996 224 504699816 96 315 643633274 321 278 881071715 266 862 499963210 773 439 902617214 831 844 58473600 279 744 27037301 9 570 643910041 348 326 685362969 191 760 88145980 673 373 578191231 18 557 210338773 747 665 668726137 803 961 863247746 846 933 390592121 571 1000 10418001 533 425 828385349 155 27 415336725 256 596 469683054 334 490 305726876 803 42 192906976 43 208 908310082 363 173 186344100 336 826 518594934 119 508 100362089 714 182 519146021 76 356 209092432 119 714 315619552 802 748 900120382 196 833 210878311 996 165 619954753 86 229 273306600 113 841 55249966 941 744 894908078 566 23 915180890 212 95 838339862 964 878 614250582 269 6 172916154 750 729 254989991 356 823 134623791 683 533 563303985 948 68 284181949 529 197 250923408 600 818 414175351 688 847 711244294 296 655 997526565 912 493 975765591 443 615 696925236 808 440 118003265 983 998 202534971 881 329 489255469 191 206 661260046 269 79 236817541 79 941 270325184 944 328 830867650 211 606 841282825 823 673 121813907 15 589 331803993 974 16 452912471 78 54 65922758 896 403 324860941 929 541 525220066 523 356 333369027 437 553 395221895 802 806 158299675 636 396 444213762 800 813 277227810 234 165 48617031 819 994 797347027 175 983 981535412 498 132 954845397 295 598 882987364 447 149 249530600 194 454 439487267 680 126 548079367 182 415 807790905 642 678 236208550 410 812 113212344 616 130 50689429 19 161 846271614 784 262 658472028 658 249 885441234 119 645 844048875 605 851 296071926 265 874 791638320 265 255 418878642 109 373 743277879 55 829 949453716 509 955 824341150 380 354 281351227 838 299 208031433 326 110 548337233 664 383 514920561 864 249 544507048 173 541 596527602 902 767 935602796 63 293 625254849 170 58 650187142 677 530 469423610 216 36 163639399 838 523 202790826 867 678 678042188 890 240 822219841 247 129 421880130 49 577 149947104 214 519 441101763 794 133 2721592 566 280 386111612 974 878 585189197 42 680 910009128 197 329 189437708 662 612 730781406 867 457 249417564 82 813 166334502 659 261 522057543 684 158 587305856 138 692 639208666 421 974 698237111 914 26 692168376 67 691 354518240 472 858 467328768 473 27 989266085 990 145 863209543 797 762 87274795 44 2 120833388 992 993 830072811 525 571 524665257 110 680 348625796 342 81 230192330 152 285 495459369 225 55 629312451 993 84 954793937 515 3 240258442 521 475 12009571 237 966 236170501 713 566 557777913 917 945 62159126 668 711 259702842 291 693 839307817 55 383 751706018 636 913 162893150 581 905 313953069 929 471 133622180 428 360 175467327 675 967 454576370 823 676 933891322 893 400 742991502 104 161 659747106 537 430 622359959 224 576 422441976 646 681 28250343 722 16 963039327 479 497 288599770 59 375 286315236 479 29 86748975 777 591 539380279 294 251 725676054 435 968 79044775 340 491 545772649 239 290 726969627 937 908 133344042 682 331 647185181 464 368 991120971 533 365 151830460 778 791 49940582 45 554 674206988 192 863 201094040 31 715 936656171 256 63 714316267 642 221 609024787 396 684 638522462 743 298 949959792 923 185 49789411 217 640 362983382 400 625 579401391 474 212 597192926 308 202 122606979 479 350 937911947 367 30 191969095 626 976 973033381 652 881 73157589 594 493 142960381 408 700 752972280 773 172 905098231 902 330 537564771 329 217 730828452 421 524 49533787 335 516 90549692 417 78 304500866 134 834 716629757 558 331 984581697 652 789 775703295 391 358 222673152 431 123 51854719 226 73 914875578 943 789 865956537 164 784 67075275 703 250 21087501 726 560 772820133 813 556 153079309 446 606 42597058 985 46 552040846 446 739 336350315 745 747 635874821 106 910 457744927 869 927 995686323 576 46 112265091 253 648 847151739 492 223 863438364 412 936 591263334 858 993 857081993 760 322 500454890 916 682 9138137 681 540 941334052 990 984 661746947 274 70 22701612 816 66 586692071 641 892 78368813 439 609 630440210 765 882 594174199 890 6 611686126 73 854 465041374 858 472 784995338 953 283 525726114 624 739 729995270 118 627 971445808 288 481 907115519 54 32 356781308 357 101 320803123 752 697 395961045 919 256 8684655 596 461 903424619 604 476 441766353 873 578 706833230 115 380 259680446 716 217 445806388 933 147 618905523 149 66 209343592 985 452 436629508 851 359 172476462 265 352 946753625 163 431 212941851 131 640 693753381 99 212 621208861 319 478 749158846 606 888 250729828 64 923 559680058 880 314 601791752 201 667 933725248 112 843 370332320 233 485 557742712 639 280 569193266 211 792 3254499 309 426 409978347 759 727 587437063 987 352 780506599 549 424 69309937 862 293 249680325 642 186 761786057 835 776 308045024 460 965 485105956 485 246 642928342 52 897 672213402 164 497 136848211 822 237 794158476 582 73 860484706 937 67 706634593 447 327 613521994 417 886 758229278 662 937 128608507 693 537 406828188 605 47 344652104 712 413 261697427 430 581 638996663 41 266 570192126 742 474 85214746 869 340 872414585 615 783 48118705 860 984 132541558 487 620 35597132 464 60 471029168 11 42 385630273 573 134 555761636 757 562 469679191 628 936 673415613 797 219 955974605 30 327 350838523 171 638 220192554 602 811 960561577 831 151 477035242 409 492 177165361 492 271 239109451 404 206 620672851 578 702 177253850 252 773 915280639 336 388 435758166 282 529 999950479 988 955 962662836 580 321 313918136 122 682 45413976 470 870 680769700 501 255 488782489 553 635 901675619 947 158 221448940 992 618 342854087 482 151 133106881 116 917 643590983 652 706 12500980 269 621 742272418 570 112 756188102 649 481 133684640 963 290 609407194 571 462 111515459 466 84 428886749 284 209 632481515 605 370 775478334 47 438 168743342 595 305 271203774 357 565 166883455 804 408 51378956 590 35 534294755 29 398 189015600 284 795 96289448 369 876 185480832 110 786 62820856 995 851 864181102 545 279 751440838 1 772 236527314 841 108 540015139 227 341 667848323 889 337 905759149 257 827 144339422 636 427 932484678 798 200 391374199 675 438 548950585 83 234 409146987 499 989 934399321 621 762 367079038 831 712 541375874 875 577 320357889 217 478 818778406 338 35 221059065 861 903 777455748 921 116 157290552 897 858 777444523 10 227 929555683 226 986 36521678 875 294 775776290 336 965 78742565 589 935 40758752 249 847 946980185 398 69 113746250 852 401 359363841 763 588 579706650 697 30 258306608 815 816 805376228 318 824 273869758 621 880 40561971 768 790 606024793 367 36 546851292 807 512 634540109 510 309 628353693 175 853 439521268 504 531 837356431 609 867 510511506 49 620 694742266 38 942 853359754 471 537 105304993 395 957 382419897 419 777 13034491 39 319 293700640 857 237 673830803 180 926 678257325 748 591 629183834 402 357 43162240 546 219 751312836 881 961 218478687 785 238 401582541 438 574 942832919 715 760 823003270 553 379 379416944 131 954 8140561 230 584 105830689 123 190 972483529 74 320 637696443 381 755 626154295 684 203 314224093 884 797 330230707 957 301 198742243 575 9 406454433 899 386 655627134 113 418 958884158 940 45 596267322 708 842 613584113 488 384 577854397 88 614 984794483 93 847 318271204 501 788 66828530 13 215 452223163 310 149 898827412 393 956 395072738 501 303 42780794 222 652 40995906 330 852 928859740 483 686 470003461 30 526 591952377 403 995 103176509 658 659 152426434 284 597 892243971 495 500 238453802 734 927 14163328 949 113 683187546 828 636 488280831 696 534 838040788 96 694 803926764 412 705 511597265 955 795 218713399 713 502 906316131 112 339 825383766 312 541 406906979 682 567 182158847 566 969 545088908 821 417 164741951 180 581 909397709 352 57 84478803 993 309 506328206 714 531 765688916 196 185 191332396 862 574 488221704 340 20 127974614 949 323 598648097 15 523 707766240 402 988 624555953 509 442 108124314 904 958 954937847 728 542 798913159 724 240 470780431 33 108 523617707 121 872 164602578 121 684 755708320 616 490 179385318 679 820 489321297 806 995 525667851 450 139 94654122 336 210 990701847 286 377 7273023 952 754 523158880 70 114 500368829 344 735 85813034 901 295 495313585 273 939 651660326 25 628 925712500 705 393 816016233 216 100 496550132 888 231 461502315 127 267 644081776 593 850 563622608 733 373 592354972 439 250 591252270 368 194 30339815 915 284 322095990 208 490 961778234 212 663 779454320 711 256 419625430 385 142 221570210 681 536 17512650 583 162 559888957 547 298 332790169 626 959 946603017 6 785 535358698 853 299 445657392 793 832 951045026 243 603 693964897 67 712 358439484 504 792 13960689 717 772 59293597 16 272 269421873 39 776 650639851 15 581 862541316 106 854 398820846 907 880 429253878 611 877 965930301 2 43 332725361 307 102 718001883 129 417 124093897 202 467 35200003 229 451 589612771 819 396 104881894 931 335 364782845 275 964 377133203 503 365 858703267 89 277 678449072 646 156 149327057 69 115 937390161 621 428 899479985 412 148 611255731 471 669 562449785 455 418 29481654 917 507 478376093 808 86 345406012 941 152 499834011 931 581 769208389 133 207 982373850 964 561 385847146 485 421 540051168 814 234 764470577 506 466 151626709 150 476 247485637 275 212 549379990 166 34 982882971 432 705 811170878 371 377 853682304 627 295 394364970 669 538 78496495 986 737 215789800 965 233 941868612 651 395 576765958 24 501 65888683 546 809 600724052 840 751 334136645 463 142 768903003 606 727 44349080 397 694 421291052 317 880 907195333 70 382 581758197 545 673 491320608 645 213 859497249 184 44 906934943 981 110 757612118 280 73 903973590 940 266 793484271 568 567 77848485 18 969 479463251 209 142 191639623 374 832 822060158 237 471 700810190 771 720 131206370 648 401 274539233 838 367 964864331 857 862 508730101 922 273 308952935 633 773 956513740 645 296 936097790 753 103 617304040 667 27 278902334 829 458 816549404 8 408 99900978 397 268 520271079 620 762 714195456 563 627 530562019 768 372 7654852 507 301 301436438 359 494 344732271 542 9 450534643 43 406 189370438 231 360 811398766 590 6 723828406 626 59 28678285 125 69 130794484 993 99 9063471 255 953 954402025 991 970 144846540 948 254 425824664 5 338 788891413 556 857 491685928 415 82 561195748 649 764 280392652 679 294 111134178 541 254 472841683 600 971 593074932 686 609 598155090 702 789 680189286 132 441 319674590 640 147 521641964 524 437 253041624 559 837 28945918 926 119 333220335 244 51 326388276 193 228 980780348 773 950 839029366 603 95 546160551 366 230 244817294 384 709 625416401 925 448 20002462 292 707 137319574 409 706 397201138 435 556 61733128 475 693 417750951 211 235 665557008 942 638 776634760 618 347 791306110 346 148 924069708 488 857 994444477 114 431 645080388 75 923 419867091 859 721 75460590 445 992 178655307 880 865 585552229 79 916 756865215 329 833 140666543 688 21 221056054 112 353 871496682 320 742 267721289 199 598 304067150 332 176 364940775 996 523 645880406 820 178 271780402 118 818 41256929 387 686 213987207 191 84 73735524 50 267 674584632 54 664 265243979 762 197 346047523 224 676 377780431 53 765 852477910 815 916 36209378 854 1 708325496 858 962 406932910 265 632 417508905 717 885 828165351 962 708 909684906 373 776 26154316 183 870 558665405 823 451 96515450 921 728 995939697 107 777 821597 866 286 828178810 608 706 414500639 699 593 825418808 554 539 447099100 791 883 595409879 239 710 57944590 562 865 338555576 550 477 193945282 513 589 43059238 422 354 585405809 981 124 973798000 251 63 365912334 874 973 88312278 342 360 412190707 339 801 99525083 220 489 1475022 377 522 239650291 946 473 292522602 792 620 318332599 605 579 648379349 822 143 941512120 366 593 85841698 860 451 912541334 347 674 349297441 247 160 104483832 712 808 552438827 849 118 838421557 427 399 704781360 468 707 48022382 790 829 442076465 817 658 219399010 414 188 434573834 823 935 672066144 118 747 658230535 806 348 704727710 627 612 16810014 74 239 473330283 443 888 442222806 838 475 132347406 299 314 636498513 579 690 711727047 347 823 385964830 949 741 374340204 7 426 339614113 484 544 845685822 865 635 70171054 561 479 586849508 651 536 610248996 271 953 752193135 255 333 382183899 407 980 103454693 900 320 806927714 385 680 707175012 236 459 973364777 572 6 521051958 868 466 981381670 813 369 608252843 36 540 147702593 319 235 287830909 469 941 774997706 726 850 59927393 334 30 963255890 714 286 230001881 635 126 575906402 596 936 113779840 486 592 401912193 828 125 628755699 284 393 994957506 7 445 221910853 850 832 56387245 290 227 741928240 995 425 247509380 237 548 276476211 568 86 492501325 738 82 218371714 860 635 497217115 642 324 220692533 595 704 367048163 196 418 984621587 288 747 589921920 343 467 992191993 635 897 17077975 613 14 255876357 671 282 402497548 580 1000 428169800 377 522 966816068 506 704 705128808 264 231 222703943 397 534 406530801 588 205 592680540 141 279 521643553 854 730 331307776 819 902 236059219 66 146 509210321 883 661 780007598 301 434 917460623 841 810 845332078 142 303 648066390 807 13 613727075 839 766 738787938 400 857 666879115 493 96 104484016 125 566 547859189 130 795 468965372 861 453 726063595 679 99 581959690 567 601 761658120 368 107 351438221 950 502 414160343 862 587 1640378 409 163 987965276 767 397 583295516 975 707 517362948 794 414 737883913 153 712 146882039 558 820 870900132 960 466 481379070 873 471 647993251 649 579 392877295 599 98 323643310 991 261 323957882 428 239 790717374 393 49 807312921 757 269 669839982 408 986 217561424 291 467 110535980 576 553 213466069 318 849 329159879 600 13 186027013 508 609 520453512 906 608 397999607 978 166 263102602 660 131 314480895 119 424 472056055 72 322 260608851 314 22 999817901 738 494 226507073 305 865 863055704 891 842 96400230 665 830 672442148 248 153 700191152 800 710 595848803 703 381 476230460 891 206 42035598 541 25 327163779 983 308 720932853 577 192 92065329 411 833 337372226 683 757 304552507 3 555 942187989 537 480 246943740 846 800 297479864 700 61 642260429 687 482 147654078 857 845 882500802 959 491 689234107 187 140 461951877 85 818 847666635 479 594 93374490 171 283 953570110 11 354 787002550 831 855 328814969 800 779 650540649 318 234 92264063 492 554 168579781 451 745 956009852 171 576 304346162 165 319 798999989 999 743 220903296 650 158 572873632 898 666 549517781 507 933 286406116 474 752 977537747 373 194 451632638 118 583 194053112 468 720 873794036 141 910 954090439 665 277 640535807 819 435 538654969 625 675 364611199 258 439 102748615 987 652 27628630 840 253 354687754 632 601 898841913 363 142 387275513 350 464 346491599 162 429 646562934 279 323 116490530 532 153 745868964 125 4 641521227 838 608 208283449 590 882 65572014 710 505 309047593 867 674 561546230 516 245 468488042 384 86 540883835 161 553 492084299 703 222 862335417 548 27 746335249 959 582 630985639 19 894 918356156 864 96 672648222 345 99 299215051 270 770 848662081 721 819 876547457 311 927 973110853 735 962 863273296 978 241 800079054 513 426 930362703 926 109 338811571 259 925 753466037 223 522 370525238 16 116 224641525 8 181 612917746 538 677 765731419 875 175 706339751 869 293 838752362 42 46 991239526 464 537 884288276 874 603 352311546 532 738 252449159 205 373 55212251 721 335 502520221 179 51 573446520 753 232 267160720 856 559 662871096 359 803 753402133 593 347 352092296 586 132 163248304 436 662 428701096 642 391 422116012 149 448 322632641 103 68 951271337 374 338 405858320 684 815 991738201 552 411 22165104 611 887 743736828 279 629 802160963 558 351 95008857 282 970 600428245 330 581 716572087 196 456 137515653 683 407 238036247 42 643 274436044 960 949 518617222 936 106 959956866 987 43 388308758 70 460 676155031 377 363 934122650 693 829 865615825 356 327 666346149 500 640 407792507 358 633 701303097 773 889 213513511 111 708 650807130 434 715 205760343 517 917 598676706 706 238 7975805 9 652 565639711 145 18 973816060 448 737 247731600 15 380 336106947 213 525 890964497 343 156 681385542 431 70 824930477 414 664 954410892 381 370 635879410 129 71 481601351 68 396 796746882 477 334 845262550 362 827 253130502 3 725 54334163 622 961 927061511 742 189 623275038 519 977 826345790 754 505 887073087 682 879 550569894 350 189 796057649 678 67 684940104 63 40 159655372 304 458 91233867 489 333 804520850 254 546 573405050 419 766 807328396 618 255 272485937 53 881 999288871 363 28 552116776 916 457 12129295 493 766 599952839 403 773 476720311 25 695 788800726 943 446 45767718 772 920 369731867 171 638 851412147 655 963 779267825 552 250 657332481 742 57 40948498 477 261 765678288 418 433 952703165 772 62 765676704 623 746 88608525 256 338 74227778 900 569 285191768 914 951 513830983 414 794 414487874 878 251 878337137 57 256 933511703 451 733 156782288 623 644 886771768 463 770 192758411 309 611 50479150 596 917 335451282 599 864 679068253 99 487 225785717 321 74 566385324 852 655 991538773 947 477 747642781 820 334 676088421 963 796 468303557 902 285 373971970 325 126 21428360 481 961 31142425 744 831 340446170 904 443 61855811 507 172 232017764 347 715 27718354 144 373 514017226 924 629 850470542 609 94 768770433 563 504 450626863 588 110 110266717 627 588 564819207 808 148 900697593 938 523 699000220 639 25 805412534 410 999 309730801 161 645 770711556 776 694 258692632 313 337 975952875 421 74 649475871 4 842 964619467 326 879 113670798 503 393 561946134 157 231 375453881 49 599 726678091 407 23 419703917 3 325 856850822 871 635 170586029 590 657 571236844 384 631 778931586 279 69 845146016 341 737 249090954 973 731 234794863 181 103 406114223 327 846 15875235 980 42 833744620 915 872 44024533 502 407 148492796 51 48 705072565 582 724 914969839 677 599 704830504 993 834 393638596 770 489 222002820 902 126 427533108 325 92 413063859 152 602 53340128 602 958 340578714 726 394 759612601 495 40 240253496 955 372 267993219 18 597 81504169 235 869 785975848 819 167 15757180 24 674 806803294 655 218 681403323 735 699 406500235 17 503 69571086 292 769 818518019 955 224 833321114 391 556 289888733 956 822 338552006 364 743 770738331 390 986 823713153 640 228 246200254 806 793 351490539 998 846 792805411 515 922 332895774 164 670 709999359 960 104 497689392 257 651 431279909 983 692 582076896 991 424 386217194 285 585 326237333 668 990 92376743 59 551 734585209 372 653 213867316 757 696 80043241 685 201 666178733 995 997 423575484 372 779 523041726 415 184 169435024 355 460 26435832 630 883 456024574 461 893 537621808 619 882 480264493 775 90 581436871 873 918 158578128 873 628 270948833 876 823 624959159 666 318 367252307 580 823 777505852 968 688 452834523 768 797 864864952 508 952 478966689 935 881 455767977 25 972 676495689 603 337 4111297 134 782 12658081 596 309 304983788 944 385 856562297 114 752 775477773 624 739 251191645 177 596 363156454 697 680 830000793 141 339 595314866 292 814 667181946 843 749 90279904 586 850 867814415 566 649 321739188 96 536 498015354 152 957 493452168 291 288 469158083 719 788 315562813 647 649 361019800 115 639 366820858 167 159 663911487 591 785 929436534 2 541 877433909 807 194 949885253 393 993 844799499 550 411 413045876 136 592 869197066 640 379 367703409 207 501 326681024 286 903 918574815 360 258 897222961 740 217 876658185 994 498 343299776 633 1 56542508 368 793 295251285 259 676 300640448 919 324 881560660 419 813 243036620 860 536 984122681 404 126 298495126 207 975 65876065 161 714 820257699 33 118 433614500 204 759 154586830 997 267 907526100 411 601 811107498 448 18 509132132 689 178 931860621 581 457 703795803 306 951 153414367 213 557 415880111 839 609 422597461 850 759 834671378 266 114 396188596 224 333 422271788 194 320 468120810 753 71 744669604 964 511 75028663 299 812 908206045 875 911 250555299 324 470 831620628 970 128 260692344 381 690 426240864 537 817 256884459 212 147 588010491 209 733 49034457 655 458 419426588 319 283 109719353 278 689 423738614 567 907 324111896 300 5 208406473 89 237 221060304 616 920 776024676 773 443 57220 526 582 748357977 271 693 422777298 418 824 505782547 534 501 476077304 817 151 618292996 162 954 523899842 841 396 762292801 408 276 182331304 490 804 492085039 576 26 572709364 438 533 259936262 931 902 274843400 339 211 166589426 188 988 759327245 809 80 385667301 916 88 320329816 282 410 90877993 826 442 462449359 370 477 158765937 221 380 808952764 202 864 463484044 858 881 622725563 759 62 277601303 587 476 68522156 412 278 417600258 208 526 777045118 895 867 463661163 493 242 39502363 969 692 164135676 86 663 598785593 285 864 480404579 182 449 855469582 258 434 53511897 730 606 369598222 345 528 770418114 433 242 79831407 632 640 641442435 293 91 55134316 306 424 574205312 488 662 162379607 270 582 763955955 512 891 881014532 737 151 973514775 622 983 724468709 219 292 455006292 464 513 805748618 258 614 508463474 384 170 764351642 365 894 428804909 234 453 139629004 554 823 411638972 805 677 530310877 169 499 893856810 878 784 950972226 641 305 753646563 739 651 846550259 465 588 868928184 350 361 841343442 995 627 133517887 235 708 488461284 119 736 482170286 457 595 155236721 314 206 306312392 858 73 330299449 761 198 867374981 595 720 354097368 654 554 591632990 466 345 802911556 53 511 362007690 483 431 911514565 525 411 995177289 541 74 704743484 381 935 368662263 396 740 211184202 888 769 52143633 815 136 992104601 696 81 316477692 459 926 826265893 634 622 372962269 203 974 360334320 590 764 521593308 573 821 636439150 99 797 2884064 581 653 784315598 742 982 580766461 502 849 605291273 133 349 789346584 217 996 789056369 448 139 19345139 63 980 468845711 495 110 667756307 371 282 701624858 510 352 901315315 508 1 232037 731 485 758036413 680 366 846679785 759 215 160955226 800 813 832501208 81 969 84910767 331 350 771087783 742 832 75297535 738 402 462090762 644 582 326324661 909 490 540941727 347 654 644069465 32 871 603497881 789 527 831002715 774 32 831320252 484 447 403335330 277 657 623043871 322 685 919605347 339 444 461359893 745 517 983098672 778 978 472321928 897 565 423261933 356 785 902361454 305 298 869527373 751 818 710136940 84 53 594306043 536 638 163395215 305 273 554113822 855 708 83449452 105 405 435021575 203 656 76150521 878 623 323570801 313 243 814692464 907 440 225249386 461 609 468179860 943 875 868842954 626 314 18326355 920 970 211866871 334 583 131422672 162 275 17006510 140 30 657560498 469 199 792040694 444 67 320970628 648 455 56505163 911 440 810028765 410 971 319663315 322 776 808770323 163 406 809335826 524 845 526927481 174 789 641585711 58 861 328820104 443 826 189729537 519 302 997769723 346 931 904561907 277 977 129252990 535 711 161558885 219 740 53125310 591 299 679268807 323 866 718071372 190 983 25469199 328 229 461292570 210 675 158642664 250 700 864916623 431 232 489322346 852 741 203652327 902 673 726367892 466 129 338672536 323 659 886682359 545 156 560409217 607 83 115277801 236 611 439298122 627 625 420486311 747 835 939198493 363 510 373494088 374 160 749058378 908 306 701927751 845 695 718372409 771 634 761004320 664 749 153586105 106 909 634712330 609 929 420148239 162 528 774835758 469 215 547490658 948 812 617968469 327 783 770992167 908 594 207599248 593 901 740545266 870 752 274019722 724 186 362181577 3 502 882707345 996 155 146465094 340 97 789932801 562 23 428610695 161 371 370939435 851 939 630172561 493 796 822208314 235 982 229082671 339 867 905562333 285 299 352517022 764 56 863337699 928 493 40886737 497 683 1075218 875 413 880954311 82 795 366903900 700 155 267190097 504 925 840732054 242 264 224100689 961 618 473208152 159 172 380070945 450 766 142769644 834 592 484416215 32 257 734269014 43 311 775023185 365 887 650925398 415 841 251427586 259 621 740856112 326 719 355068428 957 883 129586632 126 221 780293315 286 583 168883104 45 499 242721988 158 281 81721914 47 940 900976283 62 232 756616428 371 729 825310806 513 728 976094301 549 745 503687130 394 825 259329529 366 390 649206772 526 692 462574482 510 260 833131186 982 89 411532729 908 215 45340219 884 822 177054614 46 276 301432537 15 686 972746142 401 831 128531685 178 968 622267631 579 968 231757785 668 72 779981908 982 122 152778244 517 252 764680551 341 373 977742030 300 507 209005167 464 697 178515092 757 633 822858385 768 783 901210133 922 939 526202024 855 680 68024360 103 24 73671237 239 696 835941071 444 777 897498879 208 863 946164411 778 180 518627763 471 514 715441615 306 838 915280830 62 787 848605854 7 900 965269367 397 676 798059321 167 154 36236465 989 365 956904237 936 157 644722249 208 350 265191892 868 583 77634026 276 349 612033519 708 757 197397264 987 108 948386432 170 455 278417779 145 272 772424228 171 853 135725302 395 315 296434805 687 572 312372220 849 786 606565455 236 359 558078681 843 314 965370532 116 57 647287568 28 108 900637699 645 242 206126046 567 465 765655310 805 707 530957652 605 310 592525781 5 636 229133125 565 88 277056809 656 63 828908145 278 161 212838892 522 370 281100717 356 667 170543517 602 199 524460482 202 471 28672272 1 417 344312293 538 435 660107901 780 517 529371300 348 753 666466763 714 82 794082321 545 57 243538583 614 807 295751554 312 545 929074890 434 747 837567974 43 531 158686274 829 922 466271334 247 706 910707268 692 226 632530181 287 569 525612706 598 423 144555260 605 190 616134309 681 816 540738812 741 675 854873492 213 680 872811093 596 390 769488394 294 455 888722831 122 949 538817093 609 607 480734804 677 88 225091544 803 5 696151619 982 372 52778845 996 583 996753919 327 575 881276134 679 877 347922370 343 723 28292602 494 524 444750752 96 53 610980011 626 430 561078286 80 508 315012205 144 773 931395629 783 401 761388772 396 253 475467737 697 516 522439382 323 980 793165569 44 498 174618144 938 223 320477567 495 876 845417106 131 974 499293871 988 85 629183895 168 550 843829396 358 701 948160444 638 953 89685358 789 705 959036696 136 873 19533881 63 557 859422478 667 363 482321419 36 628 829558635 185 809 895599136 589 746 38158045 695 154 108458190 804 774 170494797 58 147 527264132 644 361 563736002 131 737 889908337 19 479 626583196 286 938 581762861 995 699 497185595 202 927 431660723 65 424 357830280 311 580 442466911 162 373 196541573 255 600 240298712 176 190 242192434 878 111 829448065 725 303 976099126 605 157 245489107 228 749 817192431 697 647 74240902 822 673 249959181 843 857 635881014 344 787 168637072 917 161 63471837 927 12 577455321 75 517 68986965 741 334 965440568 169 961 992056327 55 201 201646003 434 159 580372031 857 455 271993075 902 959 483731240 844 690 226188900 404 105 391331396 934 878 492768892 192 990 767352048 739 930 910071926 675 873 589042607 235 909 11881177 259 173 387584975 161 211 110379015 363 276 643336081 392 698 211246883 842 495 393370320 580 751 332758706 733 111 225172743 873 25 768920890 469 592 456287547 617 594 45645058 648 716 910765853 213 259 38676765 422 792 942687795 589 588 35978989 568 571 857607906 678 856 457092681 733 418 168941144 150 619 854253659 876 804 113352797 714 491 992327589 517 713 197106176 607 768 898861066 629 915 811083214 480 31 343080376 856 252 592989803 279 894 790031517 198 385 37520513 575 431 329525918 774 219 598788305 331 320 783801304 63 625 98077222 365 849 55620612 197 766 863976588 158 863 558570985 604 564 510022271 339 361 696983831 578 939 895985442 557 452 953535989 805 504 130276283 885 424 719478219 969 680 547903765 98 32 933835123 267 463 459490402 447 435 906321644 131 926 728303306 411 470 844454999 242 44 230081288 696 184 277930506 933 974 899565689 20 581 258470594 872 493 863256275 632 597 448875591 751 803 289634852 84 916 105207262 770 451 160410573 947 346 817413604 486 99 180643952 997 644 136837114 519 917 319443129 236 990 377885578 38 929 39436855 728 967 384093358 229 796 511303634 365 574 548062527 609 987 135083150 838 42 865671977 533 485 730593393 131 268 567071678 457 531 263349074 718 730 406822079 265 362 196242059 468 441 945836284 927 763 517480316 378 451 581058658 516 12 811110687 369 516 579949051 904 597 659470974 6 261 956748866 416 83 322723986 761 336 143360836 888 967 792371700 260 864 972374592 495 160 798513930 984 344 280793286 325 294 438772544 726 886 271871514 208 268 761166245 995 866 503523266 598 439 724199589 409 910 326018505 814 169 196844933 27 216 807747315 1000 7 473629440 561 306 889770733 483 670 698939872 300 502 308638531 332 17 82028233 639 437 184725744 677 57 927296896 505 988 918118322 163 635 10724672 775 221 192559328 496 628 719563352 547 58 993774564 190 868 268929639 991 959 841253474 927 454 695367596 768 21 152337000 88 47 959474179 702 237 274011914 215 284 719185486 162 305 517871521 711 190 510720565 771 616 408213669 469 82 261438538 945 549 807630349 798 521 157601270 643 158 536425487 940 460 600164392 725 765 819864537 514 686 533640745 781 699 479668592 451 604 325403840 865 341 795296690 829 71 18151996 575 383 951609589 976 571 971901121 66 179 18080391 281 516 353836325 188 397 680424051 488 688 718053680 951 835 37533165 782 211 384670423 748 778 606667984 154 649 464718547 988 914 764380961 436 847 697611148 629 694 243881941 444 946 245645017 963 805 269670002 584 7 122903750 879 167 978548872 791 905 300506728 940 812 17274254 140 682 127537212 761 728 275712614 985 459 14754393 181 774 707349890 986 684 442870410 401 538 723071871 215 773 674115152 122 935 266209182 619 567 873783179 485 896 422224863 186 511 520622315 242 207 291199048 259 957 707186287 249 791 141889497 34 41 198148069 401 397 63565983 869 96 495943427 218 11 959570231 707 763 76760805 88 506 477972298 895 98 397805807 634 247 632256035 281 959 602061064 794 458 298721608 12 386 501863353 237 553 119230608 351 614 162720853 71 477 448530072 307 340 907801142 473 432 626980481 262 582 675056319 970 516 379881324 912 965 989156561 792 376 508935024 962 445 401003468 826 617 902806751 953 773 457886698 805 227 632724267 847 901 881765546 855 527 746103639 285 988 55917397 987 896 566020134 74 571 349300346 72 166 662667822 658 258 820343996 229 927 694111144 457 259 678138864 768 985 49476530 939 221 934191473 993 932 18405348 345 793 639938956 495 273 706124998 175 307 859389102 399 425 775119838 559 775 51425329 235 763 40039268 974 210 933282213 653 282 397031231 55 84 78924961 299 469 174208013 813 679 546422615 218 544 14628166 987 574 472543206 473 483 383102642 235 998 470433746 212 626 149866292 906 701 155801083 970 80 524123656 59 904 679642362 213 612 907176216 501 5 750390345 242 739 843158583 155 915 902253995 869 636 597530761 988 789 155592675 45 361 310732825 290 515 927641379 139 23 678530604 21 83 78254260 22 552 373948617 745 547 463403839 608 637 913995461 14 40 376432417 302 25 911878796 740 606 320477474 408 802 450168994 246 180 997659238 30 774 190658261 553 830 396516484 794 203 846849341 692 570 735260367 938 707 212920075 537 260 440790266 23 920 413591443 118 26 12347305 375 138 240330901 530 576 833341758 8 203 113957783 597 81 385246884 632 833 212137580 433 485 640909159 702 296 55402212 661 872 881497568 294 279 126870845 825 291 634850590 719 240 409878930 11 764 658584602 625 590 447057596 288 427 607449597 794 579 699994915 219 317 990511146 138 352 122371080 400 211 441403631 733 495 503889680 312 240 822426243 996 680 788712901 522 293 136618347 308 934 105363443 312 843 273510141 92 516 554523279 799 413 296528430 362 157 579530257 238 170 561609914 643 728 466233965 773 165 338212518 805 544 526966504 300 708 420501662 990 786 239653855 433 94 271030037 50 37 117145254 340 71 174595566 147 276 207107744 662 871 346116418 116 51 482733804 509 659 178395747 428 685 714850715 682 177 427807587 402 714 508762772 196 911 464531086 86 120 780051076 43 834 333539250 711 708 990959744 692 596 338017023 662 677 92154246 77 710 496637347 595 156 619760829 417 177 119347890 410 683 848441789 982 649 537232806 15 856 493055404 359 71 66891643 212 903 235543260 176 461 603149394 581 282 119923339 197 820 67707708 860 468 79828881 27 278 137825022 208 624 837207517 281 906 507054953 656 752 271157165 296 685 371229345 138 808 483817234 892 399 759352784 125 70 579777615 649 880 867526937 325 791 14698156 976 230 915048662 91 219 993855462 896 199 687703605 218 596 518832771 326 47 344478864 39 389 604522232 543 764 374577787 594 110 549807177 308 40 162270824 845 376 803291953 512 605 918707510 33 585 50483824 336 324 94282732 423 655 422806361 218 302 264918392 589 999 711782215 98 528 212539055 328 941 559119277 907 605 51843880 522 260 181163281 946 775 76668680 762 102 160588058 324 569 945781149 945 937 854448855 91 413 1065317 785 402 542197132 444 674 497094487 817 465 16628828 400 111 441016923 225 935 742497087 741 306 239622285 792 866 235607188 977 594 298591016 734 322 624395102 862 760 47533322 866 280 537372045 184 134 155119882 324 689 138207302 668 998 790973462 690 703 471877468 92 213 968881896 21 273 835269268 966 454 851947504 567 837 836614381 349 950 369730525 931 318 922611181 700 232 297894127 563 307 586650793 106 82 267495928 605 40 941317020 236 262 25820079 321 502 63278969 842 724 154105607 873 959 781633243 334 928 268235763 634 764 80562316 988 638 994996549 101 319 956450759 705 121 131178983 597 656 155217185 741 664 997689848 318 909 906642939 735 431 569020156 739 892 860268581 770 612 544841518 627 869 707826915 527 276 222750954 767 271 864854003 31 255 400032834 792 323 236931360 643 980 934863862 806 75 851637586 541 271 557154595 972 568 3411360 470 733 671046342 350 174 856567705 245 372 368996660 303 667 54583042 862 852 277894169 841 983 423104245 12 323 484052294 739 222 252537689 522 722 700180285 34 179 802580786 828 18 819035641 342 244 856583213 671 335 940221426 448 63 66236524 950 586 428666860 730 858 877821639 766 717 312817145 700 586 802064747 821 875 569557333 380 390 298702935 494 758 911122609 828 171 90247768 536 558 486897121 276 775 642269863 891 281 906541790 636 970 747835893 189 933 937945582 311 700 468471875 510 161 649594850 955 165 241667014 803 460 4096530 231 394 669017029 396 342 35803401 201 880 444162008 445 3 598204506 90 4 2202679 439 775 4658713 394 82 505639827 863 77 852709457 59 681 323623439 475 186 357884677 831 582 906309692 966 898 99528473 369 46 392901171 87 230 549948589 606 980 440448585 160 516 578947311 78 836 673330819 238 9 442382281 922 156 141337985 63 203 716311037 229 277 304221336 509 91 477313623 915 434 400345128 548 182 220261694 639 782 837102518 505 211 963061536 611 832 29599228 116 555 922581878 214 474 547576187 66 815 496391001 493 362 679607631 176 757 593658195 938 624 76876116 565 756 523869538 671 619 355036730 262 329 13887600 77 235 333705393 945 688 516487782 266 648 781418150 740 643 94237143 566 206 463893034 387 944 656352371 190 279 405171682 987 182 200770065 634 683 88004837 809 2 520130568 538 498 688049434 330 400 294289305 805 655 4260191 805 278 871283581 832 424 583250370 204 365 439102231 818 903 8813465 919 552 437848339 263 858 68314835 634 498 877846136 227 737 14071634 351 766 702867115 143 842 194703986 958 861 397395324 754 284 4200442 324 21 293769048 533 679 168780838 417 259 880250111 691 775 814816925 267 187 220201091 914 966 411467339 244 677 272595596 279 477 831013565 468 767 345520 29 164 762081554 470 856 523094873 345 402 237669815 744 633 450965157 648 428 516422402 79 586 89142099 459 705 610872919 4 203 757626174 828 105 458453550 135 472 32221706 285 142 378255091 538 469 508998029 201 660 122430689 627 964 853520478 293 3 939667732 254 763 358199758 875 898 232471152 56 769 87042022 668 689 874610582 421 862 721240886 764 908 346319443 835 712 441257735 743 835 453804479 443 314 512352153 346 777 506508971 992 519 701617292 630 360 461640589 680 317 36444821 925 36 138896081 896 528 520108324 998 240 604893822 954 292 786334652 581 900 304099531 818 531 534082262 34 735 225365533 864 980 7191517 81 559 148434498 681 347 770023369 618 784 76183114 443 620 377781545 183 86 191492219 325 958 817273509 675 7 887798643 469 805 321315825 689 260 823332010 145 440 834063896 950 424 79236090 930 172 310571201 55 331 475326242 18 876 326070221 637 648 587694586 210 538 368750759 402 612 334187890 967 722 760040740 420 142 56308435 682 349 740971401 278 696 773404264 352 565 712722681 650 897 298956485 122 89 553621690 54 346 149490650 405 663 950270379 231 35 536389395 301 335 658339690 979 146 790327646 214 181 458571477 926 907 233267196 769 21 490858755 783 9 728629734 703 72 575508418 458 301 974469832 506 61 166546372 696 632 573553351 9 637 322007012 395 345 939280554 506 591 120936374 481 251 542004340 840 301 875595417 749 701 565953014 821 469 435687781 26 401 220337932 633 887 19860569 739 160 742921325 608 120 152938238 795 903 403383901 128 442 205793104 252 452 633118846 828 432 637178611 60 570 290614439 567 901 285591184 314 206 520553966 645 406 765954681 516 238 147704 139 954 245722020 490 529 360126299 463 899 7271959 827 367 213344659 400 498 854348624 324 652 353736209 742 237 72865019 476 823 183785891 133 546 996827986 40 150 386553671 858 544 147498386 886 530 92485782 769 578 572555691 925 840 452524403 436 245 647555597 980 965 361914119 356 411 914139716 468 108 15608585 192 75 927045720 96 542 252590857 786 640 260405748 326 198 852710159 351 820 961734439 660 121 382646711 512 340 286224871 836 771 307221929 403 804 671416275 625 355 854608513 497 259 900373375 820 322 295942109 85 337 873713079 498 230 638872191 282 510 137592055 120 599 798389179 23 142 616588342 990 199 465512428 997 47 273536757 36 61 787738965 630 681 402995635 189 509 858018582 302 757 323534507 811 43 484356450 527 242 627734976 905 830 353961033 132 821 469441774 342 807 244598100 843 82 280803837 420 519 603215049 275 875 702531957 417 707 124658631 529 117 510674518 824 221 808885521 445 676 680715023 399 999 152072440 904 876 30062538 468 886 802454474 490 878 15805042 841 588 956334686 838 702 49138896 95 443 262528162 760 135 819909761 577 709 162725509 283 861 57803151 751 239 182141566 843 675 631690186 871 649 708775064 444 800 271311683 140 142 274097778 129 526 147809938 962 980 160298917 968 490 975406213 546 39 364681333 23 910 609394855 747 295 602127924 650 728 96486921 711 542 867267602 182 46 657491019 133 859 842566380 306 149 956463406 834 335 38549 242 651 47668174 505 908 100035254 886 900 862731960 778 622 696241175 894 204 570023581 275 766 254558965 491 379 557080 985 425 141007784 391 637 457910427 265 176 788811437 424 697 369370555 364 445 279854266 733 863 496436547 404 736 356470049 217 452 880773855 588 696 331822537 559 45 347751286 84 58 714648879 890 98 56182712 813 384 406845891 620 799 261767663 12 989 890596255 197 655 897793180 91 18 866446256 41 679 686545020 848 157 543511452 208 597 205908172 167 696 645783045 684 239 154924644 426 793 898460195 597 519 992119081 663 716 678603387 467 679 354779629 776 876 670372496 626 560 582747119 86 614 203491957 609 422 384016642 811 534 281704427 485 560 211969277 494 864 794817142 855 340 884555940 515 136 736910042 421 387 678842639 140 336 551400567 393 408 732730995 162 978 574595972 547 496 316512483 957 170 726820270 860 900 292070441 852 398 996494403 945 8 609636810 535 168 201556579 890 916 185981108 37 291 123777103 292 71 375065424 102 804 919030174 349 854 524852147 886 292 834045843 914 302 319114599 67 140 344459642 861 516 193876944 780 777 599749694 709 78 389047758 835 307 509900128 321 649 323810787 143 795 232420176 530 49 899460011 743 575 632392523 703 229 953317434 464 538 99966056 584 346 483349787 729 684 558436204 474 286 831360112 999 378 155136761 664 776 845294955 853 574 364009219 742 791 769038022 191 43 293717169 524 488 849913731 934 79 757954334 560 410 454292809 409 205 531066391 367 359 255334262 652 659 783478810 595 435 652186049 624 255 624726923 35 93 214578235 970 633 371437440 35 810 148476818 472 64 147466738 350 680 426710528 630 128 848608100 545 266 527404574 298 358 98989883 69 963 159536728 885 988 365740151 951 712 864385729 401 301 530594163 636 232 512855872 827 868 919571112 571 98 348449253 607 425 148547164 734 572 703398746 380 715 924005919 200 698 305721132 87 263 713990759 881 404 70129159 645 492 530210875 875 164 63971791 757 420 496272612 695 517 145754522 587 821 940716978 934 461 855081913 111 291 644526210 372 795 496112132 867 153 898556757 81 168 804491107 815 72 772921657 597 365 453166842 932 497 515505551 649 261 143632230 828 666 377984219 885 490 837615860 464 546 297479148 356 728 271385815 327 771 106170127 74 204 858416161 582 779 217182280 626 805 950416187 763 38 188846375 473 134 143234058 583 257 946983364 137 609 492037416 861 178 259474757 426 889 765656116 503 497 715992516 75 307 579789303 613 91 425509175 360 376 484900501 307 774 139576667 548 798 218144635 196 811 56479194 845 719 314715485 231 110 694256888 756 800 199366461 594 154 597691277 417 95 972631447 370 343 404143228 292 320 961973999 390 102 274744529 211 405 552947643 325 933 622741080 422 211 677608810 965 36 575377374 435 166 321681008 987 930 990810765 575 914 652169766 56 926 706198672 170 61 837462595 152 432 216684211 361 579 729630328 910 998 146559878 689 486 543663706 775 857 128229284 480 891 533965496 382 57 796382624 913 704 114474781 967 5 328866295 524 822 625221194 150 876 968910808 299 922 743447288 744 742 585493152 493 717 197865320 926 170 804485866 664 715 999838430 129 111 348125845 476 757 943257158 183 574 750339309 823 29 668490068 968 617 378113705 101 993 377854585 922 190 894989836 847 915 939138539 913 368 414796899 816 449 43668965 173 646 18141111 647 659 599362717 627 265 202024114 380 485 181604588 186 518 865103910 33 415 13657596 731 398 879892972 593 180 588123583 467 282 328159368 232 538 216723187 187 300 656956127 116 488 738605681 937 100 135855079 584 710 556597670 948 859 391379319 579 319 332712056 883 40 368423000 553 782 286328934 112 158 494175304 268 188 195830629 679 459 124509845 381 315 157189960 997 391 576114101 293 641 726409810 111 494 852547252 152 132 396550082 126 938 763968754 680 138 65663481 588 729 33568729 664 973 873949686 781 186 973540105 114 643 289549553 679 495 879119865 631 511 143583642 682 737 470586956 856 44 414696731 493 896 715707915 739 110 431864194 953 389 544765326 536 922 567684756 239 179 746263018 712 359 260227785 648 725 9686707 119 810 122060849 906 688 886819799 294 753 234489317 470 512 991852610 792 810 200817923 98 735 949277388 182 697 829504905 982 370 738796243 835 906 211588116 84 432 187520564 24 275 32550890 148 23 864855617 126 989 60057168 824 533 579739139 54 371 536686505 233 261 164669094 862 301 735368809 685 32 991102520 835 693 39972076 961 392 729290806 868 354 542168655 581 907 899354175 376 871 425714544 301 944 223968769 506 826 634131413 334 983 293907296 850 648 6227328 92 172 229473096 830 320 520923107 604 750 866439158 608 80 53299172 991 357 528082124 907 877 233683308 394 503 714262936 369 215 562799505 34 801 488829242 493 189 662591782 610 996 528175936 42 72 894651487 152 302 154446503 825 947 861639285 765 666 766776487 582 654 928115245 603 193 882677924 655 197 483373675 563 780 847489472 716 792 652745236 826 12 961279738 56 552 554735799 590 259 512101277 281 778 425669555 597 731 483637776 555 371 31250810 543 682 675020305 388 699 868543409 294 716 391218550 379 696 766644096 532 171 650100034 424 173 207580211 83 404 512619721 145 709 135691167 926 482 574199774 587 643 819142535 969 964 90541277 912 974 359448771 965 857 795388005 763 563 127277412 997 415 394723925 770 737 229851716 402 428 50542638 144 743 82794740 324 319 111471935 985 547 787463800 578 149 937845411 478 652 532095160 167 225 73811148 321 138 458220479 489 897 444281318 302 782 869069441 482 162 347183822 517 995 226472846 144 386 197328417 198 94 691883097 235 299 676162165 219 338 334667665 789 371 475793871 698 528 785589458 176 470 97275866 160 122 973161899 605 767 375200491 460 705 445774372 818 619 745093536 76 920 572243826 407 312 402455899 449 455 97141759 992 276 115625465 734 294 247008831 998 36 22883740 722 976 498304586 906 204 339044468 401 156 496699806 356 941 777273128 848 380 930512802 930 264 898389128 536 85 315354900 901 300 972366766 788 996 363181652 997 960 247597296 144 414 175107742 673 484 982065707 987 430 983543206 172 13 937987347 597 134 680336116 234 523 488239205 126 179 197743148 478 182 630158932 657 890 658494910 129 628 277530500 214 621 628119065 476 265 668637208 9 331 302069816 479 424 634835103 666 698 630385161 613 766 460083914 325 470 822221111 294 424 733624959 736 896 790680105 147 486 207649814 145 544 749517248 517 815 33001668 668 99 506997945 598 389 712637894 889 143 629312662 538 998 57671250 288 347 253569386 465 34 483830602 599 1000 641489984 703 113 497396702 382 825 145214741 357 870 501567070 313 986 206326789 548 971 838958814 877 350 721014879 982 844 22393048 384 616 956560172 727 689 54402091 555 65 2116423 439 284 614224976 578 658 579196132 581 734 566900231 54 713 496863359 614 344 164389541 130 940 344764868 280 578 65474471 330 714 331401520 166 643 307534413 660 877 530120930 343 252 187077116 555 312 705209378 631 108 255655419 859 886 29744834 849 594 400984038 1000 791 622206027 391 666 483622407 99 966 913371899 643 447 569823441 461 768 478512201 969 922 975912427 79 238 412426655 326 767 896627122 819 884 290630308 908 239 667773145 150 911 36686075 934 41 615707020 517 961 891392435 948 779 619652032 358 706 328828816 852 962 642206808 103 98 879723366 784 265 155678080 657 171 305979446 284 663 807583853 493 747 423082582 63 597 503919557 954 890 181172016 179 819 392712942 385 81 796105087 603 391 674412805 639 290 669060644 468 532 574102648 779 701 802119348 488 591 454424001 469 185 976679455 71 879 148693989 25 865 24037568 499 866 296390156 376 807 413173348 632 697 276330645 377 150 802292198 46 127 557831836 131 138 780045497 68 822 182183963 333 96 342656701 977 55 634772843 356 712 361823503 311 387 625100040 429 352 986465702 794 117 944669177 687 824 344542327 333 989 735841030 660 618 119220741 128 347 782139289 593 677 39872064 490 982 667874511 759 707 843426076 599 409 395850257 477 130 164838851 612 775 37160392 622 159 75192213 369 750 288301075 306 772 330205926 910 967 27072026 583 408 841683836 540 420 384637283 104 414 841837032 668 57 918842395 605 822 44657985 565 824 353054096 667 974 99573932 951 742 179201967 691 256 978789343 630 280 763987244 339 550 799459527 643 569 416766774 455 898 117370841 421 33 496611361 897 658 529617963 978 225 191247939 634 527 277906362 707 180 977466349 948 606 754946555 81 951 540683715 78 342 49102683 593 962 408694086 805 936 657210099 10 834 149157594 200 350 599480527 780 632 125895675 487 653 949218461 300 306 81156086 947 66 868909999 414 191 78765396 400 774 988857308 816 835 839250386 434 932 416317729 702 509 521313582 799 449 51863246 37 931 792171713 181 625 521555678 987 337 585639482 828 390 965872779 208 340 557120195 248 161 424048708 953 399 968746594 842 825 556476692 244 636 777185478 985 125 632198325 256 898 674649087 438 289 198640139 159 280 126223035 205 653 539548540 751 874 957818994 35 8 533558822 463 246 869677949 659 889 13159062 159 469 497101728 422 858 298750744 836 324 116897491 772 915 804406337 170 769 313256034 823 231 869393174 953 18 224660917 819 726 729374573 153 130 319719015 192 491 785971662 497 628 346649258 676 265 603547456 563 295 481920272 254 313 381226739 163 439 296660698 11 876 171805511 512 601 610903682 664 792 308351602 570 43 281220205 286 330 392195074 7 163 992809970 461 37 883858005 48 201 253275858 111 561 643114050 413 12 907104902 878 136 976931289 789 518 380039078 614 701 317445510 449 870 95284780 830 216 21360596 788 441 723065823 919 414 328719835 249 742 287912836 939 279 843264293 923 917 890831654 481 400 238422219 930 612 107663821 860 528 437383620 578 529 637630466 322 116 387658811 720 904 581664074 157 479 682878685 175 945 86702742 565 448 378910663 321 199 286742332 146 778 979399701 8 312 565161343 561 424 845953874 778 190 872078512 79 481 489875976 394 618 859293216 418 427 76042400 582 640 782211253 891 341 961073524 430 918 966327766 109 297 234390746 813 114 516621130 630 310 818355735 931 213 973353231 292 59 871623435 244 906 757829271 541 740 907514117 305 944 828180234 639 471 974958183 325 601 503248128 124 390 227990364 720 752 702923250 214 971 719306025 122 648 371782177 667 229 630527958 754 920 655595115 898 769 40296298 280 265 571950197 797 922 783040265 786 233 680625860 725 492 465824600 823 32 791808251 280 92 358705872 442 528 355170280 591 704 558438385 884 35 163301127 244 800 224293432 715 167 413539466 90 597 451057261 653 661 289821230 722 901 412104840 144 216 798847009 926 321 339922952 825 731 153274287 550 518 519193695 581 28 268045031 167 105 790980326 69 581 768266027 885 541 603385639 144 627 419550311 96 701 513578978 926 542 443027597 468 236 159290277 149 866 205784982 57 858 309088680 771 822 12929501 790 698 12366380 930 513 764729942 802 94 158093737 244 982 799392968 69 562 902112577 645 982 582234999 601 698 743811738 604 977 941217525 396 591 197999358 688 807 73372550 871 431 797604173 20 838 77531269 507 410 372133946 473 920 449782627 932 282 310620520 634 288 974340220 311 78 576648769 586 988 425018460 878 941 485866142 194 177 572522987 456 356 433349688 197 838 604172600 540 452 988010443 832 997 833853735 165 723 804655835 959 849 703803171 604 155 936525653 104 851 522398053 766 737 28470733 522 390 593831809 372 742 133052341 792 575 528975129 500 304 699743881 921 595 686722439 545 829 524086802 312 888 560426294 636 377 631163654 781 396 226565786 333 193 489285503 847 999 654972764 430 593 929470848 421 213 612136384 929 543 684764873 874 953 423225333 205 592 220967997 445 928 927613580 762 247 501683400 81 541 933756446 445 637 100969188 536 614 381654780 200 136 995750228 880 767 929511991 450 184 974254550 583 878 406405815 454 469 578739351 779 591 385149840 856 373 628962214 535 920 742040766 151 296 647645843 407 850 990716716 625 106 565302767 174 917 411110966 923 603 265899385 496 112 787424339 33 842 261941120 913 902 677059901 207 860 601960083 600 418 268131113 37 191 355971129 151 301 502659506 822 961 883629532 403 593 478558299 983 466 887423416 632 362 17095267 989 273 190414665 150 496 138048853 741 616 218335747 790 168 234503704 753 192 160918238 60 26 683606302 585 705 132880457 481 868 507213382 562 284 560162713 490 502 245751623 578 694 181075931 548 831 536420753 446 282 617469436 899 525 61345241 661 252 166713268 411 604 11931731 71 546 857571808 589 609 666292926 674 533 18119480 146 75 203254543 597 114 958189065 261 496 4537940 417 630 568685528 506 887 792581089 475 716 283901054 732 126 17093408 204 264 743974071 547 144 496784959 629 918 173228274 796 11 261739945 672 156 939632043 363 188 186371097 346 342 417176432 131 264 520255046 989 554 866869959 733 82 237374642 358 55 945966362 60 688 672314369 64 551 295025136 254 844 407206712 281 762 535157469 583 214 575172746 879 802 124903066 61 289 876886663 603 113 92130502 273 856 588340797 748 152 724557559 707 207 249107563 31 94 800943797 678 341 555910167 267 324 953550325 69 504 970542803 818 768 59898904 523 309 415198904 20 190 233646267 635 904 295089279 863 176 262799758 205 993 919964527 326 30 431377249 731 672 171464945 491 892 585517071 436 422 854144486 187 316 898908158 558 704 582450029 981 188 847227780 775 738 313284895 51 401 99359041 395 776 808223625 745 334 844950193 189 294 33502455 331 567 364097365 876 811 179813409 676 358 67255934 499 913 276878795 634 247 728028599 225 623 657036179 321 989 662183301 634 856 596861180 830 154 757088664 298 860 667974878 325 713 155966796 246 571 56544675 170 685 176618913 517 63 868068359 786 979 683473108 835 520 77050928 175 598 206397926 578 523 734672398 208 808 157616613 851 964 933735544 192 219 896649579 2 517 461178241 209 303 613488717 801 359 292651464 741 435 857621031 490 417 614565765 462 79 591849023 133 99 506572266 699 655 180015864 550 892 582025109 578 575 257312957 454 657 798717146 135 556 698101064 206 779 248976953 190 102 192512851 411 601 891167105 234 295 277212045 1 707 507366970 566 533 910479460 620 769 164835534 640 378 684161386 469 941 586577928 140 873 841461238 296 421 182360916 33 224 902512372 840 725 407902513 701 204 702654802 148 820 313687723 592 656 556434703 824 420 337364419 632 692 820006768 424 436 696074785 874 994 178615646 885 624 94843805 275 443 17698618 998 921 514824074 92 225 630333162 952 658 825491030 959 45 263480494 547 149 30266478 938 843 134975578 571 661 570798766 886 620 932643332 983 443 801081320 88 481 645937335 705 485 600439581 565 98 373232041 925 69 59229166 921 647 655148177 243 788 5678054 876 972 505548926 113 790 554581200 424 584 600446897 187 461 152050143 599 300 887102839 332 826 419784263 251 879 213887971 848 643 332745327 898 160 908460577 36 290 803559450 337 331 701233497 674 751 737760164 845 463 245902834 466 608 209586101 942 226 261546451 339 230 667065184 155 867 719254448 777 544 202936791 315 952 659096834 88 944 477117723 300 583 379320371 196 544 917088499 975 269 784549186 606 478 375940679 873 127 819286451 936 176 530785556 892 40 681021631 596 670 378008088 105 303 109227449 971 447 829895062 246 308 169013422 387 970 226070097 2 180 373759970 999 13 333119937 132 613 449199712 626 373 774339713 302 381 281747511 263 465 828425372 532 723 733221628 950 325 477240321 979 655 566503787 77 906 640134003 416 839 130156029 998 138 560461559 807 716 117095148 394 362 988847201 689 814 506875154 811 672 245196013 402 752 716729888 589 744 472618657 481 142 412307174 782 881 220000429 446 163 633084490 948 249 123914531 975 325 828509809 631 756 449381817 938 398 193749155 248 142 391700716 843 776 188104020 721 89 872675346 61 152 851928159 431 988 959124786 995 871 357421484 11 414 696861472 122 845 727167580 552 238 905796028 349 507 205564427 961 662 514936273 627 60 726200603 466 793 226292594 435 475 830796362 400 816 611838879 4 136 974808204 365 178 769377315 198 771 405700835 163 566 822296080 814 339 26628464 86 717 665965504 655 703 506753773 423 241 642887552 561 967 445891695 145 297 423608603 751 190 141951673 336 456 692822650 350 927 273413339 37 745 785410163 299 237 545192807 189 460 830521193 724 440 863562061 110 372 683121812 855 396 821872129 188 6 699463011 709 10 229609415 30 441 898476529 334 841 600688208 13 759 508788196 191 795 140786717 661 731 565150331 246 755 326621311 61 441 158076593 94 749 49854452 618 828 200614722 336 315 124682099 476 481 430734822 423 182 389040369 771 340 176986182 249 283 401163758 710 618 412183221 111 421 233509510 663 642 712129055 308 665 164606474 876 509 952743749 151 248 916620782 923 454 57641151 685 348 377588448 148 389 231691818 696 475 588395905 119 377 43499982 115 638 403184707 770 308 950159412 494 420 902335248 199 614 396976098 960 370 787087632 856 562 24721811 715 520 228606859 702 506 761404583 330 353 171269217 857 656 55201163 125 555 356876972 91 787 13645966 220 969 609812119 63 16 240967899 960 38 24667025 546 645 392403633 358 647 87165240 225 177 257436778 796 609 189432872 585 795 828166114 82 777 856275905 531 464 206865728 75 348 390588706 317 289 670332683 985 977 249025549 590 609 351245706 223 807 622503540 608 588 567043011 971 874 326859015 945 656 942424744 204 464 768689053 123 72 900554821 876 449 993453183 481 993 322216718 296 748 1571563 603 489 21748434 378 634 765806058 438 277 700832311 869 207 329299708 328 623 99274185 304 671 479737302 840 464 351577711 485 232 241640176 309 996 182428286 690 137 734375288 609 535 955843749 563 351 986475948 632 818 525001084 603 819 858198565 166 135 892667440 216 33 725675182 9 963 920893729 499 984 966191049 74 513 234867387 333 573 801627345 223 89 249465363 760 56 754824103 644 468 58609174 287 364 204078434 35 431 586422940 258 401 370457874 754 87 798481220 484 540 493551542 906 716 239253463 931 248 731887427 406 308 362797374 750 520 372898917 39 699 996345709 1000 95 130620189 720 42 272609246 755 131 951369467 295 210 913732694 605 635 872405739 750 807 375292602 402 898 153355865 174 95 468765005 699 316 321261197 263 908 936394537 701 214 419849089 156 480 338769461 457 76 463690759 289 978 675239128 383 767 66315064 258 772 764722728 376 749 431625428 787 465 85761268 843 823 802926458 372 614 266714114 143 392 554840929 749 858 603559942 411 670 194455570 821 737 660051502 462 159 884770244 659 598 380764895 457 637 356993979 820 426 635404922 629 848 21588034 202 901 358476155 551 614 387490272 956 655 101315908 511 559 700033753 862 616 69382576 6 640 841476275 55 330 296448145 94 927 21225083 656 832 38039096 763 290 899630547 421 460 209062398 402 385 314783211 953 759 768602580 910 548 821926582 445 333 397684121 759 667 496648444 190 700 851473820 1 131 23573158 310 773 31443840 377 754 439873994 907 128 746313286 281 17 712262406 415 323 149868973 49 76 202117462 475 905 900243194 848 428 979740610 429 627 976163733 900 381 434033639 650 631 920712315 957 989 330492988 417 949 949862140 722 412 371647420 298 209 8058446 257 176 39321721 20 794 642706511 172 422 910277897 957 634 475234516 17 539 903625382 715 333 867501983 929 469 254032373 454 198 889075466 638 1 910076271 917 236 280866228 211 61 564723624 701 866 513114831 355 606 119335212 358 248 945909830 875 907 327017652 806 570 979235213 594 48 867807014 517 752 812407445 748 275 315695243 397 272 699048206 392 643 906890107 724 131 954098641 749 25 356495766 88 819 502234821 348 174 61167649 61 234 956380529 278 988 601669109 717 884 485218306 849 995 781864196 970 882 676455883 932 160 482596462 123 47 849511732 276 806 922923656 164 586 288470793 275 733 884524393 453 159 188700693 799 237 893260178 229 116 284451584 987 201 883423633 586 617 25329818 787 280 960079199 259 281 970467190 348 734 547617036 13 120 141414107 672 35 2233767 608 210 892935687 147 639 298118956 68 779 171722448 391 635 720865225 798 811 465201764 740 817 89335154 100 20 326089142 351 614 67443211 651 375 10760456 122 779 937630705 276 676 438490798 768 739 326179969 354 784 85954413 508 354 961701776 301 51 207960098 796 766 351240816 152 76 8425612 36 681 33321647 42 739 656227170 523 139 220827221 328 11 562329160 973 865 422313884 959 412 134403819 769 88 435179468 782 421 985107073 908 413 557874349 296 844 959805363 465 335 777711727 902 92 381261785 312 239 914306586 199 318 970958084 311 850 445334832 115 776 556063821 600 739 751369172 855 177 617218668 140 34 613325583 182 980 126256511 370 437 708561226 118 75 944733471 523 182 159696478 967 579 536013684 709 704 739409999 653 9 886099745 72 657 31398317 384 741 252317461 196 535 725199096 931 22 479307589 759 268 178190447 750 877 498938551 523 637 981712873 777 859 692363192 455 175 278451246 994 737 490923040 77 482 392794964 279 16 493582347 838 659 879051115 266 826 552085797 837 192 925234017 951 355 233444346 122 790 989493316 382 693 804331969 939 252 914253725 353 71 157052734 555 69 184759752 269 518 292743107 255 513 148859580 265 863 700498993 770 359 125812956 24 801 52692711 325 288 91595701 648 445 51863713 839 726 322141839 285 370 401321333 708 4 714513607 638 120 330478715 802 280 480934755 88 129 402879527 965 858 713892684 358 418 820400571 39 345 230236722 708 662 152561793 441 902 996259932 234 88 20570381 985 401 688371521 673 218 392872391 321 278 32482842 821 267 1957468 250 917 82893872 826 45 171640199 534 730 101117449 855 339 103778289 75 278 153309430 799 581 276031016 536 431 628804151 630 317 579147289 107 846 267607745 22 332 801642472 616 220 369308251 530 79 427120051 343 291 646349893 102 327 214051057 631 708 896000492 478 876 170254474 769 161 467654074 422 498 404203368 448 458 946398504 209 852 388685431 137 918 763328241 48 122 585558177 281 976 211739855 608 947 605490508 230 447 724529433 206 704 148645216 483 108 715382668 151 908 129378536 68 46 133567069 802 714 934154410 134 712 59803354 892 642 966867798 428 400 961414231 55 223 287034640 609 738 919345943 289 20 466518582 397 100 568936717 569 183 953113989 518 819 947280062 931 565 802752471 473 148 194209693 53 380 549751161 747 485 967245451 191 368 41698921 137 963 945041779 745 159 491911204 286 667 260270753 810 402 261356453 843 460 448592539 189 466 679043355 852 592 487728743 646 17 379435480 823 758 730732943 101 890 577818739 409 736 573968974 591 542 429898075 722 420 232657325 129 521 360118716 996 244 780212334 442 979 491971664 258 991 965282878 916 180 521521552 1000 69 89675699 460 524 609803668 719 154 556717242 111 996 230735392 571 354 559379541 391 793 54487818 921 110 974899179 335 403 422321528 244 606 964000339 44 882 914083839 498 53 141298808 17 804 992323455 527 925 208291203 983 875 160407708 284 275 210822703 276 210 51631517 118 933 703285095 177 439 334352699 782 931 242631015 890 577 78427620 474 646 120937550 73 692 434985731 589 747 133088052 438 220 362172368 744 909 624252521 504 760 371203310 414 110 124876997 828 923 836552255 664 296 544517915 701 841 776758364 155 589 388915575 351 358 679834478 86 736 288589889 851 440 667177236 338 506 300920827 188 541 234323852 292 457 110302290 212 951 476410745 947 185 596128186 7 124 183284500 976 83 746829219 860 594 671474136 7 175 807933252 157 385 635864931 159 171 706414972 708 63 589662228 393 764 507401158 875 391 386870528 313 485 314978326 310 525 438286672 620 871 973257313 179 128 336592343 163 726 489656410 79 566 942401078 788 830 411120247 514 646 500115872 8 741 674325723 656 587 514828595 426 147 758245845 919 104 906770313 43 162 592925129 596 216 742169075 913 926 435530479 737 235 770010674 898 520 743928108 43 740 397809261 800 99 712095309 463 435 358759030 670 267 549943514 110 18 17826397 220 54 499658106 140 583 286183647 782 809 474020227 928 34 364490885 460 268 368665533 379 911 975750581 932 787 331933698 735 208 129941160 24 636 82755734 540 559 317333570 498 324 370752124 256 968 156767255 206 273 946157174 286 402 773023797 550 527 597486295 421 855 172513505 939 266 986494951 339 8 636874998 154 632 857286692 182 884 855870757 911 590 794509206 31 282 235730012 837 882 30052825 772 765 969916712 410 61 607547002 762 884 55894318 116 462 378039922 78 81 138260364 291 985 508753190 635 773 284130761 434 29 958284157 649 368 580033396 418 863 451637453 643 505 490653613 401 889 715299728 974 819 363170189 962 534 366830782 487 964 278882584 143 686 655528858 830 647 810058183 44 658 985895837 973 348 257361503 888 496 553704747 86 206 696945648 549 31 740278377 847 175 231068076 697 131 379012981 228 271 440245411 197 742 582104300 669 610 893412293 989 597 38729508 366 464 823009322 521 85 998875331 131 750 734523226 506 826 363913738 3 677 118158475 946 870 120020114 320 373 730502675 630 918 630090805 891 760 420360642 462 275 823025997 490 695 497816135 2 593 983738866 791 780 441531233 234 82 328207538 249 277 931221068 938 831 959507285 198 326 483319429 275 741 881571836 209 483 141674599 179 412 792657694 577 832 609779979 48 580 441916149 317 234 609559961 979 264 214271050 153 213 804399481 187 317 959855934 624 269 721622494 645 428 196907145 316 314 869278663 186 465 91791047 309 808 720517781 394 313 567175955 293 175 161971895 792 922 255725148 470 923 495589695 276 584 716749092 794 727 176432866 520 134 299705577 286 156 479589728 993 696 639882907 102 791 710878324 481 120 706758 64 217 969606442 152 129 451201696 635 769 951788601 576 79 841500753 642 441 665773710 68 532 397683152 877 134 419963477 65 643 523519041 485 463 261906530 923 926 963627883 225 437 794961072 969 408 265229826 678 442 540144194 860 951 565228644 118 826 441336129 316 757 281416327 356 224 475629416 57 223 614063054 188 512 130459079 303 509 54924392 409 226 753508721 865 388 753082877 881 536 936328442 642 402 340079757 100 55 231860376 347 654 385320148 741 941 900886630 780 747 332181273 912 55 525550688 37 746 750450993 411 465 625906023 79 459 977912855 953 197 637877855 296 145 504514528 285 510 987203793 198 431 114697944 859 176 679026710 143 995 584528607 741 164 684267621 494 11 550522398 925 329 724275692 16 959 555360278 867 367 44672477 901 114 548860417 466 51 373569608 389 851 324463011 631 343 353220760 338 976 129901568 116 733 412512173 332 298 651064923 500 140 813815445 143 519 274326596 191 710 639303943 421 926 584606131 892 82 772889884 484 602 341783650 820 95 124845825 719 884 234571035 433 913 154932138 315 706 688668146 656 495 903105226 233 878 991389644 848 978 816172658 24 120 29170420 377 98 364540435 515 479 749186937 88 961 978244863 855 602 236068304 478 617 61105021 260 443 389730418 943 200 733854402 856 749 942879036 951 739 883803085 835 304 918116142 652 325 156964975 377 153 248628157 468 385 639746874 246 71 475858231 29 698 764679343 207 123 639712676 316 543 77388901 706 282 964559420 167 457 612711264 72 235 770251488 831 62 939042864 463 705 491887324 190 975 535524190 290 89 58133478 178 762 986946007 137 376 598259113 983 998 293610396 653 30 42723230 386 766 498644219 859 16 849628997 197 639 591822237 366 836 720561946 885 214 482617103 776 914 162536217 876 764 538495428 11 979 905395293 904 45 652885765 347 181 6138145 826 104 512303830 937 777 8589321 414 187 555957124 781 318 906715885 373 529 788774333 516 121 396378999 637 91 276883566 206 155 966528528 284 346 549197405 452 829 271320633 575 298 441054581 723 700 163922225 587 536 138013436 356 896 279480241 608 199 369279347 761 243 65644371 455 991 113699642 736 992 914510330 551 887 7822856 348 604 563518647 220 905 145651687 912 981 399232845 141 866 948039888 238 98 55261366 792 899 308604929 492 624 535138081 749 695 179244602 148 247 664179937 562 176 902827340 227 19 871619424 654 775 824759555 874 371 1283233 575 112 798241132 200 877 116021430 479 217 209987649 692 818 654753546 50 937 191479890 343 274 268103164 823 596 957869479 840 740 532069935 493 351 380221645 385 907 885882583 580 370 843707375 733 387 982238531 317 480 1616669 505 46 751044784 609 103 51731059 581 646 915850112 842 73 72798971 5 14 987760139 570 437 4694101 574 375 928327538 627 521 206950917 795 25 120465233 715 236 979887397 232 569 616010380 620 744 250391944 258 374 204782907 298 252 597893066 443 793 486967224 441 891 527238016 65 237 253245475 167 207 512671818 842 400 690524502 188 326 970745298 930 965 355580542 261 893 220348400 333 430 105121077 674 403 140142536 432 896 715626695 64 147 273735447 705 330 215369224 88 628 767805860 228 871 352001131 582 782 890031157 2 268 973409077 139 155 898393982 542 14 957153055 310 202 461402789 768 232 116436368 932 57 887072519 349 273 59866170 298 901 348723310 947 298 205202109 149 134 377326320 445 226 264872863 754 540 27831617 172 485 336414828 554 946 350769382 320 822 944029746 633 344 982736660 931 725 402656284 484 450 194575683 308 206 55925163 820 858 293464388 820 201 478378430 223 364 300363040 571 187 68899338 372 345 388139214 788 76 801895529 331 542 355096078 926 590 901080579 525 472 602661390 805 872 723608728 623 429 347656916 188 128 277732101 438 272 147131512 105 553 801746072 614 346 477615139 425 908 320946575 416 697 635298719 918 179 286485144 958 681 126050752 375 841 463601130 306 662 5368276 36 507 293133011 638 630 330642225 362 213 533223575 154 220 175383155 677 796 516761049 906 523 211625858 535 321 518798864 743 922 813541530 866 742 902353386 7 195 100661136 630 737 248730169 31 688 982707121 450 821 308008079 36 175 455275605 569 865 280026539 818 412 383869904 598 6 143276955 318 225 285123865 622 9 49638771 122 828 43335155 486 143 532473006 558 918 592508702 215 54 752495424 136 636 240057721 906 490 367387322 796 848 179749822 793 738 174549828 532 928 611850139 717 433 166087695 673 32 134777459 319 664 755147425 896 539 942687182 545 899 318941951 396 524 417030555 105 700 698740855 267 135 900967054 746 43 415328508 540 126 563578183 635 110 979206693 413 419 428896833 868 864 803113468 343 337 362836973 472 348 243174530 984 209 122260765 389 479 129058524 734 892 148538350 171 54 472333556 317 593 508231557 208 650 894682914 611 776 633234785 378 446 859081153 189 306 618172981 805 625 795831788 607 935 618027850 429 651 900555103 672 315 287936923 169 327 596618728 930 749 940819114 828 227 187956013 348 891 682214759 722 297 91393004 20 118 99458701 888 835 121437995 223 76 188401011 188 308 74833588 341 291 879946058 222 328 809176566 175 225 332236784 974 52 131376077 517 934 951615803 223 988 695278843 103 29 232949377 572 16 397953716 594 721 124333274 960 196 670905784 576 257 281568473 676 118 816950192 989 782 871214719 58 26 825995067 272 680 807491930 997 529 848986488 794 681 173274664 665 520 814741235 662 96 582011942 252 501 150636775 16 518 516911463 141 155 316508799 391 653 202758429 887 180 515595464 146 702 834685548 576 239 843931275 45 47 131707231 889 905 191807538 449 954 619565533 671 606 620321401 197 441 495234269 3 791 492117886 397 45 425592607 320 203 712997556 438 1000 320308165 876 605 902704906 777 387 847085664 752 724 782575804 561 823 699637950 853 644 70593404 919 541 181910573 621 75 753044167 671 235 404114215 744 208 183259461 937 734 977762179 527 846 20581704 318 797 277100247 905 92 965419597 116 608 694980995 199 204 376099439 198 19 943686787 498 778 895776288 888 482 692165367 968 407 164781283 645 267 326176219 812 63 708154745 307 237 138300349 506 420 451774116 462 276 558521591 649 325 348303671 288 768 390598245 21 167 803373676 205 833 965124909 710 721 84132725 847 194 532201147 874 335 607922202 927 187 454558110 312 141 867643723 346 748 711411956 920 65 810645351 265 542 547540742 333 200 297984882 760 284 757526010 104 323 639696105 272 296 875660312 521 22 468490734 100 603 353390984 352 4 879878670 21 320 189930279 782 158 928375990 730 187 984067951 190 585 551430064 674 281 770806035 9 505 105465327 319 15 968458133 554 313 436204500 554 893 179236111 961 652 394788642 958 39 651905953 443 916 346107537 464 280 144746055 335 766 538329462 114 524 518501881 875 247 805783856 953 362 221125816 307 235 646776114 442 303 706131109 591 614 397046908 465 946 702124392 638 769 281089087 60 390 436680166 209 447 227203250 782 961 670747460 866 92 422720416 349 335 926463322 893 426 967354478 30 420 365840838 262 876 217170629 851 418 731453341 90 807 815399138 968 558 541050935 226 90 204282972 296 908 194391794 633 295 920293497 869 796 777723087 473 114 809334447 979 324 777731358 131 734 330900580 837 595 71786680 295 314 976541220 453 753 167489382 79 450 182200879 196 213 112263744 66 58 200952238 832 185 599151161 517 890 971355968 832 101 527107793 763 973 852265515 785 667 867211118 446 345 589633255 432 124 723134352 381 532 991324745 310 891 787838705 962 644 882798476 785 812 611422776 457 808 128058 667 205 969351311 911 207 786409361 780 381 926529092 958 197 429633193 170 952 735827251 745 360 558008753 80 831 697824848 368 969 938045844 426 116 419592086 336 309 419677705 882 564 220586214 396 350 727944240 884 500 413652032 306 704 392404964 412 990 130232635 846 36 387461568 171 633 966547495 5 317 11124199 980 603 146898395 679 338 267685327 689 354 369940669 999 288 210628085 415 339 396434145 707 302 990477094 974 284 443084130 712 452 317322324 819 164 608750926 215 608 522244071 901 366 644116327 380 512 806026054 869 134 899955038 905 613 599133836 247 412 523042165 861 167 644121304 777 408 125333167 243 792 933842324 307 952 90516442 460 820 918251181 548 700 845569738 700 912 71854522 125 316 12011475 360 616 742918918 902 564 850770114 811 981 297697931 85 841 6465224 283 769 175470121 459 764 486720561 433 138 377722332 165 948 11803419 443 340 683011696 145 872 492866678 850 398 369578710 188 174 446790160 686 675 984234496 923 570 958144708 320 693 909042908 637 364 459553558 563 451 214795243 625 722 926522691 951 766 429097206 304 57 300112754 615 608 931542099 26 974 613241239 988 133 999864039 745 818 8660354 456 841 832950946 435 75 115669909 526 775 550514057 122 741 527538664 735 963 451684138 681 314 751892525 251 87 706297520 301 263 336454473 310 230 76889992 638 703 779508861 301 161 580067696 526 815 876633344 591 725 593568296 927 158 348874491 670 901 151042945 375 947 449366394 596 642 179456721 968 378 470694785 671 328 425333918 875 628 10171889 748 842 83394913 715 594 126058960 149 978 303996232 336 287 432995447 302 438 820403632 558 859 493405357 22 23 900021274 213 716 873877617 5 614 950903617 822 407 277509108 80 950 636443756 966 265 334719634 252 896 822029785 887 666 742465605 505 214 456714709 378 950 312015093 888 586 109637515 84 509 568846564 952 880 605567673 899 956 502897871 892 171 254790020 432 809 681565801 227 193 719752540 292 168 690232632 36 673 710554550 918 672 269834129 719 964 331128303 243 645 469012045 529 221 893955300 110 667 35953926 362 666 447541473 333 609 793816220 869 872 872894693 79 694 331177308 793 71 448714163 731 176 950673709 554 496 495576895 37 247 726669233 506 924 859464368 861 672 259062801 590 465 41848893 590 20 171099395 638 393 596367777 54 4 4770615 166 2 460188327 331 611 420701807 943 567 79229302 492 372 862704314 297 383 208010793 990 628 148707050 913 369 891529149 975 597 459989255 285 615 858188871 39 234 200127464 725 452 780646422 638 373 546011101 633 881 208668173 760 583 752092531 336 10 500470219 679 70 481184502 845 420 489627297 905 172 841821867 691 139 869719329 604 450 820725925 709 352 756128283 967 596 282247546 926 186 261475816 808 680 658148381 553 609 613107834 223 642 102188276 571 320 928069018 114 411 327093537 230 754 914559638 317 842 201245184 768 408 422180034 842 63 537128270 668 872 303709063 918 356 715944702 113 788 224961770 705 254 673114447 781 532 148127039 984 609 673006369 508 274 867261735 672 233 388026851 75 690 491085355 701 995 759829963 48 249 547770674 196 218 609485865 557 982 470727330 134 608 225053347 393 52 17088101 118 478 909813028 957 702 891152585 241 993 870922517 356 703 12371708 884 553 652153687 365 682 829267375 324 429 568467791 961 996 780359250 479 380 945859037 854 866 341143410 370 747 474643883 754 149 404293933 771 63 313213484 892 750 794296167 236 822 719323791 369 774 664065665 225 928 819405187 110 637 558581017 590 558 926956677 957 771 375628929 577 972 237804901 87 726 712265400 822 778 657811057 445 987 302776316 911 664 524164979 849 685 139054418 350 490 958853587 189 357 934054838 165 61 805014921 103 736 413965602 822 489 856112107 775 24 522071685 379 721 698713762 996 800 221310411 320 637 285800356 360 934 4861999 687 44 754720511 812 316 392360750 813 532 278383954 415 829 523226632 487 38 315767617 93 370 494085568 503 812 742355401 719 119 500760352 630 766 356925833 460 90 800347476 126 856 909015339 781 467 946085044 644 249 889823807 350 648 931184080 167 511 156953526 195 813 758387695 29 388 869280316 469 822 257738409 872 710 12319828 770 829 192202975 884 89 339639869 701 72 761825641 995 504 96556015 33 183 429784419 246 346 14843114 17 589 565114159 665 968 874111404 852 214 799747961 982 50 602870353 741 515 588400770 22 115 266449926 171 757 672907220 577 314 375025587 597 686 260644607 626 871 96418316 754 151 451463400 180 686 142238765 774 637 146396550 663 244 405086345 29 64 642377168 872 119 711260446 356 504 303368223 795 457 669567725 750 213 19834880 916 196 108957802 909 431 283084032 212 62 486437087 914 330 118519316 286 781 849222643 761 412 796118381 900 482 754631595 929 999 593887293 96 483 453355028 76 98 496592487 802 740 38981589 661 155 626509927 255 531 256382431 934 698 742192661 926 317 700321788 302 900 793343987 86 776 2917591 821 427 718810045 802 671 903646211 117 311 758474318 694 108 424696094 965 191 639738264 731 113 484430775 628 93 456956257 1000 145 595493688 1 478 556719997 458 265 675764919 809 756 544761480 260 483 139827217 990 624 277944486 751 232 684120436 355 461 533338918 189 38 268160566 960 570 586968256 509 457 513755751 897 74 999770141 91 507 232842541 860 911 990815321 104 331 305934669 621 349 906533168 894 119 416419349 467 992 244857173 841 900 536697757 508 427 12026947 262 426 873620950 358 348 790442009 887 855 989085 693 214 722468768 45 650 563223926 934 800 140209611 25 681 225926222 721 272 603591073 100 508 405791684 328 919 379334474 617 255 461997227 261 148 9207123 351 824 958487680 449 763 645878495 764 454 314069758 232 233 70044232 520 715 570595438 386 515 47614898 248 716 47013672 219 775 852867255 375 151 293339599 468 23 49658317 889 402 696211014 633 124 623190307 655 67 964101358 199 554 678884071 237 403 478885673 250 209 31160265 972 636 642902044 328 953 341906354 142 846 333468328 958 225 172930693 623 310 136905717 14 641 324178627 444 742 147042931 302 251 298996794 990 926 856571313 431 555 811445336 38 968 35544483 34 176 685953049 961 271 286214133 190 831 304529854 309 172 74304377 326 301 867608705 164 796 285227832 376 75 685814335 223 526 46840983 992 369 34692090 181 109 663523993 407 181 86244188 856 379 492394952 519 991 893952993 3 396 898587080 650 538 537800050 287 719 848585560 423 131 702042828 596 575 658198094 263 656 52590826 933 482 783585852 427 666 623629278 749 970 90111326 312 89 203446555 971 411 157653207 925 203 786906713 95 793 218834448 220 594 208099871 963 816 327071986 630 760 518328269 666 585 870793575 241 276 770866873 360 906 5171048 660 515 566453849 158 270 139640480 491 791 775373957 528 561 920213842 189 823 551108481 350 396 8272348 756 840 266127583 824 640 764017899 942 480 531474009 813 599 410048485 191 620 369930222 279 16 929969967 232 93 143543827 99 274 373669544 337 181 479986846 424 502 94216400 880 679 918038470 207 640 349820178 699 403 512431480 625 263 942404607 80 612 97351510 694 963 515613241 876 581 753711013 632 193 13605548 29 771 808937054 391 5 886312622 753 737 31731728 357 201 511345630 709 267 385969306 329 446 490755884 10 237 697998034 216 812 173625046 815 205 980203398 327 862 277779830 767 832 639311918 574 784 28188551 448 148 777247826 502 44 161637750 438 111 604074763 768 761 779996666 153 475 259190148 818 975 929086090 228 613 26765289 381 536 503370596 990 6 807540289 334 48 528231684 246 676 454822724 162 990 553145520 156 984 82705088 11 100 758064190 856 612 656149780 94 265 505120126 977 465 133588234 820 681 875707620 80 632 920665430 681 248 926018402 531 929 839794250 482 847 841312783 903 603 501799763 727 498 787821237 536 508 767129965 103 243 763256808 465 598 431153921 157 261 611533059 340 429 465049109 607 475 689350859 983 140 170635747 930 885 924235388 597 962 255918741 504 82 304171247 544 427 697517932 181 112 80044654 318 338 226466371 116 722 270772456 601 124 126087538 220 864 230191233 707 20 543088340 303 840 444052333 771 697 390018959 43 88 931344760 361 67 506892301 772 683 386920732 44 65 264084240 610 28 441475857 688 962 451356845 295 913 953090823 56 583 884086577 187 802 130942029 668 77 445837825 389 36 956948421 197 446 757187395 761 828 440841147 741 402 516281618 49 741 904116128 690 723 299207370 581 383 103034310 127 151 374311423 455 30 122731978 760 476 7721583 708 207 357458657 614 261 758988532 275 872 621152781 52 686 96405132 604 761 916512927 15 14 543301691 185 421 819892616 523 332 57867725 372 892 655764263 948 113 733105040 782 571 751547491 52 1000 755946290 957 191 901860212 341 755 238729112 63 348 881905731 97 197 887303743 835 904 969748842 736 806 357810246 427 321 935787279 833 985 395660998 675 536 896910362 6 448 800870922 579 221 795519244 535 77 449493317 82 603 88690457 580 734 598417960 974 989 149844207 358 154 355431670 873 909 985714098 985 320 76475658 747 187 641854252 447 357 77069496 745 896 578399997 465 293 245353905 183 4 637732598 214 530 339624580 722 861 229785872 247 486 987796129 199 41 828449645 856 174 994866814 936 355 136074250 907 819 55092478 352 3 689352135 139 777 856076406 505 655 678639175 175 206 253049167 849 632 369127676 17 487 962704047 301 489 569277112 162 393 527115421 531 36 163618885 678 33 668491526 320 366 476918387 481 877 196697161 266 768 620654864 26 957 807040923 466 861 171807118 61 349 441598937 130 199 908274421 739 715 231539904 42 1000 530801861 212 604 307594469 355 848 871876038 203 2 822505723 275 819 222977785 978 564 603820133 8 709 781834776 190 692 873345181 100 684 684441660 204 148 771180989 326 857 623773945 577 826 248220647 126 977 406523733 47 602 983875929 427 633 922904130 913 267 600007351 427 616 802012789 992 419 10581672 323 496 226908583 486 686 79353518 497 570 10614441 886 450 276939948 787 90 538981428 728 559 737668559 153 334 615014278 445 256 20429750 313 595 272918125 13 79 113810871 195 862 982056945 236 278 39161895 671 546 734629475 344 732 709089152 506 91 808789584 27 77 433701654 76 115 11992864 52 911 834679010 229 171 903108439 532 119 252435495 506 144 237113840 397 322 229645652 563 554 889615555 117 151 829900096 125 112 428578945 203 798 621616667 98 228 145244308 277 616 649749692 353 44 679908989 476 269 12365888 391 832 209037466 306 349 917239199 276 975 855104004 620 453 309116389 932 150 82011664 545 484 772242746 571 823 409499427 48 618 32452420 1000 444 56183441 146 804 892931702 402 557 610260002 567 688 249726306 9 736 582978432 385 373 86234742 888 289 196996611 119 787 261532208 353 972 969783842 927 341 529095695 544 960 353561366 251 771 525867190 526 510 947777619 341 521 218845056 356 470 487593204 325 39 971627595 578 812 263227308 161 802 711000548 885 765 498559244 280 484 265751257 384 37 236238042 500 422 498558957 453 162 294293626 25 192 627796003 134 201 325568581 287 166 293853837 986 331 415191561 860 737 538512950 343 162 689460353 142 322 219964362 106 970 858285161 743 510 27072768 130 234 68310071 899 669 625915495 115 679 216008434 68 879 149947555 261 816 616215671 282 231 724722147 715 147 110044900 873 937 780273399 510 507 396879612 317 33 814822306 913 750 927704626 948 760 857599461 148 130 50394120 292 769 361624208 790 937 80212605 821 318 645496014 95 266 155991606 28 94 671373758 803 436 666712262 196 336 40077758 137 241 210980057 428 880 550925789 470 741 65221870 540 555 468938655 21 890 568346710 232 35 581397377 717 122 375431497 558 271 644777785 519 858 502150333 273 115 130125544 944 922 61566506 790 777 860486850 963 776 56324474 64 546 338127728 730 625 502980757 99 815 511535006 40 487 19006882 83 401 454304328 180 206 27977070 803 175 418125241 496 709 753408593 596 88 185119011 450 141 675922023 285 239 28579750 462 504 954137357 631 658 391719211 290 653 249101270 871 705 752930861 873 235 278728962 765 717 362312360 949 493 93782453 305 764 177999787 820 180 652564265 268 922 793900744 260 813 407706504 790 261 18562504 731 726 997530260 385 360 938806457 783 162 203468977 344 295 198378638 376 52 252800771 324 294 541253601 315 116 613177707 987 275 467274790 10 31 823091615 523 742 122065178 185 377 707100885 324 56 631471980 178 245 320881738 512 628 40659174 46 140 652125979 580 650 487333664 973 204 535284179 49 119 894074880 196 904 476429456 237 600 400480740 58 571 357559199 210 946 232491817 882 194 560468262 333 582 309952237 855 42 714152283 411 436 65461480 491 863 216057837 205 551 266301692 485 601 390465299 268 436 562720298 23 278 627809437 453 557 879891217 181 934 383514918 815 20 223191972 406 577 46824812 318 834 21927619 959 34 928059655 421 254 260814772 177 827 784446884 604 317 249530158 892 507 1575098 954 352 185931233 221 161 539137695 253 70 592027598 123 285 772024642 290 66 708587569 537 695 148927054 877 434 790960793 279 906 206945604 473 182 94180978 701 898 99582180 768 432 718943792 528 910 65802632 487 436 730081164 380 768 251464817 119 762 840407949 597 392 716603392 135 449 908009296 426 517 108085089 915 765 455033995 671 276 163504826 758 458 15710461 87 854 943416696 801 243 117682960 56 288 208894355 795 188 52279334 175 869 859901452 707 743 660147466 60 851 750215316 835 798 811952115 514 752 1120002 967 403 549659821 535 35 980662729 967 384 418182546 466 398 265696486 929 836 944478162 870 633 538325873 925 746 548968648 787 642 27431526 337 891 131725493 218 874 118163216 610 395 540850972 107 937 2851467 221 160 30179874 324 187 506172691 943 959 845742229 649 438 450346428 228 505 959002608 903 15 417949332 950 811 161606228 131 844 659166993 514 99 362573959 740 867 550796602 559 222 676810791 698 664 159211360 659 549 161999 498 182 65597890 948 518 179898029 608 828 256228369 173 12 861201125 535 860 831504395 279 315 630734087 27 327 813170680 168 46 934291698 827 653 385293747 853 789 29433396 493 112 237104864 834 178 892065453 29 788 821476813 316 231 651477421 768 378 717760712 735 872 442835153 234 661 252290629 225 559 415163278 515 742 848337612 386 25 586577061 538 884 883530913 726 948 622661269 39 761 996288125 421 998 408540336 370 437 210249702 476 849 9080387 555 101 606330666 904 732 723710231 863 9 916612289 925 136 772133199 175 507 355471095 893 253 714460608 411 987 610608325 953 932 633483231 624 535 710676368 725 216 607145454 215 412 647011168 397 406 6658050 259 260 738901021 142 767 588898678 736 972 170662261 494 342 445071707 603 39 961066705 912 453 783892971 808 812 267237953 640 846 649628845 195 91 300350346 510 394 391059821 207 801 891655682 510 120 834617340 386 355 233423839 32 765 226533702 573 123 407283689 498 908 111214426 498 36 567178488 601 574 872857513 376 664 468213403 839 610 571283734 938 394 455993033 773 129 132248321 732 370 959100453 628 33 559121587 76 314 898023695 759 611 771180006 227 849 649817094 607 455 483060818 973 176 218159293 902 675 202371227 270 455 330465823 183 676 193806178 141 931 859707227 125 156 523479221 103 173 564874445 233 116 567710651 474 608 972081603 453 136 641846631 352 572 264797508 55 304 420018464 821 261 40561897 480 318 598449808 959 560 561620838 484 651 44473284 296 640 263684773 208 658 163932040 386 129 691932368 867 154 600154419 310 912 184898980 823 675 408458976 217 125 175348599 286 730 152882459 611 130 69778246 149 704 518810234 649 410 562176855 387 787 583420266 241 208 321752957 959 491 296533964 626 412 943373648 626 41 347075943 453 764 789424792 886 930 304335426 333 693 766012671 748 37 479002412 418 570 842478938 394 692 274524594 621 704 841623424 276 35 881883164 618 426 570038252 700 282 687500289 177 667 786234818 682 351 724864855 665 59 329464649 121 561 751510152 366 861 778987579 420 964 801945560 995 359 274008142 28 996 627934970 659 74 1240345 599 511 943749242 893 413 676394429 439 887 767062284 703 753 732876949 801 897 247848538 464 470 531712087 473 249 61819571 393 556 969129361 667 425 775920373 68 498 420545669 530 815 545358086 755 499 276448385 815 508 178538983 28 136 665167962 448 758 129089305 776 105 330579261 262 989 8484774 945 849 75046127 746 603 825138708 987 593 466851049 243 505 578585393 317 467 247264742 607 308 559155908 156 693 930324165 867 845 540042442 106 764 156485943 759 967 128210278 754 96 633604549 833 101 114015856 878 394 991985007 421 595 497560268 351 261 352258093 476 606 264889423 352 875 423717842 954 448 362061130 986 900 649520707 718 742 159461068 919 3 123048825 818 3 341141554 959 407 866862407 204 576 750189284 167 288 610596575 50 102 188045978 585 656 435555669 576 954 968119851 556 245 664325536 991 616 747276668 820 290 494108174 187 142 315094225 120 698 912290608 377 697 299327922 634 870 22092146 95 314 258565701 427 9 227702521 717 965 402048857 370 403 547352316 392 256 861269723 522 683 791582850 211 905 772230838 319 186 460300501 612 779 194557818 769 360 285658922 733 31 975095961 406 203 782369317 982 354 553325232 621 288 396496118 799 75 440517398 229 623 497701091 711 939 792891454 182 801 331374388 409 9 870943810 163 217 731677887 728 372 291253461 223 234 140934334 691 37 11952986 455 371 771210228 640 737 561448548 266 301 58590265 55 872 495980465 740 570 797939661 914 847 865126533 100 209 942004431 889 121 89353785 739 532 571691724 158 848 912613519 171 382 305580057 10 910 867123195 987 421 358101537 354 288 110785006 74 512 97087988 979 104 794249545 790 463 499743292 812 542 594399391 849 640 445922964 368 897 555086518 389 632 885975516 45 774 288951344 164 221 325056341 202 461 38905148 331 975 23739952 17 865 855204156 660 973 877356897 366 824 651078530 927 565 141598785 659 781 464670353 602 927 340461686 898 44 769641098 686 802 137982616 601 269 686426991 784 390 719954996 541 707 511300950 696 416 809394467 362 138 787697206 999 740 988115470 588 550 913004315 258 940 402298469 562 34 501510594 102 284 380037443 29 656 296899451 175 695 925070892 956 893 510383379 433 255 944196292 996 575 649684063 760 377 788905907 712 111 497628879 633 15 356354317 979 338 337812704 611 949 485927727 55 583 599370689 427 233 692657817 302 692 479676301 494 191 121747764 812 698 810891917 37 401 818086050 175 840 10714916 970 310 954047181 963 126 285758749 47 377 692389902 37 924 749623111 256 267 225242153 218 546 861369772 20 508 226810328 470 584 22786454 896 121 619493267 340 6 31900653 307 627 76337366 906 298 472081728 813 83 741807731 617 13 796356379 126 935 887971172 646 643 626327104 495 204 220298518 562 39 615674851 19 4 722318271 758 883 859408016 599 620 116690895 632 854 830073863 769 344 331057887 5 516 333442107 298 957 848177471 976 669 235156141 478 146 409947575 691 833 363133568 101 291 407073345 280 97 22065389 685 944 888991525 766 909 571179364 535 133 926264998 903 315 266572637 80 932 570216602 152 545 807069492 132 609 385143789 165 502 995400963 432 38 379054947 944 20 21427692 388 653 951038983 981 815 344287452 535 883 682227337 361 942 755633749 789 145 350105889 575 300 156967476 423 547 917238719 453 873 113165470 337 506 23810580 627 671 681891346 669 320 343715632 729 843 218309109 232 14 532155060 371 909 487335559 531 33 245730022 532 449 616029025 810 561 291888783 453 174 273665232 333 85 284293555 17 792 380785665 734 660 866589729 793 572 207875965 785 794 950049632 771 593 89088302 677 620 577407138 87 579 188998978 278 906 304165565 628 200 225886620 743 324 272069445 424 615 727020599 348 979 527091046 133 703 521820989 545 927 169763697 519 419 538357931 684 491 353536310 909 97 359744731 638 957 379316777 771 439 743715394 104 235 675398155 486 254 664292189 62 284 563536857 778 528 665805764 644 529 591383751 38 365 860058209 779 743 207534584 313 885 65585577 697 782 708455787 117 870 393163483 760 427 14800252 258 765 419113433 307 358 770089560 521 527 346005661 546 130 972277250 366 212 805531766 556 225 580076688 557 673 431905192 747 195 600694547 102 2 855279092 360 167 140970360 905 222 688690962 681 526 843782194 255 772 363413558 423 730 956991665 749 692 622255329 450 167 182998335 960 403 825780087 553 459 458558757 915 855 570108142 665 818 44226472 156 516 374680571 419 778 99515071 707 277 973729230 72 201 163939465 258 472 102998738 911 28 678063532 888 691 93618767 195 209 11623252 215 559 730200641 687 950 909223306 532 487 749106081 37 641 451491900 424 723 748083535 983 677 710883237 250 422 283777109 609 589 856939522 892 97 638416522 291 556 410134655 476 487 197567793 279 191 143876904 579 346 289622110 655 277 467090421 197 50 184546924 586 507 480570642 974 329 472569 784 572 515123283 183 536 497664212 760 681 177508354 453 256 757266098 540 649 884059551 557 970 37777601 56 767 523324661 752 886 385133972 495 742 408215799 663 253 4297973 885 834 371461935 102 559 810247358 209 400 252091800 604 949 718650712 813 673 879450621 571 50 579476612 321 856 919048233 778 336 487041835 752 685 40089659 755 433 907118934 538 394 829075806 148 901 384744303 232 722 162557715 181 388 899242985 428 55 913997931 683 808 535630159 457 367 481540792 467 693 196028136 311 513 495895661 40 362 825739962 101 746 295947938 800 55 879391487 304 822 637885905 590 654 178646940 295 763 249702381 666 127 409420396 852 42 526554583 548 20 556888042 910 312 174230571 344 844 949129608 708 236 901228575 2 523 667056392 961 920 317861487 878 71 294671391 171 401 773025843 430 210 704526676 415 628 853239646 390 724 723148561 192 614 618653902 1000 677 732513813 336 988 428285501 817 774 812516794 554 977 519536383 328 80 925055843 111 287 554128443 146 937 953314954 398 277 420172753 561 430 433634283 193 408 604009937 552 229 856712124 244 649 870536167 774 949 793206805 577 164 712194525 309 191 915436081 657 937 787399589 544 533 234411658 504 195 347099197 647 130 78725702 404 606 859654010 571 829 285277712 320 578 862153588 522 483 509191675 223 493 863598671 781 24 96660560 19 259 328479793 334 780 450557952 422 457 303643929 245 311 79692608 692 390 236336001 561 345 175287455 991 353 115014269 445 47 902410401 308 239 554246445 903 185 849536850 746 114 618336422 595 848 962156005 857 97 252360435 163 213 921909030 311 55 44109904 383 22 674651397 929 215 647013779 392 582 884787917 56 549 430336186 287 291 158288935 275 85 675633171 316 480 160636683 621 209 658979378 769 632 568826536 976 367 870442552 311 493 537125441 648 266 32418678 823 559 142047228 378 991 304238546 142 631 178788134 7 606 803488085 671 381 753183275 228 660 229604010 342 192 607278806 496 430 235766816 770 338 182005697 609 889 446253715 895 653 200619096 303 874 703825692 795 255 663233724 151 189 309362561 531 702 180096059 962 769 304533582 784 738 272026890 484 548 874222484 33 13 92198236 449 195 919267292 165 127 603462301 431 313 775741599 579 775 142096119 961 238 143329421 344 575 821508233 900 493 218379284 739 344 143411293 292 727 695009829 776 8 481906031 819 674 267026673 135 437 255494233 959 218 181343603 453 650 352124752 321 292 231117243 381 763 433673957 259 831 218494915 248 297 937427397 203 326 776603114 786 10 884965752 465 842 222941594 749 376 31362760 601 249 349916661 691 854 621023593 402 872 130549289 932 234 405521883 38 55 51673824 511 414 719373765 491 326 945326382 155 487 386783443 285 361 527920084 615 51 677480391 936 836 876274882 622 168 915650692 176 722 882885377 205 882 448278256 700 699 485160354 359 247 543325594 431 693 423226555 421 156 967664400 290 859 930508147 553 358 694708656 406 313 933802652 336 6 521050972 609 843 539684234 550 399 763498062 674 605 623134630 527 400 172873460 610 752 165927790 527 71 334356741 714 444 602134223 651 709 335076798 231 83 529657975 537 939 63964368 119 27 923681850 358 228 378822107 868 589 819159430 31 514 582940490 296 795 464486525 448 462 481982697 427 403 471991244 248 198 768111466 288 293 667400054 262 229 674263189 626 498 62093151 697 406 209389020 92 881 350824309 518 460 666446989 289 551 533251716 584 126 760197093 824 247 76629648 856 535 35405864 198 682 394690308 803 464 310455216 222 593 837764087 11 989 699633975 686 857 611045180 514 330 850300848 352 840 438784937 893 935 17094832 455 583 857699400 264 137 400227727 675 457 990631868 43 847 705116958 387 182 50132067 754 984 574677432 222 478 137473158 78 884 152909258 724 368 181134518 844 102 291038926 890 541 853829358 205 527 471895486 731 958 903322451 67 734 61966490 335 411 810939367 548 651 647074706 702 310 177337485 693 569 457836043 397 228 816918915 341 295 766583665 914 912 8283981 754 550 638677429 175 784 161244401 1000 272 796290352 845 354 20290533 584 757 812939302 951 749 110885490 275 929 91615431 34 558 517306742 78 604 405235293 885 145 114817474 673 255 652525994 886 714 352380226 425 52 500273364 717 476 490502655 816 569 588144326 852 629 179466905 140 17 438646752 778 816 531948347 773 429 28881793 453 416 67525511 608 742 257630666 909 126 310519054 93 920 270762396 315 716 648419114 230 651 472008047 748 660 49283812 362 66 31181152 860 929 752588154 143 102 393998254 837 339 455238841 985 134 811087723 809 922 532726588 133 180 675762885 965 530 379415892 494 294 744264102 100 969 630198616 780 12 433640704 764 559 586509614 988 228 997128295 236 858 983928473 908 668 577768293 659 351 425311239 10 782 123746427 857 623 103206229 16 95 727284687 768 193 73900128 454 282 152225984 872 618 407332704 984 395 585898876 79 481 739255779 635 222 219634868 384 77 999270445 578 941 561430501 296 773 703781830 69 477 396674210 868 544 293658230 435 919 189689771 324 727 872100987 849 201 572443364 638 290 632008760 368 187 784599112 822 360 299770816 272 514 239648165 658 355 990591528 912 181 16306859 312 924 482634585 976 59 292024181 365 111 585582034 177 540 42725138 179 255 558093743 717 135 210016166 200 70 23584719 690 976 284239189 96 483 422252782 473 607 246242158 132 244 879621323 568 433 951542199 700 23 167013906 454 245 38805543 500 57 649583816 652 764 442965252 539 659 572074311 152 471 367732825 90 96 266870744 387 770 471010608 101 856 480210461 302 296 89164523 490 346 663531084 756 112 79509179 896 395 437849674 97 145 694788903 640 565 929272982 807 626 938163840 389 688 691581789 569 716 545468622 923 130 60552656 149 383 853857729 406 949 662500853 567 583 956869896 424 597 355616924 474 821 501670127 487 102 939647357 428 999 671275731 897 988 473871975 842 115 119906106 796 60 226863019 454 283 886946857 112 524 355562734 281 332 384370408 838 289 621080393 870 609 291462786 626 432 651781102 410 229 681486513 262 233 765121917 466 889 236317319 116 611 828402607 402 576 515964115 866 850 503649215 984 210 906047232 692 584 250212407 934 570 169150229 590 89 831595039 350 104 603620920 58 930 806964789 15 565 808850743 588 898 919803400 596 695 260673048 378 874 721204591 683 662 120919748 988 526 427056222 614 173 69478055 240 936 955153527 136 27 445995990 571 873 982881076 151 740 580339347 669 146 164635964 120 887 746167336 594 195 873994953 158 697 493148539 832 969 975809536 522 212 443016111 751 965 998741201 728 336 762763446 105 728 176292035 861 500 173289908 673 684 934517303 579 922 623211690 61 538 129494382 214 160 831185234 321 342 866123460 490 687 304690045 54 712 496564247 212 891 477909824 392 905 657615741 321 118 826816899 380 903 846713399 788 110 265640890 347 656 761073145 75 573 880843959 76 421 457704595 723 318 538625117 55 749 790567464 474 952 969783112 32 279 355801491 138 485 160436582 572 34 340273505 133 45 316861806 471 517 751234934 712 430 369645041 480 805 342443803 566 781 710070198 151 944 966687310 812 484 384318684 879 88 208433292 432 229 669772419 254 991 381693955 151 559 678913099 798 667 283981975 762 706 388787176 444 415 767465847 302 703 78980323 744 589 310605048 167 81 790284385 382 669 632886038 4 15 856200521 541 63 734357118 66 116 744765655 490 423 528383529 813 692 316217781 60 508 655415256 778 238 742428653 313 828 139973683 864 959 311471883 322 950 585882121 186 494 882023909 861 16 353995774 274 771 885649459 6 82 683013100 12 304 939643980 271 335 557837246 680 258 324764696 1000 668 10974769 360 16 631062487 155 851 101397982 18 13 724739816 174 156 788091287 647 281 13987212 629 277 229685372 485 227 144518781 523 398 861224948 760 349 822247625 635 975 749098215 924 226 177209976 578 501 293529882 324 405 3892891 570 338 755035352 869 510 949858682 873 539 873754613 341 532 270754806 745 539 471825876 102 43 234671741 776 656 174215248 108 72 396815522 966 184 647072383 704 619 364700619 62 951 719293465 736 790 566086941 321 995 87336350 502 910 14913134 34 51 427583394 465 876 337570706 600 97 349448951 522 284 759453764 300 316 156594682 611 803 354774976 213 849 429782398 502 56 460988581 672 616 43387579 823 294 738811868 297 204 371718986 535 934 229349816 230 751 572022016 788 263 635293391 889 508 451245419 875 822 920515583 623 282 1112446 719 844 43344296 833 164 411987897 535 490 841983821 170 336 459517402 270 881 336853552 795 5 372196537 3 547 420470523 597 544 85271689 700 530 8189569 364 886 458004703 522 958 745314282 65 358 513564629 724 26 797655199 513 48 983306463 960 160 266237803 802 535 958873719 575 612 978765908 716 470 390724496 250 2 237991289 903 502 199705575 891 375 402231883 769 610 25583842 673 204 7285328 474 544 372766179 11 891 659415894 338 653 237235100 483 756 589013408 853 981 620064070 624 214 714185883 524 45 930838599 136 536 62051619 565 968 615365631 168 662 568894601 31 125 370454807 572 382 576299331 63 34 289989120 179 842 38518622 480 724 874967522 738 529 108188944 878 895 647622061 78 111 898889548 879 997 690076721 134 208 50147523 14 631 881748161 739 305 993091808 853 595 197429610 572 429 167126593 535 697 870911406 857 529 64991345 58 475 350749388 75 358 508208901 212 643 993482327 397 59 552893735 249 12 552671060 488 266 48183105 544 721 348227450 787 938 169020809 261 64 360420232 569 123 786445021 648 792 527921566 675 83 945747157 771 855 315605952 677 988 594787583 19 223 421895484 417 736 102095237 888 214 52197436 568 920 365754562 173 49 519696314 488 648 264582975 812 281 773735739 493 385 698588569 119 557 832372990 327 776 759479621 831 787 286039024 912 744 575327407 378 91 985443278 48 632 892854524 114 693 1117596 197 655 821859934 939 918 729082078 886 305 247985505 420 567 555887574 781 433 831543435 224 685 166803929 965 155 883612346 861 562 428115591 703 458 991843701 623 560 410009014 889 632 262547572 745 392 384296004 675 740 268756046 122 785 830970389 119 559 517500564 159 715 543833691 292 644 636077930 287 887 788773576 265 577 855894416 30 365 444246880 329 182 817828405 522 702 609363200 912 965 935919835 291 303 808279022 108 177 774504813 269 803 293395441 332 181 259378923 927 251 370733590 835 386 685797408 698 219 688212785 802 852 548340234 150 610 771242997 607 18 13845135 120 386 399492919 821 498 830048106 259 14 233218894 830 1 766819676 582 969 855061759 879 220 808015980 510 478 398262755 973 860 546918858 921 166 91042369 317 161 407547827 616 466 737218155 946 674 682136062 494 886 460064421 359 916 240186408 647 34 998933269 554 935 598844035 864 365 417084326 992 600 141798493 264 955 474316652 566 227 54623760 207 904 721503265 890 832 485922148 307 829 22297821 699 727 866781986 121 555 747685676 170 258 891356960 131 149 585409023 590 490 414227780 477 578 613693885 258 516 105812752 568 564 886397233 776 539 615374927 179 716 753944451 872 340 80304067 838 860 330328030 85 287 244114072 241 643 242754093 638 202 908210925 22 703 166970555 309 102 910857748 542 802 85845495 416 586 953036372 321 110 885504412 952 75 68670908 499 210 537662384 881 522 968502706 730 131 789371759 492 183 709413585 795 273 288632147 756 329 224235889 273 627 792150960 438 703 492985233 613 639 650638 336 441 468046356 548 239 776455181 732 825 24970331 379 745 586225595 835 126 298311299 633 18 693984171 139 413 709761176 814 308 287136040 652 918 701604605 425 727 888240937 401 464 543543641 844 296 263576547 741 250 498903782 87 246 320280748 940 529 338735922 53 193 475402359 547 564 881492090 555 865 804087702 526 491 69096800 600 306 144623633 334 323 6799100 602 678 297703217 462 216 42050946 112 812 517695100 412 860 8048624 286 17 4112111 235 732 86497719 683 293 413458474 426 938 314830476 227 354 664864283 694 638 83116524 519 862 6502403 82 197 299444055 524 796 487654178 982 75 111873372 462 663 768531784 164 619 579408346 284 259 74429045 936 806 168906714 526 298 211829616 305 611 24200766 876 795 503858617 550 176 641264833 752 522 581373883 971 218 719056147 682 319 93939422 401 353 245154540 277 642 975802498 129 102 758447990 289 701 591016696 249 768 559197755 389 35 716101187 312 249 436059516 884 870 731695056 934 356 86103200 817 308 723301662 904 867 413626441 894 258 165389284 99 842 638599101 62 316 777156837 839 545 490764542 706 910 177514660 632 951 491499255 841 234 980047430 443 42 49826886 629 817 264344878 429 854 394847977 240 148 918978384 809 739 198947212 198 501 166274685 200 544 495268064 812 393 583163748 548 798 241311210 931 952 514914915 609 10 254483780 763 668 929903403 110 951 668208107 539 45 818691894 379 739 204151533 789 320 896599151 994 648 718148433 683 790 287655853 429 642 352058278 197 950 125296520 786 36 167532810 165 355 184852964 993 364 314992005 766 819 152149605 625 580 556891275 671 212 787870329 844 952 223048601 538 357 552156945 246 16 415010182 205 33 166742492 952 748 990342367 700 91 617953034 891 808 439860309 522 865 121600581 648 755 31580755 686 890 290914633 551 681 403062827 985 137 935006174 59 493 475090123 292 60 638242890 557 895 673811497 72 303 969894844 131 841 849651255 24 791 221055734 739 467 605652147 381 396 575352273 832 195 788135074 725 396 651777939 435 684 69665859 658 472 147887024 210 139 200974801 964 449 595740603 787 695 363036820 408 288 799919425 379 98 156939329 115 987 731818747 483 978 847923989 159 21 739933255 898 945 364727315 756 836 883673999 672 627 249312312 587 208 281656921 598 893 342419929 274 696 572888315 900 254 659163622 800 712 834759956 886 224 834456401 473 544 2806417 980 329 109155358 559 442 769494992 765 748 794509382 665 588 14179702 943 806 956342697 909 896 871112747 763 3 261712913 172 148 458344740 100 18 675982480 378 989 871600676 873 914 299545055 305 569 663779289 271 718 470582969 203 9 129080773 779 733 436227936 528 146 362568100 742 172 323208089 715 857 156860827 856 601 123525726 275 361 319298928 528 725 533847735 793 517 244174507 810 366 520928474 32 653 176444642 309 578 956507094 887 261 417560139 176 760 94379811 698 185 308230339 402 8 188586267 443 834 14100016 889 184 71071745 764 321 488784837 842 582 398686215 568 594 403566198 918 806 905503578 807 629 862520567 920 1000 433291298 773 518 558796861 677 514 308988869 331 407 368372542 44 714 970290271 86 944 834099272 515 559 948447244 883 518 431630693 90 916 988529722 650 279 103239754 724 315 788738522 959 697 148653215 306 92 603630658 92 373 894944356 687 308 754212583 680 204 721464099 764 643 347815438 401 54 767615191 88 573 267183714 301 391 513065898 738 470 91760593 994 406 674634237 86 951 91390920 346 507 177448117 312 246 416882224 615 435 910339067 869 372 414087076 551 871 277924852 390 711 161750665 579 334 993175750 95 835 680377886 2 677 531713524 479 89 391444859 846 712 895898732 406 531 630777504 169 765 623322290 77 676 157411053 604 360 875427328 210 24 101833250 930 708 288026682 180 56 257684549 692 316 719324633 91 899 557246447 585 476 461307252 592 806 994765763 32 413 219533292 588 965 622095121 521 742 973086399 443 809 690861103 689 481 983068920 6 801 753361535 631 6 705653210 438 628 64592879 199 644 253177001 147 600 209355890 802 960 916002836 833 350 612453379 140 571 334035481 610 62 782344550 456 184 437574200 899 520 452958956 601 787 332024512 462 829 271133697 760 388 794702178 987 315 203310062 490 509 537021043 7 35 175901037 413 474 106753624 29 559 387035021 121 263 482023120 702 373 403912396 947 736 788879721 266 275 705829512 557 875 133721118 457 955 70693646 302 745 233820729 108 8 539525145 409 208 411852857 423 919 458573475 182 55 605063962 85 386 294866531 786 467 158129555 447 978 368747401 558 377 700433368 697 633 606861525 134 708 482284666 503 754 531149240 864 924 898226238 181 881 882957073 150 977 323491971 387 245 527733912 456 686 969814677 853 508 289664955 461 802 589917809 624 412 723090303 259 549 968257787 284 383 789963780 97 433 176034488 101 408 990541999 646 532 619531476 968 96 714096831 497 521 75087276 167 583 820987473 921 988 76336406 15 55 129555320 156 148 661670124 734 646 274835455 384 185 911866065 125 499 839470928 299 546 502138919 947 191 361462125 971 159 668590473 633 5 922243437 482 934 88616165 199 805 502863970 838 310 882165307 575 245 247801436 915 569 507521286 344 720 550611897 921 826 921060956 27 336 707033820 204 203 981680547 422 259 528197459 59 913 377292681 251 494 861065156 592 478 86971878 653 147 651553365 698 207 445934714 5 165 14516445 556 384 633820554 51 14 13832177 984 632 768788380 248 680 168872171 179 230 387252306 321 928 320887584 314 271 638022337 675 432 162586855 708 33 39257914 952 569 249758317 556 762 601133452 653 563 897892088 204 309 618245226 531 90 467758941 239 40 816718072 849 711 904061258 931 694 743091303 812 342 306006368 192 661 769789325 630 189 688303338 594 188 84261855 745 377 309104455 963 285 507911593 548 484 612120682 719 549 648891375 419 676 443202121 48 129 965484103 306 661 99869604 921 571 775055590 526 142 299570931 243 411 810045750 158 307 633744099 575 981 676263159 249 854 929876197 8 349 417176093 339 906 316646786 645 96 31617343 243 151 431300746 508 893 924716879 103 748 827867639 586 948 84327601 430 255 991826713 398 90 692677206 405 590 140092735 647 477 498022059 830 713 571424701 259 435 692480483 201 905 632357065 370 86 70957260 156 282 150709981 106 989 256951567 330 102 457610478 534 850 891741416 305 860 581518877 614 491 376785363 998 53 618904407 793 484 790847313 225 67 838924311 359 218 852010991 76 511 261382532 546 508 61615571 567 577 894837992 527 654 718102007 212 857 835735287 825 582 621638627 106 34 142498288 841 36 494608218 793 986 55510784 961 167 350751153 849 329 615641910 388 198 351586795 326 300 151982524 613 319 964831528 251 64 837644995 479 517 925965704 115 266 696168710 915 343 922695407 284 793 46208972 84 141 106336918 965 2 68277126 194 556 586360582 182 51 153375724 29 588 742707420 565 996 248908345 380 217 914611014 420 650 660981789 72 297 286219174 771 729 213106 995 511 377404222 107 764 902628238 482 626 280433245 2 561 221918954 469 966 692646751 284 519 98617113 832 122 830151796 137 155 128206173 385 32 53593417 793 62 170922585 838 525 261453489 52 172 462018802 201 514 928679591 769 676 445654464 308 225 64667555 988 285 777501608 884 457 819298905 997 865 443403293 178 737 223950818 255 547 5380525 709 911 314327342 528 96 777583314 209 586 357097979 23 163 8465834 846 110 176639490 104 912 931604659 743 994 578603359 1000 556 378597249 697 719 372877814 980 395 857637261 372 891 383064052 673 691 65630452 951 962 450001926 148 635 246741504 767 648 760320086 170 480 75345661 748 207 58939797 631 242 232508614 205 852 906505279 567 873 87171759 618 127 827579142 448 109 417145574 649 187 839052063 188 799 117041237 170 429 20026041 602 936 867704816 965 512 833618054 204 584 759847014 306 794 79828291 194 156 950485711 8 272 936953713 772 881 977769458 432 863 926799013 159 667 219489174 179 383 497315083 963 120 773792684 278 27 251694971 992 474 979108048 393 257 557103784 863 745 596250406 382 323 374820284 513 428 441038663 140 536 799161903 52 806 104401570 788 659 619883258 716 643 208063922 292 378 771205894 384 100 343972091 620 990 648636475 39 616 280020641 380 485 544427939 890 681 544535315 328 661 63490775 727 541 484816703 839 577 558502574 952 778 6016049 123 82 529062703 933 688 216588009 598 722 311035134 429 506 130685203 804 129 94828970 863 566 357352520 19 63 981387317 994 777 994737851 10 454 27638471 876 420 587114175 967 923 258023667 857 915 832876136 139 760 462473422 168 768 457321973 421 689 76257842 629 833 208494835 109 551 573438877 649 304 670203103 458 801 945677708 838 924 720586637 557 190 428094844 424 762 275003508 151 773 290588269 305 655 576560502 304 441 352712073 684 192 943389714 416 253 582727145 22 866 862976281 187 457 842572706 908 555 276626220 576 26 974614928 837 521 588229795 119 263 475799304 474 965 766660853 747 430 15481817 686 11 754581334 5 258 933297968 644 555 997975226 390 835 99460161 807 418 589270832 822 321 172462407 95 825 419699892 513 546 299205052 352 644 659183137 553 161 486977983 780 340 142215020 846 213 236570645 487 153 992583304 144 429 74210524 345 210 567394997 342 292 174511258 373 820 145161483 567 388 678930800 633 906 30832477 468 723 612745206 670 280 315069727 202 233 34930778 28 845 443026466 66 714 487229048 800 841 874210843 687 902 444069832 325 42 199848254 805 662 265448323 932 521 637776614 639 889 189670597 395 283 124281596 80 797 381475112 64 763 477535719 536 568 898301650 195 860 673130326 748 691 348715686 380 469 190100945 423 524 54049161 78 712 900727784 61 161 504459577 486 260 192445683 804 575 117202274 323 176 604252551 821 666 800151441 680 105 667698141 240 250 807012911 482 975 303444556 318 464 296419774 212 630 465399479 939 284 802998910 988 823 785665366 653 997 291677040 26 785 649371206 869 13 411049544 53 878 810058612 204 412 294866554 489 153 285085800 288 954 706176526 775 929 384881315 662 805 299867200 773 216 338392737 337 349 655073028 22 343 448219874 537 751 490865506 843 675 157729542 863 319 935292614 577 543 990143930 597 446 309061236 866 762 632113779 704 951 736057841 939 890 798462389 747 691 866805632 459 584 110156220 58 977 245360959 911 406 250250221 484 885 649319488 83 851 171902312 804 703 267491882 278 463 319811159 342 659 515378854 483 281 474636500 384 672 741172692 561 334 210589387 816 44 157767025 453 298 558806021 130 552 215368054 698 232 430626940 423 894 112531488 398 831 678737529 588 581 281384280 403 75 194186449 2 917 446016181 838 495 217233329 188 48 862109248 668 432 351987190 726 535 248822085 349 364 513312235 205 251 385546822 164 888 50157795 444 546 423397183 932 151 110731157 759 162 572328652 587 31 439555793 420 171 476341053 979 303 428282109 78 495 10020723 294 866 604103479