907 947 1854 1922 1000000000 726 934 146078238 498 337 376823312 903 945 999999081297170815 28 645 999999337066319252 299 234 229968686 562 533 999999003222747093 442 55 999999710978385568 174 931 845646701 107 423 999999646210076114 537 398 999999758837917496 202 534 400207944 261 95 507378302 513 764 966726351 243 104 215855991 245 343 999999927257862627 213 350 444492844 757 354 380100885 272 497 999999523058917606 337 125 999999433758467249 164 354 858828274 1 860 999999472248440845 946 369 999999557567935556 409 908 999999536135128782 484 667 999999673803465184 357 723 999999052911132542 314 875 642029803 781 678 999999824958754886 734 595 507791012 796 944 999999841834704452 470 227 758824080 168 823 999999106917984607 932 87 999999292641068502 309 883 686474873 677 190 999999282247443304 867 785 999999994746839227 919 671 999999963655101827 173 333 170464393 451 635 302889850 858 621 446623775 756 630 999999745059130934 369 439 999999832171032631 316 735 999999250586795934 298 95 662356385 679 660 503276922 34 398 509402967 888 696 999999178715927651 337 694 999999195491088947 334 91 999999402815996169 321 556 869738717 931 512 999999232245013113 477 729 999999374069682254 828 888 999999597011554303 717 531 490255481 793 73 999999817336608250 451 740 999999899653976520 227 582 999999272800919745 124 728 999999897513791705 684 56 999999920179570739 31 55 460696542 721 50 999999586409879521 947 55 999999222452432419 546 94 999999793162421470 420 568 999999644839067380 382 454 985843967 16 921 999999850819612260 569 204 237902455 149 366 999999998840614105 786 93 699583837 869 875 94063878 861 102 999999795764673835 197 635 999999785732224891 929 403 999999851998762142 897 207 999999132410521023 108 777 204270205 430 65 999999351399750221 368 855 576003802 330 511 999999511940574597 826 546 333299101 786 719 367131240 483 907 999999557135770209 651 857 35493694 253 86 472417476 124 528 770256149 654 475 120946092 689 650 144823829 142 181 228771309 387 289 139407099 401 286 999999641437789254 679 846 999999483560053537 677 306 815435674 307 813 252703146 300 134 999999257036998837 854 627 400624053 311 660 159896635 306 434 999999084745188931 865 27 671537096 369 282 999999358816419019 121 113 141889999 236 85 999999951778239463 154 122 657240699 259 699 999999220995007468 196 633 738524105 345 390 999999557434473483 84 557 999999772096358985 641 929 999999573209122473 238 578 146970933 95 818 999999909378987204 172 153 999999171740720780 771 903 999999089197941341 541 635 999999315202663563 215 211 669874557 258 155 704313927 589 696 999999491146887638 686 466 999999715792805958 118 243 999999118879972431 147 586 356282499 726 217 999999872336716525 833 324 352327297 232 204 835299936 86 261 999999326435376874 353 945 984571202 942 134 999999274640973901 47 783 191480677 94 594 999999615583577745 343 844 999999917879537002 244 569 25939075 564 457 999999231054206117 238 850 999999700520372406 812 91 999999744055645254 629 126 999999110692973844 6 162 999999045376918376 434 836 942634173 66 103 999999595573840371 450 250 999999106600850860 102 348 449674073 180 229 905445634 110 160 999072079 336 218 999999354222827451 608 685 999999421068605767 74 764 100885991 206 341 999999291108532036 485 883 420845295 2 6 437694202 88 723 516880389 610 689 999999247744250352 333 236 889179717 465 370 999999624478220152 924 877 253663841 920 856 999999398935161991 22 383 649439305 112 367 763431847 607 696 303746283 760 129 528482463 335 488 889955618 148 463 267156983 761 407 110554954 783 798 999999409771626211 135 573 999999474302300022 806 900 460085192 2 783 917269463 554 129 922140447 444 421 999999375545115102 146 488 999999105187176059 938 711 65787624 286 739 999999510919251738 793 876 836862684 647 213 53888952 666 246 999999802296013680 813 55 525607717 180 875 999999802358060089 729 344 999999173167178601 778 635 897674533 581 153 412336376 367 945 288847901 760 469 507449927 271 100 640414146 938 407 999999688783579804 739 771 999999049348133169 497 371 378660840 716 78 999999674138409785 773 825 134075066 506 348 661017935 470 290 999999894592238425 916 378 311459834 86 855 136985623 775 823 486612107 847 345 764961351 129 182 270382161 161 855 705862264 257 497 173725472 859 524 999999442279089658 376 542 999999754354139762 114 429 48959584 580 739 999999174585871307 771 908 225392208 829 591 999999566908416773 51 123 944933733 880 851 999999255472806217 115 281 999999151926218613 526 838 999999549305676695 701 287 999999242907371564 835 833 218395996 859 231 464701335 901 772 482776551 846 270 996187144 325 468 999999842910786208 789 117 371108555 298 416 999999222802294328 53 768 158127570 72 400 999999387348999437 602 184 499598184 138 117 999999865236622960 380 835 864693435 700 525 999999479876176466 697 797 327694715 184 173 77859457 623 553 999999708998500774 328 631 68290498 673 758 999999857700477803 438 136 379173185 369 121 545164845 544 431 869427078 639 442 216477995 561 249 161866861 432 943 999999471980413587 544 843 999999214014848058 310 531 999999422538436836 54 842 799999008 375 834 253136864 72 204 251991284 564 41 58501591 21 70 257160239 539 651 650480707 824 164 781467437 457 507 906521849 231 300 999999989226612969 815 692 364478636 663 307 999999779808837540 346 834 999999480620605228 153 210 999999949376935693 746 113 133581828 73 442 328296794 868 693 643860828 403 715 999999181535134955 52 596 999999754459915960 387 660 999999319010855047 323 88 616514263 667 501 999999776307305277 50 436 999999375005719364 90 696 435580751 540 670 999999093596306937 669 194 960466913 609 412 992242825 712 52 999999399295383019 19 861 999999578341654883 178 875 860937822 533 304 469734702 198 311 788256045 163 86 628528179 925 460 139696827 631 762 585249901 694 688 999999972854854644 606 646 999999243988447284 767 477 999999249086982042 156 646 999999481196251817 651 282 592156184 304 121 999999251840130819 639 496 318055705 937 430 626111499 133 800 734837272 650 372 999999955653120172 595 170 999999867236080513 142 893 999999502458414073 262 902 999999934168369200 643 869 803802542 250 675 999999626463092062 928 442 999999327430653181 653 634 999999395851605866 505 4 674394038 522 650 999999737417530051 257 442 999999635319169717 696 431 999999822648587531 120 721 492603585 87 67 294472697 748 900 999999932012712194 706 67 999999019503985042 408 351 999999563067732407 405 853 835171785 518 872 108389899 32 457 153956429 581 31 999999076265940738 579 643 462355041 779 630 790181170 518 813 999999209911536539 402 265 4625710 785 204 999999846623537020 206 442 999999535557563461 897 926 537815717 766 850 728516909 738 541 999999616978332960 366 797 999999488458707772 343 651 64532226 199 109 999999812703170501 416 750 999999224351055500 596 374 928640425 847 70 481508475 536 902 413900356 135 441 999999373705084606 296 233 127717967 462 115 999999727535462842 56 367 999999292464600505 63 239 999999913141996254 605 612 556062748 799 428 999999506385182741 249 379 999999927230963087 311 137 831532370 525 449 10075096 125 861 170151280 681 26 691879416 141 489 999999988360196518 348 97 868587885 801 282 132508181 73 197 474368858 302 114 46701018 873 892 999999133106912061 390 855 722881483 777 388 717245586 899 25 999999295607864163 186 745 999999330082537112 217 615 640460637 479 35 999999008502497666 831 843 999999463950476848 932 231 411516315 10 833 999999303431544494 496 317 999999870430218922 672 375 999999304234041544 735 130 100146284 874 490 102552106 930 555 896499463 798 483 218183388 286 423 171056438 289 35 843903000 574 417 787162520 39 543 999999539289882643 124 581 668876783 721 669 921367370 210 767 999999846994173549 510 822 256595380 631 362 999999366983787576 11 207 578319810 852 246 682090271 775 928 31907883 685 933 999999163064025368 774 741 816337421 828 35 1446762 132 826 999999138901116010 617 205 529752586 611 940 999999881554049772 822 31 999999926565417107 448 905 351504600 128 753 999999113690898697 263 444 941224134 817 645 652273836 830 610 999999452329678070 794 761 874966556 313 447 999999741338597724 594 737 999999062735635137 248 2 389168056 805 643 453993647 675 422 999999877087146505 581 478 999999757462911497 265 751 999999861039922702 542 834 396220730 193 38 443022644 600 839 263772524 247 581 126742523 944 363 793732557 389 556 592192896 150 118 623996305 325 388 999999469021063757 416 701 999999231368675433 597 677 999999817994680495 198 152 999999331883228628 832 204 999999211574528106 822 568 999999221778313790 66 526 155810237 114 422 999999894829831046 643 231 166013283 2 13 999999715885971348 681 791 999999147179368325 388 297 503796436 184 421 999999200921374785 819 546 358694092 913 253 299901801 476 481 776784556 928 796 285043732 210 385 999999752971334858 936 345 999999363888611242 407 582 653335611 727 305 431963460 814 203 999999590611164415 888 271 999999200988572796 114 598 358147764 772 205 999999407074373752 90 418 999999710442268790 620 324 999999206592345185 324 462 999999885927691199 502 379 339840055 435 692 999999144755281901 374 934 999999560883500843 259 942 758152057 75 219 999999600018660956 401 518 261630621 662 545 999999572243504076 270 737 427620912 912 906 897070548 257 694 537076540 917 837 110027437 714 785 999999193033407019 921 84 750875907 17 315 999999442995009162 498 365 909513684 902 184 999999456385576983 793 729 999999121365000799 264 226 999999983794439301 841 449 921955791 117 627 270942902 540 442 999999234689814836 468 855 999999059199582669 722 118 541974553 306 28 613741222 691 579 999999980128468528 910 546 999999254199114566 320 220 59513872 440 85 999999591926218396 493 558 999999791314064410 548 369 283615546 10 568 999999241396300120 205 459 999999806976538979 191 130 218636514 703 195 999999057230083710 873 907 999999188344048025 107 622 999999123179116257 825 115 999999699623493294 604 573 999999131592597614 194 297 999999817391348326 718 119 999999798555430290 458 541 916802262 334 828 999999407797677833 373 215 688361573 20 18 999999978290902450 35 631 999999779443459971 18 302 999999030789530096 449 324 822559012 835 875 180260973 436 442 993714048 448 388 999999136215767033 788 216 715573374 171 406 890053556 514 295 999999298055752731 15 349 612172898 584 737 745228770 696 758 674539401 214 616 999999512135251478 599 681 472121610 37 931 999999146085545765 522 688 455315444 743 16 999999657374947139 840 234 999999935387606817 72 885 77804902 398 238 163506002 588 322 999999451213770366 612 236 927786547 222 133 767753780 891 276 999999931280262116 860 55 722292529 918 576 999999550396834787 820 520 999999672983875410 94 860 825807440 139 182 999999424868728100 653 257 999999206202917814 398 528 999999986857276977 322 9 236366356 663 190 999999571419707088 62 288 999999819499144943 295 694 491457149 661 859 853013246 656 567 999999992028395299 508 695 946663671 853 576 999999668202076574 849 858 583122572 314 46 999999624796422107 224 55 250326848 455 803 564346199 465 45 731629132 595 888 999999850573553857 103 705 999999326250745624 763 498 744794882 219 272 999999887651247577 300 667 101755398 222 856 758321551 648 832 999999250301431084 374 204 999999372399092382 264 685 881033896 40 742 999999520344844293 713 231 137888146 90 274 999999099375224533 500 598 907533685 415 293 668399027 830 25 999999283175971127 779 363 66206154 88 278 666523296 600 716 999999381669706635 392 449 999999550189070347 772 76 996881121 621 704 324892851 599 88 872335871 576 377 999999235712154937 551 601 999999634739827524 613 444 745960983 914 463 810234146 404 164 294375131 130 628 384386087 947 818 999999981948936951 256 475 999999397557182749 96 188 821014398 204 231 101094486 122 127 999999203151869066 381 837 999999414062166078 208 497 63102561 850 297 999999176601654361 737 875 999999077715349266 352 190 363630462 2 737 999999194915136735 134 384 999999870365306175 27 843 376346194 349 23 999999632695656503 376 136 460907533 560 447 903264286 802 271 999999265754467002 641 631 999999454368785296 543 639 999999379052678666 619 635 870700223 293 693 647460856 643 6 999999124717265301 770 399 999999110542463039 616 807 999999523932578395 192 326 477047502 718 825 999999504576777854 309 700 999999676787233137 411 236 794386354 239 469 474009568 838 214 803500915 624 710 999999224438181337 147 267 181897581 539 391 420259293 146 187 211094039 55 723 606110560 819 216 999999791979362703 164 809 815712823 497 827 806739592 633 612 999999924904967341 383 156 999999406820657054 681 333 999999787537690059 905 481 947500922 758 476 685689743 638 738 790571105 119 436 999999260412483073 675 219 999999075230257841 683 938 1512495 670 738 356879888 526 170 999999937426460336 810 355 686851703 463 814 999999291068532930 119 415 140776089 566 429 494776656 126 204 999999739911886923 213 297 999999240646622510 830 192 730221972 751 141 82595579 816 220 104799745 741 234 999999476324946830 172 894 999999494680144153 870 433 999999587804773835 78 133 999999131863745005 881 225 999999920861412489 571 290 999999045817578821 875 137 931518918 47 818 4612703 351 482 494351878 361 912 999999833099871938 734 403 7486828 471 54 999999659788730199 80 662 415868052 185 307 999999461906496149 261 852 999999519928235831 598 117 981132203 275 343 999999974505523449 22 29 366138025 552 113 255961501 454 563 999999229012172803 650 864 354610815 863 755 999999827985838407 450 203 805091767 173 345 218733652 846 940 999999789387870765 170 631 604527294 591 282 999999644207629671 384 320 999999856799448009 166 821 47102031 614 678 999999513350206822 432 528 542596098 797 631 140563868 287 785 999999895115416486 581 579 475659229 752 755 999999505857472069 350 720 758219560 909 182 832200922 524 160 546293913 932 528 999999948950206482 933 889 669194266 295 299 999999650343357624 9 615 363734069 583 173 85490830 119 689 999999633133020447 416 123 999999687777356419 804 354 999999489525348086 511 666 953033903 862 82 999999306838322160 403 86 183769899 3 382 999999606415036437 429 861 999999294315745558 555 459 999999790873121178 617 878 980876676 355 121 374127473 800 705 999999677940455279 375 17 441635000 470 335 999999825216094509 295 190 999999627780080037 708 380 999999862524764814 117 691 999999986242736495 362 155 120760544 98 369 612124619 384 120 999999153553912652 486 658 575862056 437 612 999999655923954185 122 373 310157763 649 872 473027728 945 231 999999790004643429 840 36 886961262 91 118 999999605049842104 490 84 42750310 680 144 69274225 644 684 999999556732172753 111 670 999999768437022575 338 834 999999020346242582 86 416 540891617 120 705 693933976 532 297 999999587015185559 178 432 999999546395091676 117 813 598820173 862 300 999999460204598612 399 730 517309840 322 141 999999457132658031 222 742 999999957785074075 547 507 481942984 818 759 999999585713344687 342 221 999999990131101282 294 355 505448651 172 798 874671318 688 524 999999750396033651 12 300 999999866095432332 782 413 999999307341555095 424 157 999999914592329686 272 106 999999128194939180 78 116 999999242677055030 769 106 494937806 89 853 999999695865926329 934 805 999999217141417393 931 577 999999381293094070 176 99 132358487 529 334 999999032571690767 602 418 364333392 329 825 475612332 471 219 464154763 877 705 999999805258899768 198 348 129158393 101 694 335165883 799 76 999999326158388718 106 931 596591995 414 532 724282407 186 280 999999008947131632 32 442 999999913886300962 501 875 164159899 116 474 999999058402560033 491 149 995698606 491 277 999999569164123025 29 859 208877010 752 593 978694701 349 412 698649485 117 577 999999186411323504 928 62 238708997 426 394 217318660 68 525 13520995 341 588 855012657 641 403 327169033 30 937 999999053565900651 233 61 73512969 626 191 483278516 516 205 999999907731099838 201 86 999999010494711846 547 194 737030386 278 291 999999189177574218 56 555 999999491155206551 332 16 999999932252088793 652 424 720274935 455 352 999999964499586390 433 151 999999923838481335 686 768 999999744176180881 140 224 276484182 515 813 999999500881874282 183 929 782682027 863 128 870231987 533 759 999999824576483700 135 534 999999759305475706 447 61 999999244417064787 444 573 62149021 225 367 999999395576912800 831 521 999999377526426285 252 486 299300394 574 825 823289041 927 63 999999799828770173 391 257 746563744 5 300 72999451 353 257 999999701078075233 844 356 999999361815172957 603 720 999999016713280651 446 671 999999152145823024 739 760 999999327893753167 300 841 999999804873597009 348 866 999999616922351629 405 234 999999033757699040 441 498 999999044275752775 798 14 999999878905617376 130 132 468861247 588 652 999999366700360181 127 765 999999137352817708 689 369 999999684268366696 647 53 760106665 205 855 849937096 613 836 999999526422206653 40 859 999999045729659054 269 741 678391245 463 492 750673327 689 729 999999361952634476 837 571 999999491716135798 591 430 999999880652328921 788 574 13271328 759 883 731261399 231 5 999999971083607574 383 154 999999845686786920 595 798 999999556240305243 645 587 155878788 437 608 670357806 295 723 999999980550799060 833 838 999999071823663360 505 853 632586017 803 551 236754246 356 368 999999240241638934 423 639 999999700588473223 768 17 999999623822382915 593 345 999999460880387660 839 497 90568678 175 93 419744092 703 650 647188550 786 769 831037890 737 833 999999033407321827 884 479 999999100645375718 615 541 999999671314287102 646 52 999999969257858290 407 205 171838205 431 635 270269351 723 513 999999241235534987 365 631 348281084 445 605 999999579235319448 362 204 999999804642710563 894 645 491557268 941 221 518300209 893 272 999999635637277703 50 390 921338782 694 394 628401682 195 115 703859059 780 883 999999554502226770 634 773 999999905584702675 891 935 999999358709157794 336 396 999999037542352877 397 131 999999543630086323 578 185 999999902333009845 716 55 999999037458376702 737 182 999999523553340580 385 771 227931756 523 920 711811284 631 297 999999613251884804 1 933 784380894 461 821 999999771052675003 280 899 526561991 745 501 999999002026719779 702 394 107898632 524 692 244776480 246 451 107792656 151 707 999999667184672128 473 656 441733060 217 113 280641461 351 651 999999215994498722 677 807 999999336053984033 141 706 999999358112847282 384 307 735515004 758 250 999999668985390665 313 328 999999119160981702 304 496 999999315041020938 327 327 882867192 418 491 999999136951200662 233 272 783272631 590 42 999999859151088095 922 300 999999835501436844 430 204 999999862062040490 491 172 999999669336462426 48 191 22912178 577 12 999999347235698930 95 2 244024089 521 300 999999723208636412 858 707 260611087 334 210 999999717963681282 69 195 999999455109753454 771 239 999999498504547951 747 323 956861120 267 179 999999366479227290 701 341 985660564 907 163 148489770 537 408 999999254705521132 123 872 999999730203366016 600 214 999999640661597734 104 861 999999666079246629 20 109 700575474 127 624 997431799 621 845 909823584 32 61 999999592312360524 105 22 999999395900632133 745 343 492159236 287 755 371852290 533 511 999999858937444133 551 874 999999113805811693 188 711 999999532004570441 326 442 523572793 425 694 276822062 19 44 815430199 900 853 541840605 45 807 999999312374561445 911 778 559615239 908 260 236856797 916 184 999999886283515747 871 290 999999133248151107 732 399 654670161 34 350 999999025883854463 320 197 442267365 785 792 240325269 377 328 227144544 668 113 369102012 818 155 999999071582566425 866 329 999999627339853729 721 790 999999900977587086 497 516 999999534573055956 509 532 762884922 767 631 702992243 60 542 999999051478806104 803 13 231226124 24 36 649351917 519 481 550470218 541 710 999999983284173784 195 57 855535816 72 624 516374156 5 430 107757734 893 237 740110828 875 295 999999973869497360 72 882 690858125 426 266 748639334 658 633 43137759 508 564 635571588 822 272 999999107905629148 179 881 860327693 380 714 330256133 84 635 999999913530785158 201 457 746870176 131 890 999999096517478794 547 366 999999442760334217 299 572 999999449062596241 29 27 999999909664562192 164 125 999999769425129698 193 291 156032711 364 872 391009435 492 412 751508537 551 818 999999166014542877 422 4 107899430 657 33 110970285 415 771 515258497 746 274 999999222171602695 125 22 406628518 38 232 999999556403599460 149 526 999999545558521493 556 150 999999290321832617 226 500 999999959165146030 78 447 999999233463057946 277 409 962783164 107 74 999999666202638081 251 823 6180814 97 902 708494357 396 146 999999619422581068 39 433 999999501229971985 692 205 999999880694995304 376 629 999999447834327206 391 208 999999332149885593 171 736 999999449929167530 880 137 999999436958108591 761 304 955654124 801 812 672600270 607 685 289418069 229 108 17934299 572 442 911961337 193 130 941162160 175 780 12615480 203 526 999999540793175520 339 648 999999744224460075 186 476 458597961 630 855 992198288 660 275 999999758728172610 787 449 999999928119201968 795 67 563824078 723 50 99756733 114 880 366363806 152 815 350004518 212 328 172529043 322 59 157059677 627 153 517415232 509 807 999999607582698153 16 137 999999413049261537 823 102 999999717450948596 543 505 112156180 804 754 999999673697973443 642 762 999999772996371546 517 856 999999339914347149 278 198 161134478 419 770 995384414 680 701 755317347 735 497 62764988 749 543 999999786386358270 428 112 999999258657098160 443 730 138177555 243 313 999999770929806341 909 297 999999163262561336 733 85 999999522721934414 259 750 882132024 191 343 999999246968422335 370 319 535304526 534 137 555521824 893 33 999999901499652330 150 87 37874224 866 4 999999603397913717 625 355 161311560 801 41 999999857827368305 235 774 999999295178638483 104 945 999999480690647511 853 733 191666870 503 454 999999987223430337 7 443 999999101352971552 678 438 999999485824045504 693 301 999999686916969229 397 731 999999351654874813 230 303 233781659 837 882 324328103 862 422 801181247 764 909 999999693178098041 290 110 999999777963941735 469 645 326288476 457 314 107722874 774 646 496791989 524 512 398668708 77 194 754232873 360 200 999999064186261823 66 612 999999635808486165 231 855 613825292 631 439 999999768944044229 350 838 587610457 373 113 999999046376409252 889 855 999999175053395798 277 115 121770558 439 767 855817558 269 186 999999332902255325 660 427 999999219982650305 506 717 999999020338792908 404 151 744018299 448 800 999999034765416394 416 372 999999974107287893 365 401 105683917 913 716 999999587525976696 635 521 999999280228430915 144 33 113957629 580 57 129336544 29 846 404074218 704 208 999999876639475104 356 176 762193759 930 733 999999966104454693 654 70 686762270 558 905 783218230 746 127 38041853 467 593 114533381 109 938 984575509 391 268 957178928 111 824 999999258687140105 241 529 182519282 535 690 999999180227179169 527 317 999999866455367574 6 200 999999296271008813 618 634 257479020 892 121 999999247791424666 247 618 999999259125185925 844 297 86025883 475 521 999999001962605592 641 815 866676367 639 262 862122529 883 45 541592853 183 858 401640291 64 458 999999948127408830 642 683 53900395 122 177 276122605 931 809 570163925 686 351 999999110035580990 290 358 999999462875123562 182 62 999999587288502632 452 172 999999832662980599 330 90 744113333 776 643 486643249 736 872 688346816 359 136 999999582052301699 946 388 999999750281574765 396 360 999999788424897584 755 377 776619844 698 253 840535790 172 826 999999925197116362 541 271 999999720911840938 315 695 999999581484457142 593 100 999999535739742799 826 85 348308177 562 57 999999890409046933 904 630 943792511 769 107 317025119 731 737 999999241371507250 664 90 999999637232559332 173 602 999999775916482225 489 721 999999525314111219 531 106 999999164316124997 671 321 999652646 912 711 84902505 942 386 999999064015862744 465 335 617688851 140 925 999999793128207064 416 395 940332300 570 219 999999163797554432 623 646 999999228283227726 446 71 999999483127823463 817 438 658988648 1 43 999999757583965983 277 457 109357661 427 690 711785604 758 665 964369732 73 203 133816126 472 210 999999306096795781 391 825 738369483 91 124 198356903 855 607 216152962 270 790 88747243 203 8 440952135 288 564 999999953340895462 91 378 999999756727461291 70 480 999999850587824548 797 36 999999862525427569 177 204 999999312736142857 125 890 727568053 779 364 999999031538046474 370 496 754773475 341 735 895668998 119 583 999999107211079564 555 915 478846761 440 182 330007628 473 402 999999768172136953 535 193 185230116 738 809 11474185 628 785 999999626425256657 410 74 115055892 827 231 999999818568964108 100 57 999999324066702919 438 267 999999902307727159 783 834 999999057364966166 589 194 310283566 446 744 999999890337118164 372 481 820689006 902 105 999999961104793562 4 397 999999118777192253 108 493 999999583850631412 308 2 999999334926881569 691 853 866530352 495 327 4025384 165 509 999999639693930114 312 716 495626033 557 881 999999962869520233 337 606 404834872 607 318 999999987352359594 92 707 68130883 577 323 415101166 635 926 999999237915557897 49 286 999999788741774288 161 582 336361593 181 607 268317920 244 910 999999737419738272 592 808 999999332846053466 792 30 999999813215879420 104 902 549122300 14 843 999999835130392664 102 328 569613690 875 193 977083104 632 554 214934671 417 893 969253006 9 385 266281697 890 394 331765396 402 190 460164321 317 431 786924221 257 186 458759781 784 894 999999705486996169 136 263 824593369 637 602 392997056 834 569 985384810 266 380 999999651468293630 83 539 30874853 322 788 685916999 216 298 999999354212418490 255 311 999999937827064228 307 118 999999299357680788 359 413 935031885 14 625 999999651250027386 489 855 999999312902052425 371 492 999999610888857877 112 548 545216813 915 767 999999372801538732 106 379 494788258 905 192 999999971392750879 158 670 999999963447499217 492 333 999999262129898075 84 259 585666973 179 343 999999982043473306 530 50 820065789 897 853 999999503942198784 874 718 999999740248358579 80 397 999999095024029641 282 587 311421873 24 824 999999011986430512 298 322 999999384610119743 560 405 999999594305671347 651 231 708763572 483 605 796172118 82 423 999999098958459301 765 581 999999920112800315 730 813 999999544252383117 796 417 96548506 264 531 999999237966341324 606 466 121407952 807 196 999999572461003069 490 839 205367153 920 45 999999640375993738 694 565 999999359762525701 488 695 92213817 943 768 999999398101158244 299 318 564225700 426 260 999999439980126132 689 42 999999520474120477 636 164 471139873 617 433 999999857065446849 461 462 999999934907209082 910 347 999999627120049109 944 40 999999228349727481 938 877 999999235872203870 273 206 599997012 915 545 647938454 410 870 315092719 917 42 999999914407560833 741 225 117576699 327 455 999999394515267393 416 649 999999510352140130 575 611 999999783151019300 414 415 999999591796064953 801 663 294870395 528 36 651932484 785 250 999999027554461289 178 611 690592094 160 677 999999156626244687 749 118 999999129458047436 234 258 999999783613891559 68 204 692540152 340 306 836676755 487 322 911238386 80 66 999999091936411813 786 834 999999543005802896 658 836 999999665457203859 776 512 823991640 558 627 965263428 579 420 427116537 469 821 716919829 274 500 363647145 167 394 999999041526307758 666 130 999999591203709392 480 679 134371850 499 342 602097371 308 353 111176020 344 840 999999183135477254 317 753 359171373 349 368 914955906 89 779 979040487 758 421 999999606281273934 651 909 999999588577284583 239 421 999999499670700761 95 172 999999103161879479 266 164 653343512 672 391 441275770 465 286 999999904458501756 656 331 885999402 196 541 546995343 873 494 999999005558680018 41 783 947929132 578 318 191171039 157 607 256948324 892 830 836807568 37 540 107265258 534 844 344477523 242 733 323791011 64 534 999999056842337037 811 856 24118234 926 398 555225699 907 946 999999737285791088 336 540 999999738970195351 200 924 213846811 627 447 740774698 641 881 999999232448365721 648 156 999999539935331719 59 805 999999741519205822 690 844 376035193 816 500 284765359 413 15 721926441 665 701 999999489293314363 474 16 999999730662974163 25 884 999999843525607106 586 646 187572092 216 152 51850424 609 411 999999991015847622 11 347 999999211642096931 466 150 999999270151203057 63 309 424135482 228 910 241846246 724 813 999999744794757994 834 243 999999715247646900 886 177 999999809757080653 735 690 999999055482435505 131 160 137564702 344 842 999999438217415146 165 269 999999269735380786 319 910 677145794 897 89 999999677180290961 223 392 329861140 253 244 999999843219601004 212 682 470472745 632 516 999999940876544523 285 624 137767084 725 917 999999039402773812 504 573 999999582258963819 836 442 170783176 409 254 171732513 843 440 999999646562979263 679 669 172872367 687 724 38600979 753 245 370676212 332 95 352174020 200 635 999999100662880389 331 565 314498108 394 614 673372475 421 231 999999701810539495 711 750 999999009327916505 515 931 999999567116679488 344 567 663446462 411 41 674003409 820 938 557598251 378 249 435104629 794 176 999999045008598928 684 252 999999302614671463 351 102 40120022 147 258 312660013 723 679 999999388381141779 741 709 430822242 587 666 82389314 267 777 70335007 222 110 999999381227551927 750 927 725638839 254 504 999999630506604284 651 133 395195813 97 915 485788957 512 414 310843099 347 449 911750428 895 490 216827754 96 152 999999461779965368 683 440 999999902056333808 368 266 999999144927239331 874 741 999999619334848255 70 172 999999841890678803 718 801 103708675 265 220 977202230 283 825 999999621302431569 281 499 999999481141007605 348 514 428071168 57 295 772041068 9 245 596224274 710 602 999999065720051821 358 588 999999844039147467 5 448 90926495 149 446 999999008161191065 154 287 999999229004805413 460 635 999999053938317894 111 550 999999697385149797 221 143 999999663443154856 864 252 999999471801581930 199 581 680094833 675 345 878104957 47 215 837977906 575 115 349924129 521 708 31325858 33 390 57466188 132 754 582409681 473 747 999999299579486675 499 812 313326777 612 632 999999662498984752 936 324 581579444 478 114 521357180 221 143 999999283466141754 883 502 999999476940061399 402 543 914314349 624 218 999999723720622396 211 42 165984181 127 381 999999834596712082 384 28 724018180 17 186 889624032 701 738 716386998 58 849 999999161700132650 107 44 438628193 524 918 890266562 560 145 591752095 791 802 999999649763122240 702 779 999999836967413207 15 856 999999246281614789 475 905 419039232 909 703 999999255087741176 65 311 999999950666750207 549 372 999999491754628271 506 521 999999443836060022 437 328 999999676877626286 213 788 999999568268488284 568 367 999999246688571352 839 893 999999511041854090 394 568 999999886772069387 199 707 271711621 232 411 999999183618823310 219 856 550348193 187 627 326524192 252 646 399857966 569 34 461515814 89 617 784131611 438 482 439585866 43 328 564174195 809 751 303227702 622 573 999999746443259368 855 608 999999244740344880 2 166 999999141088866539 485 611 629062295 260 603 221328857 67 35 808026895 520 912 430370364 512 907 999999117151259075 628 95 501334375 637 67 110610617 91 577 468136976 711 189 778243785 791 888 999999234142052873 115 297 181243696 866 843 999999751991166659 909 153 999999134948997322 99 201 252496030 849 308 347196354 262 531 999999820411102407 705 163 504684873 37 112 999999563360891101 799 209 98299116 597 717 999999535987214071 169 942 482575335 930 191 999999564220978942 266 661 508478860 537 853 737965152 496 97 999999836858293000 209 553 454103651 680 246 222607190 169 401 999999626905517204 640 147 569829704 224 754 389895315 147 76 915913862 46 359 694980757 268 826 999999927360830666 176 128 999999933927326616 10 438 803308245 346 137 999999265449010013 46 88 617870533 198 539 228013604 418 910 999999389701529173 290 530 540075057 761 626 999999650305676686 857 335 999999150877625310 929 682 314090403 831 907 658068571 395 298 162606034 701 829 974352460 893 430 999999520722578842 942 859 376060960 698 654 711940235 813 294 999999564753232600 354 219 805055055 339 143 999999413992336872 356 895 999999544120805862 406 711 999999259149981794 899 920 999999350886380088 749 64 694953938 540 318 999999397400110577 814 202 918272469 876 430 999999228054488345 697 69 999999404391876673 74 165 917412911 220 829 203362384 95 556 999999577052048590 466 390 999999841028993231 879 736 999999011230385075 848 578 403817861 221 226 829898271 656 738 999999590266810292 25 35 405632426 914 570 999999922515499116 563 172 999999668850459145 901 45 999999702240453144 913 24 35325323 533 883 999999861970490307 750 745 999999503711067203 32 349 999999886527673420 26 760 927376396 845 21 349166953 748 868 999999619239554777 728 93 507201563 72 498 966779340 591 86 999999054806553425 685 430 387123785 860 635 999999545245231351 587 97 276474635 489 862 999999216263550559 524 369 828439426 867 227 673349900 885 889 999999091589758478 531 787 660685626 753 892 999999661157525647 27 103 453338701 31 721 999999729909169299 532 884 999999558190450894 901 633 546284440 605 930 755446830 933 941 999999267831778746 111 72 369859998 814 25 800327699 512 861 999999798429813906 607 937 954563591 141 512 68554655 646 245 692803251 190 300 531770503 260 284 999999583165133864 881 853 999999695719350343 834 297 190678010 567 268 999999702361640242 232 780 832880439 375 124 999999301334463899 368 46 999999273190483911 665 164 424685861 207 445 521779188 656 180 269600346 422 372 999999721021340152 906 886 999999094580906537 829 751 999999803605815451 144 354 298536256 946 459 918568539 882 787 999999665000997683 168 370 999999423450425958 361 382 999999951964462864 725 142 268397105 295 576 249145160 682 855 999999496259892291 14 339 29747916 458 686 999999476153829609 76 389 999999004603431100 255 730 999999856993499911 340 208 241283139 631 377 999999925978030135 409 26 999999901278042823 640 530 648325444 101 423 319537389 163 397 999999346610557117 373 339 999999886373415908 220 390 792269184 715 861 362771653 580 908 999999020908666984 9 115 633295491 400 692 698951100 696 97 337235731 425 195 596920807 909 134 835797956 601 693 296343530 113 539 999999005913047200 830 63 11148451 597 790 999999849842553146 546 489 80359135 545 32 999999474661981232 856 646 575275689 445 223 999999794938497547 268 399 147167135 405 76 559607035 366 437 995885970 413 580 740852564 582 206 667316217 603 830 999999059123672751 393 70 353182211 583 328 999999949572722311 845 558 999999579341197860 248 880 385670461 96 433 737008287 55 328 999999586586923222 498 246 315174089 455 414 999999890818384986 468 427 999999104335859407 215 343 999999297292205925 297 231 839204722 272 831 180019 707 434 999999204525098232 234 881 999999450226996845 571 335 407643139 939 352 97846319 185 866 783397530 719 594 999999662024515740 855 316 218742936 808 809 999999943770907054 447 831 999999272310617651 246 628 999999220807965586 889 687 999999824729738366 940 705 999999489484447683 8 285 928938515 184 300 999999095071088353 207 36 999999553081544217 395 85 999999621020258815 464 36 999999575207290328 824 210 473014393 930 452 749570119 849 506 999999778723560927 858 531 897894815 484 302 511905422 720 189 599674228 265 861 999999955925584584 186 329 999999749826973306 66 237 999999779199318663 772 789 999999585551688317 809 208 649203218 751 66 104481999 150 825 949519411 108 109 559714281 140 206 648912336 637 647 999999656372608903 87 435 999999702872459820 234 824 999999198844383695 136 742 710232539 144 390 999999482427659550 740 143 707553254 126 805 999999266110036673 925 330 999999649970256405 900 5 252451643 935 533 999999536857904171 627 225 999999024780842324 782 98 999999503515328298 501 762 668619841 167 630 999999880380049266 499 70 999999571173866798 118 835 999999976249664267 424 41 878422504 527 678 999999669158695020 766 350 256901492 399 615 684520261 786 464 999999982691749924 887 253 656155000 482 388 99672102 610 781 999999519598159832 309 647 999999900620147595 674 778 999999296542085805 296 367 999999537491291016 54 797 999999331167354124 8 173 999999694658906134 16 932 999999483864778588 281 108 999999258739166831 331 532 577443684 467 86 466143431 275 116 394296809 72 889 999999033832187569 537 413 999999912000627026 923 729 261082007 727 198 999999664972658276 687 820 999999956522604211 98 770 687841576 674 740 468420994 413 244 999999384858358772 396 294 999999880259925143 98 256 258826744 350 582 802694363 19 575 198723456 79 888 706185944 177 184 418872512 71 138 899505453 54 495 999999726759981593 123 831 999999723992113278 8 294 999999253553037301 618 523 999999842033086112 364 481 999999506013934093 565 178 999999834418160124 788 205 193250806 106 855 999999352967514837 91 184 999999180677134489 461 456 216662294 719 524 999999976271291254 185 217 999999207898022511 412 583 924297546 303 573 138306565 507 142 218577078 561 686 976062335 334 336 999999473695471560 72 344 999999024491638899 794 348 999999190186724938 699 500 145113905 838 184 336886975 762 85 885105145 189 181 999999806161519629 712 645 103468368 500 328 999999901460529582 613 854 793144724 318 190 999999045904961845 594 523 935473034 333 459 863095187 609 263 395005169 653 390 999999002647718250 425 215 785633123 494 121 999999578206230518 405 444 999999369787010633 389 663 999999983712716998 659 391 999999871296372243 240 747 999999242783208906 182 282 89069028 107 740 999999484514560964 42 421 999999064154674459 544 412 293311104 794 204 999999191667634325 13 181 941238358 573 372 548006342 939 376 999999527127088818 180 652 269440378 927 650 809849998 638 645 999999407416819903 640 745 733096491 244 837 999999584564138486 768 600 999999349462048730 761 54 999999164565087626 623 438 999999427002124953 681 729 999999832656850453 807 217 520459730 69 70 244390861 601 679 999999399440064868 751 449 299449987 742 719 999999930916439467 497 549 890135029 553 85 999999619788198568 495 608 999999485597540193 291 11 675060003 135 753 449846962 469 684 999999174119032527 560 709 376353341 783 74 790644886 918 449 895245483 639 427 759485442 567 356 999999114155380944 552 310 999999799051748525 65 535 999999092080734140 946 47 430354817 662 777 878133709 130 450 377052766 237 445 999999666321669165 554 216 999999371768390705 272 738 315902228 896 442 999999035671091662 137 9 999999068014995510 550 861 999999038848947879 928 897 999999443059085816 433 628 173949381 314 69 288221668 675 886 631991953 567 844 999999298102426249 580 505 284803508 255 376 999999091634269858 218 281 696423422 736 760 999999159460970347 414 398 836537983 865 114 999999595293641321 428 184 737735360 474 336 999999482982363119 579 242 818082365 123 870 999999341000174160 61 328 999999081685905699 397 194 623654128 453 708 999999799218427217 820 167 103747037 203 287 246980068 259 574 999999517319841644 754 875 705774536 386 945 615516306 579 500 967678565 292 153 999999399319079580 439 10 999999420326863432 23 299 999999250920794079 37 220 999999060160971967 851 868 999999015222818221 490 855 999999652124743440 582 590 498760040 145 246 621396322 44 118 630638930 459 182 999999692170967982 628 401 154922573 350 786 999999426690502338 1 587 317422695 93 947 999999990734944751 557 558 908320118 292 136 773707382 373 309 219588180 51 828 999999226252394985 942 796 526577313 878 423 999999142826517174 268 640 221011204 481 437 234809937 791 772 999999955377619754 943 402 773006885 143 487 999999514730394215 764 515 860160715 709 599 365132839 1 603 999999757637967643 456 287 37132534 453 595 543798002 303 705 999999226906045482 274 104 999999718252015227 437 501 999999718871466134 416 390 82236933 499 197 430826575 363 497 999999012942443229 939 877 352543319 305 528 999999073019588263 770 17 851100454 455 473 162754092 85 27 252225350 117 721 999999996791230235 276 35 999999842595458384 368 314 572562331 898 193 363632500 744 144 999999020336556103 6 59 999999472785813498 36 390 999999007527670023 593 859 999999453335439197 923 738 999999360619530699 244 453 853793329 821 867 999999126088401360 695 430 652872529 536 204 999999612981896107 85 500 169620169 67 940 1844185 832 903 884644209 790 89 607041879 25 113 999999864113921900 285 188 543247974 228 627 57553953 516 856 638665904 284 322 999999483997734993 842 436 999999177805459215 31 369 999999274767317577 509 214 999999308410602953 212 586 999999204452227326 492 473 487733739 301 645 999999852471066508 878 392 606724818 279 837 999999797783000045 378 542 999999294497287539 538 758 999999023002267483 524 645 999999454961979140 166 530 603434118 671 157 636771433 155 130 530893944 641 57 999999912521575080 467 295 999999512875969638 847 586 999999791598450988 464 450 720041844 521 118 999999168573711934 125 847 999999332703718768 652 204 595264017 159 582 999999808369722107 234 755 985053320 117 456 698436621 676 785 953326823 327 903 496070159 349 478 999999348965811427 94 945 999999649945004953 585 184 999999790223335078 872 602 122335543 284 509 224008907 18 661 651009652 33 505 656550066 506 196 999999323008589875 546 772 181915395 288 844 514512914 35 536 18406705 667 817 362995980 559 605 71280899 53 422 999999148825073396 655 566 509360713 52 135 176285338 722 570 128658217 379 315 670340005 896 432 999999602846931202 81 138 338221147 563 303 155153186 863 410 999999420943498592 162 462 280114074 694 60 999999180076731952 830 723 197177842 783 861 693159405 402 17 669721195 715 358 445567953 786 625 999999075094416928 42 39 577254251 396 24 999999932745158187 252 507 905135250 38 792 244138481 230 192 999999735258075704 862 105 266096531 396 760 620747637 604 884 999999325433745065 410 594 273712345 277 809 941490391 283 745 999999018272618166 413 559 999999310154578460 540 906 999999242531076021 555 740 995570485 857 343 999999175665656248 757 367 999999496615057197 392 574 999999028393354843 332 119 327136345 598 758 999999317767202252 400 454 999999832798602084 811 248 193588727 415 830 320325765 755 688 424072723 166 789 999999022869986512 225 840 530357689 253 901 152858983 211 422 999999251769936321 390 72 637309374 753 98 713699942 505 490 541117995 688 827 441601777 546 420 419235025 601 266 999999129578701778 876 728 999999079136033360 889 89 999999179815164512 274 114 999999895475905554 312 155 122637535 288 255 668516546 314 34 999999755482570363 612 379 999999116861238299 118 409 167267715 492 432 662119071 122 130 999999859373531798 217 835 560619607 749 174 189026633 742 748 39852890 368 903 999999271310038872 779 606 999999577810757551 573 490 999999835525010333 833 207 999999614828328414 267 224 224650493 146 812 863317413 369 586 999999770315741085 151 63 546762230 886 726 999999099687036389 273 487 74095771 605 287 999999279367454534 473 291 785158780 589 790 746167030 156 771 685022978 181 746 999999653150426214 333 188 519540239 545 523 999999961851060003 604 51 999999139654192729 785 471 999999177080137781 394 423 999999705233541786 840 440 999999813176225073 407 744 999999416078641528 585 207 222004391 14 850 999999127948296728 174 86 238656427 815 698 75967711 812 373 625300695 351 50 617481274 491 506 624751236 251 366 406143750 640 823 999999392350319675 163 527 541889751 349 832 999999905022058558 873 107 928639724 723 119 402180048 445 489 999999305990818098 321 505 562366383 819 855 999999245851519071 472 378 503431818 464 483 256311353 664 899 999999749648538011 51 726 925563008 385 474 999999695161554318 712 770 999999342640544451 672 526 298084925 618 532 323228390 213 693 864411740 871 153 698444671 26 706 999999418693288528 108 659 999999037991051751 719 384 999999818000931162 837 764 544821124 474 81 999999357680175210 496 538 999999658315712885 276 176 999999748324729569 349 837 999999522196164353 765 396 541043068 522 130 999999814474329341 891 207 907896670 427 832 263232656 621 765 999999222401128847 841 347 999999533171087555 152 385 999999613922004166 375 119 999999143520804519 809 48 23525141 654 547 607787936 178 759 608469936 570 256 438735061 366 140 824069983 148 372 408445970 33 620 843177395 231 83 999999538551719313 104 281 999999409993248654 907 751 773677806 368 458 218836758 342 307 999999174909219071 367 57 999999776955407810 102 637 959881872 729 66 885951465 808 647 90936290 71 598 999999781725528484 782 696 23160247 300 5 999999556269854282 749 641 83423222 22 379 999999397138003396 788 389 999999078671701630 806 746 999999912915498503 116 148 999999253396551979 319 227 975044304 1 125 344567142 199 121 497438622 485 154 999999723365129301 293 140 999999345745040007 803 294 770331045 403 417 974619264 395 482 999999149766786506 525 57 999999904226589884 236 542 930487292 689 154 999999665354801607 273 52 700156099 251 688 999999986379484383 372 804 999999030825547396 578 678 999999393749699897 415 256 999999368878363166 653 518 999999628406251641 38 352 925046415 278 823 492780326 51 184 1500163 48 474 294253188 206 515 999999848167554620 737 137 999999504466524279 780 773 210113697 583 789 999999036233183841 583 277 247656390 402 539 999999924792760294 558 283 999999338117539733 861 494 150512755 69 741 216050928 631 77 635590807 853 367 999999114255818910 23 874 999999350719969566 463 846 999999232887204444 406 359 169793056 173 867 999999950361088796 878 367 999999953409821535 713 392 999999459020742917 831 233 999999719228728670 145 606 871977836 769 318 999999479614890471 182 785 999999389819338988 866 734 999999680182237947 309 78 683666710 498 811 316876508 699 98 999999233274693462 554 262 999999645661489220 280 408 57104893 23 415 999999466780143999 548 81 999999732493828326 679 497 999999898368157065 886 53 564574115 639 399 999999415474826832 324 688 826026971 691 30 284505938 532 130 390338341 213 76 476343303 798 621 968924026 353 118 881450257 854 657 573652117 255 785 999999414242916264 907 718 999999191096662134 240 884 175319604 40 808 999999803015995190 567 325 999999910918272996 377 827 608520198 537 649 999999217239634353 155 43 450607363 671 773 265036983 695 459 119752785 248 418 440178378 906 381 351776856 294 574 999999505035420952 18 605 220038222 346 498 394826841 197 191 430952885 354 774 999999860073008391 688 414 999999306462339017 545 685 128411405 275 1 999999407810093658 687 559 701601090 858 789 783924231 109 177 999999072871396292 737 192 999999152608606253 412 799 999999169048899766 863 583 941613004 840 271 999999884864616331 286 143 690603220 270 673 383496937 575 111 999999838456769534 440 422 999999745013505429 868 693 352828562 15 287 999999948082460225 348 30 869555604 187 322 999999528570771256 291 507 236807048 892 554 999999396051154424 822 340 657157380 705 108 310292491 266 209 999999034562482956 47 613 999999219890531946 866 312 999999236984723492 470 548 999999220342917377 306 882 690239908 150 687 766583975 844 512 999999705141468308 20 460 999999384177490485 393 59 999999759791025822 611 774 999999691946609926 157 274 711891307 46 113 792298043 375 315 901932556 885 339 999999316928126698 430 317 135864111 534 672 999999084658321172 369 443 999999541137956355 96 2 999999807586952462 370 872 529061412 875 782 803609430 673 108 999999979367760821 177 643 884192699 164 376 999999462839331958 440 65 90621043 638 318 999999598018309425 9 47 999999625190575561 331 541 73108876 499 576 679571729 361 362 687036176 898 308 999999140701924747 365 760 999999772870329999 428 446 999999657201244368 227 138 864603368 589 685 999999627844502772 668 165 999999239886327530 19 630 111619519 87 574 987614904 629 255 237199182 161 180 375541537 504 30 644044278 352 339 999999649896322230 775 57 999999488653678822 212 309 218727643 458 882 272493949 625 349 999999299049284149 771 397 456112121 624 315 999999085281358151 212 464 999999540984598130 152 518 667583115 309 167 410527193 333 378 483480075 454 443 999999091550121901 319 312 656552277 131 37 999999652955470373 233 580 999999875323366193 873 60 17809969 364 158 999999767795878179 850 865 999999232502967998 502 723 562610045 186 583 760942689 681 136 999999589279000969 706 73 999999418901107726 475 107 850311074 516 897 999999142899822675 376 893 624171687 633 59 999999709520661579 634 508 375169577 536 53 999999856609322264 281 816 178715899 797 408 248339922 793 150 999999238168868909 625 300 610639286 568 780 24354416 588 113 941510180 376 265 999999616217546631 363 782 788817628 667 881 999999413897093063 148 477 999999156612222588 339 141 999999193845156601 875 538 876983923 875 409 999999714927960211 229 618 999999245224706651 472 533 119025321 186 143 287025719 849 287 999999195093165957 537 576 356975701 702 842 689379797 689 403 999999788524105407 124 808 539673629 865 860 991725699 435 851 520784784 433 274 999999199966675281 54 47 913240681 784 694 385694803 772 816 261070994 519 587 566517027 436 899 333790584 660 871 999999895227366722 665 440 785837266 391 479 508268449 612 752 999999389558075512 725 838 237721211 258 36 991251894 495 561 67989538 326 139 999999987971127221 646 458 999999585945085728 30 816 999999513408126550 464 331 237391969 167 339 984149139 365 747 999999176292273240 583 427 999999571125682380 515 770 999999619550824922 329 503 999999108443106635 760 863 999999995513359984 792 108 999999517500613732 22 559 999999085451965037 703 66 904519525 195 428 358241453 682 108 394592919 470 483 999999208816715874 729 345 839620141 536 384 706524944 93 789 999999862155401475 889 521 918135020 547 907 959167755 442 158 999999735091822343 608 737 939553657 444 872 158784090 774 84 999999564249418403 193 823 708492398 580 128 999999120705772193 485 601 999999132421964511 99 755 684887218 242 624 999999305126265440 523 266 999999037659159693 737 437 815696067 7 403 561128970 13 121 999999205434358453 703 283 999999396753961056 14 107 472275475 100 83 394180222 767 11 387099059 880 656 318069909 582 75 755715587 444 265 999999703767018068 595 215 999999661941574289 272 496 266255532 116 184 492019764 427 382 910536199 85 565 999999075154484657 261 671 420921068 759 323 801259001 700 723 999999340255040300 270 236 240086463 145 817 268011193 894 777 999999603327357551 626 353 999999333927244556 773 333 211910577 843 344 7401214 144 186 999999021383567829 833 657 999999970862784379 772 105 999999429701948297 397 610 174972710 8 835 684401840 327 902 999999971903100865 863 331 999999273413481902 652 279 178392395 77 753 598672672 729 301 999999557393992181 763 165 999999161212480329 603 409 999999286516493365 280 170 319260153 623 777 354773323 37 236 999999992197004088 175 494 181099881 64 507 999999721982530949 457 308 999999195247296680 160 375 999999171221242824 127 776 999999183135385226 879 16 401935026 724 684 999999083041212689 164 187 637073624 488 686 999999276335406222 849 346 932167815 54 79 999999671644164207 371 845 719564633 433 610 999999732834521645 297 763 508137019 834 5 999999537332261082 375 108 999999387721340717 579 386 732321738 51 441 999999783812067264 169 289 285399918 882 195 999999429251541593 881 382 905154849 221 357 999999279298578264 785 869 898753031 670 329 55963178 618 515 999999385325576090 318 55 999999445703834579 320 410 999999369332956824 402 901 633370324 127 514 999999738174590335 27 543 86988829 322 534 999999980478384939 302 423 999999792609424743 448 775 855997270 352 57 900802187 845 312 999999852321599429 572 879 672433900 780 847 999999727351541864 459 419 999999362639392330 846 668 999999571482655721 139 465 999999746014098416 541 670 999999552086420420 846 865 999999371681378426 250 881 828922802 836 258 999999997971011086 708 114 32347207 519 895 999999634595808505 716 696 218756514 752 169 999999339461466126 349 372 636246659 414 505 489748475 632 837 116580251 166 865 999999989600517930 679 702 306838151 738 603 999999930300332330 158 597 869555026 738 719 763110969 141 40 541501730 376 594 524781357 596 644 999999688544233656 21 895 999999571967954200 110 254 925699720 208 380 766009990 453 681 356229419 837 64 999999145790435427 461 759 999999070719824274 761 632 999999455654947545 346 155 175066389 366 440 999999540035637194 831 21 999999387462698754 358 761 285039057 264 647 999999349053863142 147 798 709779338 35 773 999999018961948580 197 671 999999926044254383 627 858 285626453 731 340 798359148 615 296 338402648 429 146 55333519 75 804 999999856829335005 268 256 592984520 270 248 230131155 488 621 614749770 727 580 534170979 419 590 999999009914855967 712 236 518064769 386 813 591880068 362 125 999999017408045208 731 478 783604183 830 750 78183178 397 71 999999788684344920 80 29 508610391 245 264 130748308 315 108 556678941 530 672 212328252 879 160 999999724867164764 437 542 74117286 246 647 999999085565756720 372 607 999999276795603621 20 580 999999107426724370 633 603 999999273894294417 401 140 999999471755200648 630 838 530932356 437 192 999999028223699866 838 293 418560009 558 425 868228911 90 143 999999947557634718 477 288 999999984221907353 359 686 677137782 799 680 599702907 102 166 192411374 805 311 620874241 357 459 999999416885358549 801 421 961307746 642 832 281545395 505 654 999999303015202992 414 626 128836615 87 245 251895350 497 730 409255761 678 449 999999685415297888 906 369 600335690 190 301 862271610 792 245 999999917028663677 538 760 892151247 907 510 64959818 400 101 189358935 671 720 786554439 539 140 244174706 467 504 999999508218725629 350 613 999999212779591938 177 516 137221044 810 466 999999024773637686 155 471 999999072081724749 662 460 180379691 617 706 999999331957814041 159 401 999999886129222272 445 796 222549250 868 425 642850370 118 622 999999085552950303 500 348 999999606435671723 896 716 797798538 829 862 644190422 370 187 999999288420379032 168 821 999999719557840442 32 432 878208209 8 601 211262679 888 103 920845246 584 365 834400098 213 797 777471797 191 709 999999527431024108 105 852 999999568642119005 294 565 711936656 643 421 999999874511385590 89 511 999999233912041994 200 323 468534412 148 352 999999582959989978 306 732 830573806 735 591 999999195852341693 901 561 999999188438426906 260 221 999999942990386296 69 372 999999604588629367 262 561 658138420 285 733 417097091 864 724 806235046 179 855 246067366 318 263 999999532277567209 374 307 999999055809851763 710 732 351591124 737 83 532645564 674 492 999999028928978121 683 128 64720612 748 684 581449044 543 704 64358512 356 121 999999647183580597 854 278 570314304 693 74 999999277540767017 755 594 999999162966431409 166 525 656382938 421 484 106179059 208 840 999999482002396312 688 460 950447624 237 650 864704370 641 542 999999903630099984 512 297 999999260380112206 621 720 85791953 645 246 999999495010200320 219 85 654886777 257 318 999999723061908610 470 242 999999727224461469 548 529 999999394671330277 436 98 999999139606394658 541 860 184784224 855 247 209999408 167 362 891112061 760 307 999999188895629465 901 57 50994990 298 560 999999822767922058 655 281 365751101 653 661 999999989287578996 482 274 933954624 690 53 557872000 766 305 641492638 860 631 999999489900877187 614 325 999999406572593078 347 793 999999264136929192 262 743 345365466 762 265 798353731 148 185 453374631 28 756 999999869471826224 745 267 485064211 733 175 530640347 851 335 999999972293176202 103 372 407659591 217 333 999999745615147551 870 402 999999941341430978 350 687 999999795395828782 115 706 999999111484654743 562 616 325526669 870 511 999999826114306176 207 295 33641586 650 49 932991779 128 240 999999119905404173 439 129 999999197116225129 726 624 296663994 105 593 999999729934585428 198 521 651135184 341 555 999999652661343489 248 765 999999845352121148 843 513 999999216713635432 178 530 999999991289423244 45 606 626451012 310 605 180400929 904 502 999999501476163912 884 774 322506550 400 449 927084296 362 562 999999777817385452 291 499 999999459066743735 841 590 701352913 714 380 999999753828152478 895 426 999999765165673615 757 761 999999111401836425 296 643 999999076307196216 403 404 731595772 390 903 851102739 756 289 999999162241526785 236 633 999999179168212141 620 192 459245475 285 151 165112933 633 322 797779213 216 234 999999754197286769 588 678 999999663047211436 134 421 999999442472857676 204 6 285902659 58 302 222386132 17 843 340658277 729 410 999999696534511518 297 503 170505756 52 39 464193750 891 290 142667941 747 718 999999308628043979 875 886 999999687301178534 303 163 999999099295629486 111 324 556592793 34 647 851707613 52 759 156106565 770 767 960493131 654 789 999999401217466001 854 538 999999688050201968 573 552 446497508 169 871 999999667537062753 718 252 999999425516442171 83 135 434059576 358 206 999999536960419022 645 620 72138953 148 566 44339423 738 829 799348868 69 416 640162347 193 828 999999310313130744 666 901 755508775 306 543 237738134 482 858 252135908 148 798 999999411917513055 800 259 133292824 816 774 604116300 597 577 569267313 1 816 999999400511487202 615 466 627018641 70 641 999999692757517214 721 562 999999211681120053 786 384 999999875962346789 265 339 589802844 127 82 999999931769874305 88 837 999999161132417412 657 520 999999392552163752 733 855 387561870 41 470 248251101 284 134 999999059588074058 893 881 999999041612858230 89 475 999999925023816327 458 839 999999947070175975 878 641 999999639943220261 767 404 999999885952809790 113 362 308754449 701 67 999999117870371339 882 175 999999120344244173 563 630 509889173 631 311 482381069 677 803 946437863 101 622 999999812300368607 503 371 999999708948461796 525 380 22604879 647 240 999999548365775466 107 376 470322241 310 627 999999124169037484 778 164 603547397 503 208 999999345412953428 469 297 4041078 568 892 243159043 514 120 999999573115165025 214 673 231775538 424 889 999999768020114529 447 808 330781337 233 583 999999017867632338 242 881 999999228828267759 736 599 311688426 12 478 940153847 826 319 58927146 757 724 999999923355397368 251 313 999999782088862911 564 338 999999559276672061 800 87 999999802466205097 67 230 999999426570866960 715 823 999999499094655772 755 221 604411248 534 590 399194375 765 423 999999471774949598 381 560 721376194 890 347 999999471110309432 869 206 999999977602812925 429 746 69382693 814 9 438900001 743 512 354742214 263 308 646214433 506 494 201053384 359 435 454772331 8 697 999999102063183937 295 298 999999382489891211 499 317 756633946 213 349 999999848814752926 840 111 999999616228983141 667 601 709187969 394 611 999999701068342462 570 884 999999040060353363 460 749 999999305673382887 68 108 999999526723208779 352 652 999999449524439917 164 712 999999424274683996 696 714 999999132679980285 132 429 442253173 448 773 999999957623489781 673 55 443834555 359 740 542403843 3 348 999999419974117899 802 588 598460863 59 157 999999929735486283 256 538 406456765 390 389 475673359 552 238 201727590 609 868 274758254 268 235 999999190388816914 618 329 925627238 72 403 244711718 662 14 699853623 509 254 999999210946063558 478 684 606321574 609 183 999999705184234286 596 683 861146794 335 502 999999988997003233 219 614 527900708 31 644 133132632 133 854 999999449546434448 847 112 999999463496539738 523 826 999999083848351800 700 69 999999057847943296 678 528 999999843928082487 513 846 999999283570433800 134 572 999999699784922472 419 95 999999994972656877 540 280 999999446148898483 900 207 416392736 31 94 76653687 407 587 477294213 389 267 776045472 60 234 999999560644763868 422 577 829259919 272 552 999999288889038354 516 854 42810982 37 193 999999430701979473 399 366 999999366322384567 712 205 999999757097832500 813 883 590354309 359 601 999999454157128434 181 748 999999494385651824 802 696 999999664851182084 771 476 999999417392845014 760 542 119673416 429 152 260240615 305 328 177003545 573 777 999999955711620920 246 887 999999766700853463 880 643 999999231555967768 111 150 999999924998526865 187 364 606351709 887 561 999999810849543872 529 125 999999922454008866 687 67 536848082 350 745 999999791350426078 892 594 258104670 533 213 999999405636577769 596 311 769313737 214 798 999999170349650801 785 465 999999686506165474 355 825 30063160 544 313 999999662099136254 594 717 999999465364696760 189 368 999999355062499930 17 553 283123318 534 456 999999213335737648 197 29 904834305 432 841 17856491 446 792 999999333827578478 760 114 706146169 520 547 999999626857482872 508 857 757230773 852 380 999999225104965617 752 331 999999178127293226 893 31 242883456 52 72 74483430 521 119 77366250 282 41 540191154 466 587 999999049381333936 180 709 999999264298118711 742 474 999999342101561402 249 154 999999973287932856 560 826 999999256219553743 595 790 248112256 23 897 845641690 787 57 662405793 159 81 858191190 129 118 999999613274613038 827 301 999999374048313421 154 54 985444392 308 224 345755176 86 144 999999741209038239 773 83 679343552 659 556 899439119 121 143 483332280 277 65 448141753 365 822 999999136711421858 772 379 613790235 240 61 999999273901660492 730 717 373802012 832 742 999999925354148978 411 895 999999864386821000 618 361 272962069 153 720 999999956289357269 686 454 67638239 511 63 94673354 359 360 516854596 128 263 999999722703628766 687 494 120703929 269 194 499602890 877 641 999999224455035231 101 520 999999970552739114 732 583 999999727561058298 29 861 999999695189932565 881 128 999999150883845649 64 577 822764836 516 178 999999416101744201 114 740 999999323709406621 882 711 694116437 86 658 999999168553437710 43 423 999999329384814923 41 518 999999742529435466 257 174 999999286547615721 686 429 999999389701659414 311 231 758250007 106 572 999999579219107956 95 557 999999042901717941 229 325 999999104938993465 426 875 999999317134690854 411 785 637150529 872 163 999999506983560079 342 25 913198398 200 810 999999087338713938 267 738 999999504530817385 814 857 180186655 170 617 142017259 11 128 905735409 371 30 999999160868053708 139 114 521908348 623 97 418412709 318 227 999999575019630616 228 331 880248266 510 248 598418464 684 610 999999525579993480 852 181 999999858107131942 692 88 820175760 441 591 763787759 412 641 999999721049955258 188 645 346221589 172 601 184330131 704 685 938918843 700 43 999999733801164970 625 601 999999185568484786 516 406 853039642 130 759 895180042 108 141 999999736291903545 267 352 63697477 667 744 999999897785961366 301 12 999999434141787303 756 486 999999884074505472 271 866 571992298 835 248 999999024521157059 228 653 999999718731373783 576 36 854240122 569 776 999999720818648239 478 409 515315110 618 720 820888500 540 622 999999052923834841 835 594 999999046634395733 678 396 423532622 82 78 999999512735178714 852 233 791350293 624 570 999999460047424331 167 710 479066393 228 455 999999404164763276 587 808 999999296069163535 495 589 999999483590119663 123 684 693572406 47 94 551047602 805 129 999999778257655804 573 537 999999770159408651 786 465 999999587719745666 671 809 999999146026243542 74 31 999999445949846395 213 294 999999774971437302 509 760 165384574 821 129 252643592 349 567 29395466 704 534 999999560527720270 492 697 999999208764248684 566 574 543375570 271 621 619497767 58 777 565872576 417 435 999999763031229602 407 761 999999874413187283 259 728 627366646 24 865 999999578427300578 864 100 67142693 769 846 999999421223687756 404 525 661251642 395 837 999999549908987459 904 590 309022439 529 59 777421930 53 65 999999534636059976 794 823 999999440920154920 593 613 999999041014127494 399 542 999999609265267524 50 545 999999002703004859 817 836 759323617 676 279 999999854585452833 241 690 184860043 875 574 942836946 432 564 284650307 724 4 428612525 19 634 835514079 34 727 999999378822889020 77 499 999999876508409771 180 271 999999307013533173 46 128 791406190 139 14 999999519600500097 616 223 999999239911859467 801 516 999999413823862340 343 853 999999107332884557 434 868 243042862 173 512 999999219555382054 80 48 89416311 729 18 999999859321031380 894 881 999999499966442008 183 145 674625988 364 57 790410635 628 250 999999412470270576 850 423 999999986121088785 584 732 999999670010935835 487 673 999999634258928117 320 433 767712431 588 722 841739231 333 692 587386242 697 606 999999479530553202 109 315 768632930 170 373 762754611 494 339 999999639978427061 70 350 58407568 238 803 601662532 71 666 787825276 54 638 485412106 336 34 750581869 210 392 459488556 471 410 999999684212878761 440 190 49633332 709 826 999999573360686329 253 8 999999425311459994 114 86 314617778 640 818 164246058 440 492 999999714701011627 168 520 999999985602700092 820 440 661364202 870 166 218249126 446 823 481917392 658 311 999999098820136496 739 778 511220820 175 510 380440437 403 249 903462975 594 417 999999064679602513 699 154 991303651 824 828 999999545493762986 716 231 999999382413937257 698 903 808554378 661 819 889898633 85 519 353836736 711 590 399876855 342 399 999999136596635733 338 350 999999134239438584 298 491 824033473 796 901 999999854643965347 392 891 999999700443162966 868 234 358072395 510 453 999999283608724101 486 301 556071470 902 670 797750017 602 628 999999440518692589 344 11 581705150 275 109 999999967869188530 348 539 698672277 907 759 549482984 523 716 426939909 810 323 661182602 725 897 999999779818884229 644 57 999999024038893432 722 616 999999349208363529 527 572 299107450 434 15 87279847 311 409 583664773 21 525 653109374 258 574 851935400 469 195 641011484 384 220 639197693 697 596 855567881 822 66 999999190125418517 74 294 14262977 581 165 999999825648744952 591 381 999999061101047613 360 856 921661846 12 549 764775704 604 238 999999839243661178 879 684 379523907 337 669 713927518 550 791 503188848 409 881 999999085961879791 702 286 255142687 62 265 852863321 144 215 999999195576877720 467 224 999999479579715501 257 577 280233518 222 520 999999058126551924 561 903 96139493 781 774 999999311073758635 862 271 999999189247587162 526 350 392592744 42 720 179290294 579 562 529440288 801 254 999999077560625689 169 348 999999162141379387 214 628 950413366 606 520 999999249697635434 856 612 531821289 243 163 999999702221216227 842 663 999999121500335062 888 84 17142565 828 621 999999286268689642 302 681 999999295471410581 159 395 999999423060941457 147 220 999999864897453206 726 58 999999802699933397 259 903 176356493 265 411 498065319 464 560 311002764 183 529 999999327051391509 802 315 443028052 859 17 920636276 490 603 440896761 461 671 861020029 567 211 964985942 378 725 999999775761882885 201 599 842556618 610 570 538481676 576 389 999999229825502989 327 577 241823678 493 481 774383844 788 335 999999776275394660 441 67 999999708055069358 650 717 999999629705690579 717 221 811326441 588 743 999999821511026257 718 590 999999974001693016 675 717 11391904 207 774 999999455403112198 446 130 999999437835946976 330 782 488107580 135 565 999999639270750618 757 283 999999485109891262 756 73 217751143 856 174 999999372537330523 142 513 666065764 88 52 762710907 24 703 464929404 468 729 999999291845189329 334 576 999999865121415137 858 633 406573514 36 473 999999655224891595 528 426 999999159389459009 471 841 300294518 617 230 999999981840917303 5 601 999999852513632640 441 823 755341197 84 905 999999983385987403 26 105 999999896742251678 416 525 999999096547893403 749 151 999999396933544292 195 217 999999725930731139 631 85 835874296 62 591 984201646 729 217 999999773121889876 396 905 999999914524992342 319 136 999999347416367631 759 350 999999823550434606 807 852 911271277 490 852 88376813 106 170 514810623 121 203 999999214104757795 388 280 999999063631727847 490 160 999999429341382577 795 565 999999392108574031 354 693 999999078932425311 78 863 64248430 176 878 907206241 788 536 311025314 145 893 999999885196223033 682 149 999999124996470369 560 552 703647894 63 223 5332401 88 492 377175921 609 182 999999135467720088 797 804 999999906235507910 250 236 999999920963025960 649 841 999999919416796636 362 768 177714022 241 696 999999373198179056 35 1 999999009067409435 831 221 999999121474698969 285 813 160567861 612 154 548944937 722 295 999999655317573544 369 328 999999847054463455 86 683 999999439447007078 221 680 426217802 466 310 999999873186204343 419 232 999999887234060520 819 341 999999363531716552 832 681 999999352980815080 235 249 299691429 853 172 634039487 38 601 323459463 69 658 663734717 717 236 999999875131918503 595 707 220022702 254 18 999999071200234741 297 368 703275738 887 615 999999471245202067 296 319 94836299 481 66 566911888 443 704 574734726 889 523 999999037719915461 860 38 17305811 857 9 999999979145293282 378 590 847423639 863 432 999279870 180 136 966970437 6 210 620068936 96 857 999999184399271977 92 889 963149491 699 696 999999197044356148 671 729 999999935521874759 530 398 999999958459995002 626 196 420131095 225 42 661493979 132 16 999999125214818627 739 690 999999745927534886 796 129 999999492852543990 520 743 590631768 524 448 336346688 792 287 931552846 237 902 999999966224756300 823 816 877096701 394 329 999999546658676039 57 512 785051875 605 313 999999900200728522 581 520 999999866735105708 95 241 999999465097168057 287 720 999999552986362325 39 598 999999479464594103 13 9 488752868 14 800 280636918 284 548 999999312579238790 279 687 968344087 749 212 47128513 140 286 999999281860759297 669 463 999999592008851646 845 577 999999038659119361 432 592 285749384 781 810 265559196 55 255 360067547 549 465 622348154 654 604 999999693554859046 92 589 772534671 669 615 999999523307191289 65 340 604353906 252 687 999999138319783938 409 681 999999010760930190 336 325 747367878 408 760 890709224 651 182 999999841436782571 33 37 999999318920660203 163 743 981392371 231 418 999999397015536546 822 256 999999362394651453 418 397 679281610 38 81 964618851 10 162 563965371 639 103 999999305331231654 105 622 760055239 888 688 359167842 238 347 432485579 854 350 999999141839696772 581 549 278979004 578 685 999999437325968755 777 356 999999282705702872 389 905 418016196 25 404 25063163 86 540 999999663600640404 477 872 999999646387019412 528 904 999999295001937820 645 244 501373130 750 873 999999032016740931 216 235 908750956 637 632 791537519 559 590 999999299419249087 30 559 999999259215774103 282 24 999999123745357856 752 78 955470499 576 453 541233996 73 527 999999057411043643 605 140 999999842367743712 404 183 824481471 165 590 999999693813388100 146 657 169660826 412 277 269337407 353 855 14605342 872 223 999999420628229755 765 764 829037960 625 657 999999465830185759 137 563 741059672 785 321 61112373 424 63 999999939227791542 131 820 850176240 461 563 973289629 642 689 917942858 696 87 999999880343898962 84 445 153722622 905 821 999999073607999521 155 518 779593221 689 731 611143365 536 417 69299395 512 764 999999926610321647 110 655 109468474 452 447 96857206 305 764 999999184948323118 656 619 140713225 793 467 309436965 263 733 197509574 857 385 43331461 455 838 999999272417050684 194 407 999999725546328725 426 754 999999754428625060 563 855 412421761 836 303 168396030 604 869 536510438 228 138 999999906250274036 61 6 421631194 244 315 999999775026888534 623 187 818170435 676 309 765852568 734 251 858115565 531 75 999999412517113566 479 188 999999001876516790 211 190 999999682724413007 215 615 824640952 848 820 999999671161741000 5 597 185052935 838 57 999999753242643053 361 759 999999093020903709 734 499 999999608457690313 791 450 999999613338059184 29 253 427829030 680 89 999999220702475227 850 794 999999327810686611 825 320 621814356 162 352 999999352595435147 242 580 376510830 84 539 81771978 674 337 401709867 846 555 999999169288944096 622 62 433772429 462 218 850307400 119 172 597400608 289 207 999999447678458580 4 181 999999943969077798 417 696 999999999113646003 172 114 607788079 642 206 852246543 569 786 880263574 380 522 999999388923808591 901 768 999999086964842184 272 701 999999452871795467 591 275 218452264 724 95 192092027 770 14 999999967688201887 16 82 966659036 505 290 999999618659251002 366 358 999999324746451820 113 1 999999710252797823 743 241 55905832 619 356 474375590 218 66 999999727224731019 307 777 83585298 592 828 770559231 465 502 202661062 636 883 999999182463656750 196 716 983955583 584 832 999999764743617736 126 777 999999674390514328 856 525 991131193 600 549 999999598894079414 624 470 999999373855813722 545 676 999999482257333436 149 566 999999031893327111 334 670 999999920282610763 61 125 999999803005549332 112 592 854317868 410 778 999999883896246219 374 744 581252825 723 95 999999286857061282 512 718 999999048160327756 311 18 272634335 805 722 626529844 81 200 218332570 533 740 999999584564053595 189 369 280875892 295 460 999999746414813131 116 209 999999083963547335 648 638 117599697 560 516 564413443 112 421 948712114 420 572 999999638813122276 163 384 999999514654265247 308 93 999999220425362057 665 329 999999764004920276 44 136 999999092334011885 733 647 334138495 91 252 999999797437873944 836 2 845809189 114 284 391406727 571 279 999999295252391670 786 617 70940381 476 644 999999004234894413 547 242 999999829170223422 409 227 913130852 200 507 61141258 331 753 999999283947235766 32 242 999999543293454302 535 377 999999409754949402 590 136 530069581 770 62 247301068 785 101 999999333776967717 328 884 524039955 197 426 999999349220162410 69 346 999999127090706791 838 723 495436317 383 377 312255784 750 536 999999471590863732 596 795 999999434062786772 259 70 553003882 581 605 999999965801609883 367 376 999999372230610487 673 582 999999334318399664 553 870 999999238482393573 654 375 572042576 425 644 999999839093591480 738 378 705911153 868 597 999999577038958782 780 297 85347390 692 312 999999034755932276 297 613 999999083782481109 544 772 999999019026470773 230 656 999999378848640453 463 580 542501952 881 866 999999125912684181 16 53 999999414507203171 639 830 999999627272045267 184 316 999999862859832512 608 90 268623453 391 15 894047458 535 562 535413800 131 33 17889628 145 544 999999541219603283 467 769 999999625856147376 792 672 999999395523597773 720 399 490535795 355 365 999999135093032058 705 431 433957035 18 855 210467645 308 774 285521628 123 871 999999065104180620 161 6 999999302472723649 203 839 999999364199957579 851 628 617081219 355 339 550738427 200 108 999999023698928261 691 613 999999456279878025 399 786 132458551 883 499 171642020 513 819 948497183 22 565 198472234 291 318 999999870548011706 79 352 598997373 485 27 999999942414761412 884 517 999999428781027131 601 559 147333865 71 209 739516564 206 241 136742324 554 461 999999123544003513 494 515 999999797568665575 72 113 797922456 210 317 872412664 140 429 873734568 215 775 999999144322060181 674 108 999999480568999370 469 339 992183673 627 619 999999733050937989 92 748 893643482 815 152 999999892845995369 280 859 470554765 292 554 999999400134330388 463 626 999999037813657076 451 14 999999895405848899 735 43 315768298 582 73 774809513 42 728 728649812 323 206 45472960 202 350 105691822 653 384 202092859 116 75 999999857924261924 572 338 999999391074439680 533 418 999999770726565086 651 511 999999921067887992 176 528 999999777302312752 804 352 309063167 501 83 999999908977371291 744 718 823476937 456 749 999999684100858527 903 827 334913995 775 266 999999107971817350 489 820 999999993344024530 37 2 659504076 710 160 349965888 143 743 950581240 579 839 481833653 406 391 999999840683875309 487 342 813402985 339 65 999999199880106020 101 402 71658417 512 812 999999090974874257 587 619 999999603026943689 734 88 613744394 662 413 228354267 764 861 999999351957737143 465 741 120095398 556 641 737899321 685 174 176543372 849 257 999999078844147010 781 581 999999647718069692 438 542 999999240156493876 795 281 999142317 48 798 869220968 653 298 999999619995782548 345 837 232393603 863 337 701542186 621 673 999999780513406189 758 763 999999648471781933 178 877 821986625 679 724 111597229 453 389 374968877 784 879 999999956010767664 789 892 999999954561866707 740 542 999999098074719456 327 255 410987233 815 504 959797947 546 547 999999775075341188 514 901 999999310970373353 590 28 999999611820839235 534 757 999999770808353393 76 902 999999347745961804 117 160 337150077 66 238 583324428 641 533 999999575417353626 73 891 918488939 612 92 591229364 171 365 906015383 748 267 999999557935010980 408 82 999999239511191308 571 738 999999989570609607 740 872 999999712557832855 359 161 999999324464893331 239 153 999999543051002383 773 640 230112935 166 755 343710471 712 736 999999674674451031 93 561 243385995 542 826 999999274314452768 693 424 403248149 313 272 999999794117104706 715 418 999999298678540427 477 100 999999337343110870 766 532 999999087339712157 344 210 558305742 240 460 999999656183789990 599 532 214168309 234 419 999999375962841018 641 432 689360754 404 459 860654548 824 520 999999284879903191 232 869 999999611670142420 565 595 395644806 516 907 999999924413267762 670 165 999999968436699308 397 854 999999245412456577 29 740 734530899 329 193 999999291777725114 421 158 999999540567306865 647 319 999999096210944611 103 455 999999473704528776 663 704 999999123234626930 586 728 331742638 607 9 889213801 706 823 890188396 118 468 14150885 883 37 999999028282695747 226 861 999999764450581753 787 207 524133889 874 763 999999689438168269 793 526 999999855477994159 770 831 967067039 413 57 999999640445268362 96 835 999999060245161256 276 884 619200853 135 740 999999067622570542 555 146 999999040777888135 392 298 858051509 390 704 838300760 732 655 999999181187437048 194 347 999999415635027423 557 67 321892416 299 87 559592373 123 901 192748867 204 21 672939574 764 128 79207564 855 907 809000682 577 907 999999566693599406 777 484 280300791 480 265 986410231 339 171 719947455 646 687 437598299 508 728 999999208844929528 849 745 602643648 761 114 999999685365417759 769 805 332717590 516 283 999999619452571048 102 556 999999785697387401 87 409 999999528781191578 761 327 999999708131045830 802 691 54976772 3 574 999999162645971293 718 167 999999877876741358 150 271 756834958 382 645 999999756775762620 46 521 278379553 295 47 999999584901532220 77 694 906378729 100 622 966329164 643 102 999999428794980280 574 107 760199131 428 115 774933768 160 687 999999086682601978 425 823 497238198 387 854 999999955640097401 402 114 999999306078200669 330 406 999999365655690487 580 285 999999623214310059 563 114 999999856209206210 892 615 905226054 393 701 999999017007472105 691 400 6188211 583 300 894622275 407 170 999999900669780332 462 277 318897496 836 462 999999628092442459 885 725 36869372 45 86 999999663249484726 754 423 999999690590846606 316 796 999999274441182709 571 457 327976279 839 286 116330332 153 732 999999642689835408 883 157 55810137 637 869 999999225580670572 533 294 999999789423111670 2 147 999999745687650883 556 352 999999490581125374 183 436 518916997 650 813 632799070 444 599 999999568215552748 264 814 999999441541920444 897 303 999999763729575419 827 661 117499945 450 142 999999479305002096 869 891 999999649980352529 399 893 999999121649912369 146 751 161873771 406 429 999999077200161988 774 542 487834261 314 381 32874876 728 319 999999473822403188 741 514 999999838846337658 317 758 806111602 474 118 999999552899826980 634 568 815108840 888 752 999999668259949736 606 263 999999491111260620 232 696 205095192 189 720 999999619960816170 292 356 836954543 245 662 999999360754638427 518 37 999999307615499648 252 52 419529403 574 496 999999352560714938 370 625 886089163 322 390 999999939921747026 544 211 999999615700513103 719 300 790930022 483 346 775498225 398 95 999999665776127150 386 514 999999095347324528 466 65 999999006995169795 503 15 999999953963289848 440 237 999999017617757070 403 562 521766880 373 601 999999818846972579 65 559 999999870868227209 787 690 999999889861544113 753 834 999999692790953639 587 58 999999053539866339 209 339 81910133 544 7 61779703 776 648 999999512534029548 204 2 999999424640547077 588 77 225817213 304 690 999999648221171466 830 274 999999391071770855 6 885 999999009890521066 792 802 999999212599275095 629 619 408635320 97 854 999999424127721338 689 642 967968858 572 215 26131127 283 222 999999753409529579 555 196 999999947049537773 348 255 298071082 338 575 323207500 683 325 614779051 248 681 744137226 777 594 647284005 456 67 999999760742812896 683 494 999999855631391344 334 473 999999515822182656 680 471 999999689406721330 293 590 999999991829713934 567 140 999999084207150375 466 853 414703927 75 86 999999634562090243 294 742 999999912045412622 722 560 483139719 799 766 999999364658496158 405 459 999999394004882178 340 545 635264328 10 202 430638963 373 652 999999127982710384 458 747 619088337 356 642 183892763 517 104 999999241385042137 242 650 173454972 243 763 999999429701479823 582 619 887165536 218 682 813286915 803 861 999999154133499654 381 668 999999664105942113 515 534 999999472255088780 884 343 999999539942226087 862 119 999999057569476955 521 790 260576496 60 101 999999801612653635 135 453 999999900498468809 498 76 926588125 533 709 36338135 874 139 999999451503802763 768 456 999999807960160902 836 463 999999460539673258 483 824 999999680469580193 98 678 203905491 484 711 818211901 815 321 384789813 466 906 431250788 736 826 733441677 870 219 641047958 153 523 999999871136625958 841 641 999999047354615952 423 357 999999697751473136 570 744 747306777 222 422 167711123 39 874 360918178 174 29 999999863278598618 868 816 634012559 511 323 999999849823662747 502 758 999999029799386558 450 257 404128819 290 130 999999873389588613 349 671 999999819170820514 94 165 871339136 737 97 999999366094193326 331 43 999999887536235628 223 248 142487057 846 888 999999573232376025 192 661 896396697 796 717 999999071282269851 685 287 999999932762931057 358 733 332094690 867 527 999999104130167775 337 31 999999537119337474 56 542 999999286633794437 340 293 999999547991149104 870 518 999999495708471450 881 332 332724660 260 502 999999225061344575 138 668 540664606 67 315 999999432902670623 679 453 999999608865489281 267 718 999999734516312316 298 62 938788669 431 494 926930150 591 383 73017360 361 35 776827965 217 275 999999036979013276 848 251 999999520857007995 822 529 999999092441226062 156 16 999999091274729965 734 605 999999488454663973 451 148 999999683551676648 223 699 947152954 352 270 999999480054156678 292 587 999999217102034824 370 597 920561683 603 156 999999432524770091 781 823 999999294335272861 154 267 447187843 700 111 999999055895283022 247 459 694926254 273 451 220708659 224 694 108173999 398 773 999999087864616860 99 815 636532651 389 429 2956332 526 783 999999374999507016 821 557 999999747400258053 507 7 999999054923210154 899 398 999999661029051678 379 854 999999359135645767 300 46 999999491332573118 818 74 304966330 617 135 98807165 106 849 999748955 220 520 999999258540560939 98 221 999999943674309998 820 749 901225728 505 238 999999611052128057 120 306 999999251361217531 181 96 999999743777121088 707 397 325235031 565 250 526555545 194 735 697318303 630 237 999999326832396289 759 611 999999633012848324 616 504 851839429 776 607 999999880293516540 501 37 999999843468454010 49 644 701766643 825 777 742205216 185 227 999999837412811267 514 478 471244266 368 545 999999687442505461 487 565 999999971151613616 144 386 999999162728273167 835 663 999999129227106012 236 374 999999969118865315 573 538 373811037 96 477 999999678641222982 367 622 999999038318790967 148 271 515556201 904 86 103902829 151 477 999999738331522540 899 724 234511390 905 270 695673573 664 699 999999655247636391 718 830 999999635633132672 815 678 999999216691931242 184 557 235826660 497 288 999999616226071491 743 113 736354039 181 757 198970347 827 478 53731263 111 720 564915122 848 750 999999869290603071 200 201 629372159 785 774 999999337567735820 236 528 999999501490234426 304 90 910860118 553 875 999999892842420075 125 397 253012323 471 607 939738666 365 717 999999467911946076 226 465 999999400193789608 123 632 778360317 190 222 999999110326981504 325 150 662676695 613 319 145722005 279 261 776849181 887 494 999999708548489425 212 295 499606873 469 486 999999176170361176 50 267 131685459 205 256 999999165747894129 715 547 604404093 9 641 999999565461791164 723 494 999999944691818614 126 783 892145768 7 395 788829173 450 718 764132461 790 628 692592369 192 892 817240705 278 648 999999841757483751 635 841 305370305 551 643 999999775969646214 204 145 999999845383111099 397 806 999999707412706600 749 170 699419387 237 645 999999127953809477 75 303 127151978 751 453 999999238252149552 449 610 999999806898996378 830 12 815980678 591 242 860741768 531 376 927794497 418 885 175888682 415 496 614939873 746 296 999999788228002652 125 837 370598472 748 36 706077349 362 25 999999874710768844 77 576 385108285 682 803 999999233161145999 616 783 999999981072653516