904 998 1838 2048 1000000000 768 611 999999832389927684 394 315 999999792859256716 767 366 250253051 161 224 28995129 514 484 999999826349689248 214 670 270588203 854 266 784985751 561 905 876251845 448 8 527631747 492 956 999999746412136649 283 264 999999868642878352 413 924 999999763302518206 300 411 999999069878121187 585 346 999999954934112847 87 677 306180149 314 722 850927590 43 494 999999705129794601 623 349 999999333951288823 622 704 999999019737680259 403 522 477903451 434 59 999999207459518330 108 588 999999881914437290 145 582 999999444554275266 619 630 999999663320622229 959 229 999999519928832560 867 107 337862819 77 598 88378004 677 637 371575433 49 704 999999657753934255 236 538 999999307766200813 431 727 999999747256116035 575 107 999999700369052522 509 911 999999260720488232 799 215 449577891 405 469 679432258 211 845 999999546427968475 793 626 473657410 647 356 904006116 789 900 107164438 349 146 421924150 962 582 999999117754851269 776 419 62615136 533 41 691243458 287 716 684525912 333 330 999999135669736840 271 118 999999094338117079 678 727 413764737 46 316 7277313 158 907 31709047 434 453 80956389 368 21 999999673611730008 147 737 999999522459362254 409 838 999999402357814190 835 921 999999577162867787 679 134 999999284403403375 595 913 342446152 228 536 999999157834550917 566 71 905605982 339 744 999999268636216695 832 242 639257163 979 142 547353376 77 958 992010562 528 923 999999875335334461 502 569 999999688371664221 593 438 221468419 657 803 773055645 582 90 999999899986869421 900 502 999999038112158382 259 626 999999496242248553 989 136 999999377977824093 31 62 999999398145057815 630 537 999999049129031081 492 579 897346410 196 316 999999897747060131 777 432 999999300610169333 78 973 92193220 744 67 999999731699033766 562 715 999999903500719690 980 871 853940747 62 810 999999083873848703 605 519 999999212064572272 773 740 999999432949852627 941 441 114849883 172 732 999999080539517367 156 244 999999312607157905 545 256 999999759334317784 447 817 999999182665992909 91 238 999999926982282000 441 893 999999562288785826 68 993 42738496 91 290 668306395 59 777 682240098 524 891 999999124925770136 132 150 999999245941156910 117 860 999999893469327898 870 391 999999616251769849 907 97 999999198216037302 688 971 356950543 181 775 999999143551194682 184 376 474978044 207 368 999999142635505682 711 436 604079156 386 453 999999558814671102 709 122 999999647722529170 183 454 999999060188373142 14 512 999999921313530271 468 741 999999608696193194 710 546 999999105665579089 11 566 803968394 775 147 364785934 517 684 186927996 506 232 662219277 20 757 999999182307708882 46 966 939141052 324 156 138468783 485 828 590798190 672 908 696671140 400 673 999999316867488347 383 169 767609903 972 391 931047806 946 785 999999206327564829 62 46 863823120 578 875 817510430 486 888 999999889648594994 180 523 874929675 505 208 999999476431681560 451 525 339987095 344 865 999999566552632689 239 622 369339360 324 926 999999741994377146 541 863 622136483 52 209 415065648 719 357 161136437 816 868 724899419 463 862 574906988 261 10 999999460614932459 982 936 905708181 743 969 480207336 471 104 926800817 120 526 997446446 401 737 447538576 335 872 98479624 64 402 327153019 580 472 999999777046652202 150 636 999999074940580510 299 117 550735675 783 89 999999288722698517 766 378 479197381 787 432 999999189212718965 282 400 353653989 985 157 971650596 258 304 556389559 748 436 999999333655332053 327 553 999999999848221420 309 729 373884503 696 947 999999155039826742 709 774 999999727715144502 902 933 616351631 86 188 383952860 858 913 815721473 340 807 999999190543926537 389 426 882391422 599 915 999999894924914686 875 898 937346284 612 180 607227326 6 905 999999647297998588 736 976 999999463474156851 65 807 999999854909618394 261 396 162659623 316 827 999999237587822027 784 872 999999683109887027 333 415 461215292 210 598 999999361782902469 38 623 999999947684557926 470 796 842697392 815 412 330854338 54 633 596676658 315 972 999999340517608932 410 915 999999043333944564 228 483 319658663 913 216 999999736190227968 445 310 847397109 112 412 999999494129523019 86 436 999999495537697976 457 274 257833021 168 383 354199964 569 447 588177581 538 274 45848821 319 668 208252988 2 572 999999016760651919 862 705 873017388 8 755 577871873 24 318 648727000 370 831 999999892679038051 594 554 999999464172241856 237 122 999999129902035988 766 699 999999100885857031 994 683 295339532 722 767 999999179081357546 836 406 999999317259411409 799 706 999999652468185353 286 179 297069989 830 704 19109991 312 390 999999515184740948 706 803 66534933 573 206 999999835476877940 390 59 999999181619937488 801 310 999999605168207873 462 771 999999745138019682 48 935 999999686810942279 284 62 610298512 428 214 999999759366632336 258 1 999999321415746187 170 79 716526586 213 464 711101751 228 917 999999914900845562 377 516 999999439278959712 759 727 999999903736826883 129 94 93361992 804 606 287698609 867 60 999999606590035007 351 892 483813203 868 211 494150190 258 723 999999873401463542 47 970 761623042 716 247 999999046162281102 704 634 999999754130825008 494 411 999999084518373916 974 244 148892307 912 971 999999722721345857 95 90 999999112872556293 925 226 999999221611768375 285 862 999999743752925957 331 638 785049567 718 241 81991540 242 765 999999384010147424 43 282 999999366942964104 604 183 999999323124227257 43 250 731767646 598 201 357597278 954 385 999999134068343696 180 756 576876386 89 776 484412674 155 482 999999627350373929 234 881 960795162 399 485 999999175802462965 115 467 830321061 463 382 543124282 994 506 131753680 418 591 999999109821629289 42 747 999999529881520693 246 732 999999093057357026 266 91 881173237 94 197 999999783338442683 962 621 999999684865828343 28 158 999999739242305677 674 356 986565163 516 377 925704373 571 831 999999809721447292 143 843 999999351068224121 656 102 849604015 43 230 999999537225874676 107 858 625659142 940 482 999999404720893458 427 301 999999790633390199 732 595 890941452 482 274 194655875 322 780 643779374 121 261 18935282 782 384 999999385897050633 826 149 251479590 42 970 999999522847490420 364 40 999999206656183139 300 224 812249922 527 243 999999507492607921 403 753 999999184985814745 951 966 999999715237360694 876 961 999999720160441126 634 130 203272587 5 931 999999554305380395 140 876 999999896369219015 867 905 11976308 188 200 891547119 507 466 999999051494815393 554 583 999999566204028691 890 211 999999888670336049 664 121 659322344 284 739 999999418754406960 636 777 589695803 555 712 999999650706572119 997 95 999999104850044866 950 56 999999715357288106 30 161 999999475827805671 14 542 333885002 511 983 210919815 631 426 761951943 769 201 893246425 392 222 999999009145571442 208 391 149230010 427 877 189394481 104 121 900809765 302 66 11939720 666 305 999999097654002657 306 893 699000867 918 23 999999260739059116 252 356 986761136 415 783 999999837530990686 691 679 999999820494898936 337 493 984408708 330 411 999999684674641903 29 747 369260177 484 335 921925184 466 101 386089109 127 485 999999400801313237 529 591 700795466 161 227 772392688 615 637 923573110 362 87 999999894120978607 235 943 999999787601316869 458 320 999999767234975840 72 777 252280857 589 898 914222337 498 132 135389931 275 820 999999218529013288 501 349 999999052942406647 738 656 999999161708275952 659 34 999999617691072277 270 420 328702385 435 892 496439848 202 681 456083294 515 371 999999044100974297 679 639 328538693 725 118 999999893317180931 774 597 512305183 952 278 999999144098711774 87 208 76596553 321 831 999999963228555341 878 970 999999209822952582 354 941 510596858 13 274 999999214589082682 18 690 999999177198228835 585 480 999999969252567024 508 694 738185312 658 248 187733290 131 438 720478831 298 306 154074490 211 373 306028427 911 93 999999622151985721 152 139 999999795535642777 335 376 999999584040247261 352 608 999999499046608082 883 278 215123584 702 639 704985519 3 828 879422041 523 830 999999352334772546 178 778 999999579388624643 652 346 647857322 787 757 999999373127826746 466 465 102917775 421 447 909375228 639 219 999999982119383223 509 190 156341778 966 54 244299590 100 292 571135858 765 810 999999074681766976 442 279 240774434 182 821 999999513793773456 426 14 999999062619956484 85 344 796603518 550 371 180941648 433 304 630815497 361 668 999999932578571131 773 50 286320141 257 286 907064655 424 578 516574367 771 720 77364151 974 665 985171150 341 274 993254111 81 658 492433881 248 691 999999553912061819 629 904 371450109 461 601 999999786303724015 369 746 342575777 124 723 999999050682568254 298 137 999999981285208546 581 97 472309296 160 781 999999649650553669 902 281 999999322895178740 54 599 999999634474806096 712 195 999999091973044472 775 184 622215781 22 58 929768494 967 955 562894047 202 676 569014233 342 86 999999939757067248 781 495 999999354514398185 539 280 999999816092528327 478 971 999999102869831594 830 197 982722103 802 329 999999669528447502 313 77 774524953 357 863 999999038508212920 194 812 999999924507019701 169 121 999999150349203068 99 928 116982721 969 988 587911166 222 852 506755830 850 362 134696305 992 552 659574169 715 90 907917114 844 405 124331356 227 178 327247470 699 445 999999099238464305 752 480 456109590 472 373 999999645030512910 884 942 326485381 263 882 123298974 173 735 146571345 289 60 223876417 206 467 999999462380836259 621 722 65904237 189 360 288810530 412 356 999999310604950003 56 821 999999169611846360 201 559 999999105409026895 931 146 986853755 728 644 916655446 694 681 999999144642226067 569 310 547711884 42 251 255103882 28 90 367836862 996 953 357419046 472 544 999999327742139212 540 571 999999923829230888 976 878 999999481970631168 230 134 999999412421000435 75 483 252857845 973 813 815731610 783 563 624705294 438 224 999999589698563741 686 768 479493818 558 125 999999907548066773 788 892 999999198227106435 338 664 999999294393751928 125 237 360404172 753 871 873341440 248 747 999999847515895484 480 689 999999904861201005 280 938 882404808 259 573 999999358484420624 578 306 20600887 711 351 999999261146827439 101 558 999999091983288908 202 116 768923984 847 220 252359934 80 357 999999862581019908 570 599 111215898 944 1 999999821352343378 692 237 660970932 247 150 999999419630255595 508 31 220529172 795 396 589838208 792 62 755574885 807 82 53256196 280 583 66608039 421 549 999999256094575457 326 491 999999272237513219 908 373 946780723 627 137 663850001 638 567 999999388390574522 432 702 767789198 930 133 553382536 349 983 435537431 302 564 585647605 166 6 45093538 122 645 439468736 577 482 264709266 534 582 611203667 140 858 999999280245819196 453 360 154375523 212 959 759916872 699 719 999999534934976078 450 105 999999190917583054 190 40 192636708 717 757 999999881232192540 606 956 576737367 306 377 197349138 414 959 452815494 668 90 999999660432303156 105 684 900888430 842 905 83045164 323 146 999999923010409030 185 639 999999086439355584 30 652 92326145 834 203 999999452850276819 370 203 999999110877408117 777 542 999999044184776263 694 414 801129863 914 396 738627526 665 619 504760380 304 391 2068861 90 821 782192315 936 919 402706718 499 304 51461366 532 158 999999507700250964 763 215 999999826980513288 687 820 999999987608671964 703 428 999999685840704551 733 717 10294818 224 389 956335189 245 967 999999957797109035 107 242 999999116722866475 258 538 999999907978908702 963 553 999999999123107594 651 467 999999712975612336 475 677 778267837 198 819 72046297 956 267 611076481 305 282 999999590456533129 149 382 999999613350498496 358 464 999999343674488940 772 477 474736463 670 463 999999227457122909 574 220 999999737934671957 385 498 999999482039413243 481 138 999999967038701770 562 457 720168364 565 768 999999648566880700 742 526 999999596502229252 791 43 999999061807914364 790 197 21544413 958 248 104727592 478 585 498367904 313 996 364385488 374 417 999339111 676 858 552657071 430 315 999999681450811428 761 286 999999298922704884 932 325 999999546326760525 703 147 999999723227729148 102 778 999999098245822471 802 421 796320078 6 908 999999265015454717 866 625 999999928962192751 861 933 725386478 168 457 999999416102914866 968 540 752936405 750 255 712775741 837 253 999999439946274058 16 645 725753107 9 594 999999230234328616 884 931 435125851 938 787 999999984571820940 56 335 833159723 350 829 356480006 358 100 488503118 664 322 999999572041464260 311 928 999999168204761646 441 212 999999797850037208 225 340 667582922 716 829 628743536 850 85 387922590 968 480 338115336 619 911 999999743410186188 662 991 999999975715790945 452 797 829207795 446 319 999999623829023440 168 693 969623357 590 59 625847979 333 97 875325134 232 757 999999829297693750 238 332 47561946 296 480 999999380477933055 292 913 503224455 383 625 999999546203177242 957 416 999999576151253767 454 510 705899747 638 258 304187274 832 590 999999947474567965 35 99 999999517793688161 697 974 234990778 824 137 999999764881247452 909 863 999999288134324482 289 848 30140198 788 765 999999437992987097 985 706 999999105867228153 983 276 999999757242314299 827 51 951696650 904 90 999999021537992200 204 90 999999640143504456 538 58 233064780 657 863 999999658715704039 403 90 413815684 926 904 915643429 900 99 999999890668106636 994 14 999999242768094697 428 916 767919 650 485 999999581665730198 407 973 56806337 840 597 999999681349702778 167 276 999999209513135097 920 640 999999822531429742 49 15 999999710196454546 338 946 999999253484197704 880 908 562276253 341 330 464047432 192 197 999999995050344639 655 373 999999394243498413 601 512 447127759 775 962 999999272363488854 964 887 999999151742009976 118 924 999999743437696624 133 622 999999854850786276 791 383 7370901 898 235 837624281 179 327 999999591113313116 633 474 999999569421460927 698 360 73871859 496 286 975805735 355 941 267267616 528 106 999999163358102192 712 394 606104602 738 504 282232930 26 184 69260056 689 968 149380994 106 391 999999330299769290 58 745 999999128589179586 309 227 137517454 753 4 952019562 388 125 999999036846255985 954 172 970514211 542 603 999999407284954868 165 749 602664241 301 878 264742994 934 364 999999272765423397 220 849 760772870 279 237 999999888270226731 814 409 999999819319824512 89 389 999999010019062004 45 676 158558947 491 161 808296346 698 864 999999615616267469 552 376 999999572684708771 361 484 146905209 121 138 999999866540990326 551 645 999999815326455066 217 879 999999165680663116 397 637 871857700 134 546 999999524531345690 518 111 950264430 970 580 397585525 60 571 284726934 341 330 641395528 625 406 999999221726928236 491 290 915846790 164 168 560341754 176 850 567406163 125 637 71372815 564 466 999999677004454379 565 304 210672982 406 482 163088765 180 58 999999395469538001 111 953 999999729209893171 726 702 891446063 350 92 718443523 593 460 884172417 651 625 980076981 464 176 310477424 880 904 193823997 723 474 911479936 48 739 392772074 164 847 396430 180 788 832179755 379 325 999999590807199172 995 292 999999694933446049 678 162 541914597 513 162 415255568 774 399 463538461 296 75 999999583624784891 548 391 999999015549956351 730 583 974147902 531 90 684125444 27 446 965300172 657 471 999999603806611075 62 303 196549873 461 174 999999819264964382 258 13 999999645205703624 842 69 165613838 476 919 999999251652773690 546 736 999999233707668583 49 604 999999600023255741 282 239 999999752193384366 444 35 999999206939831759 142 241 610174884 464 539 999999192158276003 560 807 348055133 9 935 999999475362760391 323 212 700735152 138 669 132497696 748 278 999999960216575713 628 818 999999607251795689 49 406 999999549362299596 774 201 999999425295464608 190 719 999999157008014584 507 597 999999154960091237 195 36 999999824021117211 661 539 629757871 984 66 999999503955578290 768 632 999999258212184963 841 655 480773880 535 81 654936912 745 178 189579234 833 287 148114470 157 582 988293757 141 972 471307605 693 45 999999163694439628 960 658 872653703 385 559 999999922031359636 395 48 999999722218560682 105 226 409918429 666 965 999999361676809221 497 319 999999992573321509 820 826 40419191 903 955 869571855 135 438 999999486922061692 646 404 999999639885126416 461 877 999999626338498809 902 308 999999238142107741 386 8 999999782728868630 365 116 999999383089591150 515 67 999999424965155435 1 747 999999862773765912 997 364 999999316957974023 430 832 999999448124316331 290 284 999999745272756031 420 12 999999619230109862 52 942 999999627247013801 553 651 283178250 972 632 999999539915817624 733 404 650291444 916 402 312436830 250 583 197188332 923 925 708782310 520 474 999999881684264968 664 21 999999904179922845 838 696 999999929099639808 174 389 999999370234222946 706 765 446064272 120 538 25743732 747 790 276233323 549 304 999999288804468140 398 491 26695661 313 633 348392648 941 255 999999639994432589 726 288 999999678009466901 219 133 999999750697541322 238 937 963601620 299 505 999999047669147966 113 146 943719084 247 289 999999001517631104 471 731 999999519213475498 360 286 644163624 909 850 999999479844313562 435 947 371279453 846 155 228702147 207 545 447215316 965 913 545078214 348 564 474282865 4 768 531422617 365 572 360863193 452 291 974829126 807 656 999999595295005315 312 335 999999986538272322 92 763 642608961 314 96 759671584 818 116 325181600 923 203 314703537 535 646 955843382 743 97 461893018 167 274 999999518697391719 114 132 146567454 635 619 570012540 284 867 999999805304793969 795 787 999999645253810582 112 126 999999881671356403 143 909 818569018 760 663 905423983 76 267 419408180 852 723 941492566 913 471 999999463370319195 974 283 999999226382815894 109 551 499747567 665 612 999999141467485370 528 637 999999647733563028 83 993 999999446772003035 565 870 35379115 255 965 999999395670448158 134 626 443592618 205 206 762561674 836 287 702536739 372 534 999999529879038595 305 598 392275024 737 406 999999817070019984 139 360 293361278 648 477 999999198437419119 129 304 999999798560517330 648 567 999999634316223892 402 813 156120051 547 908 317021732 264 442 499632647 891 436 999999321041578821 513 901 999999981770260719 642 658 999999142956719379 956 562 707408105 645 336 107597833 530 811 490235892 626 627 713288827 218 208 999999086468870043 331 166 310551508 425 774 308041348 531 62 60538168 630 111 871708590 50 606 309441954 18 787 28221758 738 406 456779766 891 435 999999823438517433 241 406 999999049103963601 191 703 825463815 408 761 458185597 543 891 999999474102312608 591 995 205854583 537 11 655731436 720 903 629200225 682 558 155671095 713 182 999999873189956820 579 360 999999038777267643 750 76 826016789 275 539 999999790678648296 566 854 999999650434411474 895 608 999999220416908122 699 441 999999989880418324 609 57 44618970 252 86 999999456248902605 490 933 932130836 56 569 999999812342608353 978 807 58277881 573 950 999999139731664711 441 825 999999048621191882 517 844 999999474016618558 473 758 362319612 53 17 258292405 490 484 999999827054067083 767 155 463016418 356 113 334121203 281 405 999999224436645108 968 325 365589032 60 913 592499933 474 917 999999988681891778 365 196 392628967 256 454 999999326983893106 209 857 999999135424930006 641 826 999999983723043742 38 599 999999769660719436 365 722 236697170 874 695 999999848502591377 249 938 193346903 179 389 999999552618911118 645 350 640792261 468 293 999999297423147107 578 334 645538652 464 917 999999835560658557 226 749 958158378 455 214 999999645799649977 582 173 961417847 705 531 999999994221033520 40 662 999999532530550233 119 433 999999169007305782 387 821 999999375179724559 358 151 962746931 827 316 999999310885605823 36 394 260232506 298 624 448565219 866 907 476146233 772 65 708102852 116 732 41645755 879 572 728119573 15 371 965199290 151 158 421420854 331 134 999999099418229770 963 832 213472104 632 115 999999514426658614 764 21 999999304873783612 192 713 999999990201906245 664 309 999999915076473350 803 137 157888114 913 488 999999713243645430 160 666 999999211568186688 938 759 667334008 633 106 999999660965257723 272 51 999999475671163745 439 242 478866722 511 619 994526727 53 17 236944787 207 482 999999094109258582 924 512 999999966815181407 566 955 999999973921140283 87 437 999999727549986756 48 467 109136817 392 24 999999539167023185 419 948 999999857078995066 423 99 780249193 743 451 653932982 381 474 955234626 184 662 375908655 116 135 388140424 485 582 96329156 873 797 999999090537346588 538 404 999999450678237386 157 916 999999912998745028 651 341 999999450627958350 549 570 995425185 632 152 999999301983001972 303 182 999999000374610305 802 501 999999640333291008 714 819 467816454 906 156 999999540623054788 248 607 999999420408349421 302 654 253650714 586 680 999999570899032419 739 562 999999422805919111 256 838 35290192 754 481 704502280 148 144 999999356393136995 405 827 898337917 828 651 589130714 110 531 999999744753085017 121 36 999999131360329118 567 562 999999246451917553 957 334 999999785093080661 613 246 584397305 267 51 999999942261176019 45 33 999999396923671652 128 993 999999265659511767 338 855 855636091 797 272 489775684 933 409 999999252364106482 544 649 999999773239484876 739 122 999999873997513445 322 456 167131293 389 68 709950226 764 761 105665075 795 725 411452383 66 673 999999475534117860 872 640 999999586720903550 568 135 946767191 447 771 999999687668018754 467 582 999999740397235726 856 324 843958002 336 590 764465654 853 913 999999478584459736 285 645 999999490020103925 222 5 999999633180552638 810 912 999999675923570251 238 653 999999830254408605 942 371 999999605502095761 456 472 558891268 882 413 282374838 262 23 8312669 13 753 999999689711474921 954 727 999999746535532169 488 167 114060617 617 647 999999549511290475 727 274 230799982 165 586 662022718 563 78 106360929 668 172 999999415436654847 816 788 725949225 969 814 603167253 685 927 999999394526996403 649 233 190202030 871 135 999999518421435703 55 406 999999299584252239 418 731 999999988236690928 798 105 953919626 240 915 866211769 404 966 999999414677277543 33 539 774415698 915 607 999999571412172984 645 821 772172394 190 595 999999384719836107 68 821 999999801282661650 396 813 456945337 454 912 999999029875599020 381 901 237965229 553 618 637923542 590 716 952539271 660 391 965612210 937 263 999999761200700148 414 122 999999133415104226 281 710 310012856 608 26 999999166681892968 371 790 999999249309069720 588 767 649551766 564 179 604657060 76 590 712620457 157 23 928120504 793 451 877901171 644 371 999999471005812306 498 776 704056537 384 55 662361918 326 325 631980489 144 199 999999943219312481 146 373 821049887 335 619 227957733 35 753 56958541 227 562 794956153 367 629 34719944 85 485 146211345 652 399 999999466465699663 387 438 999999130760577063 123 248 999999618775727673 3 824 901650232 818 462 999999668896973612 581 125 190519598 29 293 999999089011611723 655 656 999999417710668174 91 263 474711815 624 973 980561490 618 14 262793226 432 901 999999127779290142 647 703 999999742914476529 725 539 192943260 36 482 701861757 77 164 143742401 347 493 999999819171155448 847 927 551186711 124 792 999999030779290895 39 84 694596230 637 978 999999524366633302 363 978 795430086 663 908 80278076 172 589 189057517 704 276 890003414 794 39 999999004126749827 193 98 770535680 327 842 999999884799119687 877 863 999999365767384737 708 813 356371507 269 187 67925091 277 699 999999361895852229 320 501 999999612396400493 505 481 999999538538249961 147 186 999999327472263568 296 501 999999219442017218 533 471 999999951609963576 800 119 590445937 886 458 857280881 719 513 129020796 156 925 497226936 959 482 999999528891629848 260 663 999999700582638334 817 715 999999854224215954 325 867 999999735156375340 247 41 670727568 538 437 999999341373498106 343 170 999999166677084841 522 411 999999723601388544 52 279 999999621955767135 70 778 927652737 50 994 405576943 621 333 981518601 329 414 999999595279491830 122 51 999999772998146687 293 216 999999468463729417 573 133 158983541 606 53 446822093 512 905 999999118203550678 62 110 996337614 236 440 999999413308572613 898 986 999999554262188853 653 547 999999788072311427 477 224 186974413 423 546 650439410 921 719 999999945815985141 796 246 691424047 76 622 693218141 997 989 345597849 378 973 475989514 58 231 794330515 252 715 236025608 737 90 760719633 597 994 999999322797397992 274 565 200350309 988 722 200827247 955 913 189619985 92 453 999999405456142179 462 668 999999791022421934 252 125 999999453182769078 260 527 999999639223435793 502 540 920926561 161 386 733902061 343 108 999999461628727338 758 931 174521565 276 286 84172186 217 943 119094202 569 719 635153655 654 589 453015504 460 154 96005384 473 488 999999555231461115 909 355 766924255 250 417 999999125704097302 555 165 726285101 991 89 608179426 388 528 374499841 186 573 280910482 774 948 756714417 132 665 437313001 873 784 999999747217506750 324 59 999999952236251457 141 190 999999406397623332 645 616 999999621986453990 802 783 796292109 525 161 999999012073825748 670 419 877846587 990 795 22332984 993 550 999999160498290617 928 253 351749034 857 307 999999025483510432 903 828 999999711504065059 153 676 999999229978865888 631 193 999999667174259180 265 531 999999590566243480 779 821 890528911 614 267 999999174196640798 702 224 999999346000875843 165 919 124340787 237 675 999999623014663975 255 36 999999295949240406 391 656 999999110148314230 217 686 999999856559483261 916 752 966202112 455 689 999999926764894110 100 598 943213670 21 135 999999267539273192 376 904 497276820 743 116 701137443 819 642 999999117040108161 643 441 188409927 996 184 169468557 322 305 999999929134792175 170 627 431111736 63 189 999999408139713297 634 907 475917348 534 918 999999711273550514 88 904 248930903 721 27 771168721 937 480 999999155120840125 241 38 999999309646056231 204 715 999999772757331875 908 436 999999515944935104 231 806 144205047 443 376 999999594913303708 162 811 165320328 234 646 999999695295928606 573 498 58229456 475 257 999999670903644057 137 224 625393121 779 31 926428918 823 368 394127076 824 256 999999552573779396 42 207 505687384 739 232 999999656637291077 671 735 999999472093490831 223 504 802918818 620 241 474013157 203 59 999999756828131258 53 335 455822963 7 978 999999619116352290 997 331 999999371716905653 819 421 854658114 3 937 27234691 812 968 999999806262708857 44 239 999999716911380684 786 235 204228394 130 562 999999706965162337 885 500 566179232 496 895 999999608460334344 786 190 999999456466995752 364 443 999999971651023697 637 373 999999217661552349 507 538 785309714 441 31 999999523804571150 63 461 327382052 459 937 655870979 79 643 999999044295138435 441 678 586399680 898 533 41063957 126 208 814268488 313 934 748044384 740 621 576715883 607 441 999999225961391844 663 304 999999504840898273 84 62 898127061 296 449 433248443 681 890 999999395613643483 888 474 689681379 345 966 999999166654326912 822 61 237937254 493 656 999999254380656017 498 451 509225043 769 145 999999878180280656 101 280 999999091288796975 828 270 899802931 770 238 999999142124206361 313 713 797119585 55 140 496519275 625 602 999999284217635232 956 161 999999457151661451 199 333 999999674567674229 687 371 999999095604276189 987 590 516621608 806 550 462193524 140 355 587410736 949 189 999999575014296161 244 771 999999713651373291 375 312 465003493 318 661 905361810 757 669 631931489 900 340 228067017 17 57 33229555 464 572 999999604275172314 289 552 16139547 647 474 999999716379251005 563 303 595280802 87 197 999999559113722505 894 511 858005266 596 439 2443927 591 552 790469146 133 406 717503755 843 348 361428497 592 240 320388184 700 341 645571569 386 803 991442088 935 992 999999053457016916 934 538 999999512541934374 785 389 622602921 971 915 999999956663460866 267 470 999999929166539119 117 860 334801236 945 645 999999171581566693 290 474 566317840 97 267 999999185836211077 483 873 999999093945274317 744 489 346966337 483 649 292587467 32 390 999999861297060161 504 643 999999079133522166 151 771 999999055567800458 780 324 654473289 846 238 999999813490458257 273 564 821709651 983 2 999999147545930734 695 241 999999449992500502 353 259 155325836 604 176 220555679 3 437 999999975325774058 215 632 999999536289667875 700 262 87393028 815 699 17096030 140 236 999999109472581942 24 341 490985987 953 17 999999033562328389 346 379 999999236834344891 390 597 827155358 998 872 999999323220398553 618 382 703142625 983 482 999999250731662141 594 398 363911040 136 578 999999117851015110 103 371 999999529326332459 918 842 337759703 372 969 263564172 557 312 999999939331681345 805 26 999999349276569123 686 644 999999649702034468 920 6 456352239 216 278 999999709393750173 897 15 999999537493188928 330 620 999999000442347931 831 438 987767536 690 657 206248449 893 438 999999552838022941 35 718 999999038022848869 808 360 145329268 559 932 999999709248227224 977 701 635695688 851 90 627904824 23 164 999999581777735526 964 894 779109904 775 258 992431513 526 432 999999940231670986 714 639 421504394 762 320 631038323 297 259 465114235 682 159 545135567 266 757 177009697 203 482 564059298 491 647 419422401 316 591 999999851070279700 208 862 999999592918969113 419 405 999999771761985375 23 627 532966468 654 265 131838529 965 312 577008844 322 368 999999975974931319 608 90 999999867125390544 809 597 615653074 93 599 173379015 152 790 999999595332552146 242 131 374211376 301 919 999999534717207927 714 549 816597930 921 179 799501539 411 915 976223293 96 41 999999523426012408 683 949 999999043637735537 289 699 127192477 467 797 999999086236476398 287 564 150467245 933 257 999999924479071240 503 184 975399914 437 601 636670426 778 439 798651324 23 722 429315410 11 453 294690052 600 466 999999643997505218 680 359 999999801050443262 79 524 999999668963321325 300 337 999999523965610974 918 80 999999351194876995 34 77 999999554395998017 839 948 999999818302113459 937 878 999999472363380899 297 979 554003629 165 829 475425145 186 990 515747325 271 857 936381467 729 86 999999031831592875 432 421 800542632 253 145 246074129 745 279 308204308 245 277 94514076 334 167 885621030 649 357 177422053 702 72 999999267879957690 611 699 88610546 724 810 643771906 153 679 999999492871643084 123 38 999999487607998163 893 513 275793597 643 439 999999738048824462 400 289 76730902 293 425 999999212970271714 517 779 672853197 89 919 999999797296431194 264 699 999999130663568784 493 640 709003868 611 921 999999456434364963 353 819 999999139577795526 199 477 999999472721776861 922 14 999999829994126121 233 403 469454126 104 455 999999108250921700 778 482 397051764 69 577 316054131 246 405 515399733 599 829 999999542606740188 449 141 999999916661278383 313 322 999999894495417629 613 108 999999494193277947 105 206 999999727943943756 332 142 999999007538764327 414 52 999999119037201940 306 942 534594921 850 564 999999958983960258 46 931 999999635158721091 592 325 246362818 965 800 651075009 858 142 180817395 516 73 999999442616613920 822 67 999999714399066775 761 111 999999129018113227 10 35 999999476528811100 734 171 840304902 927 41 865167544 135 366 936430972 611 797 754088249 22 770 51230314 471 472 827700005 370 884 999999783290711861 130 929 66446739 229 942 101970562 142 765 999999040172168383 310 637 999999331417960824 74 538 134009168 2 168 999999834494511805 278 550 999999569618696210 243 159 768831842 452 755 999999204916952208 410 161 470989648 914 317 210415318 307 277 999999654666857625 96 781 614730543 755 447 272854809 881 980 999999572122201903 745 762 811653661 597 639 999999387383780470 584 731 999999953696020122 154 640 999999059838325538 598 479 467008689 864 101 658210753 639 416 866648577 61 966 595581164 896 199 999999534577977453 2 702 642830138 955 527 650511579 160 722 952429052 939 514 75499245 112 667 832538727 159 990 999999619516614534 226 263 88880391 516 644 999999179088763087 775 487 40663673 454 539 999999666843714215 719 787 999999522275394221 425 599 163511824 976 17 50978164 489 782 123956503 849 286 121816404 859 867 183803582 135 169 179775244 416 795 565343490 9 682 25508015 177 461 999999156766573170 317 210 999999373997726502 889 397 999999770425726022 881 320 420044125 948 646 999999324630370975 906 531 351802597 707 431 762900857 12 872 999999019039039328 556 990 743176651 37 372 34731990 291 615 999999229074500353 553 867 851421374 389 731 840251616 797 439 999999415942543437 40 972 811971933 602 752 361809588 697 389 847184938 73 866 789638422 701 117 999999234477945986 130 384 71061416 977 662 201642993 829 276 999999176290973091 308 655 999999563705313945 846 408 268318146 738 152 999999017428545610 642 669 999999401037493351 961 467 999999796869585556 863 704 266910560 653 304 967853776 492 226 999999490055373648 200 100 999999139062918947 92 232 715975439 315 66 999999273005075700 982 990 604914149 57 319 595965512 732 637 999999281742259549 98 973 999999598101939662 149 223 441589889 159 862 41423503 189 575 287860783 531 508 630171413 58 737 518275224 539 785 999999729695290299 483 488 601108142 285 409 852585088 155 289 875495292 671 603 469377619 940 965 20673543 379 415 11993145 922 270 492525227 219 538 152953885 796 572 647165618 97 643 999999741607928931 16 524 999999617945369355 346 934 273178254 360 459 999999617222271243 15 758 288297895 985 991 674110995 892 618 551335736 380 812 999999346142316245 399 69 508855840 288 385 881334634 699 637 999999030903707773 487 507 867024671 109 399 999999121500794753 197 179 961257526 719 833 17414913 19 657 999999179729368315 693 419 432613627 417 968 999999653454589178 722 392 784957968 953 839 999999916723992984 142 313 887855768 310 387 999999884386901786 176 401 999999625112980801 354 264 999999427552751494 811 125 999999914244775348 872 777 999999871520014334 429 892 999999314327492908 71 94 816959773 76 930 999999526807849783 408 20 643365009 274 179 8335006 474 30 105191373 379 492 999999118066957197 337 784 999999459406883242 95 941 846973135 521 676 918655887 978 134 999999367727798484 914 513 305532253 255 716 471452076 540 740 371397111 975 62 795941174 475 432 999999677298898557 30 972 999999048621938455 365 416 999999170978158343 382 135 860415734 910 271 999999398223295552 572 456 999999994630642620 854 882 825752924 494 857 999999884792731884 848 294 999999237271423343 523 747 893334723 667 56 999999277188314791 687 398 445300316 420 982 572747718 717 491 253852998 265 224 999999870484853121 484 329 649706574 857 111 447243497 981 140 68757181 864 310 999999888889956915 590 115 999999441054547838 476 750 999999635239659205 331 255 999999970169350738 616 382 806317727 601 703 999999628779469499 983 558 745295471 487 178 719199782 59 206 645101217 563 230 215587377 192 666 692856792 664 551 979036183 187 798 896318930 223 622 328700058 827 135 999999160953583444 29 387 999999617325243399 420 178 158104299 214 669 316336600 82 359 949291467 919 642 354936353 52 325 575658986 606 26 363454676 824 108 875505433 733 81 75041137 514 293 91754623 168 414 886616169 140 602 999999161540902780 853 26 853709224 640 184 999999238372266470 707 885 999999195016121570 771 485 707712467 140 610 999999746674588067 968 797 735159091 207 339 388686763 691 665 999999462150657622 441 682 755978809 101 272 999999961716751628 394 236 999999881524266262 463 879 999999441481311773 295 716 988037468 415 744 280664241 489 774 999999637331929120 62 499 999999667350903362 576 981 999999999842346037 823 681 999999070135527509 294 636 999999583875992087 536 966 72576275 596 467 793306902 389 771 999999460943863658 823 621 164872362 854 507 377808863 24 113 544321815 845 599 343759916 623 807 872680737 698 33 648422120 590 290 146721505 784 735 999999210138985988 976 473 841357000 306 757 93966475 811 646 438676590 602 683 685875390 588 592 999999467622370032 736 51 999999447618446606 669 606 999999275697014425 316 685 294023299 838 599 890094423 636 96 528609329 899 596 999999263752073929 80 21 638382093 756 251 46678595 608 195 787388039 85 74 999999751812343362 725 67 406085606 307 660 476260336 235 698 795203589 986 407 930635765 772 544 195332591 887 113 999999338470767523 943 716 379824729 660 491 999999812633119058 252 85 999999845206673250 62 669 999999018922237715 639 456 950945455 508 867 248688135 500 534 999999049952888657 178 489 999999954054379358 670 167 999999032488547469 929 180 999999843119787029 738 106 803868659 909 130 68906879 436 656 699650762 828 664 999999798201683623 675 966 319075102 527 612 413244254 607 197 999999635382410194 53 380 414456398 277 891 352105526 980 553 999999603637059529 429 381 335847270 741 15 165691179 406 857 836571641 440 592 189848083 524 710 999999304099084740 393 933 277998212 107 669 999999337189416964 78 552 505487511 615 80 541975175 339 758 999999623651979401 171 482 241254785 274 44 438568426 939 633 316606846 962 990 999999847815428492 94 818 999999013726343001 175 214 498928698 221 559 318025123 808 943 999999272958616693 446 116 942925421 676 533 11909667 618 63 999999745198244558 741 633 999999394160779886 142 304 268622827 721 406 999999693041128506 245 191 999999029590832190 636 409 70719045 469 200 189058444 603 738 999999830169022930 403 282 294758468 619 902 999999029705303363 332 961 339497333 511 846 999999769318885419 848 588 340533235 872 44 999999242547248559 308 495 999999391276056785 67 785 999999641899110624 894 138 999999073626187902 700 293 909812230 765 167 764872800 254 224 999999962990825677 710 771 501268954 589 579 843279121 465 192 999999177611181460 673 637 118090198 147 408 255359337 537 846 999999803180781429 905 389 999999013461178041 51 471 732454664 355 382 688705571 163 117 606568691 422 464 265580476 934 158 999999002791573372 947 240 999999267770761396 134 244 999999514820578948 544 265 461121773 479 50 999999469669014391 927 167 999999296518005592 268 424 574556645 817 872 584383664 389 924 339555288 386 181 478844074 106 618 477603693 285 550 947833191 325 274 552666205 552 467 999999798679776444 351 57 999999995571623859 803 575 999999728639925662 426 420 999999979793228578 535 645 636550452 759 652 193854087 437 331 999999739136468853 592 854 31978396 546 747 999999115552211065 369 81 851507850 587 370 999999634615874077 573 387 999999960933546011 328 472 999999984665224971 337 707 999999478900904440 583 785 940191703 911 830 999999711264620011 991 177 609196950 773 659 15324031 805 889 999999821656255030 895 103 184295397 424 579 242795612 250 943 999999476814148173 825 182 999999043805276995 684 253 507271180 128 117 259194331 529 595 534579465 519 223 999999825642255969 292 451 999999568669637687 746 915 988435123 263 418 459638824 633 332 999999556501341565 606 983 999999481082303665 975 84 999999572400758912 66 605 999999321898953854 785 54 999999324516777537 778 132 227095595 109 426 876746545 687 804 999999033922656381 103 592 876149584 83 618 480986122 879 958 999999330277174346 743 47 999999418897225387 353 132 999999353604409591 869 904 999999485124629704 896 895 999999231368744775 629 556 747854959 855 100 856274177 10 463 864456155 75 222 999999664355730616 495 356 999999717716799330 522 616 999999126961700845 883 600 999999481757533805 25 564 999999394190175986 70 320 388823250 166 238 999999987072933731 501 958 971502712 876 812 999999297841443984 735 644 999999892036223131 588 998 94678972 251 146 999999771948193778 82 597 999999347534093475 616 272 891232095 71 225 842627588 996 360 999999941092752656 263 789 823029688 480 286 160011281 755 262 714378666 484 696 347340507 611 860 270061972 840 478 983202211 752 602 756262039 359 94 999999258752855928 373 197 829839565 187 437 334721980 749 865 147989807 143 490 963479935 848 567 384479461 25 208 124420560 819 174 977019458 375 651 999999109480963317 610 158 25351417 41 334 738593837 406 884 999999406759444993 279 253 602739367 71 882 552699675 510 138 999999317639584005 314 111 802761657 618 134 999999368630878700 860 467 999999511827259332 821 224 436429052 801 163 999999463037409890 740 234 999999458277488256 366 436 758828877 358 170 367999707 323 289 999999089735151598 925 625 267030286 525 287 339654068 512 132 999999645969980734 917 286 999999614403180985 813 411 999999315184525998 751 253 559901251 882 625 999999767768185683 845 634 57826804 818 652 999999196392673020 811 89 449183608 488 551 849236484 865 632 999999344765621008 151 82 927013492 559 355 999999400518624205 677 270 999999705629963082 731 71 999999948161440049 12 117 999999744152753649 585 903 658481080 669 257 885075166 992 949 564621011 155 536 841025149 84 58 999999239154996997 556 292 999999758654006992 901 592 657838703 497 793 999999624274956591 512 564 323593712 99 438 116784731 340 482 360712533 328 351 999999766789263931 496 211 999999148448310904 399 663 999999813957149389 773 818 571424902 463 434 999999281224046574 319 242 999999153576925080 865 187 340262557 410 237 999999608993820579 267 243 999999966034344027 847 214 999999242411087901 799 769 531766964 193 176 999999885601351666 201 89 999999521125603472 440 787 242898445 481 431 14773146 79 880 260085161 839 450 999999086651981194 818 742 487207272 404 780 999999645718214041 535 887 768958966 468 538 999999898033683566 622 901 999999699628153516 210 900 999999287636610383 460 609 999999654067927957 591 549 861345317 658 401 360065838 676 801 999999544322237537 274 860 999999677817792094 117 543 999999445117958848 85 404 298567753 429 392 999999995071382919 338 386 249880628 105 547 529471932 141 437 999999458971777828 643 691 999999285725500497 401 189 728254214 157 775 665913636 295 3 999999728040417125 808 184 464896384 17 19 999999166924779340 623 796 272286924 115 138 406072889 385 302 38016440 451 668 48320351 218 349 644184704 362 883 999999229437348626 534 106 999999166451842638 881 78 413333490 725 731 864575461 470 804 999999167841720679 802 138 167804619 868 221 999999077338412703 526 217 999999417692922991 854 74 999999175761095545 336 800 999999617403994272 459 260 470262846 749 382 999999549409661537 288 637 999999783777549415 119 782 372844342 14 295 999999387632503666 567 313 999999405221248637 350 532 278834224 603 65 279138446 425 652 751432218 287 175 599237027 358 583 999999331859680128 484 379 999999541497985723 312 58 999999121256316025 658 902 152534890 898 61 999999089241092376 471 341 945447226 313 799 186386085 548 512 999999139337310732 533 624 999999638669014197 650 197 999999701783503930 800 524 999999478547830189 478 761 999999175976179979 660 88 999999823771863094 673 762 999999470718782800 348 609 354680358 360 744 999999712910469891 632 189 674472716 339 498 465120722 389 861 924987287 510 197 999999939638997875 710 750 999999403851351232 747 581 999999228477257493 370 445 223466116 96 894 999999528101823112 645 274 763630271 298 340 999999787983191610 482 844 913951818 553 881 999999379541416308 847 3 999999684405032946 171 525 536798633 879 801 999346126 14 178 999999350764327566 307 453 999999482878069365 391 732 999999847819452824 835 296 999999633726975492 873 878 97872841 163 65 999999595727674403 250 632 734298802 309 714 479417524 599 153 999999478369246097 95 244 999999192209909495 44 30 999999371835974618 190 517 686706554 456 361 632220397 286 164 821067100 623 270 485449893 683 650 999999661479141127 558 498 999999334129229483 374 744 300349563 620 876 136921047 509 573 697136320 210 117 999999390020113693 406 405 600729925 123 46 999999736256043755 640 220 511747662 637 364 999999500405630097 470 438 911519895 669 671 999999642768572703 524 55 657204692 119 148 555880915 268 591 926928465 94 817 242992977 743 222 999999221818771584 341 748 999999116520914715 692 847 999999569960943912 378 475 999999255336402303 188 427 999999143399264286 574 432 999999227496736098 657 201 762219790 29 438 703633106 630 253 436927660 426 106 999999357402555821 116 659 677143571 780 100 999999402241563134 19 415 999999292304782804 878 786 999999524245028781 824 497 154873484 799 141 815357898 5 516 938033517 243 52 999999422309846455 45 198 999999968556668693 654 298 407252802 823 14 999999984356697577 786 678 999999245782815996 582 330 550042334 532 803 813550496 658 425 999999278181470759 173 84 999999064183821337 826 308 999999433228922275 376 197 153326372 383 270 191939051 27 237 754228205 72 635 999999817575962365 63 30 999999268268027033 423 326 999999938441025758 351 144 951077640 823 108 999999384646471586 440 551 931073814 478 676 21659873 82 77 999999741066041278 20 186 664504419 18 456 999999272477791899 585 197 582553684 208 420 999999306247406799 8 785 655631920 614 432 999999338688548436 426 461 999999808690427343 469 783 50263946 211 683 922445652 134 404 999999899720201952 104 213 999999816364588139 711 426 999999258142339746 90 650 655953597 364 479 104042106 618 159 587064878 898 61 999999757884287153 100 288 999999086285968261 842 167 999999499896154795 566 298 636609424 535 729 999999463965202466 684 79 999999762795035743 204 270 96418296 165 185 555678936 702 482 999999903274125909 364 42 999999503516669138 420 848 999999268842333628 278 579 999999966881110345 255 66 999999915355900331 273 507 351292746 51 245 380658332 41 277 999676087 40 300 999999615314961969 705 333 967729815 815 639 371673253 69 805 431066484 517 753 284399141 671 393 999999459723628133 638 721 999999212998712188 724 880 999999170237333913 706 409 769388112 528 561 827508027 325 271 999999301118409538 537 18 873324478 435 579 999999992348018273 606 516 999999786096187734 647 796 999999721214825095 699 432 4481795 893 292 999999533422863642 832 609 802216422 717 363 351658020 181 717 999999805745402631 856 366 414740209 859 217 143977668 36 875 382940220 292 611 747478243 699 174 188096354 134 852 358679630 871 580 590407845 404 399 999999980512954450 733 1 999999547392680064 349 816 733272284 611 108 16968204 366 774 191305692 158 394 435172719 449 63 170547248 180 280 999999134510599056 269 325 282899414 151 735 999999142833715144 452 585 999999554969286480 507 360 517425105 20 802 395148514 277 417 920219545 228 188 999999790888200844 535 880 345978959 733 341 867069247 99 729 743934635 78 724 999999516058609596 693 761 999999037632696531 893 291 365791307 41 399 999999066803988774 523 218 999999337102454558 547 548 999999258920314693 662 438 999999458459579976 704 520 999999486247503052 800 736 40096889 63 217 831540056 711 574 72139347 115 555 374801420 781 681 408241349 778 155 676081553 145 83 233196741 611 791 999999281458508547 580 47 983006675 91 881 999999376864059246 842 224 670498201 374 200 713966122 561 215 999999380147847819 867 152 912729587 533 357 999999193164696124 769 466 51346778 482 736 674403183 885 660 902538911 344 749 999999470528542047 784 362 999999952767994895 318 795 581683339 686 397 999999723518261391 230 879 999999203712990765 834 557 999999808060381797 836 180 821304079 713 770 740748550 490 679 999999568416095219 857 227 999999413363911571 151 369 278761366 516 38 434144243 264 632 999999700428328419 751 475 525303439 50 520 999999649321166025 133 249 127603892 705 606 999999680779621561 530 32 180464696 856 245 999999866799868308 688 712 999999869895227950 447 704 999999105303704550 425 638 999999508376605227 241 441 999999545319568073 205 242 107670602 398 863 999999397098761556 203 405 999999909749221889 77 388 999999890482562492 11 560 155278060 744 332 999999632483376526 71 368 999999329789306637 898 55 267181464 900 773 59183586 229 776 124333231 215 426 999999784865032067 112 240 999999755251954057 618 662 999999763754713253 803 748 874569432 716 32 613228941 110 763 999999737761941568 213 119 999999111450890876 858 274 768543061 240 442 426845411 279 28 999999044284936243 120 65 556942619 373 810 109645995 876 197 802397140 408 321 999999963862471529 349 567 999999957811015748 272 79 349109380 64 85 999999898951199189 667 412 999999970633609631 420 568 707560845 589 707 999999896827895054 236 375 742166617 777 870 999999020099820269 74 720 999999787396824749 480 809 999999621242623972 159 133 327492199 810 726 430926000 612 805 999999276399410099 787 625 999999976762107761 345 424 999999097736328855 598 423 338730072 827 818 547942656 220 299 999999212777974117 290 739 527103264 150 527 338679484 693 614 999999629296421059 685 902 257632384 624 668 353776944 226 361 999999857527485002 336 526 260081116 182 356 717704616 65 516 999999590131006377 174 397 545415727 208 847 999999164827123434 736 28 999999210087754936 755 564 927235995 357 816 999999000173002557 861 548 999999490070301469 732 668 352567252 541 883 999999233255573523 493 324 503372546 878 837 999999654662578644 602 494 999999344222758345 388 127 241542008 649 387 579774311 46 645 175160591 621 571 999999500009074771 472 124 629280570 299 160 953842993 445 62 999999678914517423 788 269 999999775720964765 391 502 999999338104762149 356 247 379803830 817 882 742934370 11 108 952965858 432 679 999999693494002884 486 7 544621884 813 116 999999954781817469 615 335 963425563 328 12 11886549 801 482 999999047166976307 422 820 999999016235418640 367 109 999999662630203571 666 250 999999797286577018 807 834 999999481602349758 690 37 999999904156512961 581 429 999999566012604805 665 465 311188238 825 87 999999583183235844 815 104 928379477 621 299 524710827 265 756 362597963 457 54 203403897 850 360 371214621 214 113 999999126108496588 729 598 458903596 222 611 413913666 246 439 999999122980839455 710 183 261495319 266 386 468442126 740 11 858643905 61 65 999999087526180684 80 744 912647388 419 178 433213020 833 28 820355516 177 675 999999668242048017 691 130 728820887 873 813 999999573766359107 794 412 668802060 841 282 999999981722479693 368 124 999999603622949588 839 600 612217762 177 374 754875772 554 747 999999111837160028 225 227 385438800 431 532 834339270 334 805 7877104 507 219 999999972396799982 845 761 999999367426796865 820 348 999999516524061803 738 472 999999277349459746 797 406 999999034663443883 822 476 920288335 221 315 999999024305154338 866 183 999999992941473162 25 359 999999353505066869 355 233 579660311 21 638 999999233395879517 139 43 999999496470807104 593 181 874974107 49 772 999999781785109916 356 320 999999544802145184 686 467 245369574 140 634 999999021531263037 822 585 999999716751734152 334 295 999999191355095574 83 266 880549489 645 823 999999444676607216 244 184 999999183733211578 673 437 9290990 1 186 186383028 739 817 776943814 402 352 132384328 428 373 999999366794020010 496 692 639373358 716 144 754141679 166 449 999999661648789715 895 167 734486232 95 361 925316244 22 64 954221366 507 521 999999319802903973 352 719 511020438 434 744 999999151623826079 70 671 999999169156129062 111 265 26347016 11 588 999999467125382985 459 606 307967916 691 267 999999298282771533 792 773 999999693085909179 774 733 999999354517854597 581 199 968278184 452 870 999999720888750628 518 825 999999658230421042 157 523 999999293232822637 169 341 999999078809073862 818 698 500667201 1 881 999999597066203658 635 307 401743529 708 192 368723421 644 804 303189552 145 664 999999748708673741 684 500 999999197381902168 121 282 999999116858542143 81 848 346254539 165 67 105913451 834 83 80800601 654 153 18384121 511 80 437648300 192 575 102335366 462 734 211033618 560 884 999999411130903376 249 463 39665060 167 835 855287196 32 250 999999637978412518 754 614 999999827812094319 772 823 839556309 395 503 999999104473477946 740 1 344055169 186 750 999999619155131403 650 162 89552645 892 180 999999495711437579 383 350 999999619781338424 449 29 999999064510949319 97 23 329986863 220 607 359808502 75 553 451701545 244 669 994495763 572 615 520535643 581 296 999999320121423841 771 719 999999997776971131 454 755 946191624 793 147 999999161551518331 19 808 873138556 684 635 999999250364805268 528 311 999999596771805555 701 823 999999313850599519 461 420 728778400 300 597 999999110417130245 559 336 824604645 791 852 791686983 870 765 310325899 893 903 999999511340876523 652 423 999999228069493564 100 135 999999391539053270 697 440 978134157 323 457 999999585393614137 145 531 999999416093193581 582 60 727700816 29 80 999999028720693567 831 448 999999911883340793 351 805 999999049733019410 596 50 120401910 534 18 999999310510144892 770 533 999999712279204668 82 465 682928514 172 656 607192607 756 444 999999945780721996 1 673 999999333258047559 377 138 999999937370249806 230 117 999999362335504377 418 401 962605442 282 732 999999977204814965 442 106 214322938 95 852 999999166318809386 32 607 520676519 414 593 197894075 645 384 912495886 776 616 767853992 642 445 602232239 370 593 691651478 715 18 383917306 895 898 999999638256640946 511 679 732019083 727 212 999999316529715854 245 659 632001515 462 232 999999875411460756 517 32 999999340775800169 536 129 999999859067928522 375 260 999999402191410773 104 595 999999006707915883 581 130 999999332157995462 573 67 999999724955216470 306 286 999999050643501687 512 734 355956285 6 461 998747360 479 812 696368871 676 405 999999657718379266 753 710 314324746 748 561 530837832 84 613 999999886046284589 62 116 668907513 731 290 89467916 98 207 999999646033647071 314 715 999999965317425974 124 301 545034939 416 755 65797887 301 532 441825379 280 844 999999557327649641 234 901 115287654 282 58 443109968 818 31 999999508417906514 446 400 26854794 432 175 78854720 55 223 999999449169944979 450 503 999999456722312638 161 197 999999657015755367 612 326 576933703 64 375 890209278 555 903 704721469 230 478 999999279351664045 835 898 999999022715945559 663 249 999999767533500776 746 385 118452582 267 149 112710802 283 33 780659714 279 427 999999908467473572 656 791 999999311101154607 700 260 999999021247025648 266 321 43236624 259 281 891892310 834 818 817679208 423 80 405213177 267 244 999999408536316790 546 379 999999637705960937 118 315 838315544 335 878 999999490741267558 159 121 862453075 672 546 747270556 634 129 193864440 397 151 999999944932689702 176 198 999999088055402596 467 186 999999450817173419 360 243 999999238930514523 528 549 999999933596669966 743 346 795699135 835 810 674135897 324 817 344128670 824 836 292681110 149 847 999999893555048628 631 395 129725479 424 456 376208523 674 362 999999225451406540 96 444 529996283 508 873 999999901675188686 291 237 999999298125494681 458 523 999999787096914267 35 663 999999268161976648 307 691 999999960279515376 300 869 999999846520115754 467 505 863821452 429 241 999999109017779240 794 904 660313196 830 662 999999407741277042 672 19 999999461429376172 887 134 944595415 412 773 474609944 96 633 848150640 483 765 924884846 511 840 999999001020133102 156 406 999999881980125972 8 395 999999580549190181 631 217 472606270 162 423 999999900157095185 305 43 999999432881027664 456 659 305551822 107 538 999999912790428251 443 713 912466304 611 672 465709691 595 152 999999267745280601 746 410 390773094 98 888 999999143842825227 560 109 999999804017949881 841 656 999999782352174181 786 496 907256188 783 295 249598020 667 790 25254471 74 459 999999034470008383 904 529 999999662074877317 666 570 828848549 647 687 330789917 866 716 999999912214578909 816 898 931574155 302 460 574791571 460 591 999999270264971820 352 795 295936768 557 897 999999385904923070 218 376 106595319 58 388 768448741 262 353 999999175432347449 21 640 999999114201164486 249 439 999999490691747669 21 212 999999187297563315 658 427 845182416 290 560 999999883947636841 297 859 415779728 142 211 157584397 678 426 999999115811546360 223 406 204408478 537 196 577887625 430 225 456002435 396 426 949707007 835 414 41213774 863 35 88238471 641 532 999999525495576752 287 533 999999192670184626 92 166 999999803284849471 166 844 487025273 476 608 176751184 633 181 871789078 884 452 469200950 844 5 911336561 893 579 999999250566964947 197 538 999999508002131647 37 460 405551494 394 847 999999809286973685 86 772 999999725591750584 869 153 322072839 427 39 472312886 477 797 405511917 213 436 999999025072881170 693 642 999999306767338663 766 762 483084601 691 696 999999650492546379 755 80 999999725515594762 600 440 83985058 413 221 999999395115607182 704 361 999999243322064434 671 311 713922280 769 710 999999261814948730 853 631 999999787974530385 725 136 727428067 397 10 95396568 139 655 999999457001998151 24 814 999999285658176013 651 861 999999011762063694 828 844 583923059 887 467 999999772646508949 689 715 999999459634601228 889 691 999999215132638156 138 449 999999528592317309 809 903 999999598556182670 375 636 72540829 252 738 888442009 299 432 636614221 362 67 875400330 804 257 687826088 769 468 433466697 531 518 969714041 269 838 999999296999109301 331 199 999999024378280482 320 615 144086849 523 643 999999274488111602 233 1 999999003119562843 75 722 410874114 236 520 248805563 521 204 945225541 111 539 426732398 688 144 79053616 122 378 851466818 153 844 295813139 271 85 206409659 363 579 390436843 604 214 611019415 687 775 605086435 305 468 999999646095230888 388 201 999999101360485523 605 326 574002897 20 186 834824664 712 895 999999594240452279 309 709 731026904 542 764 697084100 27 307 324901730 901 634 177998528 235 77 178634165 719 580 191188389 655 775 999999760774358681 653 822 999999306805349588 311 804 999999204064119717 739 761 973574892 543 615 999999177766680820 799 660 185178611 880 519 999999785549578484 653 866 999999130739983772 799 376 999999677408648103 353 657 723212213 13 225 383736386 295 787 999999450771219363 567 851 296959109 346 236 999999824885998346 715 554 326552063 685 58 980703123 558 6 999999752281541233 725 236 355149477 397 164 458798287 286 643 999999056626629950 560 656 999999360931690518 696 791 999999760289974806 723 846 999999624712274445 426 80 825115697 42 624 150609423 625 120 410786297 135 802 71724931 852 568 646512362 768 721 999999033230639122 556 191 871278281 211 66 999999627185002297 322 626 999999969626064067 889 158 999999170665239181 497 594 999999521144815634 103 319 754511098 276 56 999999879954057792 104 652 963344613 121 110 999999906897916922 216 496 408145816 10 773 999999989680051723 764 404 999999950045952336 405 312 621711336 666 851 443060257 122 62 999999039351954513 714 608 999999651900564634 652 811 906753042 201 473 608667514 157 135 609105812 148 312 999999102040520210 757 508 311812265 348 134 664638652 881 659 999999856644489605 885 871 999999886821609839 529 592 756473003 491 55 168196841 381 848 17733827 155 475 999999636854886331 804 400 634233115 163 846 999999093028643520 338 196 999999124747327009 393 18 105950676 608 494 999999849194243042 847 129 19855509 687 620 999999916752244881 883 824 306660637 357 314 999999604163479839 588 218 999999965434872375 354 592 716666858 578 857 999999008897928629 539 262 999999740128616182 805 750 999999369302723831 242 200 479593922 298 80 622841056 852 323 999999813978693381 45 763 204694472 489 388 561252770 108 558 999999291086438078 858 95 588129403 798 698 999999808981242699 753 793 906486221 366 712 582277260 767 323 49574544 239 728 782827995 64 593 338616600 817 636 999999631416939238 595 643 999999146831322443 648 278 242505496 874 464 399547664 268 309 999999460932177520 153 903 999999989051202631 490 622 999999301628145653 816 197 992340575 551 790 266215060 273 589 941327276 859 148 797858221 564 790 243782001 103 316 700602663 515 580 197148302 713 532 776929217 860 184 18976596 562 863 999999762753395724 320 535 721594555 522 505 999999566575458955 294 229 52509406 514 319 745922717 328 631 178194951 395 125 999999266559848031 48 257 999999756264679573 875 333 999999844848076423 281 599 999999474071514152 626 647 184901397 362 438 398871494 40 24 999999623124632677 254 599 999999675260556754 144 65 999999317357528586 670 168 144093567 406 65 999999434860770226 570 21 666351735 596 699 603726669 560 334 276018078 248 346 664860341 846 673 846882117 658 393 801475927 361 93 54597567 793 187 999999215247140110 899 299 337270038 72 8 999999034562539361 138 872 984169821 586 99 673139093 3 237 999999292403262751 892 520 535705845 241 607 999999854209029014 611 707 527807549 73 595 999999893324774982 273 377 833262038 146 653 999999062318344597 2 164 999999326212623347 799 302 999999751506559828 400 871 716392715 573 700 39612579 440 215 971563787 897 278 193194208 96 502 999999655832719347 23 737 999999812374959782 112 16 322516835 31 701 998996773 93 427 535926860 271 343 999999590154774085 202 280 999999678382916904 817 880 999999719020211759 795 818 133403696 139 37 999999973566046684 88 1 999999758782383171 4 723 762610653 667 204 707269311 19 542 999999475695359646 265 354 999999202069752498 59 879 675761029 506 620 999999193108749087 593 123 145749462 796 525 659043409 326 432 565654728 484 205 683283518 39 801 999999796243560058 819 193 999999205576625908 737 522 999999704514744072 54 786 529033743 676 549 999999964843449512 403 292 391337852 330 220 999999416933541948 352 628 639921399 192 456 888470106 446 832 768444438 32 615 999999285838026180 545 475 999999908675953517 835 609 630053145 667 677 999999524511807429 124 213 109145443 703 869 999999354709190678 435 66 999999566524112685 841 434 800943825 89 687 999999986981685306 230 662 999999717946292254 284 640 677002657 147 892 149796405 736 134 999999550677053418 91 450 999999982127565484 875 112 440897774 515 326 999999991418547302 869 394 999999032663780421 576 25 999999217150735452 59 816 449352290 16 313 989200193 288 227 454080431 895 881 999999020404101555 169 287 999999800700363434 745 348 304898563 486 719 999999332848340792 816 175 892011891 570 691 999999976439720332 769 514 999999160234650400 160 585 999999063317355482 252 875 6006603 119 356 999999070834480559 320 131 999999864754169341 223 676 432674284 381 709 999999557858832736 36 24 999999568654134095 680 612 999999403277029390 365 406 104669860 740 611 999999159942952900 453 744 454903773 735 283 324852533 879 453 921559024 335 345 563473569 210 117 999999747886964596 424 844 999999086512178157 899 660 999999013435995931 566 548 999999370182670978 541 464 999999675168560805 437 378 880323396 468 313 999999392540349095 713 85 4853698 53 446 999999944678622686 237 365 999999707760581968 807 248 993862524 136 752 999999858757777380 264 421 999999241711314586 500 659 999999485346486844 885 435 706664667 674 659 999999686957146968 244 278 999999015385106164 709 380 999999517674699504 76 101 951121164 247 660 498585390 674 494 537127260 859 722 999999642843275745 104 703 645123748 370 386 999999022408726788 199 189 999999012074547536 547 609 822897552 215 574 999999075676530681 253 132 999999435910774112 21 86 999999435733692222 251 446 924113807 379 108 999999191338367202 627 285 999999105854053709 412 888 999999348053213607 894 645 999999129639142344 243 298 999999748368188487 113 772 356120458 333 486 480600810 289 58 155108323 668 461 999999302775678082 142 749 952402428 466 698 938687959 579 203 881683808 769 239 999999399227034876 72 250 977344552 664 353 338554587 671 806 999999070955283628 188 767 543073749 781 753 268604506 514 458 813395303 398 672 433106909 57 851 999999473800335738 218 376 825196489 304 617 403305656 297 135 999999358817428429 485 242 238645726 227 307 764457424 249 349 880895357 423 228 188816219 558 400 790322510 133 424 999999590806685629 486 41 848531894 762 873 87052358 876 503 999999063804263964 380 861 999999849446402321 329 679 507864285 97 71 664523821 276 884 999999141566417163 279 424 845667631 125 894 999999519686531799 21 893 999999169288900581 688 221 400971034 238 295 381279695 437 123 999999649768396847 195 81 999999655960468424 792 606 999999105488519825 396 584 63526231 212 227 809922731 411 393 581781022 387 207 671727143 646 228 999999588631107973 862 676 999999648085951727 277 284 310098987 507 212 999999812206597652 900 605 999999631291477585 97 393 999999423629182572 517 449 999999937504175550 759 361 877537762 223 21 129601613 184 116 992935966 833 445 534801031 156 498 999999732477547426 323 645 322657334 659 77 999999855736192629 738 232 139213252 765 477 999999686607791353 684 359 161877967 175 717 34431520 140 895 706126742 16 700 993512752 421 245 999999037127184358 274 308 999999469755073061 516 848 999999843065765265 691 419 999999162367718186 206 505 999999938381542478 183 122 999999259743935313 498 159 719003441 53 290 373189147 60 236 544699746 303 629 911413929 693 739 999999925223159441 398 800 95750425 390 29 466246089 705 651 418567438 571 614 878635880 825 221 999999988658346095 847 762 377437124 602 334 391159374 246 289 999999177952501003 53 595 116968695 645 77 297095775 15 91 999999733119445047 533 223 290136315 830 349 999999337264315373 615 138 999999696409558576 370 503 829878323 783 720 999999293229828513 765 791 677277549 2 578 999999395228975098 771 434 999999388105502353 649 791 301367265 126 90 999999224412192707 66 74 745201531 749 561 50633967 502 46 337243377 332 62 999999016808087077 80 568 999999224336813840 381 472 999999788147618303 285 354 999999685359778198 840 902 481577811 297 183 181972595 677 283 444672731 558 92 878405774 763 209 999999472815887492 760 574 999999681993036566 552 619 999999822410802413 370 71 493369980 505 503 999999112092079471 229 449 999999306618943371 397 653 999999082893435618 98 318 704252336 756 709 999999505167190168 867 800 87745965 213 63 999999521510647940 747 756 999999286936058499 184 153 999999280688066559 228 354 704169826 86 714 999999619523282368 527 65 999999779389346309 128 358 999999010208695396 171 368 999999466860496780 84 181 999999285218408784 636 33 923439095 111 829 999999504972012347 283 3 117942387 616 678 999999471395895952 311 536 999999891737118972 151 2 999999664530292680 357 798 999999810716233215 343 391 603686673 865 601 999999090886561941 297 655 999999353061232188 837 865 190458033 672 12 539739467 359 16 999999763345182732 639 627 999999936823236636 741 111 412166402 294 149 999999555108913475 607 354 948553806 656 334 412401339 134 94 999999562129114805 236 323 251205951 877 6 507267661 877 882 999999095172608618 687 256 999999780372583721 562 863 125182707 123 286 999999635348800491 40 590 871419680 703 243 999999531841712685 179 896 677247380 47 812 121264879 239 255 999999172753140369 794 659 279399053 378 733 260054500 55 731 999999777600556100 489 736 999999142660688517 56 78 167442645 495 211 28236545 433 144 999999348857226037 560 553 100426632 187 451 41314347 863 352 999999493208750859 370 420 788537273 444 46 326665973 790 848 999999936951899622 609 2 376314368 679 436 999999751547038080 786 734 999999888438042625 410 856 999999391840965905 103 689 999999968426770754 504 334 999999770088267348 191 895 89190981 368 176 999999157031052212 111 289 656114510 594 411 686079319 843 881 999999418777084445 815 85 141462687 536 354 344883877 662 84 47886111 686 592 999999291840381731 405 526 999999593312445289 724 74 999999010185018281 429 102 999999892858057207 200 198 658594056 632 647 999999573064423368 785 181 999999527300778691 383 22 999999506655151569 52 843 999999288870747531 742 337 698866123 400 439 235259431 687 606 762062668 890 21 999999018091062622 838 481 735924431 723 354 37182806 272 101 976991471 532 833 999999029848671983 621 245 999999125903343603 246 796 999999502506507740 348 842 304067556 741 370 897992380 154 674 907820356 317 58 999999414703011841 169 16 999999568807703290 830 903 999999658664526516 386 281 999999643852764306 819 381 999999414866655530 436 507 977417268 900 197 652468122 334 201 999999023778514600 857 59 321800943 741 363 999999124621302944 762 286 999999671299981536 803 652 999999683286187923 621 260 589152282 441 129 323029254 551 789 999999105410578355 507 295 999999013159434516 778 639 872092852 101 490 919889930 314 408 700520549 179 882 45587580 619 101 999999015327148767 741 558 105684378 817 181 999999265064271048 708 657 999999785012134452 866 223 960763263 444 606 927873923 811 83 999999601612663452 244 619 999999751322922070 610 603 999999394100143892 293 778 904260133 214 646 757630980 24 390 999999102526916628 180 281 466597371 798 527 929125199 764 351 188962098 102 398 598172975 69 237 999999578925537910 25 301 667796045 158 510 999999248731965185 139 716 999999624910200953 201 739 514087257 653 474 998068544 870 281 999999253878812556 464 108 999999804190119458 333 145 339233951 675 872 999999088387378586 5 823 999999326705072647 794 501 675797141 829 310 46474188 505 330 999999840375496061 258 397 247813503 702 30 999999701734104456 194 109 999999104451991348 107 51 899277912 522 479 435244077 601 510 683177560 473 66 999999974387767466 229 726 701380443 882 431 999999617178710564 438 506 317140111 459 784 999999475788859812 805 752 999999160040262674 47 334 242941339 561 214 975276496 598 546 801885910 881 269 999999278813949088 151 359 416269349 486 815 999999369212521872 435 368 342193207 831 177 999999317641115228 327 800 999999952435551027 168 482 999999813695201047 384 737 999999890145022649 666 10 22131057 329 445 999999457658506790 13 558 807609410 896 363 999999552433571562 783 847 999999649370188100 286 181 999999519925187228 872 701 999999514927674212 883 671 971106317 351 82 561735935 321 510 252264509 130 553 532510640 34 446 999999061240020523 23 627 238377710 902 134 999999391778943066 384 251 736174221 198 580 999999567765409855 153 266 999999193292395342 863 801 247669993 148 852 824710407 57 727 932285990 705 128 715110347 816 384 34719946 480 355 151809877 424 724 999999125534344535 563 315 333856849 7 165 999999440763697940 549 3 464633912 316 542 638764594 599 276 999999094766135135 736 187 999999354288468903 605 378 448257077 726 691 926209709 373 445 999999295576353993 532 764 344649864 229 651 999999761955945712 620 118 957284435 339 899 999999613159117269 498 243 354282392 618 897 999999992628562277 873 727 333081600 259 135 999999934139370730 234 298 199074920 837 812 999999523206142738 131 752 372340621 555 646 552514756 628 488 999999672218129878 209 357 243618626 424 685 651405938 840 817 183085178 525 133 999999434838357548 307 844 629927837 661 262 239821484 271 719 655989249 475 129 999999151456343413 608 561 861853156 660 711 999999420098177716 182 231 706122148 577 322 999999016422273213 679 700 999999814589006567 306 44 100486333 540 260 999999227017119614 241 861 198935511 708 452 545609865 838 795 999999392748048581 217 142 999999998993836033 516 346 469428952 346 201 999999728638197049 712 716 924184466 476 96 999999627057768584 135 769 999999502036577735 348 331 621602205 486 255 567429165 369 121 999999004957064805 652 16 999999426441909057 792 619 999999377270416520 728 820 896672834 254 783 999999991685788127 637 273 999999177458068461 267 885 999999975891395526 528 555 865069403 337 900 254245777 696 38 999999599211120318 411 521 999999987260022231 134 483 999999841390019344 198 652 999999040027542757 416 367 999999541069811162 675 297 999999556050663581 547 861 98731292 700 580 831429646 850 322 999999910862110723 569 165 999999060510776119 474 135 787216095 417 886 999999931601101647 500 737 919562034 341 255 999999641080012080 349 614 473539297 891 859 999999631479446729 414 426 425952338 304 519 636647621 273 504 999999020022392284 749 326 999999682651633676 70 403 999999384150602189 426 368 175277431 418 289 795716381 482 108 999999580631168742 855 304 306886692 15 446 999999018709342758 410 564 264600467 632 667 999999801213126607 864 274 682907111 302 574 999999614734466995 683 738 999999354506870364 711 249 999999614566170416 125 627 999999371311674300 474 382 22404033 622 392 999999311784947933 732 874 999999198417239929 392 562 999999385660104598 344 599 999999981089362677 313 671 287520992 850 188 999999541418970240 195 876 999999916971174778 30 314 999999900625502804 260 798 999999327895799225 181 659 999999562610957361 276 220 751057518 902 862 404019791 780 62 918494435 900 331 999999865897061146 230 781 608404415 671 899 912223251 322 828 999999051730120220 140 610 999999454464376484 46 152 49673646 344 194 186690175 386 119 223686486 720 424 999999358575230781 613 547 861374789 76 465 999999161420740937 35 750 887779974 814 101 901667795 239 797 999999014800971108 557 345 807736051 183 360 999999270912202282 659 580 999999062039955487 67 81 999999937587075646 625 170 999999378349406558 401 52 413870365 267 295 999999914105791669 883 844 445328144 78 473 999999105891095493 93 848 999999919630273459 860 527 999999973980452724 234 237 488337669 164 58 235304162 342 904 999999319579582746 356 530 46677899 747 46 999999940755046922 499 188 254596368 9 874 148493877 165 903 999999214407482054 445 705 999999782094021913 182 76 999999395734804095 145 354 999999039075464238 31 28 999999417396606274 429 403 999999389599209163 644 203 999999157542181366 522 786 999999357193348515 224 604 999999130947303383 579 580 963016946 757 23 94022895 855 160 383897636 880 859 999999988979275237 77 892 999999535789715877 363 731 999999194790894464 655 785 283785039 656 635 723366866 436 205 559389654 788 511 552916539 573 544 530160551 92 138 999999941748556642 507 504 999999653046426562 716 868 999999623505383831 283 8 999999096202391143 499 803 999999064211888091 409 440 999999442690439227 825 129 999999333884546387 459 744 999999838887181851 109 382 822796711 482 648 661614508 694 751 999999479644405444 256 766 987038304 622 487 110530180 191 586 908658576 257 749 999999676029777760 806 39 567499419 182 74 999999768586485455 17 24 47722554 381 307 75987642 275 874 237746631 219 66 999999515074557796 5 342 659985140 464 246 999999419392743847 884 70 500899190 474 218 999999434876211667 455 58 363621553 58 9 999999436322616949 590 697 999999047151590095 629 712 999999915707336321 452 168 123527757 483 289 837386683 270 225 999999153031732462 45 707 999999699442613321 186 782 999999226897027428 592 134 999999279164656447 305 116 999999344629708331 582 725 166890171 614 599 999999565755454877 740 868 843655427 774 698 999999665414179297 75 163 422491711 457 133 904382525 382 93 16499351 132 481 999999871019615196 221 310 358748964 691 269 999999596603190369 758 608 719576470 257 107 615934728 548 719 999999516907862443 106 646 417536636 861 875 497133886 844 580 999999358374301367 873 547 999999689868061256 309 474 999999881977045161 228 165 787889002 373 255 936541570 722 839 108333249 801 604 999999337350841740 178 679 494165192 370 207 573555014 574 245 999999025928451368 586 224 999999262031424548 407 903 514553929 46 709 924457091 727 101 901960770 530 660 999999335236231297 251 611 999999902060388709 819 129 999999883817397979 149 324 331342383 663 114 999999323338031078 744 189 999999220455350655 423 445 999999761944641450 85 273 662465210 115 692 606893008 372 659 266871470 370 434 999999696189237492 7 139 999999034497139577 226 236 999999787135390600 734 740 999999157449054920 180 210 105292950 282 50 999999284018380550 2 85 999999539477583513 719 802 999999994756174761 205 747 999999639723976423 182 732 680637062 868 212 356414229 304 199 989055236 632 560 423936850 698 538 176918710 237 198 874960361 468 824 999999410049146158 467 210 627475519 886 428 999999615577484535 567 704 935651981 826 417 999999951625982849 750 84 999999946426211210 243 224 83330540 113 95 999999905498614499 887 242 327961106 311 603 999999093214197460 331 236 999999462275223477 337 333 799963123 297 607 999999743922275859 666 362 197428941 186 539 537577089 42 748 999999812888887450 204 619 999999208214753591 179 413 687792447 34 756 378872373 284 546 244706669 227 301 999999091355635863 730 726 151142222 500 31 999999425171911380 664 793 367040869 549 700 999999934587674707 68 736 221639781 404 386 999999306678993836 66 152 867342533 84 673 999999864996060903 460 389 656688620 653 659 999999237767940013 117 126 999999176584573782 822 663 999999453067372640 677 228 27182061 904 614 999999266771797823 610 328 365310951 385 531 999999083810777403 253 65 841362931 167 766 999999673483219850 396 656 942630011 42 818 955612308 570 294 999999873419267554 811 230 716464532 812 577 999999063853780764 230 712 999999266900484181 800 863 273977584 851 239 999999311569520719 342 770 39218970 147 80 866952135 625 597 320313882 226 664 999999499911131301 545 866 999999475671601151 196 783 999999861803417082 218 866 135256886 597 696 999999269012456134 604 84 795443867 257 885 999999003224341730 546 394 969890690 61 236 353495187 216 656 999999764944981483 520 700 729720506 758 178 234187354 749 297 999999318465209148 481 203 999999598591907878 282 233 344281974 708 648 999999613144660809 763 281 420488851 501 170 999999322935262352 293 231 513209299 710 828 999999755707312759 418 204 718659735 879 244 398759949 695 771 999999696062424683 803 555 999999952909147380 628 795 999999166000960859 410 877 570364589 452 131 999999584822920060 445 606 191841514 455 358 999999284743950276 829 553 263870818 177 4 977160218 269 251 999999436233623634 561 867 999999791482025468 722 580 793756640 418 820 999999245840405314 423 682 975960151 528 609 817615831 6 555 999999669242988087 7 657 75346922 98 206 999999577767689876 362 829 999999261321219488 12 824 999999519871725816 297 565 712499494 25 487 442115491 28 782 999999260627029034 902 80 999999741058351830 185 607 999999773854171116 835 853 444225412 859 88 981350485 2 300 999999016196138286 38 276 904499238 611 885 707243063 682 336 677690983 187 379 999999406418652126 509 744 707829015 538 700 999999037405822877 657 584 190727252 159 192 280573847 460 259 543955674 382 763 199634884 33 506 157257646 824 464 999999434600255454 122 767 999999669296137689 869 5 999999903430221530 811 877 886974965 310 678 124753666 26 391 999999072770567953 554 785 742274745 5 310 999999892110635333 58 66 556983536 668 877 754668548 204 886 622177100 748 650 303610828 715 129 839853487 104 62 999999850986181698 182 714 999999264998573018 416 262 255753621 654 119 999999997931534381 17 717 999999381088862424 680 489 999999811292862585 424 834 999999903925209764 570 320 999999697269103299 272 173 999999762044651858 315 698 999999500577314926 678 303 510590568 641 894 539044233 540 525 68392552 264 601 999999031400417877 471 794 413198203 502 868 999999839235872808 81 625 999999544687921268 754 438 999999719719664970 15 38 261178036 56 395 130049694 269 417 797944981 732 330 50524618 371 509 135271169 119 419 764381982 324 653 549942231 719 273 965699684 607 518 701542260 209 824 999999305422790785 160 846 596119349 571 306 999999147786906786 670 469 590450461 466 258 122861025 132 671 757257448 608 789 999999386507428690 729 791 814356504 126 455 999999374387578811 274 227 926520248 884 112 999999869206057316 737 882 969322984 334 77 999999862439694430 154 301 999999181849197701 401 875 227920272 729 549 999999691236278689 892 652 896902146 488 62 999999457773463429 724 555 999026736 849 237 40396208 48 202 999999261744794385 52 210 683232889 222 152 999999694925163400 464 217 938273294 880 883 279615522 205 755 476781069 487 227 999999118220867820 662 786 298736502 355 372 999999219980387243 374 656 999999006094338405 318 798 721586529 164 345 999999840967480552 451 60 999999838661662213 439 861 999999070259449254 783 275 999999896671582883 336 266 971672432 169 738 157100711 413 886 999999200095994217 519 32 272190191 761 802 999999195504697934 877 634 711365333 382 774 6311338 752 255 999999624406842732 521 674 999999677190414423 339 839 998569515 892 550 999999340238349784 305 694 999999372993329045 550 438 620007073 457 486 874438146 503 818 114458736 179 8 402221766 401 559 999999366430648692 129 580 999999166624145333 613 471 846262956 830 262 414666714 803 108 999999740691206241 340 91 458394784 86 757 999999183962811165 84 482 50127487 275 312 733209916 99 430 246956389 115 789 999999366591024200 877 875 999999225157283280 766 2 999999674247026191 211 687 716557684 655 838 999999415540398173 267 277 306970327 470 848 444443567 102 622 376233418 73 253 999999560563461292 587 112 528828916 217 18 691818782 296 473 168157483 627 176 255863115 293 711 999999174931915513 728 515 141619950 114 611 25266276 556 755 78511448 752 223 999999165107430431 101 786 226554792 379 709 999999297551981285 403 222 306549880 300 550 999999689167632415 155 579 999999309618130486 310 768 628046117 179 573 999999046642802853 160 126 420639871 567 91 999999258114643746 136 236 999999607773765273 233 139 999999017654443530 657 419 34437458 52 117 999999306584290275 106 45 999999171354726184 832 710 825426693 476 892 999999314501618812 446 77 277384620 127 516 999999404335982673 772 159 905020383 260 132 999999461050649476 706 359 579779776 578 323 999999069232529820 878 118 999999370034556300 142 637 999999634396078430 189 844 999999911838603174 145 58 258692710 152 717 999999066223605545 828 560 240960509 256 465 999999549716011809 776 258 999999196762718417 491 502 999999718407856909 709 668 779886311 117 880 851742849 43 357 999999956204160149 782 593 999999178470171980 670 301 641948972 836 129 146782136 159 618 753480937 170 459 470108575 617 773 999999455186302722 223 630 591053348 806 819 631692712 5 787 999999899779070010 464 107 606769621 886 65 999999176401827026 890 752 999999862551190435 469 772 536059549 540 120 999999423665444214 890 715 529527701 684 353 999999053462431648 58 268 999999070359170900 473 199 393319757 680 734 815619468 290 638 821262917 793 389 980626548 565 214 206226191 434 327 512376708 136 876 258072270 871 778 904431679 49 221 835312235 494 903 999999057754430269 108 178 999999863061175197 637 768 209206800 152 363 324533374 650 836 999999516203507061 852 83 999999496294168615 666 577 999999971490533325 415 250 872265228 211 836 299700536 635 794 999999105026374156 292 211 556548272 261 509 713647335 420 304 513546974 542 373 499976898 661 850 131489305 496 652 553836944 688 564 877218690 840 607 999999059399736691 525 881 999999656024875760 367 88 665696029 109 575 999999731776717737 94 432 567358856 26 631 764329585 583 657 999999729864858376 539 510 999999599241530539 724 328 950544686 775 633 429695639 859 506 405730101 848 634 569371582 712 745 653968557 44 176 153331426 510 549 999999811078150385 126 686 999999061045482424 486 129 694723959 340 45 717822081 861 765 999999432645585424 373 717 999999441911147049 181 170 961825009 194 237 999999236755515206 486 864 962679147 435 346 999999165346908595 400 370 715789101 726 113 999999342653887603 375 328 599900858 247 876 47942387 452 167 999999000749452970 581 689 999999440575866175 95 515 72135179 564 456 999999275331588456 263 203 674224659 502 460 999999688633950858 607 456 706683175 453 717 545796248 693 3 999999581964232805 903 599 999999108065203030 100 801 999999434236789118 498 110 999999754384271477 411 632 868475795 744 580 999999061560429921 143 814 999999143736028555 51 763 999999101821516259 83 26 999999249324045147 350 440 999999109632905652 624 522 999999395822268966 304 307 999999000708571356 347 333 999999075268622648 607 889 999999506670875789 797 871 999999034157831889 324 898 478996487 235 755 999999795864233062 448 384 755749887 821 266 999999037697555479 308 190 999999514895809535 473 206 999999131958358623 387 419 786325447 232 565 999999061477308591 423 672 999999863661780676 623 274 405330316 146 674 999999891349051274 681 678 999999300417479054 249 114 699821197 808 354 878890217 539 296 947685675 360 59 999999160169916256 202 283 594674307 339 303 929975575 325 125 298740510 889 783 999999335342128144 409 401 465532256 461 219 999999761927033938 188 50 999999158308188125 835 16 245754331 637 545 542922571 337 884 776047082 707 81 999999495036844864 681 107 999999776328212667 403 725 999999294095318913 61 208 999999469199781841 150 281 331228753 617 467 661897506 793 163 50797111 508 668 999999860049193378 77 63 999999446193675002 767 159 999999285948322935 497 884 53266146 789 687 999999632376895737 318 719 731038749 721 859 439489221 575 701 999999912313223797 83 819 582964683 895 657 768360239 351 845 235068258 661 798 999999604525769958 491 258 999999389711049163 609 580 973120119 405 519 982619077 236 183 999999349301250867 75 181 328352707 85 634 354604705 896 390 999999873154926144 681 504 999999321366397538 506 459 801235955 458 471 906483125 428 373 999999850168847065 30 793 999999029493144104 212 846 999999202926004019 39 719 999999588481421012 831 820 999999695662818691 316 652 999999592843700442 330 595 499879054 730 266 537719809 115 844 856129725 372 571 36676162 475 776 999999736389237357 62 485 999999456402996067 636 173 541404106 826 203 814135854 294 51 999999224688937572 449 895 999999878558234792 750 735 999999643884470326 252 347 447118186 124 834 849089276 214 894 77685737 561 807 999999598437588667 474 73 999999964137488044 512 763 999999915445110741 698 679 999999766760462853 465 225 605005930 505 97 999999701508634291 137 440 999999060301507167 718 732 812599587 87 623 839419769 461 269 999999190127935186 702 693 604749182 789 505 772834517 844 563 680693549 888 510 715267670 43 815 55744093 33 470 340978463 513 886 165515894 553 501 687239769 276 338 999999643016661562 853 307 999999875434615205 777 583 782561646 68 589 999999041869750207 231 393 600907480 321 748 985385008 534 696 999999561937284611 629 468 999999334677472140 842 732 691376250 785 324 669024808 453 845 442736523 830 671 26626814 740 384 999999814793088989 378 323 393505344 616 736 999999567043682306 492 234 413204872 186 820 14411754 128 184 999999253411952367 207 447 999999133052417670 584 170 848170692 663 371 549125968 480 337 730678603 666 739 140305186 897 211 353122150 216 679 795311526 544 245 720856217 603 322 999999551206933682 568 108 92384112 106 717 884529599 601 328 558240739 48 756 999999620134424844 822 249 999999700427426367 69 757 183403387 848 87 311644602 299 495 162405179 188 633 999999446888509210 189 548 999999828287715494 653 323 977434026 330 898 314914878 625 456 484662609 779 544 999999050959082243 16 78 850530349 867 356 999999724308992655 87 532 142805751 141 646 521040210 740 711 999999747503441194 619 436 71700812 72 435 328249581 824 263 999999147791382508 655 740 999999761833698554 223 651 394824839 408 757 999999836617573562 389 708 631947455 537 249 156180930 767 254 999999281922583559 622 470 596821934 625 676 978147890 720 285 999999149401661193 736 138 973260139 446 475 999999740175080617 317 289 999999674531228743 626 714 187588927 258 438 185465535 510 79 567823262