925 996 1922 2092 1000000000000000000 153 249 158477878 127 780 999999103141917270 213 791 12394203 446 425 929113001 693 871 17444055 203 20 199287470 892 992 969188013 95 147 644288333 635 597 999999092381355921 647 184 680441693 352 566 999999640208938563 538 370 474390029 434 849 338952564 362 490 999999045705339121 882 330 999999721958600626 906 372 517078548 482 609 618724020 775 643 252879957 358 698 999999272918800479 18 674 677059765 924 524 999999099221119252 988 839 999999357867402787 262 747 127123424 520 831 284951868 99 215 999999545712367903 743 740 102916326 332 909 999999390462544530 507 245 682612708 648 651 999999229726313103 660 874 999999090994438866 54 372 624767112 254 774 999999669256821374 750 812 999999016386202037 283 106 999999937422754998 22 532 999999347648674619 536 21 999999289568184907 656 860 999999390267402353 116 739 999999360765578694 29 725 5836294 73 477 999999274416671872 930 524 999999934715610429 337 293 999999419268288236 101 296 999999092822670587 696 453 999999355977065005 632 644 999999918504850537 305 624 999999202805194744 413 289 106003571 825 864 999999398434264941 691 408 494951202 521 252 365395984 24 681 999999373001557040 975 501 352715543 868 396 999999812831260470 354 31 67981901 983 423 999999107026201586 919 593 999999315219322625 686 635 999999746229821897 580 849 999999400075960506 702 257 999999175845981927 484 102 253304401 874 803 999999540119340812 187 63 999999597844466981 601 782 900536837 952 483 272847472 363 851 123535132 426 549 614424629 963 219 5604284 612 422 999999157428620031 44 64 435406471 783 424 999999727862366848 969 856 108236897 404 14 999999357453098508 818 449 297495186 949 934 999999189440773420 968 395 526884958 110 2 288045304 510 174 176202974 545 772 545976529 806 243 999999241275723496 13 175 999999512686255221 252 969 219412405 683 577 999999437154736029 89 307 999999530013128201 711 856 554116863 774 674 999999570562014777 321 942 64938763 421 836 999999937976982434 486 309 916965386 276 649 924718803 962 908 999999656603110549 259 293 856557859 98 944 545583030 502 902 300123002 190 363 883985391 116 677 99207891 874 216 999999743771682845 238 929 999999688715085676 417 618 37874739 820 617 941381769 649 1 562593765 92 513 668346533 467 452 999999253336760121 495 603 856717992 340 573 999999986957146609 319 813 10244835 146 784 650720378 205 515 999999291613244689 467 682 999999081076871465 250 533 207324744 913 39 938672135 715 974 656656265 991 858 999999786715724519 776 910 999999269773216780 398 993 326340621 615 408 999999464312366785 887 479 999999663411799735 846 666 999999697499622238 291 595 999999820470649561 488 509 999999062737254989 505 770 999999319908325368 450 80 283513541 64 616 556781273 308 436 506047460 806 305 999999898645380486 988 657 999999039760762204 629 632 999999251914755970 187 116 999999834047495728 76 884 928359780 664 721 999999058668164106 618 86 919175569 184 77 999999420452688996 69 304 999999930491838267 987 219 106572241 934 813 999999563852889856 304 344 996811713 834 374 49728079 836 346 351864256 815 833 805778986 643 705 264064443 40 463 999999991677357762 748 30 999999826309376527 950 551 999999900766209795 821 853 999999835000486327 986 176 674180428 34 775 999999586155824384 803 228 783993439 780 298 999999966815572815 4 288 999999939368474595 122 796 212749113 178 747 999999204867711393 363 549 699965 663 343 999999140702759330 382 623 843981399 221 616 571017774 289 674 999999127494909645 216 664 506114703 116 67 999999382570586629 527 983 242101653 608 350 999999499955831147 914 607 123580067 17 642 999999676564725815 276 306 999999369753170182 729 874 999999851575173772 306 347 999999452385654091 766 769 999999060685421526 1 176 999999620705443440 585 947 728351381 381 217 150159339 85 168 77609552 239 95 999999171420424080 504 760 999999830289900596 870 50 163465641 968 365 999999964760715466 825 836 999999469288504103 937 193 999999536603630209 676 762 999999059975127867 326 434 999999025111793113 190 110 999999349206625627 911 973 210258984 499 175 999999745697688102 845 146 999999194532371995 710 167 341221578 255 19 3293637 559 694 615877721 584 672 999999192445926586 641 970 999999661432609343 197 745 999999331822316212 95 884 631261841 701 960 398407433 331 772 999999134650149202 604 331 85643313 869 10 999999329273239933 129 29 999999875460679301 977 537 999999412070531981 790 508 114155332 422 633 999999829279454817 106 52 999999650142397565 927 777 999999604528735392 279 345 999999526043490628 561 222 999999351815978112 579 466 999999580723344208 641 751 876872116 105 177 999999614915237194 200 488 999999316438917538 179 48 999999064048868310 908 868 793606737 648 526 999999230891235709 288 672 999999184306530852 649 71 649710230 400 502 988796883 274 203 805182821 647 806 245737869 204 844 999999795319272090 835 56 330650704 7 956 999999558771858832 701 589 999999589835691050 898 210 358626039 839 749 636478732 49 383 999999738116526842 382 228 999999135199792872 189 483 771839655 638 304 344645659 791 594 999999166324562655 320 503 999999202560492231 344 776 122082113 612 731 406951491 268 911 999999758582423005 567 922 638691030 723 522 999999585063266820 767 866 999999275750115627 991 795 999999588653582992 531 595 449408009 806 726 31735081 683 677 258569629 55 814 924393323 693 745 999999124867803224 935 782 225683441 881 861 175294055 652 138 999999044739263289 433 629 854081771 713 698 998174268 496 713 960359172 491 293 999999603133913925 872 388 999999934741036919 251 75 798720045 335 451 999999716225475710 408 453 999999063967121478 554 284 667644773 388 266 999999352493023101 568 177 999999593844677305 289 746 737567858 262 654 386036523 466 284 623170793 404 941 999999343804965641 159 411 602535756 277 199 999999922708303588 629 873 999999636015358545 828 882 987288438 5 282 999999093086078114 525 621 653706511 601 574 753188912 197 102 799757927 854 819 393244289 53 575 361123355 203 142 999999924189158729 491 789 999999516772013768 369 736 110779061 255 795 131051901 297 919 999999978777675255 915 221 999999594435360182 100 57 999999573881293725 524 626 914084973 971 774 221272311 219 487 441918778 324 898 999999606828640533 624 451 999999758021625795 873 180 806953977 207 405 999999015239487070 524 648 701410183 809 864 516550020 745 609 944595957 828 857 82555495 883 593 425437183 135 729 454510674 766 773 999999895827808749 217 14 999999386508272230 193 410 999999226319696488 138 889 421039173 287 742 287613889 899 459 999999843224888578 273 802 368139267 106 254 899937188 90 375 357563004 333 914 999999127216990377 416 833 999999963176556897 422 400 999999846815763598 826 481 999999273847027675 179 396 291843808 48 94 194727774 92 268 999999706550625051 94 912 879142135 212 309 999999440443704969 187 360 999999048405552369 294 255 260333326 563 201 999999877824860882 827 678 999999670382757567 852 439 999999756419840404 661 626 999999218626417121 639 481 363391983 862 505 999999739753429121 476 911 195144411 641 475 904612115 404 199 303559419 466 451 173820759 943 352 999999468895400333 916 18 676002923 10 668 148324346 6 212 999999312947882094 861 848 322265963 125 221 999999857877305005 257 795 869775911 436 659 586024063 851 301 199973417 535 629 999999565509132551 38 748 999999712275283353 23 455 727704683 507 157 319011939 98 874 999999973568968225 815 211 999999159740663397 923 774 999999743999793183 317 299 999999092863564148 917 615 949362624 457 453 999999457025460226 36 33 301354002 643 901 853565484 529 923 99641237 718 946 999999218426280036 58 53 999999510295023908 918 21 467685577 409 164 974773012 907 714 999999453822127820 211 533 999999552444813557 892 801 999999206029034742 250 141 999999174348826560 590 172 479527056 700 839 135006334 489 141 999999779173544862 202 327 999999551785079684 381 70 999999753390712781 900 126 999999627955866754 886 665 97064799 126 162 999999241484186622 595 373 432518022 906 445 999999018564345699 716 200 999999720526089430 71 337 307360512 546 851 968283318 345 751 250197051 963 64 121135263 215 478 999999360333012796 824 823 999999482397386728 922 132 780798704 606 503 999999598308878037 610 163 66657290 266 904 880340767 147 204 999999874420615117 230 818 999999735177486140 556 858 999999343062920257 579 747 547122999 842 583 999999536989573989 692 729 982995271 407 847 999999349866411941 968 294 968624889 965 357 207414251 730 759 509623822 550 727 248439204 183 199 267181020 824 782 999999234024475544 628 9 999999507237477144 670 677 380988561 452 727 806193020 884 567 890825507 110 172 324443596 129 411 502895069 757 483 783064582 147 117 999999389218789376 704 445 85416894 114 548 999999979173137595 718 738 177284085 489 108 999999460312072748 144 277 51317999 512 848 999999653564877325 386 42 105109756 716 662 999999958980129302 9 947 366210987 9 258 999999277197412546 768 926 999999288832902467 257 334 484153003 966 453 999999622024490614 339 419 695214967 985 845 465331672 544 396 999999940006303882 11 354 999999954100343134 837 294 999999153767405003 213 872 999999357484782621 365 226 999999358469119951 241 485 118706622 350 794 131059766 110 161 999999817687795547 304 256 504715153 927 94 999999530477914827 242 398 72426798 738 150 999999657229704168 878 276 475040111 338 824 878578330 256 940 318681104 249 76 999999490711973832 475 193 41976092 689 363 999999414357083608 77 493 1835819 893 519 999999933727518591 92 923 999999310703703866 213 985 999999090111796642 543 100 630753232 967 662 757043910 166 324 999999115776917408 179 125 759538148 674 654 412636759 461 187 281083304 667 661 999999207017375937 779 23 999999570722352389 915 540 633186402 171 673 999999699809775313 347 243 999999694621575059 947 985 999999748288950501 974 402 550374241 942 323 999999222411458936 115 759 423068518 748 475 400362845 264 839 356557655 16 538 548465211 29 14 999999136446959730 470 430 999999190775043798 230 774 908304349 727 136 529034927 265 436 999999083327826033 367 245 782034865 341 346 999999648004698488 299 228 999999007520293301 147 394 999999108610771755 784 795 544560235 699 925 999999294123637561 594 370 968960509 493 106 194578762 790 945 999999638372935902 539 614 999999294596122848 227 948 193132204 176 678 106486931 581 619 999999828192653482 408 894 153102058 258 406 999999857197778153 512 267 3783700 863 447 429506088 59 72 522467411 189 920 999999938537302576 817 738 999999487697215385 66 732 999999926860412657 939 449 999999512115468460 238 98 999999648956731574 255 836 999999526491288048 775 564 410832339 281 628 553991378 52 495 44935070 61 908 918239200 606 57 728882085 865 684 999999823937125932 195 764 999999055068008523 258 743 999999750199963633 310 641 999999448706635103 933 208 747437221 838 34 999999600578085329 514 549 389200023 914 354 999999989990204171 926 743 266299492 759 784 460624406 334 468 2471410 534 2 175951199 312 54 999999372390518547 763 784 999999940479385785 286 6 999999042396065085 627 365 677277430 978 841 130661242 769 141 536859091 158 947 999999369404902064 721 31 999999553326728503 215 609 636230675 315 916 539630472 506 782 999999608533040075 243 235 999999245763589592 172 870 999999062612633031 256 132 999999935780051094 864 533 496447450 398 748 60732423 74 503 999999662828742167 651 868 999999043026691078 42 188 541473682 67 359 551464388 985 324 999999474097140865 716 60 999999213795509626 588 746 39154498 865 138 999999975282441446 789 284 999999590000716140 69 254 771846262 417 856 999999004280876601 946 407 311872879 514 632 214445913 509 430 999999795102572019 835 996 999999283003501671 453 784 182583562 92 112 999999918580361866 219 136 999999882141288176 97 464 999999556062247149 501 732 295692446 922 505 999999751289659783 266 565 999999212524829384 955 889 999999180213368834 632 63 999999106668684455 7 109 999999663658684028 137 401 337040526 169 202 999999904351688184 54 144 999999392891065162 192 495 999999373771725515 52 288 292345192 905 121 999999479514427614 607 384 999999394108393071 994 449 999999143711700143 562 264 999999463529622417 431 674 999999729404248968 86 677 732883280 393 892 999999504450189579 290 124 999999626357996335 991 475 999999555855812817 921 687 86025146 422 775 596928516 171 824 339453685 353 107 999999463114721053 937 196 480964821 848 864 999999786825188905 415 281 716212668 120 226 999999867302233463 82 638 999999653314132267 826 604 999999462513646511 985 638 999999669496228413 576 603 177521769 181 396 999999121200445165 990 943 330536883 531 256 999999920427969156 191 496 999999678152976742 269 834 999999971349685165 83 720 999999492320589846 869 384 999999708743680463 322 236 999999531592793367 629 874 694453991 386 830 817222764 497 567 565174864 725 887 999999318755171782 761 302 328546125 256 361 905669924 484 424 999999847456118986 503 288 65930036 809 741 817304495 403 840 519080681 126 827 446738218 878 629 217684369 482 743 999999211511850472 362 235 999999303706213531 183 456 171382149 75 228 310031628 576 694 91958282 547 524 576228959 97 229 417360536 981 300 999999164072569829 511 825 999999720460210660 811 315 67642983 399 450 999999050604833285 299 743 999999701015506853 866 621 999999561547540219 304 554 651553260 596 497 999999478521412995 732 839 999999911786069979 336 449 999999244267922183 257 46 999999214536412724 530 593 999999035070244016 29 198 999999503208351150 415 3 999999818884144504 188 931 999999244359382415 351 947 999999747194848967 220 541 582871653 700 826 595818542 195 839 999999958632181480 462 466 83379745 2 383 95750963 802 44 698024010 379 55 999999589589193270 73 871 549491659 70 284 87531429 411 9 534572575 262 548 999999208811387384 389 726 831660111 489 995 999999216958022163 180 349 999999328117139491 812 543 999999780798793414 533 626 999999047855670014 447 476 999999365637352684 313 584 393679179 698 577 753198075 627 51 528436283 16 431 999999058137668106 597 647 999999134488910347 316 976 999999777717675398 55 324 143598603 888 824 866345486 297 869 999999878652178255 288 221 999999185593763553 842 248 767162158 400 401 858871246 64 756 281500118 637 298 999999770250572570 862 884 958154495 706 566 761500331 860 747 270689901 60 602 999999576744831625 370 225 999999778946865336 214 302 47999154 849 425 999999122269671641 967 962 999999028247967155 570 704 427246833 538 780 891288673 910 46 999999162244023579 139 349 700970746 573 162 999999329798167383 101 91 86732426 808 640 999999702038475173 47 36 747843092 943 469 782874028 223 272 875737718 125 40 999999935770286243 770 923 184435251 579 584 999999272715374528 587 679 999999257034425416 645 637 999999663600373535 10 638 292272127 239 754 161593234 687 111 277982129 537 721 954123410 200 337 4456774 786 922 171056921 107 791 588825777 561 514 999999371173445319 656 438 780986248 743 325 999999419759224288 702 432 999999810926574672 516 38 999999458813248253 709 108 495541940 726 668 851586446 209 14 999999918107111193 406 64 999999518889257761 680 727 999999751780605388 936 387 575168067 912 968 560631117 117 871 999999264873246522 626 784 999999143296036454 641 873 477028654 175 227 339852834 652 441 802836618 625 253 603317987 555 948 399231283 93 774 999999907182589338 797 562 999999007456578179 57 23 377072344 131 602 999999332136696930 128 978 274964983 986 227 999999088152041369 492 827 148643433 722 487 999999152774110412 347 341 999999749939867250 798 456 249556686 856 615 999999943577052559 423 190 997123105 651 473 999999773927787349 750 46 589709836 919 465 999999656790779889 585 470 311639864 726 537 999999630924693717 442 637 798784681 919 696 751879802 615 694 451109275 54 687 999999048054169749 360 396 999999063705185189 783 698 10400653 740 626 955051369 369 559 140763633 522 775 999999223083759521 340 868 839585963 267 675 999999754773450473 3 370 999999293253379112 809 543 999999936088333701 802 668 18783415 602 503 999999924158793162 150 886 513687915 204 481 587476854 603 267 999999047686369532 57 318 473387121 583 38 820638263 555 158 241265381 335 799 168735944 468 360 70035144 62 849 999999718198003251 922 144 999999815317999591 895 682 685489292 526 83 999999236298268945 224 747 999999473988345849 577 87 999999879204728114 826 409 387995008 504 153 999999731836405711 307 346 152786734 925 44 28205685 966 881 467635417 847 858 54092824 397 660 999999646774736625 9 200 999999475309053791 909 935 343395714 575 847 273001996 709 521 678094293 540 757 999999884570351624 662 14 568809824 530 533 999999510550263772 632 253 999999706829420460 160 60 375347543 50 621 630665941 639 409 999999803470499894 784 674 999999478903422031 540 443 824886373 99 666 105758344 572 777 222711637 326 310 631244817 502 478 789790837 342 585 999999993393403009 717 141 350903240 972 873 771183474 918 146 437751589 853 877 786822368 646 858 298102825 795 903 972349448 253 835 581008073 558 795 999999260008277608 904 995 999999827624086412 317 892 759919708 479 575 53458240 164 325 699155353 490 189 762169388 843 692 999999016149008036 418 381 999999100729868004 741 642 544821337 588 219 999999795958136326 838 199 371607682 150 953 999999976697501793 872 701 268124422 79 464 999999718069865547 684 401 485930675 827 400 999999516215305744 791 303 16714375 927 981 999999268150118705 150 845 999999965642244071 904 827 863782982 841 261 98850083 380 829 999999467561699080 170 43 437786766 376 305 999999814276731930 206 374 545551495 315 726 545308480 328 778 962856981 112 759 999999510622346644 841 564 999999811646464571 485 587 999999037581901089 66 967 991774927 842 837 999999138420126282 630 889 999999796689606592 304 359 999999280163836073 691 863 999999600884571408 228 83 951039986 381 913 999999779877592519 407 14 998228736 682 312 666266292 958 886 776316309 480 651 999999024740041221 608 126 999999242874337633 547 503 999999076642649340 220 449 999999648250675399 361 975 999999191878448522 938 828 999999893796276332 359 958 433068607 814 651 999999405780540776 397 61 999999022237995614 244 109 61768336 471 449 797127261 658 962 407667202 974 843 54072138 546 954 999999760996003727 800 36 763209910 926 910 670936675 992 583 285032055 180 659 529617625 909 707 682834509 310 928 999999699115285509 12 940 559136469 427 845 150528646 356 436 999999290276030384 30 309 955713357 911 865 999999374404192523 565 305 999999092453684585 551 429 999999620806555594 165 369 233701747 418 543 158739801 978 615 999999045340296214 85 365 476892373 560 172 383427890 761 803 763187146 493 644 760077677 550 189 864712786 168 833 999999275858945457 932 131 199323212 422 725 119946040 231 323 606178781 793 268 372433759 94 487 999999407576855068 665 475 999999453185240897 704 127 999999254217023150 329 816 532772481 290 430 553161926 498 680 381771940 561 454 289216914 114 269 141798289 580 128 999999505116400163 199 424 999999429571062185 141 674 190921120 392 351 879305194 80 641 999999221090639997 307 597 284035448 688 760 236994317 985 257 999999988550595801 477 373 999999557051897526 369 196 561057394 829 141 999999338961044928 752 533 734413482 788 543 197970410 778 864 561201029 327 811 674671021 365 795 232437324 929 251 870124790 401 402 999999111875239646 15 279 999999790412269950 477 341 36428563 881 686 612006778 226 784 999999896418210905 101 649 135466388 451 706 450835223 553 700 999999450688832365 785 305 999999062378566460 660 132 229386974 428 132 999999763989418821 4 589 999999044581247017 537 124 999999601281338248 185 457 299347496 630 907 999999721710836158 52 171 667429855 901 488 780157706 980 238 999999041959310776 359 249 847837355 99 980 999999295445729811 521 483 850143352 677 987 999999040481038632 607 359 525086936 832 158 999999402169772028 152 450 999999129674181719 949 104 999999477785033529 859 869 999999649786336273 168 458 925082108 723 834 999999304625264221 36 354 29189700 793 644 543749193 938 544 397511203 586 587 999999290483422991 677 93 999999771802631324 809 946 999999304861241664 119 794 917355195 243 168 129611586 919 389 77458796 419 891 885583022 880 818 634103988 264 430 906693879 169 396 594349946 455 767 999999475716932342 582 948 999999835350226576 972 697 999999338257983647 28 871 635052418 197 31 999999217500686444 993 662 748995560 63 624 999999196734744332 833 533 828734395 296 818 684156632 449 886 999999285017301198 980 327 32681389 742 968 999999902877910553 466 115 664033989 224 738 747266782 889 549 970621283 917 886 411121074 639 969 999999131884331703 248 547 999999107674085347 70 429 999999459206472831 708 698 999999570890920451 258 343 589208211 298 864 999999540785685027 665 657 754149326 54 335 245031216 758 192 691984488 306 584 450249943 278 381 198395105 314 759 999999289442774125 542 854 999999580974186142 73 820 999999591708091166 196 408 797328849 831 777 999999626309785575 932 514 838034335 417 574 187685637 505 907 999999342542661836 174 449 902628006 127 900 120141020 123 702 183488990 334 4 985448861 87 257 999999495374461554 430 258 296327259 480 46 771349965 628 543 999999414119829623 445 772 225466520 155 650 606940331 248 536 866333283 557 31 151937655 475 923 999999718804438380 545 975 631023017 305 537 666623425 992 677 999999069200771751 791 375 999999558542610899 666 930 999999624949945008 405 470 999999242264827424 551 15 999999318179638638 461 601 184079540 347 515 999999674384101771 840 804 999999866559092699 783 439 843502193 441 828 999999320796329558 319 698 999999476501021432 737 122 999999849991393092 960 277 525334729 365 481 999999971548555676 739 70 999999841050571070 680 596 999999084397241276 822 676 999999068962663532 377 243 862579358 779 154 432950586 118 720 821705226 515 934 610746543 412 869 629144230 253 378 579754266 356 898 999999121071683054 835 664 935326040 389 298 999999033672525256 732 216 478250739 736 525 403968847 729 588 999999232112482984 520 296 999999769235417963 291 211 999999787594080384 744 212 999999097667370143 235 947 999999607660180353 191 953 999999928459935967 332 211 999999976553086254 838 89 999999349422385419 421 826 999999303040384446 961 362 999999623408528909 639 356 999999983377182246 383 99 523785406 59 402 658595866 705 823 999999509364071497 49 479 977226933 280 984 60908587 77 600 999999056263729622 862 188 99416345 727 35 77240862 331 730 999999641414468716 782 674 198263721 903 634 999999283521878931 623 669 704550376 798 290 869289139 14 350 622408146 41 744 999999051551659686 405 211 999999231153096985 734 874 999999765138594936 425 777 999999928635094314 178 676 552597360 981 578 598350341 225 52 999999178620354382 246 749 942373662 555 57 999999138954474355 82 886 999999049493770235 425 239 999999764867678218 35 164 60343510 935 8 999999179828121929 395 874 317136197 568 177 999999654924131766 429 102 590259173 122 588 999999117857778446 644 721 119570190 676 335 12279833 28 141 870640133 903 26 477574839 323 661 404947410 194 586 263046809 728 646 999999534254383162 487 708 522133677 507 456 349799478 163 456 334506845 51 572 685197618 946 749 999999118982003304 167 56 999999027950862096 400 57 198775842 40 357 592685228 830 629 859774113 845 749 999999987402922483 270 120 999999211268554613 851 22 999999501153814094 311 609 960575872 827 57 999999298376690021 109 427 949439615 928 819 671192065 746 724 999999355570907508 650 484 693697206 237 870 127660341 144 66 999999169836300861 617 385 506167169 9 992 306853069 490 299 521517042 37 223 876016763 960 306 999999483122392524 642 556 509575612 33 570 637495151 984 273 999999504740660961 294 271 267247020 394 915 334959318 208 654 532367908 81 911 999999121462475551 720 363 51880275 415 796 999999104782658049 216 995 241593865 303 744 999999872362189633 714 853 999999747345903689 455 385 999999534335848391 142 52 441614495 896 912 149194471 458 310 896580249 634 943 38874580 348 406 999999905089075912 884 395 999999609065073453 991 906 999999379822419521 315 220 999999762673554371 628 890 76809042 502 394 999999971388426035 118 944 349519056 826 489 820122957 590 773 802800562 261 201 253267673 594 784 756824635 541 918 873947562 448 76 355133200 443 144 544557765 86 421 999999882460878616 723 10 235116244 912 82 999999586434272662 553 946 838705983 968 892 795888371 570 855 193299496 523 316 525456402 571 272 597155577 823 257 541149075 561 121 999999654025137254 65 285 750105161 733 117 999999507391386575 939 752 489184603 514 350 443610592 681 317 999999213542039428 72 92 906185770 950 349 999999109418469646 793 195 999999623637504642 329 211 287990195 293 93 999999323922266733 110 93 975864079 357 668 283104774 293 379 89304748 799 815 184100910 773 353 999999437009503728 420 747 903089883 834 667 180266536 442 42 835969726 558 970 999999578681595276 122 542 999999848075050277 714 929 922781224 346 106 917240940 982 676 483875692 438 68 725871163 583 240 562407211 292 424 258195165 849 227 524470418 44 960 460331567 471 457 999999710202080000 591 637 712506977 429 635 999999023012629849 413 944 999999460542192660 46 84 943204326 227 609 999999469850622601 732 553 446566634 125 99 999999368051820754 89 133 999999652436061638 912 599 839547422 330 834 999999203245548710 911 511 999999370450855859 568 1 999999517894679673 865 182 59619095 357 534 999999515590071535 396 626 999999640767635809 875 304 999999277419541706 756 264 741447880 945 942 963686582 771 354 623090247 766 489 999999369860173224 591 369 85589530 68 706 999999938239599520 411 935 999999351441882217 21 307 999999994513948893 825 185 283712278 43 407 999999567626896613 142 684 278310876 43 110 417908512 614 974 999999353514143140 392 704 999999102795175925 771 683 999999578945747224 703 985 582862904 867 154 780222423 567 948 78819074 218 549 999999773770865784 568 443 999999039242429108 566 164 999999670882200717 125 836 999999370131525839 325 456 65216818 22 118 999999636571488736 670 475 999999974205864950 876 154 713622217 655 400 89621074 277 436 999999763068459117 130 85 999999420880350837 63 37 999999737104300348 510 989 22386026 339 451 999999976346181961 694 292 999999788883768056 263 618 512555018 811 479 668493947 313 115 999999296405349411 395 770 713722389 95 984 986014289 857 549 26035269 174 154 999999371375969400 683 459 281263213 172 52 221486870 867 671 999999348336189089 124 843 826219057 115 940 999999107392097918 374 306 999999526398346336 782 19 999999876434940248 589 6 497063680 661 268 999999525824509530 250 166 999999582936636959 308 535 999999452168564191 228 136 999999234872683578 439 364 999999240455085148 19 974 449779737 724 834 999999374960639992 346 674 611500728 423 153 905956534 449 774 744727393 848 103 435795739 198 233 999999656535869266 734 625 483334579 80 533 817127795 115 926 999999408633716545 236 889 999999501393936878 941 55 999999029266241420 894 593 999999365578504459 776 84 616613981 672 346 429742892 414 678 999999494737737926 56 378 999999147665191697 127 683 575107201 349 743 999999468018423331 850 502 999999315270846433 541 217 999999976742330361 685 816 120229736 833 295 897747747 301 961 545965473 547 394 999999479556702197 745 754 999999674922076875 20 862 9477453 550 550 999999538559435373 811 729 966511928 948 514 53750192 390 702 255703736 161 232 861007992 420 201 677629386 273 309 999999159004197770 942 845 999999796269132624 132 774 999999376855116615 422 522 999999509496286712 61 484 999999557246234731 862 811 435004392 244 379 999999436946196567 957 424 326694089 355 740 999999403313702875 275 607 999999592757592095 724 17 999999349298023632 995 279 999999455674537869 31 240 999999110968575775 162 115 999999294603696313 140 453 999999690325600411 46 787 257213171 805 747 484363032 756 868 999999836349205381 173 630 999999031405022163 945 89 492880800 931 914 657409315 929 996 999999711888295320 222 208 726383541 796 234 596249387 23 871 999999619893062655 773 202 999999512025141420 333 566 311032607 111 164 999999743596339296 186 51 999999775783800808 690 519 74732951 953 579 999999294620271678 81 655 999999360779197952 269 672 99062095 364 660 999999547250057714 900 850 909959151 393 373 999999956531832342 604 479 999999599844513960 494 585 999999150700971016 798 145 999999570764378311 103 765 999999224972431054 910 743 370090422 32 863 999999995317364851 560 887 999999645543785292 866 495 999999619080853496 93 357 313509070 91 651 198240860 421 976 999999401486779527 58 121 856771311 575 949 999999713123997659 735 811 712708374 494 713 999999720847858268 282 727 999999391933620387 675 115 300009655 882 953 371569616 200 299 999999056742559401 619 572 999999865815895123 12 380 999999053278461923 402 782 999999363438108735 518 424 999999414972859928 996 359 436464759 188 572 999999696833174752 641 871 999999672976697061 122 345 296677716 920 918 828767363 370 384 357155347 852 474 999999575359924560 995 540 999999484957962152 57 810 76124209 895 772 462274563 382 810 579546682 490 361 999999247693697583 240 482 999999854422000660 704 278 999999432880282391 253 896 80654251 28 217 999999073688108134 724 288 999999412614952350 687 794 999999003087403965 279 795 889532429 160 873 250527579 769 380 999999405892423431 149 439 999999538531930473 30 89 109459440 519 983 546556325 148 39 999999252900598310 459 537 999999081426484735 27 417 941640987 444 672 999999025030288954 731 328 999999278970502158 640 509 56200709 834 308 999999645574986060 117 483 999999153422016738 122 260 601342158 570 366 348253572 88 773 367023595 978 782 424240940 805 191 999999670772966960 366 177 289458487 391 894 651892778 517 917 999999317870512530 3 154 263451626 685 595 788552751 924 582 387208492 777 135 833861485 564 654 999999021315936241 121 717 146677108 192 701 999999117092283207 668 661 999999359710432013 871 821 669174202 885 107 232112347 598 727 22042671 468 642 233517003 22 111 367069028 478 988 570398485 418 229 457914042 161 443 999999350610733624 750 102 999999742163814982 896 189 583371017 853 427 426788712 633 812 492963225 30 298 295454796 982 687 989608036 804 487 999999184118521246 368 93 999999371177878268 360 252 999999131087289169 987 655 576043888 488 262 394178288 240 90 432766846 331 774 608476649 861 785 999999075814580796 119 371 608760009 970 227 107482160 143 82 999999498671902296 483 782 999999374607386140 375 884 939548934 250 869 999999439245380081 994 521 828400724 247 510 999999117388712544 233 258 777094226 416 959 226167933 797 898 162590411 58 561 999999647975930910 440 91 999999567606559535 202 584 891070410 750 645 999999283277968219 510 288 794451756 71 12 999999971643216968 902 317 922403162 539 594 999999605575518265 38 910 547041688 207 239 944492927 803 45 205353122 366 772 999999097416805023 979 524 534109882 502 748 999999267679302515 373 759 999999157800047379 954 215 882939281 990 435 999999788597672598 454 367 413035922 753 777 400681332 540 843 999999319153532768 830 118 999999214229189339 503 394 749161285 307 79 167657798 685 29 744510902 682 221 999999544114468341 154 824 999999202822331675 375 180 252028681 599 923 73217004 577 457 999999232324582529 8 728 999999383127388576 813 309 837382282 515 943 72253954 397 884 999999769476471083 53 350 838332644 211 920 769513601 170 189 533756597 920 406 260965542 616 65 150073156 642 976 999999065736218764 431 759 17102387 766 447 390926239 568 215 999999203347577136 563 465 543146957 959 470 787727357 133 868 731474798 762 697 828333728 245 554 537642058 52 242 999999932233594484 391 524 999999291956889923 946 406 702636952 557 202 123737141 390 709 858115643 977 187 370727153 860 117 355432934 736 257 722925044 513 34 999999198578258865 94 719 760649984 815 959 790810252 762 359 999999886101363128 176 480 121688488 695 813 709298307 440 104 999999120753580527 787 229 311504312 448 179 198590438 34 941 498970316 385 717 792032007 37 645 999999248247068620 943 862 938456260 156 677 640097516 463 409 926262164 873 311 833917473 102 217 724211968 688 647 487643399 556 467 999999945766005614 167 789 999999493755187109 619 817 999999648600295104 694 427 321926887 839 845 999999835390112630 431 793 999999930906737039 114 611 999999995378345627 836 221 999999623724565102 609 257 999999062480377882 326 787 999999673344633613 260 822 999999071752917853 530 185 508356004 272 389 999999084755991745 905 113 999999326527462397 410 288 927922227 549 824 999999421984414782 577 125 812040649 522 31 999999533952522946 804 467 659293074 953 396 999999517147560480 940 245 783572212 264 218 999999572360390655 188 64 477410561 247 959 952537797 682 18 383856315 640 309 399095475 483 571 999999165303565146 316 12 756477286 692 753 999999660081469060 147 112 999999797482580277 902 757 999999587558130990 877 405 403775415 315 384 999999717055419966 611 894 141698854 309 293 520172114 33 726 999999034822905725 110 803 318420974 495 294 724145638 545 803 93831909 19 65 999999305299628897 754 859 57090801 63 713 632414905 669 888 999999080210032787 657 526 999999577242591080 795 836 999999714208461198 914 985 999999277460097598 482 257 999999520782168000 348 594 999999635715458249 659 911 323635468 254 26 999999176531656567 817 421 627660209 818 972 712625900 247 343 999999204783584452 104 482 999999032674457904 481 884 515539930 779 125 836109973 651 319 989630407 693 125 999999716997962844 697 162 185085143 936 476 999999795939399805 525 525 117750191 902 651 410238265 361 600 999999976811049944 372 981 313592217 983 657 999999728951345621 493 12 999999736353444324 781 850 999999355694524837 818 777 999999631787788746 641 943 999999260860559806 5 807 482770250 942 821 917006416 456 129 999999769527169324 619 731 849576917 241 844 370605260 273 424 818100605 844 879 510617770 246 520 549408637 466 865 189212705 755 529 196009889 900 338 645389389 764 351 999999276614490529 7 253 999999918591185486 41 644 100740108 194 107 999999601672487685 891 271 999999867471128627 151 827 999999214734437928 435 679 104683769 96 626 999999464959408646 718 483 999999078156582145 777 136 999999914733323581 456 347 999999784766622352 755 707 999999023053741704 578 615 999999348459326555 110 900 34479431 462 324 942468697 474 199 999999807148163604 174 854 807037995 897 580 388518116 347 743 184585100 371 284 698336262 113 922 999999170648769814 964 76 999999284979375465 214 699 219766469 364 618 999999329996033816 548 567 708219197 955 689 343745611 501 470 999999367781055685 810 805 820343756 627 174 106556804 917 28 999999018610408738 266 211 291919045 144 668 85917003 611 202 877347015 35 460 700834353 816 676 335452845 251 960 999999672363196966 630 284 999999459919015611 141 80 522789610 807 366 999999298132801444 855 93 999999140044071763 940 845 999999876272536460 417 383 999999531992177785 825 955 999999093401578680 976 900 999999138868067912 754 802 475744849 229 643 368924130 430 201 999999057166234014 193 635 35403407 153 454 999999316602499506 9 755 12878605 676 898 999999869460085139 492 74 999999937173766315 473 857 962456301 676 526 358565508 160 735 584822476 638 754 81219154 254 993 933995762 124 225 17184348 926 192 999999207220581365 678 777 999999150004307882 283 934 984154394 765 254 701853504 285 100 287017534 763 852 545698237 646 657 999999767684786020 965 66 999999248075684741 599 710 296141723 575 54 610623286 884 795 559224263 858 626 23879581 531 15 400662569 143 747 435271709 632 654 728647376 350 248 999999108869789516 707 918 295904849 25 405 999999184464897797 598 690 730146504 367 232 999999538249533051 118 282 675568813 500 792 999999695925693432 557 508 999999834270844135 956 304 283143240 666 315 552455145 821 142 999999293915168129 199 834 999999185068943543 548 432 178299818 463 61 999999247758422914 721 847 999999179106709249 715 575 999999947779679221 522 479 383522857 692 213 617556794 636 252 999999578020386351 78 26 314596997 621 592 999999962479950373 772 743 353424787 517 306 104295821 271 743 999999379324003557 295 706 459437360 486 815 999999282266197717 831 99 230787186 378 216 999999575081459992 245 404 277358945 720 191 999999738668281101 108 434 999999678289620480 852 379 999999917596906967 753 135 796932779 528 564 843117491 233 383 999999067163433853 356 294 314283961 465 6 999999077087266701 255 483 901123395 12 950 409419048 466 519 999999323314046305 162 905 999999316867986131 635 909 999999928387843964 535 747 999999964233746398 153 92 265691110 298 549 999999122833993880 679 947 14910384 106 570 616894210 487 677 999999089374126202 653 2 999999790105860259 98 218 458248890 866 219 999999129237234194 486 206 374090253 660 827 358001793 776 858 999999699214001703 611 868 87848097 818 683 999999831055368928 562 876 712054351 44 404 999999858594812206 325 288 767547545 37 404 999999559652916304 690 900 999999575879985349 844 340 999999512310113526 576 662 425412849 700 916 999999520872456774 55 915 999999298951904504 71 147 999999652314138585 617 276 626242370 14 453 999999806654746572 782 604 999999078267234173 302 897 787773312 794 503 999999344898174610 359 30 999999519899695785 630 741 999999933011388999 613 840 999999039980122666 520 363 999999742299902721 299 439 999999206168718505 464 743 999999887750878660 372 952 999999748266953811 155 26 999999713823466421 284 992 999999179718488387 955 286 371119509 747 985 999999995521324071 619 697 999999247580072192 441 622 870840828 103 79 696327570 123 695 999999002181970509 538 250 960795874 742 692 556814571 165 714 999999091679132786 362 629 999999187069680388 594 579 974692368 731 839 58296377 623 185 999999017395268818 247 265 257312583 655 488 999999094279281133 182 264 917820949 329 903 36774380 879 86 999999627417078090 424 188 544414855 437 929 4879399 355 545 999999584868475989 403 787 638984430 631 638 999999934716682111 928 938 785841871 250 497 937421295 916 662 355429606 384 18 999999835646792807 789 880 999999208854580384 173 257 999999568600172091 449 773 999999339092820035 732 205 942518525 871 138 999999099116285380 962 143 999999959236751231 806 962 999999019128012835 298 388 999999876161494317 39 778 999999268427702835 158 446 489364259 604 875 879462922 401 782 999999071192234095 641 42 999999458141964560 555 580 165261462 281 528 677709045 493 399 892309314 573 714 999999280580999198 65 537 999999128593679988 184 419 908906802 565 948 327047905 840 844 85144686 557 744 471066467 101 349 999999775893553624 673 57 900054847 244 414 999999306344519415 372 44 753521944 909 230 798275861 592 106 930766395 658 212 39709739 925 254 305521407 367 430 370399506 725 466 999999385898648804 767 923 999999572987994921 597 171 999999365620388487 632 462 999999692318434972 890 895 999999194090545204 587 235 435142222 23 988 999999308665287028 209 667 999999912022540622 593 824 351817200 249 445 952539688 740 714 633243357 230 323 941150239 505 337 225095819 448 668 999999497160859072 38 365 495275021 820 98 815842780 818 948 999999732872238695 318 636 846030869 1 136 617472074 600 421 999999392003719248 833 618 283867655 671 865 17286750 829 676 999999642948860540 12 817 954303615 296 36 941898964 869 404 489414620 196 938 999999688313671375 180 299 385764731 210 795 388328515 876 370 999999080621362162 679 127 999999209964036511 622 637 999999050742962498 267 777 999999570086661890 112 762 999999625465637577 833 527 999999958772861754 255 149 638965170 815 527 999999561636888767 426 690 999999011248692466 6 398 999999154708443229 303 923 999999393165477345 100 831 606537721 805 239 554072823 150 85 369778790 803 739 999999097040247656 412 833 999999375773772364 482 671 999999727790984021 686 37 999999421707541775 39 712 999999083492915283 681 231 999999896840320546 552 278 999999831793597915 989 896 463177027 849 511 999999583363369803 596 356 228192556 594 279 581707184 234 228 999999891035100266 666 856 500183724 37 888 970323628 343 639 138053988 532 784 232448662 834 246 133540777 714 172 367176868 751 791 136092970 984 595 999999918840150524 303 248 999999954215077008 1 395 32716366 462 437 999999020250573254 574 175 999999597087213951 368 631 999999043733393046 84 943 999999528536620105 566 117 999999965567411538 368 838 999999804753231762 128 587 301009288 633 800 756148090 620 791 109049164 984 622 939235689 706 941 999999903906397746 257 739 889795014 921 136 999999656713033584 79 235 427220588 222 298 808843050 172 927 999999849741800039 387 885 999999800986132643 788 603 999999876467602272 343 463 999999130197090177 537 795 54505272 786 506 999999566536369368 749 609 754235654 479 88 248346751 718 498 999999463995722144 872 770 999999670008038151 589 966 806833971 46 473 999999236589531758 760 669 999999166314302247 686 767 921814110 422 233 607198694 788 519 257740683 177 603 999999980284040439 232 857 837119143 654 748 376028072 631 421 260319055 980 668 999999884800308031 800 504 999999730750624735 472 699 807546465 186 467 378284946 460 167 240399835 792 306 490169198 73 544 999999398779034991 29 11 999999283872510394 438 165 999999277588543813 934 132 976686100 432 154 941240227 452 921 27100064 928 704 999999388752380006 401 612 999999116171855677 322 915 276573410 134 721 999999144476235286 26 430 552410387 108 700 215045525 145 64 999999791444422026 292 219 408705794 770 961 999999531524293967 888 684 121295674 469 365 999999083504944458 45 72 671285117 157 206 999999611717780172 205 97 805434132 239 159 213498186 732 181 930771403 605 594 999999382937773324 215 858 472127563 406 892 894393953 944 839 658755936 347 524 999999800871488486 424 370 999999710460075875 687 790 999999081683016343 857 146 227752272 300 836 736652931 456 768 503891365 635 309 999999503447035390 508 873 999999341575898109 854 359 999999799103843453 398 905 902907030 819 506 999999961567365452 157 133 999999178595086685 290 807 999999063535622548 145 272 999999972506484317 784 554 780290777 323 771 469040973 850 795 958580132 638 48 741912504 622 195 774980959 569 172 98229564 561 169 999999580124113891 468 620 612105751 314 860 75426419 716 908 999999568839983179 419 300 744774380 652 291 999999918093950978 302 102 999999698104735498 951 78 387942692 317 196 999999084912520959 842 495 452116570 136 257 576228416 345 210 999999287723999690 873 837 542489906 597 526 95696981 525 174 670214419 973 769 484766664 957 52 999999752408975780 36 760 999999314113983453 590 413 895291857 596 261 989702630 719 173 999999780913190164 269 898 999999750327895247 390 961 999999395013479086 732 491 577070676 414 163 107131243 686 498 999999291665519759 292 413 363474890 590 879 999999461074378210 201 279 999999661443814147 712 236 521197659 580 748 999999947579971771 994 308 743408693 473 772 999999647436683544 583 576 999999984765526519 83 634 610072677 801 133 999999550460957484 330 106 999999976145822957 113 743 999999096576363247 312 549 820558760 682 966 211290014 561 174 827379661 708 694 515975709 377 9 538732573 459 491 999999987464594938 900 163 999999627181183084 313 116 999999470912626578 124 399 999999763788940301 758 347 999999686629831844 533 70 999999011785268523 345 805 733490843 549 42 999999158864716927 720 83 103178039 716 257 821921517 582 67 999999447853178818 83 193 999999695748709861 916 19 824671385 329 181 999999546143046884 799 575 106490730 102 411 999999539702534227 94 876 999999543959626734 383 719 999999420879563401 476 921 212589563 28 321 999999585045054530 396 105 999999886215966557 91 220 538259194 366 119 999999209424837735 840 917 702941130 547 801 711132776 775 345 999999364154131171 568 127 999999107038984358 260 622 248669643 774 193 999999842268566860 304 605 830966260 165 234 472829459 590 617 999999485729307415 71 117 190294356 704 8 521026767 387 482 166202458 167 837 999999250566002842 595 263 999999839834386383 22 731 999999311919366612 591 761 109033981 434 415 999999114512197184 198 890 634225951 401 888 999999729926368691 617 803 999999593817396689 255 812 999999760165703846 819 375 999999544391031725 781 291 815645636 183 335 53855062 808 602 999999884027373659 240 599 999999373805121733 257 412 15146700 272 224 657802501 858 332 691100887 294 393 781776802 3 357 876897831 392 362 999999151700525880 42 620 999999325766254912 422 919 999999669166188533 377 434 999999543029118390 208 294 999999339815627187 784 579 692973280 592 330 15894390 716 837 999999835362939455 225 897 914528688 744 139 261376495 316 880 735547039 410 826 612326867 209 898 999999842677758097 588 605 999999241235238295 289 354 622594647 135 320 999999060444952032 336 537 999999086075922703 865 499 999999854989519685 872 586 999999417207130460 871 682 208464576 36 600 999999706519427779 459 753 999999594236677465 22 782 806649891 423 338 923192019 4 221 999999179873733227 663 698 308320380 862 203 999999018428583251 202 498 831456742 561 575 999999750680091817 157 904 999999053285951532 848 312 957165386 666 338 988602791 689 911 999999018930098605 882 382 999999562036489458 557 766 572008852 887 626 585309133 676 455 817421041 578 553 999999371405873960 255 534 999999059718519426 600 513 323764532 512 474 999999743820236634 788 537 289005053 204 697 999999267647935854 850 209 999999311755436290 518 851 252307721 521 840 481317575 147 408 999999897252633925 860 136 790799770 530 11 753371053 30 654 758270795 677 428 744757202 637 327 999999545346966846 252 911 999999602493959165 254 652 561281444 291 606 20676721 151 264 999999803770425896 534 283 369896681 527 557 999999617672653359 548 9 267328382 378 35 999999362333440080 110 867 999999224940206648 611 910 999999638926059229 528 200 999999777761598251 81 662 950060292 465 427 999999582861655857 186 405 450084991 885 785 999999597128116974 114 732 726626712 738 631 789122325 534 27 999999636354993488 697 43 580574780 872 814 999999198184779834 299 776 654937471 588 572 847807108 331 378 999999872082802964 678 113 999999168594379830 923 888 999999668803945266 339 130 999999958761790591 704 251 999999948024498047 358 237 904169528 414 122 999999499980132903 886 704 52128031 15 363 594489582 655 735 464746968 500 650 881575504 46 513 544462335 773 9 999999755581551567 645 827 250846152 895 796 999999219482189422 399 342 258544763 813 408 724470742 640 429 999999748251396760 716 547 999999464271862668 202 861 621766072 598 851 130401498 55 777 999999937834993145 303 478 999999125095264687 18 749 999999088447674774 687 803 999999390758900018 65 459 152840128 323 487 457199139 321 351 999999355937075957 673 265 999999410078681378 523 412 999999655709878777 307 381 999999076935120850 891 582 999999859272397774 553 440 864352524 503 398 542742935 517 9 472691367 138 305 999999564886199517 48 571 999999861568310538 858 753 74803838 463 508 844732063 536 207 999999126734394904 347 110 999999328976228721 276 356 451404465 512 472 436665211 44 806 396607437 785 392 373792617 855 704 999999848279899571 924 492 404988966 287 453 519453709 713 603 999999648599798045 143 748 605540357 587 810 999999917516701470 286 534 999999096658921160 699 400 781118995 609 797 999999824144646763 10 27 280493216 820 328 999999029305895079 667 38 999999137256550566 283 767 686643277 140 622 21040771 923 259 999999725588275775 728 126 248341485 141 190 157765482 629 654 318023882 44 850 806570523 212 616 999999800283433890 342 416 358970503 66 878 999999414568109863 377 112 999999760734475247 317 659 875644413 390 824 20254708 762 420 677457942 885 437 446754823 361 134 959968625 218 389 999999281798181808 49 481 999999161671344056 446 209 999999092927263516 75 73 826445666 330 490 829456740 846 249 999999168209103390 613 43 487766796 412 901 999999382381759069 26 633 723251996 249 195 999999396220800625 388 533 999999642246271666 872 45 754573772 830 261 386828691 476 823 201434206 626 411 999999848690196610 574 458 999999582682208555 30 831 999999511518793154 750 359 594640541 318 483 678390304 538 663 999999143486712861 235 424 92256349 359 23 144737345 873 145 999999548720851826 401 445 999999816742985307 282 895 914873349 743 401 202870900 89 712 794366291 304 451 151192662 311 588 375020578 205 417 310017557 229 642 999999131723066302 811 414 999999051994358803 16 302 999999093007414722 497 357 999999441458034523 580 885 184682211 28 840 999999861058641310 167 452 999999191893445156 923 883 999999293220909632 112 652 999999468344575094 332 909 814486467 5 258 797831621 665 395 395317912 236 633 999999354866964694 737 685 999999123525543278 98 81 152980912 774 864 999999053875431852 517 515 833428344 176 66 999999451355426653 857 903 999999693940636842 891 250 999999755449860136 370 96 616712426 759 917 467810758 375 744 999999465418308478 178 696 999999135682603129 905 517 999999587116539532 769 813 999999642512854887 729 706 112012571 394 311 999999254722293759 686 574 132710850 453 901 999999294129699378 471 874 115722896 559 894 388553861 919 43 999999040950178717 696 539 999999208033054811 507 578 260146900 35 184 999999188487647150 664 229 80943292 369 771 999999139709135447 65 171 343650281 382 130 581557887 562 517 445788784 791 22 861686584 218 641 290498825 866 482 146966154 159 241 691028418 442 507 999999824208808572 519 245 999999828948779015 590 421 53773496 880 714 527994215 207 330 694461336 77 909 305054371 421 309 999999394844117305 434 405 594948387 599 699 93692902 658 557 999999682405166729 721 306 999999881919134420 40 1 73823885 592 914 999999826045876315 1 288 999999565942900016 918 505 98381745 351 223 509220371 771 580 399041059 657 660 563744966 558 709 271394638 761 390 999999850903155741 584 481 999999451733019756 683 655 229682562 607 214 15005293 268 267 999999623608064606 163 406 999999619709722940 9 389 999999282466892418 468 578 918507171 588 27 499289189 23 152 999999193913429512 130 358 156299248 64 335 243555315 124 232 999999791669416475 39 177 298219146 209 125 999999200293991017 208 580 999999392733187520 507 694 999999316841523120 651 805 999999665230203349 154 917 999999757139269819 844 852 999999521690729784 210 788 999999169543170518 717 234 703801096 456 598 999999128106070313 635 456 999999834117874916 433 386 916930896 774 253 999999336642258927 905 362 999999557817370366 504 814 999999335383489763 144 424 999999127420193991 919 525 864133865 226 824 999999692189555045 516 170 757325912 738 259 699727029 361 496 999999626855816659 368 130 999999499465794307 806 776 9764292 267 591 864415088 694 50 593046151 751 617 111420822 151 245 770943393 245 659 822529254 93 350 999999492617473981 162 473 999999729924069055 70 339 451119676 455 207 999999444372761999 330 562 999999983031450915 822 746 999999007694011160 264 282 999999392118814571 73 5 886240143 315 142 999999432521772788 404 306 999999486914771763 160 108 999999512689490537 804 82 272825605 314 21 353517525 918 733 999999158581209973 246 27 999999016181381825 784 599 442113794 148 905 487788395 594 612 999999494505827828 41 22 999999332202554887 333 807 46256505 458 437 999999994126780582 531 794 999999308702663670 55 268 6722954 678 503 999999806722937620 838 16 797922325 902 113 999999202847031649 358 639 999999034035484678 474 598 999999088159579642 427 422 999999197150277411 464 449 343742639 329 445 999999518059808964 412 714 432496572 462 707 34035261 888 653 999999848317692383 347 378 120769228 698 771 811700424 580 132 999999556043396594 815 242 999999309423030495 917 738 995540995 719 335 999999950858026370 152 408 999999988121714043 614 54 926901670 921 79 999999029105203566 267 12 312056637 278 743 999999210732961634 425 611 364248480 502 283 789383180 115 74 999999744379225603 508 273 999999230201883847 894 200 999999341049784083 238 225 999999831303739745 18 606 405119262 623 837 842641528 312 41 999999684430679385 884 378 999999769818634105 905 219 999999816143346750 157 59 999999668666026465 50 477 999999769645235034 196 645 999999934963495772 35 604 685231794 382 256 999999495524058314 850 19 999999723403994551 807 44 999999842430019661 277 198 999999837379206179 810 766 940450128 356 203 694045384 876 452 999999052860810121 113 212 999999879506829167 499 194 940325738 214 324 745568159 174 818 927781446 221 911 999999519273056212 206 164 999999896086354168 579 528 999999466698628633 111 405 458285622 128 425 999999119579052271 214 446 701552910 487 674 999999548688059328 155 455 445054884 155 216 506358873 730 118 999999828253357813 132 337 999999183662241145 173 313 999999486382719324 532 482 87431621 681 456 898214034 30 477 999999148934945812 491 714 9862154 496 597 999999061313585486 776 338 717772227 639 456 999999040284412893 716 766 999999651120148681 550 315 157673021 621 167 345237573 605 488 999999312691517768 135 688 718620364 492 286 999999077645778879 567 899 999999589797940537 529 410 875051660 707 137 999999016468990963 353 797 42990119 868 267 999999779835036892 165 736 999999315776925791 161 413 296961270 572 922 999999466200197058 608 877 999999847646180352 95 844 674688684 753 365 492497860 477 746 552753828 192 416 999999817738698377 93 58 582664846 678 145 999999523267554712 155 42 526445965 812 918 808823246 209 866 999999482559093303 745 276 999999701006787779 289 45 999999930715116615 480 147 999999516931128637 41 375 185910310 663 756 999999838682793932 760 510 999999463737243619 66 302 999999269467928962 599 160 999999980807728351 893 844 999999477889805384 649 917 790018243 466 458 455844240 385 199 442437992 275 392 841429062 31 742 999999975190004882 267 186 999999788409747883 244 492 77625115 301 911 431280189 791 94 999999674975094063 777 692 999999554918611589 327 425 989756590 390 759 39476730 925 242 521276656 488 43 962486940 828 223 999999842711909913 55 817 838309965 238 799 999999168945769760 59 309 999999276117055337 584 24 999999856979681261 507 525 851433297 431 108 999999871479755005 433 67 437202120 627 517 683154393 633 403 399275138 64 232 999999378857934436 432 876 969815476 58 923 619161396 713 577 590285324 213 536 474367333 112 77 999999105068634497 666 918 999999168907621685 413 841 999999443179412632 810 594 514057612 890 318 868492283 659 492 984660794 247 99 999999898533059527 50 408 999999765443100469 16 761 999999995254351036 397 318 275899260 629 269 999999394974883320 722 785 999999310292765936 222 141 851146533 285 194 999999878303394779 100 558 552191803 836 151 999999690982292010 463 451 999999473614662764 533 89 432953958 232 689 466780215 314 259 999999313050045411 628 646 52112328 279 652 821083219 131 909 999999015721423617 310 238 999999436314160810 302 145 999999389288773110 642 681 809801415 177 270 162341244 746 135 999999033997349152 236 477 521738763 376 855 999999245418694565 298 14 999999044693005805 20 784 999999917472702304 630 768 999999976024286818 518 823 999999807432296814 136 165 999999998391169693 595 7 682936289 54 330 999999809547569656 1 810 999999320684356236 106 422 999999290612387554 17 566 976242998 471 42 865922076 732 589 380780729 393 563 537888013 549 564 999999695653115312 889 101 999999301675209726 334 542 999999349141279092 796 437 999999868649191511 135 897 16623271 255 549 939077149 285 786 999999527092661275 846 189 284010987 616 364 93290079 488 546 999999485789275573 363 292 999999629387662439 681 41 284797529 88 630 999999744935782823 331 738 999999204798765737 252 780 25800340 174 101 999999244552826654 334 823 999999185266984681 213 439 999999161142979201 394 313 756981338 845 9 999999074235264269 245 802 999999307515775087 796 445 634858958 752 831 999999841524804749 778 803 999999199725826592 557 331 999999501367655023 660 418 999999454081570352 739 642 999999002760795411 439 676 17604771 441 493 999999177509319229 505 904 511670071 447 405 999999761522878079 181 756 999999979502145379 786 482 999999827704285944 65 42 999999591455415187 47 597 999999753513142921 776 638 999999178268604347 55 289 920548161 399 707 88394121 797 385 797648661 807 27 999999646317395157 595 732 999999182824135737 115 362 999999275899089477 647 182 809406769 465 252 347271075 22 120 999999901144840831 366 64 164757106 51 337 999999711831410762 395 245 978539877 816 225 452568566 908 565 514856590 672 676 999999680229229966 526 709 999999984522298000 694 912 999999065894429006 817 819 999999531829576915 443 835 999999337951942375 849 706 269569167 118 407 999999409059850954 445 32 999999512792941257 393 266 727273180 76 241 945340696 844 9 810965109 29 378 855820646 661 123 999999813398596573 781 135 999999051758543876 11 163 999999970912853222 645 922 393116787 305 722 999999837206819568 475 179 19594108 240 142 999999447460141995 559 412 433373939 388 361 999999637921834113 220 532 999999447003093027 461 241 999999881386552699 410 753 919615726 650 496 999999548858589480 715 408 999999701536880289 689 816 640479787 742 678 126617369 498 586 999999110347416417 215 608 999999192056461274 234 649 254646927 523 441 271889930 670 377 999999981335998777 486 456 999999132880907041 468 534 549578431 768 648 433944747 123 313 999999847405979094 403 28 999999432179641529 689 463 999999150227652595 309 537 781021170 19 827 999999994147866868 901 808 999999521885577338 825 869 221884943 407 133 999999268539305986 402 180 845379553 40 356 672326187 872 523 746718604 345 793 422428008 164 426 221047610 299 521 999999255785794652 281 846 602835416 164 477 351547010 284 743 331233527 433 897 526560209 132 605 231314638 640 413 999999118428402780 733 920 999999285545718395 887 898 999999415371371688 34 276 999999283626632714 478 356 999999680329027342 398 139 863422854 420 663 636562590 63 293 139654176 823 273 999999298494543380 188 101 604242078 871 905 999999200422541645 141 12 999999767838306278 847 5 999999035689086488 876 904 472753200 216 537 999999955540788542 123 103 999999057197023831 797 878 823354316 604 908 986412562 152 614 999999930297249971 239 343 999999778737584369 470 151 999999506811544824 78 773 895825114 690 71 999999227819134695 637 678 137277429 715 497 381450766 233 586 102344316 339 778 999999755724392039 564 568 999999904189280514 479 141 442707551 699 144 174578992 630 907 97667773 350 377 999999101759359804 467 172 999999715563244795 913 159 698341016 319 888 999999307416088966 415 179 999999473740888117 425 120 999999562600595138 864 702 784348448 173 174 332354364 718 345 999999443532378469 718 816 999999498986300927 903 184 999999535750388753 682 173 999999199107239495 304 488 387251596 248 559 999999966677548627 283 569 166368602 499 288 501943154 44 59 999999398972105939 88 395 412190388 548 105 95154665 861 652 999999855219411455 910 634 350535714 479 247 999999143103404166 503 923 999999987243957542 892 784 209119553 163 92 920327492 662 16 999999081593189263 663 548 999999241495206048 513 74 534853759 564 780 999999086501860355 225 146 999999009514679725 43 590 999999941145700510 327 426 226783610 67 133 235061166 782 252 856359994 780 373 170678582 10 580 999999956947268273 634 848 999999007290677106 14 627 999999873097023235 127 642 999999816694847914 604 797 999999930832490662 627 802 999999794033925754 389 530 999999340042099768 101 232 136871516 558 471 487561324 240 383 808798134 896 6 999999370180067121 680 191 897528302 614 742 927329343 807 824 908021267 829 848 814925138 258 487 552136689 920 654 946485783 288 62 999999636062024662 882 309 999999058225828997 570 598 999999640696999524 685 745 999999914924452212 278 747 999999549643325729 733 92 267556618 751 699 999999389157621903 839 898 996605130 682 251 999999192810386063 116 59 999999604307598687 617 837 999999837141387823 350 568 999999723129016354 842 385 169311369 893 55 925878322 426 521 999999848993802697 608 546 962376725 629 717 999999371278123765 618 309 247369824 242 134 791290224 679 641 464250243 156 513 999999988015045595 669 906 251238437 43 662 999999474908135726 700 142 999999066892418265 804 73 999999474748273776 74 133 999999944775502597 545 385 999999223509174432 384 764 895612410 343 288 999999768865422123 24 765 999999001809280106 178 846 478662323 397 529 209563305 770 512 999999362376964170 1 137 603559657 209 293 735446008 187 665 999999047575417700 235 711 980898227 921 428 736055472 897 14 858233578 668 892 999999423025064758 692 535 999999230326169147 104 423 90538324 103 828 908499802 279 29 999999355546110545 134 286 999999564044951326 501 101 39399517 262 616 999999889360375157 175 145 249224528 445 139 129480463 376 115 999999047202393262 841 237 255234614 665 458 999999262297506337 84 616 999999378431479427 374 16 999999196065172973 566 365 825673466 576 134 999999475694459460 761 639 911717754 585 17 559841980 854 18 999999426742064494 214 638 593522955 698 29 179043819 38 449 722792018 199 699 639588536 46 366 999999707499330114 214 759 999999688744807867 848 114 999999712440372604 642 216 999999981522086826 52 272 827971972 458 724 414955875 76 444 999999449047430824 835 367 217322764 5 429 999999714032934431 867 734 318421900 194 15 982370293 435 900 198302039 74 592 980661932 79 837 212699519 754 314 999999815771003515 908 179 338655477 668 94 999999057220211312 672 579 959873777 757 717 257958655 74 662 999999424521563352 571 918 198737209 754 29 174981233 148 918 999999877557108990 631 246 999999761775751254 840 626 999999231551713346 167 850 999999211113499334 479 893 999999381746367943 284 499 390432879 442 20 97920473 912 321 999999754684934318 290 654 999999431391755768 220 675 999999732031238116 641 71 772667735 606 532 999999200197955159 875 242 954984938 289 281 214855301 69 145 999999363612442806 345 637 617738520 757 295 999999005961279121 78 776 999999362642839778 164 112 283215416 61 450 433977594 755 326 572046764 562 440 999999165591994185 609 4 999999031721231150 666 597 150392361 51 627 353562090 573 632 648399516 31 808 146269739 159 269 999999306561938359 248 25 999999137295235997 213 110 271532073 227 321 710512290 58 20 551731652 544 302 59475271 200 479 999999562038944066 913 253 179650786 290 392 999999819959320705 626 357 60119348 597 818 999999405856361702 2 27 999999031964208032 389 103 999999179003261544 158 23 999999656705085877 267 339 109987495 416 245 999999951001990013 789 886 935624487 773 402 389834835 531 254 999999872708236717 343 642 252933424 373 632 999999859358975321 434 68 999999987549456240 337 788 999999499133341672 829 403 675310566 887 231 227926407 481 412 653096096 705 668 999999182369850536 780 432 443413166 572 391 332104018 777 719 963908764 7 297 661013592 623 877 999999358932581748 743 456 416663928 806 680 999999324969130690 120 537 999999633664466996 228 252 999999206824997242 105 689 614671368 768 404 322688518 519 890 450328280 64 622 999999050464644928 473 649 999999909902918023 702 747 810594198 448 330 999999646680824261 409 890 999999997513264549 16 756 583307765 654 131 999999792935147648 13 814 999999311794446710 743 517 441728880 673 114 165314438 24 867 533869111 460 670 750322623 463 9 999999673586675691 617 618 166363572 222 280 711760637 904 180 999999697927211430 723 708 999999321440133241 397 30 917268474 659 426 999999545319707828 420 392 999999455134671875 735 852 999999385372897772 842 831 999999397424195563 435 94 999999615752732084 668 392 89552051 357 273 999999510456775757 674 498 406138284 356 272 999999048316826354 86 755 604197080 38 325 999999758828015523 386 120 999999301004993947 438 238 109628001 628 430 999999203970858130 906 331 999999121176269587 732 482 999999216148199205 702 769 396076785 786 223 701409986 375 825 230344903 151 314 999999048951741824 217 232 999999307597207949 304 268 999999782362775934 498 20 761944777 144 27 897824898 881 838 349411007 604 309 999999107027128786 794 233 999999443033862389 468 115 999999830798112201 139 763 735409861 484 255 999999075984282397 723 172 999999419013271726 549 206 999999097683661963 510 377 12006113 461 130 999999037674799483 160 10 999999433404085628 644 811 999999835658031298 715 854 999999468822889773 8 565 999999717923409326 765 165 775016710 798 671 999999204168199932 280 521 999999598055742774 811 390 999999318460544062 423 268 999999797963058673 270 29 385188487 107 200 999999377097059785 161 184 950905663 747 208 999999466904056742 336 197 848643941 174 377 592607086 222 26 999999270211556988 814 23 999999074695024626 556 458 999999491595769207 734 523 999999121983597979 133 334 258738245 10 741 999999272253834552 706 688 686099426 289 517 999999821199015506 771 458 900384229 229 763 610330128 522 355 999999319748606127 119 451 147740454 851 392 381593484 414 271 587189053 396 283 929860020 589 842 939505277 566 901 66826037 867 658 867499939 864 479 999999044605023803 140 571 999999889249658501 850 92 720342882 525 426 625058002 626 604 999999371153405348 317 701 442903325 764 801 16856707 75 697 999999555784826397 552 319 366953808 565 863 999999719474406208 499 498 429319319 610 567 999999265007646607 367 558 521815683 486 700 999999046851044323 104 449 541751569 823 131 999999348684975420 646 689 999999066557691194 387 685 999999210643166647 541 924 84397821 249 405 999999181078471920 837 175 999999373382513184 540 903 999999198833393108 522 852 999999762406711712 884 786 71205157 658 623 388044751 391 665 999999923969365937 679 540 999999894052800691 809 783 999999671930918537 488 726 115469451 388 699 999999783290185750 671 766 25921481 888 243 956315400 695 25 999999880934951570 145 405 594172458 326 833 999999903373585707 880 632 397330573 509 49 999999224984361299 500 217 999999456564425268 265 324 58881227 817 616 999999387679859989 301 750 999999723061521908 845 811 999999434488445283 21 671 999999026596767006 923 775 999999515868314537 536 477 596465861 195 788 999999590551032910 514 104 999999101014290083 185 380 356864001 303 318 367901066 657 874 344247351 287 766 999999569156935870 622 590 999999344350610853 190 569 175116527 613 492 999999074470800773 248 514 999517495 493 684 551358626 825 70 963545485 493 619 999999010341541491 922 295 437821197 501 897 999999333717380681 7 87 728398441 145 290 999999798169650334 613 548 105895313 127 291 670490191 593 499 174024051 225 921 363562375 898 666 360619242 615 251 211663135 311 137 53107794 830 880 999999622183364216 129 403 999999338806546904 120 611 386312048 868 174 671627103 420 44 787910407 894 430 999999959246109133 793 117 999999237546222522 553 578 63078128 762 522 999999995251172451 710 497 577935396 648 430 747154528 91 211 999999767092461951 475 385 243778061 143 89 999999180483708089 335 753 999999262922495276 36 355 687452717 421 809 322905184 481 45 96212581 724 294 35101167 157 604 681432906 393 325 999999964454063525 881 216 999999058596933888 110 701 899554320 456 17 999999340320081648 363 216 98475298 242 590 974077591 37 619 999999435345672691 769 831 870930050 414 481 590729983 670 262 159613011 381 62 149809519 204 604 556361049 105 591 938924512 877 690 292029288 98 758 999999921566269543 375 229 999999263932025584 137 259 768152136 473 863 999999104776784660 492 539 233009272 485 910 999999481269131686 495 228 886093773 566 43 999999896502962630 902 726 999999447892343507 893 309 999999354412247963 703 293 999999054037943057 860 535 668127012 911 424 75159743 638 769 616013551 785 458 179654000 94 290 999999628247184054 172 48 56924275 121 223 999999151998370737 275 147 106144186 614 597 999999880022977764 801 719 759147920 325 356 999999026702639098 505 799 782580515 5 609 999999558313306235 155 837 126315555 129 20 305457929 355 246 999999936245600275 380 680 943661450 705 662 999999367183946734 516 701 380699721 874 623 51157909 449 364 142648782 379 858 342734547 223 459 347287029 213 886 999999333962322823 203 339 999999627630906251 917 911 999999557325404054 384 588 761457192 720 558 467194952 197 271 78327356 42 433 878087807 453 125 913612471 237 142 819641131 438 359 61446901 588 860 329411105 233 878 999999356377936807 428 238 427690516 400 498 999999393596158947 328 196 999999552148826730 524 242 999999214277473812 72 282 913956844 546 61 90862626 920 176 108994436 403 778 999999333679834083 695 555 999999671343001287 496 308 999999720219472499 128 4 201210751 231 33 999999992784491945 335 98 999999436633358528 296 752 193910551 746 841 999999760341732117 130 555 603799273 805 195 143222769 372 631 999999922165584857 649 379 999999245502651679 20 38 342430182 584 619 478933782 781 351 374938613 398 649 973538395 91 330 837734083 823 537 72206037 831 701 999999628172098479 276 740 999999358010436904 357 372 999999230208105250 866 239 999999638706813731 796 411 74505696 350 137 999999686731155118 235 738 882322465 758 607 334310259 542 556 708706912 761 734 999999529469043875 504 490 999999466767272983 764 43 999999950751683289 583 334 999999442203209541 116 250 561761750 495 602 999999963943660141 280 351 999999227989030803 880 521 999999809883235676 39 251 45166174 784 809 999999793131065124 323 866 999999521042185843 370 649 999999285761738999 918 803 879759337 565 594 333875969 203 428 999999150354066300 532 66 999999049517763359 442 408 999999043538615785 279 396 79598417 254 797 651567603 29 732 942976277 595 251 999999214554570535 373 125 875907177 841 45 922124186 547 376 999999373446131446 404 701 694677462 128 840 999999978003258550 843 487 999999022842938215 438 421 903091309 168 149 42935893 187 278 999999974698378118 754 31 999999262499659498 185 16 288191306 630 158 999999703360965785 555 796 999999984426008994 761 246 626900369 344 869 722523459 577 607 377443436 297 231 999999206470029728 485 285 236388023 594 474 999999959732853512 191 378 999999159381288899 171 421 999999120187904240 844 617 452423940 583 175 999999636221858790 454 545 999999780776365050 139 840 512741466 385 145 313665344 246 91 385305528 314 47 474677152 415 445 999999848893477164 670 189 30397269 470 2 358656221 250 830 317788546 534 337 102058978 364 380 999999297095298614 779 903 417441043 142 84 193372986 424 470 999999267297708690 849 867 999999466302588141 455 71 208106277 189 145 999999445821475488 515 898 999999501326955078 820 611 37600003 709 103 999999070979126802 384 638 999999262302007351 253 249 999999894333988102 793 314 725537876 553 168 79042290 823 782 619762991 608 703 775000292 123 763 478915486 312 112 429893472 850 24 656311360 211 852 999999586645880859 181 322 864491223 149 881 521532690 117 360 999999363481000406 803 71 354972348 579 393 999999059428969511 620 307 948424714 485 236 784068807 603 105 633655219 543 600 999999351209123196 833 78 244822741 746 126 211433874 736 508 999999899501537255 539 332 814338674 406 636 999999380683144719 400 886 999999545303029683 712 47 957356384 173 2 999999765131625956 731 147 318086798 684 717 71949268 19 692 999999481458581113 308 444 307053444 821 302 999999017103498335 904 249 999999461500819823 198 458 979229504 378 175 771791511 796 546 999999882834284645 57 598 999999136927259185 726 488 999999684373589143 223 636 583824802 693 773 577116796 598 597 291085844 682 365 161480835 566 188 842736821 415 900 766817096 405 404 343023801 593 882 999999090281046747 518 269 999999781912763136 52 564 999999001768719712 564 460 999999004973808758 310 789 999999062676497303 196 158 999999739698224459 609 256 765601413 474 646 999999698487773724 810 636 887191915 397 775 999999228401799201 94 311 999999784707829391 243 841 850422140 230 123 999999842946335374 848 238 683941812 532 19 879134513 29 246 956180436 442 481 265637660 553 139 999999868426441057 827 185 999999651402749620 322 846 908121571 214 133 711184588 545 701 999999365067654990 824 167 999999371000992342 657 917 653562588 522 686 999999221086690414 569 801 999999121535956568 205 249 999999098229465402 500 368 999999257560002549 458 607 42706623 569 461 999999542087350008 440 799 999999373878272543 367 382 215835809 625 438 999999221168682276 217 252 756003845 177 419 999999264234861597 849 449 421161944 747 292 164638556 154 74 916024100 721 270 922221429 429 892 999999658559000000 643 22 261311243 554 15 999999940259903903 490 783 163731228 764 644 999999894252763342 33 774 999999418254253764 90 83 999999797243002647 72 206 703558551 702 259 28011486 362 186 999999254387439198 451 475 999999343775811784 362 921 862516833 395 61 654570062 74 802 999999401107226633 877 675 999999358430450750 280 556 323703000 55 195 999999974892195896 418 840 999999286056588736 890 491 462846370 763 255 999999640176996817 346 642 999999678749068883 106 474 217542506 113 115 999999783263222834 70 756 999999980158270511 391 137 999999119589425375 919 34 999999495824286400 504 553 999999340612601942 511 40 999999337833629408 35 513 999999601797801351 39 462 947304542 766 610 999999768565593924 150 769 702892845 879 50 999999784376765883 397 872 999999521291285523 453 546 999999520941105241 511 906 933412972 826 614 99005205 402 736 793562632 560 440 999999278365434164 4 787 699513414 814 623 939914972 804 350 999999997409842934 471 105 308817354 116 454 220721706 79 627 799790897 892 283 999999453190527323 52 53 933283058 68 514 999999650618723528 812 285 855953948 374 176 999999647401815741 647 797 999999004957211220 229 436 80089774 578 490 103215610 339 610 999999343845694759 891 92 748131099 477 619 156302332 705 731 999999269324583510 825 131 236996665 646 850 999999248771600056 393 899 999999700569732972 630 221 391499768 907 624 999999602243880327 176 240 999999895671937690 32 407 999999918012003252 790 781 516881468 132 306 999999808551876916 212 424 999999663143964568 534 528 831003589 843 148 185744294 494 158 999999464932200203 783 788 650065887 430 98 999999393781424051 201 179 445414836 320 658 999999508412639436 719 449 826683560 66 79 896442783 780 226 36076532 653 171 999999446493154846 713 304 999999777935781285 210 848 413724106 794 125 999999273045178599 494 897 492067342 257 617 388542455 273 823 999999984676595054 12 639 999999248747026689 853 274 310969648 772 120 999999089225988838 445 257 356717914 394 906 999999283659285027 199 119 509841533 400 641 886693147 464 270 999999633533316372 86 741 417941362 726 168 661160488 854 629 999999905519233406 782 96 999999459089472815 487 410 482980105 874 518 834421947 7 803 405541991 277 691 999999719590316772 529 845 999999576248927783 596 221 531041439 403 563 111236618 502 874 917780643 450 597 378487631 675 647 999999671871715704 916 592 999999015409920051 540 161 329125830 267 467 265359358 380 465 999999134775866230 856 22 999999194448272755 880 582 541216041 244 618 999999224936944742 359 396 999999242683027984 95 207 638871014 393 803 999999747456094333 898 98 999999063555144830 774 39 569248986 81 316 999999851585251915 631 392 934784981 265 727 824661830 418 774 999999044276406240 311 675 999999501270991866 637 802 999999237627342214 793 177 934802023 869 86 331290496 270 133 999999978341604913 864 857 999999872685962533 751 138 999999994314012886 4 126 775866070 521 839 999999006697546872 493 547 999999988042543941 266 304 997615706 789 101 607807080 21 55 796876891 182 230 999999101239907290 437 534 9461397 523 251 767420645 373 823 631626623 731 690 342914472 577 193 999999200175826069 864 685 881042367 486 140 646088304 814 883 999999928224151958 617 892 999999795716250656 626 861 999999447789745820 590 351 123517922 308 516 321374423 794 693 88507657 68 692 999999983923251783 540 40 999999807193013067 689 40 603985399 916 775 16933688 448 54 999999395604865414 889 343 429877727 63 50 999999656786740190 85 90 969856577 890 916 548387544 5 254 999999922237330319 183 240 999999669513613816 439 153 13044668 71 245 257978115 665 283 629665385 899 22 999999791191881883 771 842 999999439690906991 132 185 999999571353817798 181 798 999999281016737294 834 837 999999144153057764 250 766 999999631931014364 27 474 994227918 81 643 143906759 315 831 14017614 502 117 999999742510295682 480 249 368823028 527 189 999999603256447556 443 626 979277660 909 925 999999512669740053 297 464 999999859836757433 303 877 408983059 882 656 999999047013037115 122 588 748464465 558 283 40910373 425 715 999999289675999045 456 153 861106759 292 589 999999171959775903 870 888 342904511 908 491 234690492 777 498 999999982483259762 364 418 240747622 526 233 999999987092280565 59 420 999999872431656476 792 208 287111959 688 242 999999987233303892 424 328 135146506 658 565 938327556 773 713 999999037359533275 116 523 251039877 565 760 999999640738856178 777 212 830496784 316 195 41652386 924 19 872299969 92 834 999999310171914218 351 364 81353602 387 110 999999752521627051 428 769 345621981 382 830 188697110 878 124 999999905301841589 165 560 999999522085347022 276 735 999999881922637035 528 845 131729079 853 628 999999561743828283 21 58 458952819 371 712 999999304320498049 824 314 999999192767324383 632 575 999999685917487083 255 620 594903884 853 779 606299801 897 138 999999126687548908 592 823 783167520 483 221 999999526528801809 591 500 999999128357770806 459 138 999999541113844650 301 254 999999331649757802 537 521 169987496 748 636 467098611 709 520 999999236925854347 605 840 253370768 227 54 999999305311614686 224 823 871614059 277 322 961838360 894 243 999999286611335194 103 134 926693942 848 28 999999873357593144 197 573 536489070 470 651 361178585 240 769 999999671733454538 437 77 999999495903278277 497 665 999999118553545773 32 350 597345737 546 755 662050912 220 513 999999136674397987 800 898 999999877946043653 580 286 572467125 50 522 999999363700918265 608 462 770134584 15 133 999999506916609770 179 480 999999182604285588 258 142 298340240 833 580 999999436720864225 164 568 999999119608369807 594 356 46137395 270 734 716863262 297 68 999999568889337825 268 796 999999880388973879 571 385 999999981449680188 902 723 999999842245360614 405 136 999999916601915978 170 796 999999821333341001 48 654 136844598 471 185 999999669098816337 128 92 999999666867803188 371 887 999999692189030119 787 802 122520639 595 236 999999754649375666 485 735 188716152 724 134 312809908 121 383 794199027 246 125 999999243031669235 311 160 76317857 206 923 423604035 878 353 999999256803093717 473 874 373925955 819 177 899442255 707 482 999999834708718829 707 561 999999827267690942 219 724 844050147 180 179 999999758735975169 293 475 507749430 599 292 999999122684405555 696 383 929297306 203 524 635534677 745 661 404136597 460 398 999999727524165294 256 672 309593421 820 796 510112940 894 174 855515115 408 606 600560409 779 293 854877905 508 904 999999687138907492 389 47 132051985 137 513 471825180 185 719 999999389181308149 228 90 999999961435090787 770 251 211072890 233 427 999999159888093812 896 740 999999696658036289 542 334 999999019689413614 353 341 900898559 710 491 999999440341300557 339 131 999999684382705717 436 469 999999658442446135 99 806 660961758 178 783 999999945673480919 311 556 762386035 239 223 177201115 411 756 999999642090462941 239 653 999999346413715424 326 32 999999483507884481 93 161 280278085 821 333 999999621375416479 6 522 999999260821521656 736 302 828937714 109 304 292559865 613 853 999999919874760018 364 371 906790408 548 169 393640547 169 439 999999521999332930 737 658 999999549975782796 454 156 999999038275105220 686 727 999999406181965884 489 872 999999623334377542 341 853 999999558470693095 610 669 999999793733750540 146 123 999999526957177886 792 386 999999497503833917 448 253 999999363668621716 448 71 57529895 467 758 999999735394729501 324 638 999999069956172573 492 658 999999706393911813 749 604 614882833 629 368 88364304 777 267 999999438370512822 710 249 999999654582201304 805 786 506152885 719 292 932747383 659 628 999999575907450730 121 426 999999493492307702 311 398 999999452509635526 408 788 757393512 78 445 970224255 394 337 999999531512798371 864 865 999999562288647362 414 392 999999695508227205 868 206 384870060 541 639 340012598 852 337 999999870191049382 50 809 999999249668119244 908 300 423757001 22 619 744569038 435 572 999999591578276344 318 170 999999127027543773 909 249 999999076524963537 516 791 999999206229908559 497 676 551169614 359 925 55329956 370 676 279140078 738 616 736142922 231 577 999999848039588668 65 234 999999321509100239 470 479 999999761179565447 360 30 999999671039869247 413 672 534303333 419 301 291525615 795 869 999999974631374024 251 802 163821188 361 180 999999187108536764 42 201 999999472257466237 57 555 669024700 833 698 63562809 739 655 999999385827128101 307 69 522064614 709 518 972818618 587 410 336164859 578 785 999999785250988850 93 854 999999023672108189 125 909 999999031274204637 76 669 999999332529152838 254 603 999999416945661708 869 155 999999091926703494 772 683 999999861881296979 667 280 999999703356413562 30 846 190617684 313 790 155064732 723 127 999999912194171758 714 418 778457574 23 614 999999605266248715 213 446 783993359 25 691 999999457682754444 859 363 775937936 613 627 305466632 156 207 446745816 511 392 999999603289656804 607 802 302039244 364 145 288093469 117 652 999999315744847394 846 694 999999570663816215 670 275 999999452928416796 201 579 481161572 257 186 999999499791718689 249 142 999999335543718711 862 309 999999987152276136 383 604 337303648 711 485 999999715248111878 339 545 818959199 172 13 999999411222742035 843 389 999999899557029531 766 392 999999832318768438 88 734 999999500237207341 625 486 123596730 693 136 999999710979777081 134 185 432855905 738 6 999999048845517065 348 102 146810775 352 228 999999232381896603 614 303 999999711463855399 520 898 999999954708791153 180 446 38541512 331 737 999999874419617973 103 309 25953756 122 232 44125394 8 178 999999065741675734 345 183 999999707917243536 204 359 999999011673958906 520 837 999999079679792810 412 622 297493498 882 41 43023711 545 627 16408744 879 658 999999329209927675 603 182 999999146654235847 854 451 537059052 50 32 767850698 586 790 999999921559920241 457 329 999999281201443934 97 752 999999940670337465 562 908 529038721 818 228 565479126 135 214 432967871 793 513 339043781 535 373 999999764982692409 455 567 120511023 840 341 681032933 676 235 999999922680701812 104 751 999999154904392567 701 28 804068089 106 652 999999380627704793 163 408 249063629 786 914 695165789 86 898 856639880 824 595 166330052 65 923 999999254323548670 108 309 999999781443169955 140 490 999999863667203792 920 105 999999185919366323 905 298 348339746 305 597 127274299 120 352 999999806713397331 205 312 150538772 767 35 128858197 597 813 205191826 664 733 999999221395668544 477 248 26089040 322 151 786752628 417 321 312940398 140 337 249450004 675 709 999999636549473876 26 594 904784629 377 814 930120110 686 48 650942855 222 789 622890508 512 632 999999831510847517 795 534 454460117 683 811 1864237 582 146 999999189764989426 374 574 155716872 858 884 999999440945207937 376 55 999999276504571504 849 151 999999645190344160 704 122 999999268004557527 915 826 999999361373731683 523 381 152095471 405 521 138510499 742 290 261573281 901 405 999999148568782664 503 769 736669902 212 23 432369717 713 624 421030761 778 294 999999425246478910 26 179 612379598 375 513 999999424768883676 89 723 999999501433679591 405 358 999999233883999633 914 278 999999698490633936 893 567 999999343529560573 539 636 532414884 750 514 999999994721263904 832 613 254176246 855 706 670051357 877 542 999999375542014800 887 798 999999232213435045 559 30 999999907301560701 792 839 999999510551220205 616 795 999999384456207746 396 909 999999918971935101 603 460 999999427548730509 241 124 458771188 594 733 119586870 563 158 718496669 204 90 37830531 542 167 525262977 454 631 900634264 381 168 872163328 338 597 999999845665078576 113 453 999999150367856684 897 434 687391409 122 402 293802456 172 652 999999540547395866 304 323 999999570034200886 295 434 768816822 914 876 855004293 644 883 703924166 78 517 626605102 838 707 569920251 464 846 823335589 45 407 977719528 706 622 999999868981540926 590 396 999999676860513054 450 764 999999899212605908 170 633 726719036 839 857 999999823414751816 624 442 999999513864904933 578 223 999999899348701003 388 62 341090870 721 98 20612838 596 442 769625931 360 413 296362884 211 6 999999126748671517 162 769 999999710905887137 6 45 464941947 283 478 999999945272566878 470 82 999999000508493970 725 474 999999020440620800 612 365 460268576 375 241 999999166373845308 90 621 103485814 400 380 734085416 756 806 999999230997570317 84 534 494461816 282 119 999999886431097351 263 381 541684688 863 418 999999840397120103 894 736 999999328168578860 638 38 999999395615082972 581 756 257524158 73 211 999999601574505060 62 857 999999874830169963 556 769 999999724045469167 867 771 999999788625934999 452 614 999999128539286143 168 8 652921443 303 820 144474831 551 761 193800775 560 261 999999107773481166 455 216 999999844541872068 478 106 218578692 87 636 822143746 29 174 736579229 419 151 739830636 368 480 757712721 99 594 999999515251347306 892 683 999999679208997388 691 337 447643988 707 11 999999921958073852 656 449 866732769 294 673 999999896499086285 839 706 999999761182343352 62 232 821793894 290 112 697251166 652 518 999999337200764875 634 333 999999540669239790 24 405 999999299980242865 755 418 792519683 487 311 999999667343586291 772 619 999999675968203730 47 129 941620981 50 81 999999127190189895 602 448 999999568306355377 590 896 865529669 298 608 88050312 39 420 64663666 607 899 999999487904426097 277 262 11581991 790 449 999999696524131669 265 131 422840614 769 831 460825758 15 95 316438597 230 650 792899245 609 738 388188829 32 105 815663384 887 374 999999730047866761 740 232 924688154 484 658 999999807416745494 324 139 999999399210639738 911 309 999999991654100012 467 302 561827604 287 544 999999104823009965 114 635 999999437948933974 563 797 159530851 444 306 999999971130079706 615 871 30504599 366 841 442748041 100 456 711387741 56 316 473060363 204 684 999999916315590778 553 63 935394643 96 558 925883317 795 914 611684861 841 482 999999640378477179 506 501 999999424679897762 60 624 999999696360168315 854 621 999999578991793663 920 8 465951293 189 633 446246937 349 476 585935752 422 104 999999974339628978 464 385 999999259201290380 420 721 999999367175633213 758 299 209934476 831 110 698130326 253 279 999999153423540795 348 564 999999283753440479 650 216 999999031664667350 368 251 999999035791900281 96 904 639808473 208 753 999999592285474781 271 727 789165511 466 606 800602375 311 421 999999433033779668 741 501 999999834808935841 709 652 999999697639897051 291 892 999999836115630377 80 207 999999232437100811 514 740 299006862 756 125 483389873 816 59 999999667392580538 575 745 725163931 193 378 999999268554382382 42 36 792463060 296 74 999999743017560951 692 813 999999253910468190 431 849 999999934287325837 883 214 815300784 913 875 999999820754650628 307 900 127267813 414 671 970609772 426 602 225345036 261 667 264770406 591 796 999999621323072821 278 609 333861939 733 531 881428207 379 710 838758954 507 370 158181235 354 162 897877551 570 625 999999751084734049 160 536 999999104093099696 52 564 999999972951839014 746 422 999999742734399210 15 453 999999839108040042 165 629 997220957 767 596 999999879138353093 381 644 849268683 482 216 980728270 362 774 999999078806474432 185 224 701615921 601 779 435365044 287 401 999999242618987338 802 28 520268748 277 789 488730513 60 400 999999935158229815 636 216 169523932 250 378 999999244028742493 384 277 999999533956070510 70 660 999999522588417984 65 402 999999997425437836 699 163 925571286 491 36 999999157555615368 189 337 304991830 680 66 999999287195465861 588 167 999999824514690204 319 555 999999579807116116 76 250 999999260057542083 359 260 13052280 672 694 433771216 411 912 999999858489075867 166 27 805974041 248 432 999999748644230482 401 690 777189728 619 185 999999285840887669 306 385 503563179 408 163 293092662 472 602 999999396859203622 51 493 999999787674421052 386 612 284246625 469 80 555747240 906 714 999999867350831212 82 343 999999575907872164 56 537 999999823443972304 207 424 352349764 158 823 999999442008805804 447 896 108151298 108 427 703626696 334 903 843861591 418 360 247839670 155 57 698739177 873 522 717569532 404 809 255941929 290 253 114545765 431 549 907699693 817 423 999999634777522237 457 52 936106657 38 847 415481064 389 333 744571762 444 152 999999562421762855 719 440 97622061 303 145 200085487 856 487 999999909785735010 469 629 999999487845651411 421 794 999999248323897851 205 865 140881781 876 151 999999259577036348 163 327 999999851586940692 269 667 999999471781480510 652 689 920093397 903 168 999999210970599437 361 581 668184714 832 392 999999887296511273 727 232 999999939618331256 575 164 999999000476028280 658 716 608909317 340 241 999999471851218474 234 786 334102693 767 528 999999134107959936 414 740 999999202851521539 247 365 999999814563832115 259 475 956575961 53 869 999999708912567192 82 156 999999167972388480 370 386 999999364281174410 161 836 822427996 328 634 242804446 126 334 999999045927839237 452 87 999999261564367397 375 360 999999253491543646 274 583 571250338 399 99 999999821572918464 664 319 971049752 549 781 999999427628420929 658 397 75644921 159 73 999999210220918437 408 233 999999656292436679 257 624 36719969 808 20 999999687158374871 365 304 152301068 437 336 999999624717978272 300 798 999999993941678698 498 322 225497513 184 224 999999060571439459 117 797 999999701906582853 153 847 999999759479095572 78 579 999999647426065351 88 746 999999904576213380 138 106 341036956 430 505 267462206 70 433 838829431 893 465 999999395763319485 392 377 385969091 131 395 999999980738631838 282 151 999999702562653853 259 851 999999240240137775 507 217 999999685616830291 298 475 194643235 595 40 787790028 57 676 999999303224912242 93 2 441570854 725 493 999999711031369724 842 759 999999611267597735 536 65 999999537415366206 479 27 398785600 618 438 849254715 200 475 769055610 838 690 999999990482440298 16 490 999999010864866972 744 236 999999018752458366 634 145 88906336 413 161 359341996 903 246 545387585 17 182 590205885 368 715 786165809 749 262 999999574807080442 228 860 999999338096275772 427 175 141988914 22 592 241160931 743 178 680247228