946 927 1978 1909 1000000000 667 444 999999848822372397 462 139 938737909 225 711 999999513843421516 564 252 999999561999447908 865 590 829978721 201 489 911304646 825 33 999999111185452145 603 234 480152734 456 855 999999611358179864 97 82 488433005 208 229 999999899394986920 413 202 999999540425661746 80 220 999999060764460352 441 747 999999046092911927 671 545 620487996 285 780 282194941 299 83 371514493 922 810 999999271795363351 501 861 192436519 456 765 999999492939329250 277 327 193594544 167 305 804202720 670 166 999999694243375019 806 326 937563694 169 428 999999747696675020 234 505 28014007 408 67 88172831 228 873 999999681615223281 478 612 999999428594368847 561 123 199038411 692 501 553869483 581 517 999999611575550347 196 193 999999827923158091 398 527 999999974408993605 407 334 716456670 581 556 999999683670617766 65 695 700211427 111 462 999999061242172112 816 414 999999765214829140 876 33 999999874913623871 416 3 999999373987704568 598 188 592324432 382 615 678286657 911 872 999999066483337783 245 451 999999037846030827 289 123 124566033 656 723 683291914 170 525 999999821111955665 841 565 824989505 535 215 999999250529946611 871 678 819162518 206 363 602895195 184 142 820320144 603 605 999999186187907410 571 795 862743682 755 568 747661795 594 635 999999141990644952 56 144 750517081 325 854 770709538 9 830 999999306646114183 28 37 999999633730642851 734 896 999999834012043121 160 483 73452630 910 531 323126515 495 304 999999685166824033 897 4 999999833342404520 522 836 999999025308566129 246 171 999999674077256132 919 390 478713482 265 436 999999151054359072 487 145 999999006756387207 578 2 603438521 839 724 999999297274099785 262 29 999999672483551709 226 319 999999803813784109 216 19 999999966837021690 488 417 999999123763732030 394 267 650189972 759 873 906650572 448 706 999999978013587945 830 722 956789680 519 163 661893927 294 422 723103357 511 308 999999205309638993 289 772 133900520 807 326 999999023004188837 337 670 706498893 564 474 953619054 662 186 676758204 924 329 999999811997589234 921 463 999999102451142947 245 186 595603813 793 637 112680970 11 395 297436916 716 294 442256360 401 209 578217787 812 346 874562748 523 517 999999058433516574 688 904 146629382 352 114 822997599 919 204 710014718 83 877 999999533674289874 751 416 999999337685864723 638 878 130338939 86 461 999999469067829899 501 300 999999784060952728 914 419 999999402165162675 859 304 332932596 559 629 325347360 317 812 569487850 643 111 144927848 624 161 999999999852244800 722 635 999999326659349052 580 879 301066671 802 724 183027012 828 457 999999086235915367 338 65 24598624 814 21 200919921 872 409 999999013057966335 804 437 999999288369253202 519 273 611954602 862 745 517419828 905 208 988668007 382 598 892214140 202 556 999999623497737725 115 22 724971814 741 730 481498697 132 850 959698292 47 75 999999881556835373 705 205 999999757759191277 277 374 935120772 629 300 999999567561629660 870 109 658706917 253 261 999999339931012690 384 829 926938208 181 325 999999284797000307 919 598 918728268 772 258 999999667739013568 618 288 966640616 637 534 40126981 707 274 999999364694834490 456 662 839598745 125 96 334503367 311 852 999999091337516785 324 389 195163695 556 508 378828011 479 584 504302931 788 724 298980755 315 171 63430561 59 481 999999316462844749 25 839 379399144 641 899 233527080 40 239 406213756 425 682 999999394250854180 904 839 822671480 716 419 999999761272877843 689 574 999999605390234501 474 806 999999225064088097 362 438 866578528 353 49 999999302866047798 60 749 688643329 641 527 999999885002101321 254 700 601860478 37 668 999999495199252051 912 195 999999918429199144 177 499 501331003 303 784 975525761 536 772 999999426471316651 351 57 999999392688041200 181 799 912286005 204 227 999999656392349336 264 373 765440898 492 770 848493284 650 15 999999727886473735 701 689 999999876560813509 895 308 530666121 597 467 999999046716182998 268 214 883684833 296 615 999999272850092542 680 466 999999384213078936 319 582 274413138 806 751 658341244 132 98 746350473 606 864 613525735 552 784 588933980 289 594 999999837158063184 409 809 999999123923491945 30 269 852861383 534 174 999999539245549791 894 302 927640427 605 559 999999177485003193 647 693 130237143 559 538 999999855103804138 493 69 999999227785612383 829 611 27237979 325 485 999999223253377162 765 188 999999366075852796 278 620 206907832 244 188 999999086215550741 43 324 999999320163239073 493 423 417309717 597 791 118301037 927 388 326256888 275 448 999999473627188008 561 726 999999331845348606 646 822 999999508070290614 207 51 999999437575904295 697 264 978040678 684 166 999999818729414176 155 847 999999228669192068 263 344 999999864069008396 263 241 788415679 259 665 758618139 872 33 999999015143816979 25 166 810431126 417 103 888625308 631 811 438619249 354 459 556753648 762 402 999999674351370233 171 466 999999284815479096 699 584 660454275 637 199 999999304483407391 923 278 330503507 888 62 592684945 653 834 999999559832313085 794 436 999999418265093969 613 799 324604804 326 900 319172384 177 816 174798822 610 834 999999190253554870 251 537 861999254 673 169 16539242 378 347 999999655460186990 99 869 346317774 588 715 999999548323514469 162 315 430213599 463 766 642025697 905 352 320950804 451 852 317659525 204 308 428562160 836 699 999999876913235505 677 464 999999515040219803 132 489 463138622 111 250 254167573 752 354 666317477 573 656 155606583 258 107 753608440 774 722 999999155358422309 348 441 999999611558076518 745 547 999999479065739434 21 498 906991429 142 691 999999224104937762 493 804 174837367 766 736 678280809 913 351 181781503 868 27 999999708207533536 343 645 999999495668678639 818 580 506095736 575 827 999999114080254106 316 255 999999022553530057 392 885 318258479 910 738 999999243657438587 651 601 999999250522439573 195 215 103877000 844 393 999999068090894364 514 617 189183072 469 33 999999145633200904 724 279 846263630 892 558 644091833 454 32 114887036 450 591 999999585553902436 72 821 782043886 352 424 999999938606615285 316 366 999999502182401810 430 905 999999619348157333 166 751 999999277540351964 529 528 74831255 188 427 999999951007974905 821 684 999999420547282715 487 732 877872907 152 864 503829468 450 197 337523990 231 110 999999627228791172 247 902 999999688759639626 744 56 999999321245801701 740 25 999999515339819903 447 53 335062018 761 624 999999074941735618 904 44 999999065663043207 744 823 291165916 13 292 999999718264521033 554 220 999999004642257978 723 812 30581044 34 194 285448430 202 904 999999921876289894 745 15 999652625 630 228 999999220328038040 40 794 929777451 438 632 82938270 155 843 462736201 60 283 999999339062644776 79 502 999999338626117386 487 67 620438468 15 765 185815337 150 601 999999987411915237 54 343 999999403877167037 594 357 2485257 736 231 999999029367653369 572 380 600898201 174 870 225145314 352 396 999999985535110091 143 616 498553684 633 119 999999831977805110 482 795 999999949697840616 358 444 789106783 633 816 999999594025142105 787 890 512388318 918 370 336917598 389 565 999999864889086264 149 313 154192707 857 215 31541169 345 274 438404384 56 205 490377943 707 144 482557996 898 92 42859933 349 219 512797018 202 769 332133852 118 601 999999696003274563 452 61 637347929 693 704 826735672 781 81 599507356 527 148 999999949170938080 256 846 999999933685621118 617 424 999999709311115254 775 545 77491900 70 471 263348072 641 259 682746878 170 523 952575679 140 835 999999589970025751 915 832 644205177 29 636 244486996 577 662 999999517190588283 92 637 469167917 346 744 378850483 752 853 999999944248766393 830 219 870098993 225 736 999999314332687949 52 823 999999180066006718 302 354 869439393 3 124 534336906 291 188 545101739 890 759 999999740691664875 612 517 999999195454157634 140 113 999999261069738581 874 864 999999602059905988 649 727 999999509516382432 104 298 388851731 164 421 999999145839373525 355 299 964668778 685 922 368706690 806 811 999999974785201214 539 392 390459789 419 114 51242880 816 621 999999447711825338 14 715 999999793323884722 660 404 647236576 655 387 999999630573323565 685 811 999999754402510826 713 279 999999640099185641 691 304 626091456 795 560 999999323863461621 24 42 999999457312155614 396 298 999999985686723359 119 674 999999416479618710 231 768 999999401338792794 463 372 286620145 848 91 999999932082171698 514 701 337185902 120 878 999999200331800897 214 245 999999815160998400 612 462 999999206903826496 925 782 729792908 209 905 491696931 90 198 373006541 19 351 542887797 625 644 999999914115604846 357 169 433090299 304 563 999999250665000903 356 705 532719165 847 192 133336428 843 641 983372129 912 21 367084027 911 384 938637138 833 126 999999638356801871 640 865 999999540483579360 4 606 999999330439371960 660 460 962208105 676 431 999999566454052301 826 546 999999167612740589 447 702 999999837376270575 560 682 999999633046417714 373 432 999999033455774783 347 105 692436642 360 870 853334919 190 473 347689618 923 779 999999990388743684 507 483 332859797 276 515 999999137692115723 77 91 999999484780915137 376 920 999999999518353483 589 51 999999234590020344 426 34 999999762973252503 42 425 762051981 648 875 109727980 231 318 65846160 619 709 999999997539151395 900 813 543013177 298 872 794357620 414 729 999999987698625909 684 730 999999652054551305 121 176 999999642249235137 896 816 999999709660868899 162 714 129737129 429 300 999999424776108652 780 351 999999321595309199 348 14 999999336848414524 143 390 111526041 370 775 212230218 167 601 888004273 799 493 982680386 659 686 999999435810703841 535 696 871724049 913 614 407542094 749 231 999999048718965485 576 644 999999797529427217 504 864 999999523496818489 710 832 3859558 444 129 999999830201613255 605 232 999999703615436035 235 515 22119210 436 255 498002682 22 466 3497071 822 548 999999705162497200 743 25 377618213 761 263 999999888599905041 71 147 999999613847439808 779 305 422402525 879 330 816842297 477 500 39365749 885 81 652044163 349 26 999999426694750281 652 286 949872808 55 284 174264910 342 479 999999499303377505 179 416 999999853857584748 5 82 999999057151488459 227 721 999999561108032163 861 488 999999105881806087 562 608 999999654403834035 438 287 999999636791604514 169 558 999999846724999619 896 235 55667375 778 309 999999412881123607 79 572 456555058 414 736 733351412 765 834 370286741 32 566 383680947 359 300 842439436 450 530 999999739969711941 338 610 732267534 525 123 759631632 16 760 832595635 221 776 545675098 302 40 527131203 227 397 999999018567514838 422 371 999999964675629525 800 426 999999498518475589 85 710 999999432553779888 903 829 519585521 358 847 999999390296656749 405 607 199655505 368 295 999999158981684637 900 736 396792887 167 869 999999985096910786 740 501 791477637 145 675 999999241568213499 238 201 999999008648863959 133 446 999999076811107651 652 157 999999024823131514 440 531 81481309 192 738 83521065 488 658 999999862553022707 548 789 990273555 748 62 49804109 727 283 389203525 536 588 206833984 586 481 999999290069108601 136 906 845789586 689 745 999999103657461028 289 446 290954735 502 50 999999495978867827 122 686 710390534 397 355 682515129 164 824 245671228 181 652 64323415 803 73 999999808021556731 452 76 999999754739414080 87 563 570434248 917 901 999999179268605127 504 762 286193809 528 789 999999531430475013 592 363 999999514653944488 661 167 236127219 645 440 309929919 759 442 999999546570223031 286 848 999999468279553855 814 269 999999313238472683 201 567 999999432246437424 105 504 734023030 22 91 999999112855301560 906 67 999999482395053894 718 42 67139992 461 237 999999236399387813 622 55 999999208341277788 626 873 764664190 512 417 336447909 53 129 403798902 624 365 506461443 6 565 999999163857167627 925 342 999999952008224311 274 331 999999290430813909 431 556 743954759 33 126 999999712551916609 374 27 999999257471310214 616 447 617443551 795 165 999999744078741878 733 792 999999192912054211 493 192 161024954 525 344 999999669797759729 607 424 495207025 24 734 999999959604342699 63 687 495375546 585 24 999999970775526633 451 834 679042383 415 298 999999871662335182 219 448 765340156 74 752 152577738 420 98 757445934 530 48 999999807872654284 114 675 999999235499823139 426 459 999999059506505360 461 798 865587219 526 245 954555177 212 657 999999581398826831 81 115 539213680 825 40 328521859 404 169 716557551 9 405 809956928 813 628 999999865162264375 483 460 118645570 34 612 994543292 669 298 671744462 153 335 58647665 369 889 999999769814417926 365 424 632247735 327 78 999999105466867629 367 160 317793641 517 621 239371880 68 406 999999528460089429 233 503 836237165 823 527 999999321312639894 683 86 999999964934868806 84 60 555319126 699 879 999999814568618673 319 807 468427748 831 343 999999400064388101 732 659 225704238 454 741 999999005332952961 311 185 999999532388527120 777 784 999999707001053173 300 706 999999294678053621 680 425 218832802 492 430 423074437 882 310 999999277686511494 666 518 999999689078284720 913 88 999999560966431865 30 484 999999074909081699 786 85 999999776590999541 20 86 999999047199570899 885 19 999999800521175018 262 657 899040352 67 363 470520262 852 829 454352672 10 699 999999297337680890 296 495 999999137001356495 569 295 906284152 457 831 999999676817824369 135 822 999999721188044905 168 422 972636736 147 546 999999607162897648 377 592 999999560769528639 576 386 779914533 178 538 999999995081858472 76 584 999999443221461731 83 366 999999733960856903 600 138 318027173 765 799 999999821833768820 82 535 999999915001432988 423 89 819169047 591 689 545436635 77 651 999999785037893089 232 464 999999639676321287 5 437 682061372 609 129 999999121302887012 222 807 999999836986620167 447 215 999999462976680787 50 174 291083709 266 236 418574910 469 790 799828910 371 694 16278261 623 884 999999057005189870 14 903 999999145629741546 40 368 999999450832645936 64 385 999999595906233331 762 35 999999844547241520 19 53 536392853 374 817 497070104 617 157 999999845268615246 271 789 197551762 695 538 999999359823729908 790 807 435084109 146 685 999999507787323250 226 316 515409040 877 16 999999372259474600 736 604 999999908225227556 573 174 903866921 560 65 999999299697147029 229 616 999999652642565364 855 344 786793905 9 86 519891018 590 478 635843431 378 402 999999013024751030 392 478 670063463 20 371 999999758066798834 746 583 787383721 657 843 693381429 346 536 999999952151537945 372 390 999999132889062162 815 414 957697709 465 720 999999910837822417 702 491 999999177821148894 920 313 198707071 443 926 444201463 697 363 999999056812318896 721 321 438891701 391 870 999999370287197315 907 217 999999590209835571 536 286 999999010051007813 885 689 999999171202512669 457 90 844896479 597 651 999999077782106367 291 78 28362947 784 83 999999605146293832 781 738 424024104 545 198 989105400 284 689 999999199469379845 402 81 999999502558224491 129 724 628283712 343 599 108481757 664 447 999999158497767038 381 625 999999770687422947 156 589 911706628 194 695 103907654 889 894 29631093 307 651 732943965 850 125 195991173 270 553 526089138 485 249 595613706 390 466 615772165 833 66 862416466 142 54 26164118 553 74 105374581 385 448 447439908 71 760 999999142153693643 227 286 999999104346292285 516 107 999999522022814459 276 915 999999993159895912 249 236 999999154375215332 273 417 766223584 688 553 582357033 880 612 999999018513259184 377 115 83870395 722 123 693526669 881 287 999999708169563836 497 351 818895779 49 225 695976208 554 116 999999095343882230 45 504 999999200115422469 726 662 999999979900280358 672 204 62811239 451 247 951627466 387 417 163840126 739 488 999999388092257573 327 535 999999188769062857 883 823 836028892 723 724 999999836649523101 277 108 920337592 35 422 999999528433043556 535 694 999999893149605519 256 35 999999641578296461 161 688 772714220 834 248 999999177192829092 599 73 314716833 734 571 945544702 479 2 999999209071851235 346 531 999999477104681133 326 294 999999531763050086 516 478 225774010 186 328 999999655755198594 189 399 999999705154767472 910 803 824620417 790 292 999999834909607243 303 120 189891187 382 768 999999221931263374 904 733 999999652679836679 257 52 548033312 914 510 999999849057310927 214 217 46955631 530 347 999999474050830933 683 509 999999357721604669 788 590 999999316040242726 46 682 150859493 604 502 227821016 719 330 999999533316944419 313 825 999999801896689351 303 380 999999064309056992 691 637 999999239203193612 215 112 802453517 646 678 295555038 99 242 999999737074956108 350 442 999999889640744805 334 32 999999326516450794 439 450 840001844 524 388 407791553 694 351 999999257448700589 448 36 999999348175589728 36 545 14376977 695 35 999999311786237140 424 924 999999267589250553 807 922 557040905 445 331 999999989387106748 601 661 42972341 653 188 999999420426580925 406 248 842271433 879 750 473034758 835 757 989718828 82 893 332596458 338 235 999999290839579075 692 512 508012461 91 103 999999346155823078 884 818 999999655724616152 535 169 999999989441698255 895 599 999999411646319816 166 807 999999607487465446 267 661 999999612279965073 831 254 191007294 773 385 999999694138142935 99 435 999999824303042383 501 537 857775055 169 129 999999263549627565 214 747 247515448 176 182 999999202696149149 271 513 999999671360701386 123 459 252818203 552 377 556046533 767 36 820864840 75 678 999999036434717067 887 514 696136467 13 16 999999806731404203 273 673 855692204 908 581 999999906100152275 903 825 999999484896013502 29 371 999999955274216446 586 351 999999485556527947 651 268 372724165 926 71 999999602410240721 48 830 918803201 51 186 178494033 421 58 999999465348993580 485 195 658050125 213 587 999999974434767762 754 635 999999024194948001 237 427 999999483318496767 179 572 999999267246805407 900 378 973967973 287 699 147458825 884 152 999999530750471266 650 818 999999422540098238 126 392 999999190546812116 569 58 742468802 301 249 999999250776941057 339 143 999999769550073691 451 738 999999927730939099 354 823 999999604355038942 121 635 32367888 883 447 214467776 418 816 999999369480823958 737 673 153664442 830 294 999999051227347883 634 429 999999906444304951 172 319 999999804108090472 403 645 380109985 100 875 999999939163283366 394 241 999999402057710182 107 598 999999903827321764 330 264 999999998290050146 515 837 70952888 622 818 999999082703234058 636 361 749677772 317 277 60594291 445 867 974711017 396 917 999999406675289869 638 174 350565034 703 918 811210017 108 485 999999746267709826 915 718 999999350565387518 632 750 999999122907894654 704 897 999999572452212140 728 803 999999635639472149 449 173 999999052161307331 556 49 999999000380183002 179 607 519583823 856 745 999999819143420382 42 416 430441300 730 887 296253991 887 567 919760818 773 84 666210047 673 838 999999629197243845 574 119 999999454433480322 89 372 999999626527879281 429 79 800146744 256 252 724430092 230 542 999999946831995838 825 226 479834088 41 363 999999596885227528 99 183 43180786 190 541 999999280654009308 701 513 999999411029112442 735 919 999999740594396661 888 717 785160764 652 43 275479246 748 236 999999234254574463 411 401 999999431406479000 504 415 19189898 449 17 140048008 527 601 999999078241500320 143 127 999999107728862580 307 459 999999218638888346 568 395 999999103191440104 234 480 766966762 799 488 480658570 350 834 999999626052096608 835 822 999999164365782648 326 535 490211012 265 258 999999136918102147 879 155 999999221578939515 584 869 999999734314611392 212 485 484371800 901 679 221872506 809 500 999999131253830415 768 885 599065660 457 165 736303741 343 725 230963521 553 73 247423283 858 461 999999558861886499 97 167 812619980 265 349 999999858670707948 855 291 999999123792215897 373 51 978737080 149 725 551510109 762 927 760716040 245 96 999999414106385652 598 155 999999696208785109 682 439 999999412393665762 410 465 999999950560874294 544 144 999999956065405821 171 179 437585883 750 301 701687697 507 554 924387330 269 326 999999898035587724 270 418 366476624 415 840 468720214 442 598 565808412 505 165 999999183381501167 67 754 423817714 221 359 251565546 6 674 999999752333962235 58 207 999999532092153009 126 799 898812614 842 884 999999385147875942 168 766 999999034454957617 110 227 999999080634551082 225 749 999999324514578552 611 177 371355742 551 589 740526684 61 368 999999343964356789 681 136 999999324092191312 455 750 999999892865644522 583 871 999999977624423410 332 535 872635354 747 257 999999599239310590 564 407 999999534272415824 898 180 740749493 713 279 999999176717414250 97 113 19803931 703 52 999999949777387958 356 541 999999256231256322 297 903 999999101840005547 863 397 810831498 628 635 910707231 771 782 638693684 369 140 999999034037012637 33 694 954030444 595 404 3301322 607 466 134504129 33 806 829676647 545 393 999999686342853290 869 83 83824009 918 136 368145702 847 855 163147579 660 408 17422395 763 751 851153280 646 926 999999823468604213 263 738 999999003241999371 346 681 304095893 595 837 562245706 425 87 243987631 924 31 825272315 250 201 991971107 490 379 999999325928238529 380 748 999999934505210498 615 69 452497661 525 166 739033640 110 408 676591244 552 194 999999698836334441 181 890 999999717447440288 582 598 999999629635147273 587 584 999999649640916104 608 317 20789449 220 41 235818289 557 440 585988735 113 912 999999768160412262 859 487 999999076864281971 789 445 189197903 604 869 340331634 844 414 844274573 318 237 999999785695596287 834 478 301751374 769 448 913818759 795 821 384814440 611 438 999999473379731009 817 662 187244924 886 197 999999950781244526 473 128 535528594 457 772 409778884 915 870 209201813 70 73 999999424319051558 639 300 999999709935275946 790 678 999999881640711825 261 317 999999442578136023 356 645 370705990 119 607 999999160075916532 266 691 999999655400826457 476 809 920551754 602 409 999999754873028195 474 911 337145655 565 12 976273377 324 310 538523350 62 303 126065958 165 829 958636498 873 223 409872314 368 363 839056182 300 231 999999195633741300 679 382 999999378862511604 122 885 999999238587229432 351 310 454073012 809 250 608601290 820 279 749525224 667 271 999999641652106875 292 723 999999590057925574 630 454 999999556666135581 102 701 999999648319355175 282 547 439587368 144 604 524823363 614 520 999999822238805789 354 444 999999539276180127 147 22 999999896326924993 694 808 999999436520839325 205 595 999999340920697828 288 142 916799842 868 573 916660643 85 83 999999263720307311 805 830 999999058481732771 674 893 169097740 184 642 999999079282423585 511 399 644609866 295 899 656110051 113 339 223835982 150 567 999999587085100448 553 545 878266564 521 207 999999178236799608 552 159 138052046 309 725 999999486289605165 788 580 999999389599537352 862 527 999999297061287724 89 279 566869119 473 698 999999433588401578 298 871 999999377502784301 920 42 936290524 138 562 999999238150404399 286 354 999999376516488424 407 336 999999969528569831 162 543 999999972031358115 216 137 999999803738034941 309 680 999999922799731000 760 196 999999902456160104 718 575 398575633 179 262 440805403 662 849 999999335087307154 364 657 923829993 131 662 999999914421651615 47 478 999999019253997682 342 290 30842002 106 924 738201810 38 647 999999176802341563 84 33 999999477564225437 468 727 526678467 754 210 568989571 358 683 321329793 878 183 999999141435115803 178 220 999999961838539004 403 68 829276229 416 121 398932529 858 889 84936383 344 824 711723716 799 558 999999421331421685 531 821 677242632 659 523 699293559 801 160 727670673 144 263 999999736159877920 52 596 999999734462178784 842 193 999999785288965981 38 763 999999859462874646 615 215 163575224 840 112 486000189 542 706 999999382068474879 550 258 999999219221574103 312 919 999999463300076877 317 204 999999919842701285 687 632 999999711656966621 745 616 999999721207987268 641 926 999999922881315210 855 791 999999359113363139 796 512 999999992187226104 508 920 999999234165128903 481 49 986011223 147 764 999999770613578775 95 269 999999064412734797 627 132 999999697864048412 739 87 94831742 733 122 999999237326777850 310 724 822440161 272 723 999999345315912086 184 756 999999123573297856 260 761 135192347 172 822 999999907189621468 306 643 899042862 146 714 824551453 845 709 999999404503921700 421 629 756781950 275 478 999999303737066436 196 406 134534289 720 284 999999467853257897 600 785 999999721169511010 65 303 160764930 725 386 199210119 459 795 296777282 642 563 999999993974034151 528 167 999999837938899649 844 354 999999551216800327 391 563 881035070 830 250 999999045616308258 322 870 999999916727005897 2 772 999999022245399342 708 605 999999484794965750 702 705 999999849241239857 460 550 999999658808003589 496 805 999999863431133557 385 761 997528856 50 421 137144742 309 368 999999452810756178 185 527 359509700 687 440 999999843276147903 621 834 534654958 114 803 999999510210806987 192 131 999999219869971597 700 390 872967036 848 900 999999199112453854 320 107 791248656 210 689 875888930 124 167 487662084 128 795 999999104973304484 64 121 550190000 902 448 127210715 518 443 999999331421348153 612 757 932804574 339 736 999999631439570295 742 451 999999180266619299 469 202 243287342 722 49 687738085 547 478 408304834 804 333 999999631778393929 402 41 999999778200733137 274 525 656805149 627 425 493492171 731 589 999999700734524656 388 592 999999852137900091 840 848 143952496 319 505 999999473726637718 180 216 999999933089242133 828 105 523074663 492 556 999999589500354527 159 727 296181047 177 22 999999082591977880 99 788 999999857451999138 94 323 77800327 595 620 550154765 277 421 999999974702568002 769 539 697669309 767 918 624618020 598 501 320699667 668 864 999999052627990737 2 470 869140381 120 639 999999209962437087 475 339 999999941340063586 573 392 999999297566503191 668 885 999999426921951355 908 141 999999913635877795 598 788 494986594 689 798 782691288 352 651 869861864 43 121 602017199 899 166 970634439 819 338 999999131147939104 247 348 825573657 500 872 999999470431046239 199 727 999999961300299763 453 585 999999925375812085 168 389 999999424811423777 592 719 999999280830219611 252 267 270410334 107 68 999999103245870885 255 466 999999623546016815 234 8 999999626671906185 141 91 669164496 181 57 999999770761551599 100 529 148251252 461 919 418411381 810 179 999999358537750709 919 94 999999256375791981 472 557 970562117 488 94 999999954214708059 211 273 173887453 304 699 520664689 259 859 999999958832438965 884 409 999999194932668093 480 884 999999916740673388 816 899 320961308 509 431 999999182737275908 397 49 999999330487725534 689 408 815412025 608 387 999999165440250715 242 521 999999782064526967 269 782 999999612553881873 735 495 606416603 154 729 999999877431558180 647 194 999999022169738456 279 363 999999780503483004 237 417 338604234 174 368 428589545 216 699 848364889 782 417 59388647 37 371 999999355138184621 799 291 999999601601976498 703 177 999999391191918910 341 810 999999452929296555 658 715 108766095 281 770 999999388484256424 94 90 742607192 331 545 999999045813549937 494 592 567080575 54 157 999999892711526267 328 793 999999636824707583 828 52 714006449 38 158 908757784 926 792 999999447199802758 860 390 999999573871769959 427 30 999999062129407526 854 318 999999713644006710 672 34 999999517347890092 861 730 754712133 363 798 990818967 215 205 999999160924010155 867 563 999999432539811612 30 610 999999680925162764 343 448 999999467825563890 242 106 999999346726204310 431 783 999999463595463638 914 172 999999153909212541 470 698 999999829856085885 725 184 397198493 201 792 595443943 24 301 999999929049241241 271 82 111896154 69 274 184306300 103 300 999999334441174133 625 694 999999107890359001 370 818 806480667 920 343 999999409013709920 523 6 999999608286984708 72 571 999999950120598701 1 44 999999706523482151 672 371 823886101 490 354 999999483914296800 824 883 999999482814786567 28 327 607696459 293 740 198170732 789 363 211671632 180 530 999999426089624892 308 33 999999667041260742 59 135 999999254015728224 704 4 999999621151092835 498 563 885303243 536 116 999999932985621164 236 661 754793598 396 742 999999138104108669 217 488 698512897 668 820 644428674 316 325 999999434840170238 737 765 999999349855517000 222 804 999999659857873783 813 594 620511397 41 316 999999631847329851 437 8 999999096623667242 456 738 779127459 178 818 999999614474988349 614 908 181437349 439 63 2353058 27 356 9203774 675 625 999999718294875030 921 452 999999945144298699 783 530 322086926 298 508 311939776 693 851 741018378 539 113 999999795974152200 158 317 999999023535310014 465 852 212261534 3 226 769974228 709 784 483311999 727 616 999999482781078184 749 815 999999603282703342 512 768 53953431 578 720 577601961 515 870 17440045 89 902 545769036 617 106 41110053 186 56 871800636 55 642 999999491606905091 502 560 999999006590526356 109 453 999999987212696728 590 566 999999066195757494 540 834 999999981737684728 486 528 901815263 543 885 335488703 538 482 556927278 541 189 999999558017155042 686 732 999999915989153946 191 164 669039512 840 563 113366463 182 835 108073174 414 657 999999911648310561 392 784 999999127416799354 562 37 999999902084271100 471 283 552511288 744 437 999999902504525541 849 127 999999611405938062 619 689 793645763 557 654 867974333 365 900 999999269029054381 183 368 999999440727460094 411 319 816959483 904 60 435089151 214 420 999999708468381114 721 587 999999336980758441 110 271 999999869844146057 838 379 999999307863801357 144 455 359160878 65 173 999999074470954364 184 664 147066092 17 488 999999736415662291 686 716 741690468 84 200 272321557 474 568 999999773714462311 55 338 579892723 751 711 355695057 646 621 44085939 124 156 999999538595434882 425 45 567285411 100 55 999999669884561476 654 245 999999058016683180 260 66 882256627 785 312 51526467 503 103 999999487228225086 498 899 999999914878246842 579 534 248791851 775 355 999999367448965738 385 544 431963571 801 294 999999264266129381 112 260 641379884 105 658 629130962 642 743 275599198 230 690 876005069 911 606 275609992 247 340 999999956828797140 697 68 263137993 450 505 548010367 875 353 999999393317249505 432 215 999999854502500478 157 521 519313370 854 66 999999121574851420 240 784 110038071 826 550 999999065509025868 208 574 999999727497919582 560 903 94090731 905 630 706965149 417 775 429668505 88 840 999999113809075042 635 266 627244744 639 711 999999952235851507 584 219 45233809 745 150 431574966 335 129 999999852045705316 910 559 616853351 484 30 999999594386246238 681 683 999999522521494212 846 100 191165512 57 738 999999445745006730 784 259 664833818 98 155 999999160503911260 446 833 532640696 591 499 999999889506683233 620 750 198258377 171 755 999999978316420220 663 790 800477901 564 296 442064332 448 232 662048958 816 815 999999813966968034 341 64 630370864 839 571 902502463 495 360 397280155 846 124 999999678637261490 178 11 999999786743606199 137 317 256161220 362 284 999999710675629372 893 403 999999425035597644 898 507 999999241961886395 393 835 999999237763197369 857 306 489408293 52 786 673480618 708 921 479348039 4 177 999999383549219884 791 843 999999947817637888 404 478 546812383 550 773 999999501337148773 478 279 999999700454307927 452 467 999999197312096207 361 417 726032114 596 147 483387685 291 595 279698671 24 795 999999945444444152 791 818 999999952139309943 506 544 814600150 314 850 533896678 923 55 999999159104693561 914 399 999999086715010528 341 400 627704540 496 455 999999170831735607 136 51 745972248 657 495 999999675178855635 148 310 999999398871524012 37 922 188745441 757 530 999999051678969650 816 865 999999074423780011 545 756 541635676 783 589 999999098060016894 758 803 274272847 527 364 258317714 267 265 999999233725891960 533 188 725647413 391 420 999999162221147660 312 191 999999640350270987 696 806 999999006412525815 242 692 999999328757716951 834 788 508883111 109 107 381046128 407 391 19959122 660 746 245787829 218 422 999999344980639105 676 53 999999259420393072 315 180 888327012 630 766 999999606011602849 506 167 999999140999491778 112 743 246096993 31 798 941461640 73 427 999999320644123822 722 834 999999357887421054 800 317 999999840289798703 898 810 999999370358297436 386 915 739339551 918 442 312487374 796 407 954017872 467 542 999999548965057604 239 589 421110696 630 367 924910382 546 840 747821480 753 82 999999257340661307 623 359 295904324 420 706 366247409 852 672 750648666 14 677 999999183956162361 659 772 380521571 667 852 999999639635710333 418 841 490603219 669 481 81875104 410 206 334909941 204 129 999999295629528275 340 198 181743698 833 761 999999985497036666 315 915 729851358 172 312 999999279099580233 16 915 999999130887053948 150 752 999999696803947135 412 230 999999404616837311 432 806 999999551735773620 76 216 61637947 471 798 48735639 715 394 999999081625987135 83 701 952905811 857 170 999999357033806133 741 519 999999137160844694 205 81 32152444 23 240 251882856 208 245 71818705 345 572 999999813721263422 365 523 999999883888736838 332 501 999999134628490724 537 300 999999709989752137 908 326 2699140 425 800 622338184 741 51 999999502878579704 355 478 750198273 175 269 930804008 259 442 999999876931179417 248 516 593772676 163 202 64777833 74 923 725480460 257 925 999999020155827652 606 125 999999765049088447 513 174 150667884 628 493 204993615 529 99 999999264707839290 38 106 326944469 707 56 472311229 698 263 149847343 321 579 999999798531283809 26 531 999999851754218762 336 829 999999694311259822 771 525 999999832066583218 203 314 999999076362222313 681 695 999999636732769286 353 790 999999245368393138 427 129 999999730385815560 483 471 999999606178105007 749 493 999999404406629470 10 549 999999858450438474 591 346 446935416 145 852 436617286 807 720 999999278169263586 316 241 242786113 173 701 999999198902202853 824 208 999999146630938329 499 883 999999148307773641 800 421 40637039 665 400 464875993 546 266 958387535 656 373 999999927783776808 278 649 999999439790192152 814 393 31043841 186 279 999999237993059173 530 701 999999290109926370 690 488 999999177183856743 433 105 790372497 769 701 999999188359457353 902 273 44026177 811 495 53247106 711 520 497787721 376 9 511243939 138 708 282685783 399 300 999999194679510892 546 343 999999402330672513 116 588 977548130 646 378 999999280842528123 588 273 999999970740346121 379 527 238256445 531 599 999999248461979140 248 464 999999232361780773 510 769 999999220224912958 794 107 999999549927692474 648 443 999999718118267354 134 110 408779288 623 276 999999035704701652 380 695 999999502935538060 590 201 793666143 891 207 23048796 849 314 999999984896061552 485 115 999999171492348816 413 859 570625115 64 890 999999482531644075 8 476 199949472 92 428 615822791 523 385 312728416 725 576 999999064792273548 350 568 680807916 366 779 999999395867195112 868 5 438141248 669 592 404191005 866 316 514177077 207 169 650744807 563 300 606525527 408 706 999999104936219193 896 381 999999828743694487 760 887 320156351 837 798 350447233 881 47 25515000 723 194 999999489024692107 84 836 999999150926725004 48 66 999999766314726603 122 176 501543646 90 693 999999973011561530 547 818 999999566955392813 713 372 999999288844769375 548 433 664173808 706 129 999999283268877351 917 440 909869606 707 681 33399106 849 927 884357318 395 75 999999841772732255 872 724 750368244 494 346 999999559578657707 686 273 354444835 247 646 999999222288429101 615 271 716727975 826 827 758189297 792 645 999999930876814936 246 827 753441569 369 305 999999595888692463 579 417 291990750 428 728 999999491948070621 345 768 936476478 697 198 999999532055261335 105 916 766340370 736 731 999999997013988038 390 406 51599345 191 8 999999486372289542 12 910 999999279797698111 357 17 999999940833027259 617 67 315200917 542 121 999999051203161475 806 675 747190517 705 765 143170904 600 423 999999925600255810 167 13 727674659 5 15 252769587 238 290 999999414590101999 499 713 373435994 818 317 999999395272919293 322 758 999999508434168565 693 310 999999490369272993 893 637 460315504 43 361 999999823925821543 65 701 906126698 2 414 999999104397219900 820 237 668868678 719 91 999999921731940698 115 557 171388199 894 400 662598889 107 925 613271343 247 751 999999555135532379 823 379 999999519633055495 151 738 6836042 194 723 895644164 198 395 345626574 756 615 360190844 209 680 999999853007016897 625 713 999999005384287117 388 752 999999447916811322 494 67 999999387943528193 275 503 862454838 101 622 999999894744550364 352 636 999999700151777087 916 221 999999271127902558 797 266 706657118 491 900 999999669429576509 377 248 933254825 198 522 27071010 908 586 999999143264405552 611 118 999999790162264910 918 174 999999783676241139 125 706 999999537099731171 434 559 999999569308230705 197 729 999999985214744366 78 766 999999840187547226 603 755 940284349 299 269 129503174 868 917 853409959 281 134 999999495916551053 99 22 999999466856464603 142 505 999999581917612594 123 798 999999013321785079 46 635 923341891 484 736 999999131968751596 763 99 588691881 147 535 999999886375278289 479 368 944765863 476 618 999999540729940383 28 714 999999926369751252 280 592 913675100 259 866 740268361 422 719 302009490 550 841 999999144181296595 590 401 19484465 902 870 61833976 253 727 723606500 827 168 852624505 160 198 999999495530902130 28 850 837353294 45 295 999999578464574068 534 153 999999012712817739 489 415 847671885 176 285 999999916925931513 260 89 999999373975627794 381 600 661361738 200 165 211228400 580 169 999999676665193513 777 243 999999725552561645 419 861 999999789747666591 566 420 999999378812119162 302 762 999999332688936042 467 857 999999202626171072 364 672 789672064 589 602 320658293 926 198 999999417598189970 755 150 706002784 7 330 999999740357563225 372 245 999999867827049537 323 526 999999999410068206 68 436 714952185 338 782 649335743 413 61 999999237940925347 409 887 726957247 185 790 734870191 262 848 109658400 562 500 999999944519963400 293 779 590479912 146 361 999999055657999145 330 150 999999789908430161 601 437 99568641 853 173 411366361 391 257 811294687 727 251 819679364 670 216 999999496926773613 172 455 784167614 108 386 91976164 764 442 999999750497134878 497 353 938169615 542 40 441581297 103 373 999999729250525934 165 867 361473573 127 43 999999558807972094 257 501 469024967 498 753 999999518494082566 838 792 480718807 861 399 119036286 869 859 999999934136014697 377 432 532100595 211 67 441045796 568 58 999999109936080728 54 237 2246539 880 508 999999377736026893 406 882 27818868 572 811 999999454001980350 563 458 436753107 241 917 774231919 427 308 999999683658917415 470 508 999999117499340571 314 772 919940150 826 400 857341428 772 697 151790089 388 454 230024265 336 269 999999316169316020 644 792 999999731537154101 96 706 305338013 301 712 999999633025134543 282 51 966579798 643 270 999999559359975648 683 666 914704597 166 219 999999872685371793 212 137 999999130644856625 840 214 384643520 440 727 999999614302902643 647 501 999999911802303409 572 147 999999498414067086 215 240 554922378 466 186 999999898273196656 746 545 405628927 464 476 365319400 395 661 693134247 824 488 999999573274030855 275 105 999999627896399001 431 287 317740071 827 162 999999645511075427 451 69 999999094766713845 593 10 20343479 10 521 903059787 62 448 999999384806039999 101 880 689822966 885 541 35171577 776 586 287702890 511 708 999999483479492036 815 188 999999639429779532 676 708 999999994040071323 285 404 645872068 400 737 998467027 574 549 525014492 78 889 316658474 808 65 842515014 762 301 539686259 187 809 398734684 368 642 999999649365277207 244 926 999999644835155852 826 742 999999087947507925 741 349 858798464 223 316 26097665 714 240 999999831990433951 155 307 510735310 626 416 999999365787429579 750 244 753248993 224 283 222316575 329 836 999999497806561657 764 861 25643299 8 783 999999063191821338 452 581 384655934 551 65 488900025 677 451 999999159121304548 614 510 828856981 291 105 999999142158019438 631 910 422496120 371 368 999999824787218203 243 813 979100422 450 528 703305227 847 248 799052901 664 11 235620426 130 319 533718407 268 607 646530738 386 51 729001604 48 777 470097991 660 169 672708231 832 656 798033366 134 864 999999878126268597 465 504 732864537 316 174 999999223899796950 39 140 999999699394739746 447 357 802073991 727 301 999999389196739023 736 310 999999094563349133 570 40 911894323 698 363 973880998 765 136 642405998 282 847 995146764 851 416 999999847499487311 429 43 447783188 708 911 999999976277093112 185 803 924943356 441 628 999999201021987591 405 876 999999078872721206 852 179 448349742 137 417 236565078 514 127 860731017 595 597 999999387725888485 665 52 762942456 301 423 65710971 224 677 999999948023216762 68 95 999999627641616540 187 704 999999127793214209 920 576 256796237 71 381 936272040 837 925 350220091 622 285 316976104 333 384 938635206 86 338 205101646 608 288 702438443 520 51 999999765841311096 543 896 999999166133888490 555 910 999999405407623129 230 256 999999760051993496 823 756 999999199823976122 392 51 167014213 442 170 999999661797801385 233 14 999999505055804821 245 57 34708629 18 38 210917223 712 524 956187324 890 833 999999088502964055 213 904 830328295 139 206 579155539 909 604 999999437764972027 738 169 999999146230147430 194 926 50111163 175 235 814154466 117 205 206082782 678 86 524497391 434 871 999999039030465927 261 88 345556928 679 639 4963510 632 865 184151159 337 73 475594108 874 297 999999118628319500 532 144 84059756 776 326 778790431 76 741 725414598 628 305 999999493708351105 186 594 999999747072430290 259 806 999999486539193891 159 348 515076692 921 241 999999376761063960 458 861 747881494 49 532 999999913877580484 107 131 232908525 864 267 999999052763246188 195 677 999999031426857242 112 909 999999475003726000 291 124 999999134773617170 292 915 999999273287356339 471 741 999999369335527195 713 254 736839399 234 240 999999338036511486 499 882 999999682747020849 360 901 999999757356272328 915 204 501715465 726 189 999999700709642416 718 848 999999256122988632 58 348 604849848 279 525 305812791 77 228 999999667173409350 658 25 321516348 34 232 999999248192518669 785 854 999999953656446580 49 417 999999700487189741 727 478 999999446777157265 869 575 999999813424044669 193 693 999999273654897096 645 607 867911401 104 331 999999857371772367 400 840 765055763 855 433 599220557 661 213 999999048324115853 477 653 872700932 507 727 296666654 544 173 999999313617321735 647 761 999999040325560787 209 922 751475864 650 622 999999675764237245 906 461 999999119198128087 453 526 999999090925101885 666 622 691642449 290 86 755549731 567 228 983190682 524 736 116033454 375 657 323491426 517 871 999999007232501399 435 295 999999024303821217 182 326 999999328886397954 52 384 999999234851603198 892 100 920140255 746 431 297110035 251 799 397994042 907 876 999999366584591418 142 169 760204919 442 830 999999335477122919 502 83 196463069 717 527 999999116922316487 80 307 999999777422106334 190 373 135641359 87 530 951561304 321 391 884004062 347 33 496970225 549 587 999999323714260066 546 844 999999882739062441 179 79 844300802 41 26 999999301279911585 417 267 999999578579713614 377 803 999999676778718622 677 514 999999956810898706 92 574 999999491340774402 729 314 377487600 610 74 999999110163011399 924 842 999999959791425234 843 232 999999651302218955 17 550 124889182 224 166 999999445674786569 322 25 999999464980666707 883 645 171960775 621 448 999999747295885496 79 520 90568382 509 401 425786456 310 857 999999131194906443 661 83 999999785627636607 495 607 649770113 556 136 190481789 116 563 46036596 821 142 999999295700492001 283 424 314190228 615 668 999999642142996823 562 394 999999045954268913 743 334 999999403244053254 211 768 999999931175876132 342 243 87989685 198 757 751020759 770 724 467510808 661 923 999999224347701423 368 145 999999515028735988 387 188 958711046 44 763 999999775939961383 66 724 495884282 383 650 999999737577224741 423 897 999999763618052922 339 25 73755013 93 570 999999078996470548 682 792 604318430 305 53 999999730345222649 91 820 999999391189607652 399 64 124900538 558 525 337287593 406 241 957975979 926 623 267489442 829 404 999999517223233578 690 261 999999884769373564 614 798 999999203012824201 289 791 133965092 687 424 999999944604760843 308 413 999999107449273972 405 371 999999611322362333 860 830 665826943 278 651 999999842602633917 564 834 999999239253367654 819 338 999999289173072204 360 211 999999940137720159 534 27 999999794906186604 542 777 999999180276220720 173 816 999999664571299867 736 470 999999687869259027 715 314 999999481302587338 32 24 942670375 723 322 999999678770399103 40 638 999999343358991266 651 517 286563077 861 543 999999931855130919 207 223 999999234276906344 408 762 300715181 109 659 167222688 325 937 999999922579610645 662 919 461465502 722 506 999999841110274631 537 431 951263253 36 555 999999132550375300 607 373 999999227859006114 726 112 797421840 11 882 999999139350309246 697 444 354842805 132 766 999999002742846357 945 500 999999905677646810 236 137 999999021357745975 207 477 999999033162504857 157 566 999999043501678792 401 552 130944774 350 77 941588081 150 723 873499539 727 18 999999475883100819 62 19 999999164601238838 592 645 984266407 579 5 999999307685354598 828 894 780241643 322 135 154780769 642 163 999999812732634605 327 323 429194599 656 767 533263058 78 200 947167229 188 411 161488979 32 524 927062183 343 200 931514416 182 214 999999202848542278 103 828 196765634 723 710 989273512 40 80 999999375118620475 416 765 1100529 433 211 999999745141617723 753 46 96513861 646 546 681193091 726 346 163288848 244 325 999999471106413552 98 851 999999454743631305 152 295 939974244 907 710 267325809 319 905 999999182061891996 441 750 256260311 824 649 999999940261900293 139 99 999999048313479677 20 83 52474476 356 689 999999164639174727 838 678 999999833737474268 363 433 752821238 551 219 902479765 540 623 999999353596389650 627 507 999999869591431540 577 254 999999522678777021 718 731 999999260647823824 686 94 999999906504247764 836 553 999999623201957231 310 313 713647851 524 579 34106133 375 773 999999245002580542 502 617 999999820368492699 640 95 367925235 337 527 559932296 434 669 999999893986950913 274 904 999999468088480650 695 882 999999417961189756 790 259 700372995 804 295 487268706 699 242 670557124 224 330 999999690115695311 760 389 460641303 873 436 999999256509234147 835 721 962141637 781 226 999999453389755711 769 312 999999594397481224 810 694 361773380 17 269 692587312 641 410 647051864 668 836 999999504826860693 215 691 999999818647580527 26 535 999999429727297508 886 236 470328423 683 184 559969677 778 412 166421118 106 592 999999837796490837 59 215 999999935447888099 160 303 848473145 609 498 159454258 694 429 999999144852620169 842 939 999999733168402318 767 934 999999037705719109 608 755 88266284 638 25 986845685 278 43 999999997273309860 480 902 654682299 311 563 593595114 102 844 999999283080063015 900 19 999999904904720768 71 233 954374363 456 163 3780607 193 156 999999459364970408 578 85 999999993646161697 754 168 999999446298555817 733 281 999999013458921693 571 443 999999833436008403 12 844 999999256075204373 28 375 4448150 727 12 278985403 166 642 970843192 360 658 430685396 144 843 999999185170596564 71 107 961913392 646 211 624507670 513 436 232281675 702 632 999999359592868730 102 902 757487802 434 65 999999870725470073 58 197 999999770150674777 768 669 57784465 586 109 999999223483361737 62 358 908127646 104 402 553248064 458 692 427644948 259 628 55876711 639 221 999999583489492549 199 735 999999652166884733 311 330 999999938249217933 872 200 993785729 766 777 999999084142552028 478 801 831094993 749 381 828656808 379 686 827060932 832 860 999999196101878681 196 909 413923262 159 834 999999275779215858 926 358 851819203 366 748 999999866432533257 717 888 883363955 815 149 803083860 864 496 999999405105994030 56 612 999999429086730628 345 629 999999852761648744 292 164 999999049397858364 170 515 805905506 808 199 429541248 668 177 361093900 905 682 999999858428419927 579 529 999999548331321914 159 876 997881235 454 324 999999507885166618 431 528 99202067 87 716 999999898085573934 316 488 187182367 66 812 999999709007119338 713 591 207245024 522 446 851547945 443 409 423458977 272 339 695899736 726 863 706606215 119 553 111066010 615 263 581957080 815 112 989483271 627 173 999999777153235018 839 931 999999318090365533 652 300 87528543 5 89 999999272146635087 437 644 999999209345785978 22 121 999999768927426725 556 279 129838231 663 311 898604540 698 888 366394497 166 412 999999873019736598 489 260 978453704 402 739 999999845100500985 326 908 999999828379682663 194 102 271135021 43 530 648513673 549 321 83465232 626 366 999999921039508273 887 706 862955600 415 664 999999135545719382 852 286 999999567141240161 150 359 243079560 192 944 999999233617577652 593 431 999999718695001733 758 515 52602605 259 591 999999937702627208 17 283 351532314 445 752 949360803 529 322 101470335 514 762 36071600 818 10 535966815 771 370 97797395 770 558 999999186030912638 469 73 537034308 521 633 306230632 2 362 999999009534091937 407 345 399498962 369 328 999999434519064155 55 211 965974713 421 646 45405660 671 73 999999878205577427 937 247 999999096836854353 539 190 477420528 720 99 999999881255276621 814 700 999999129853206501 193 171 702317172 906 781 999999470483445130 405 461 168185145 890 868 999999922655267634 205 775 10569068 382 480 31198457 418 112 36951160 587 345 999999393146382388 548 147 537770423 692 623 999999571382692740 486 431 999999993687219353 27 431 23830024 68 269 900593532 567 648 999999085121755331 181 204 738478198 229 330 838139777 518 549 775722341 153 369 999999632389002267 676 558 960937722 334 864 805720385 579 211 635460769 239 752 999999416447979025 550 138 998598006 871 916 365719671 520 868 900265771 291 401 999999414998762588 933 216 999999630190684157 267 139 375532620 666 39 182972491 516 295 999999833678074285 187 700 999999519866771183 944 55 999999733069773380 79 73 999999448788235526 111 833 999999030571974176 196 818 751912600 658 805 999999703275861222 488 103 999999733030672232 237 128 999999970303462259 783 942 899273578 402 420 999999569619564164 164 450 581181289 406 578 923189130 35 131 999999968482870460 566 431 999999127796519100 629 907 999999672958822785 878 700 210473253 510 397 460021412 521 556 999999209369095023 874 644 232965231 608 316 552050827 791 159 3251347 161 53 999999677048167531 476 634 999999410585918758 260 339 999999443111720795 932 584 784219751 808 43 999999407771913736 620 547 698891690 346 112 999999180700626092 546 500 350401558 830 944 518043619 504 253 828540023 478 538 999999208367128098 82 109 869605855 4 878 999999056938144006 192 52 999999338405996540 688 300 832056999 602 5 759647149 287 267 640110275 892 429 999999691342789407 363 132 964983376 32 577 999999126955189840 938 530 101111685 520 67 999999255749181038 365 567 999999065252824972 90 701 999999494974796914 833 741 285497552 664 715 999999087759324195 793 341 999999333428421673 239 830 999999843658144471 600 868 999999141715148794 774 650 999999074706937736 126 545 999999132408260709 247 678 263301352 270 65 458775194 942 110 81879014 269 73 182245620 469 697 112785660 123 419 999999053365088253 897 203 999999061527222334 394 372 999999562087268497 438 471 999999252343331591 470 221 999999327897011206 500 241 999999517633658439 427 922 999999064439608729 222 402 999999050580242186 848 20 579710031 880 930 999999531912654013 710 45 569305951 106 559 620500866 872 598 999999493551370145 553 384 999999328409792148 38 44 623773262 728 259 48216567 679 393 999999108025444330 177 781 999999206881835281 727 395 938004351 104 248 757673042 866 746 999999380563420794 261 292 112645925 178 243 324545994 116 825 999999818791635615 649 500 252611769 897 1 263478944 885 209 692991300 195 301 985910015 401 20 69780022 760 23 999999409103156658 234 67 999999969362888172 802 648 419308222 194 173 999999022478469109 513 886 266422778 382 215 999999920944118087 820 381 999999222251778301 70 234 999999167431963064 647 490 512350662 197 583 999999725237112999 776 340 752246004 279 794 999999309701895327 623 610 987397506 860 627 653733493 178 154 360674591 634 762 531567190 254 67 971585125 635 300 999999069725626982 223 404 999999596742891553 190 657 564647142 7 330 591091038 520 730 589441940 578 894 881725009 573 334 777463055 235 66 697984671 244 519 999999117255199988 603 28 753961625 271 933 445014070 665 923 916017496 538 178 413226169 271 297 149462498 261 180 678403666 899 177 163812801 109 245 999999417019653044 373 631 179148083 568 944 999999901524320065 299 859 778799964 738 361 149609551 775 470 933301531 361 270 815948099 397 885 999999265790778351 267 889 999999256335538286 217 28 999999309396638675 235 478 88833028 506 634 999999011306488547 699 330 447212820 1 463 394148746 414 797 999999983507973385 210 100 999999263738567361 324 84 215633720 634 435 999999875371676230 787 158 999999841549164353 78 757 999999708888542546 50 878 999999033517719333 569 502 842807169 428 906 624600191 253 888 999999546507695506 794 881 999999173427389222 550 862 189009279 280 731 999999751840250831 857 59 502074756 81 757 190331850 62 799 999999361718622753 281 588 489308758 760 739 103929691 220 872 86991195 847 800 272011237 861 755 999999289225049631 231 38 999999934285995079 931 916 999999061815697025 588 78 999999137578607968 396 877 999999487531469391 170 471 999999292889533642 756 101 999999680619896838 719 667 693901538 800 702 999999217730406756 922 801 311032908 795 842 453314145 818 175 999999137429133722 215 791 999999633274580116 367 547 999999239960378835 791 101 705695603 849 666 999999873603377813 696 723 473961835 512 892 729108449 733 333 921978042 746 345 145323498 165 99 999999248627921544 925 811 233402790 770 729 947394780 463 80 999999888564514510 619 777 999999741390401428 237 801 999999178778992991 730 618 999999953152387226 86 582 999999244940200633 381 407 452919210 822 174 582635122 788 696 999999965021785115 835 828 720059995 217 52 502554091 637 44 999999800872152124 684 452 326618648 317 912 859840495 373 930 367806057 19 16 982180701 507 630 117613821 320 127 999999412712946401 674 516 662884116 664 175 514849342 419 678 999999003109792092 254 317 999999292189373043 665 255 999999865436217055 316 914 204431899 279 44 999999747898566758 115 609 999999271954669216 840 591 888334622 302 825 875183883 326 309 17050651 367 652 999999312173810830 318 484 999999924777045220 763 224 999999079871518720 140 591 958029791 140 678 999999958914875134 724 348 724203679 232 640 922512730 273 211 972308829 746 694 999999933356612239 45 358 999999667361012226 941 872 343655759 499 834 738515332 249 465 493620252 213 557 129413602 579 349 999999967256330014 344 915 562432168 743 540 806640253 88 167 999999074073638606 581 622 999999527323601414 274 752 843411766 361 490 999999535190038518 922 1 801297250 386 853 783088025 744 938 506515370 644 523 999999323283248906 164 725 999999392374267019 612 221 999999107751657770 444 905 271947710 501 9 317960780 490 35 548955218 465 619 238035247 283 463 999999099663146923 303 938 999999458456157872 269 225 999999995994636336 52 109 541970427 110 234 546280952 422 674 534853213 494 375 633056024 107 450 581344404 805 138 999999384618345866 613 468 15285243 946 834 999999895797449049 65 860 635539001 95 115 185264469 35 143 824724146 293 352 999999748633125054 348 922 999999987446157306 446 216 106564918 894 766 999999410982232304 772 234 999999753637784529 789 613 999999856919322512 107 158 999999653580063275 789 640 999999609945643949 846 877 999999896351916977 726 581 999999182408524345 44 818 999999211653996712 733 835 703216109 378 314 999999607260932563 345 431 999999847866493288 589 795 474033950 850 699 977579807 725 739 235522799 162 444 567667477 807 117 573774144 380 224 999999061955844716 179 712 999999939779896957 257 499 999999505615960391 914 549 238842832 150 438 999999016706489615 35 305 999999179231986674 241 600 57518690 312 2 344207678 921 309 159075405 416 907 134190996 792 421 999999391296696656 692 248 423782702 242 743 999999725141671217 358 870 780663190 912 179 272224712 785 689 266283497 296 919 251716616 20 781 421301916 833 874 301431720 138 362 999999787815355410 834 593 999999040940334728 428 463 999999915630240846 609 306 556156839 211 225 326481296 573 410 90393563 585 119 999999197966056753 451 397 999999448941699719 864 175 999999005662864215 305 872 987030674 151 269 261351645 827 302 363391366 155 842 999999885217173211 877 74 999999043073196815 87 52 999999407048021053 227 396 999999078255227472 865 406 999999971121897445 251 250 44262843 913 225 999999038747944910 502 677 339327629 624 599 643654063 525 875 999999266619628622 686 184 918725687 444 483 999999030776794947 748 559 811903672 158 396 999999441103759141 670 598 274375971 242 532 999999791484737368 434 448 999999202895911077 558 299 999999747508556191 715 935 999999226569549032 737 941 999999439414257407 354 504 999999461061933892 136 476 369824650 496 931 999999075067757191 522 818 717861868 192 58 853898658 831 164 999999186701041917 881 381 999999531454812141 3 640 176837839 892 182 999999671688358075 779 67 839261741 806 940 133952004 199 146 999999522101708366 19 456 999999720163857211 651 897 413166952 616 161 697503522 888 12 578418713 816 72 374447961 624 569 598927013 916 295 999999514732358705 533 827 999999395958963999 30 148 139095212 442 720 999999590466278769 295 66 444411698 129 602 999999561730488362 197 365 999999757537826686 207 185 388663484 869 103 999999876979810923 726 635 999999964612856684 785 915 873421407 554 677 999999038528742427 451 48 999999483775424413 576 908 707267184 374 12 999999567627155077 565 607 48728125 905 27 999999710772911098 913 617 563551928 464 58 563573075 168 407 762481597 832 809 999999330954815067 910 932 693872544 47 206 999999580060142428 853 861 999999073444812276 63 383 999999794434641710 606 499 999999294522597895 25 431 999999650477565386 903 59 255492560 604 345 999999732191075219 374 769 109183888 796 144 999999728125328187 419 366 134127042 394 110 590065191 930 660 610489113 443 756 817231196 494 666 878855493 276 483 999999031044150222 687 84 999999786099286790 149 731 326870396 141 164 877390322 848 384 999999253837370781 750 436 999999455709120505 87 880 999999894090866421 559 806 745245158 484 500 999999548949769152 768 559 535289664 877 553 999999079787292056 630 728 999999348385515740 398 261 533535464 133 885 999999838247370833 675 490 999999223416549318 183 137 875798977 569 878 999999483898220133 108 83 406458434 37 437 284030666 769 796 221186043 781 719 65055644 400 737 999999566495477892 912 236 232194427 138 834 980950441 203 283 405187890 163 477 999999791459335332 854 43 999999729383970486 227 639 725658520 253 640 965063358 201 865 482162441 713 3 999999581242749176 636 685 999999203759223471 621 159 999999732209516822 233 134 999999960615123578 676 357 999999089749865427 770 799 999999076812521796 135 465 951401848 676 843 509931316 526 288 37106506 362 747 901328314 723 224 999999990618702711 898 200 999999949230989195 656 389 999999403178217755 131 862 999999084413894531 703 591 383375655 426 477 733294860 204 528 261418547 297 622 999999841539932249 873 200 999999141253218981 8 523 160512766 659 942 999999487825817238 100 323 895137086 69 942 283853789 541 895 945387604 337 272 590690821 854 26 999999920056713667 500 136 999999358841667238 599 851 630657359 845 697 999999560775966405 659 180 106732208 129 841 999999129170308776 249 354 654426230 363 813 349754998 870 471 728127804 868 299 134961217 592 697 999999718208249068 674 696 999999962699161208 650 66 999999995724445197 66 936 361250088 754 34 999999001243659069 515 796 912452880 294 644 999999198468267765 648 883 999999240776057744 186 580 752107037 704 178 986009382 506 906 828491832 570 524 999999312069225989 795 778 999999609987056250 844 314 999999838212904625 368 190 778720021 240 652 999999412329410235 488 127 999999253526349864 706 893 861614825 942 514 444165321 803 243 999999728126368476 679 732 999999580543536309 917 545 999999214012894390 583 294 994094541 888 521 447281305 209 401 999999402940880381 315 104 50040377 233 899 999999058321927159 860 84 396055412 275 507 999999904712430180 18 795 999999225807424952 108 96 999999386979091161 729 77 389691051 835 47 999999152589499696 419 316 999999948582593801 64 426 632284828 83 75 999999157798596268 679 736 999999203367546028 26 534 78662123 307 339 999999769809886290 514 35 999999025039368992 602 834 509995195 358 763 999999901491148984 623 73 75347954 725 304 182872585 886 131 999999229267912482 797 799 888331121 115 883 999999090223456312 714 825 999999784189813255 418 131 999999660212702221 897 167 999999832730880757 332 271 955257893 902 314 999999762499725462 920 783 999999966162085365 810 661 999999016028590469 503 524 431180841 167 112 999999234518291309 536 410 999999488243737380 526 389 453189796 419 78 396437191 567 420 999999719694777104 333 154 926463206 222 23 999999877487348763 454 921 999999166371501305 293 485 119360117 197 325 919209269 184 409 999999465528298468 112 37 864927987 230 755 999999330221895168 84 295 176451171 212 833 999999649299061078 262 448 999999398695162082 330 366 999999936336596141 96 707 36501977 567 229 551472423 117 93 477845443 166 558 999999343770189774 931 509 999999611961060224 851 254 604425367 501 726 435589894 173 630 541232326 296 890 999999258676549800 440 758 818589242 410 757 999999654274416389 644 940 626660693 871 148 999999594521012008 107 632 484591435 137 38 999999803391571762 83 477 619139735 40 699 349786678 769 717 999999353561641612 169 453 999999350825926094 864 816 833550229 13 530 516573561 433 583 999999553293594154 605 873 355385034 40 40 642787590 228 345 999999627915895416 852 908 274314211 355 234 418899941 234 872 852942247 150 799 999999675153743590 779 593 790740865 350 753 752351549 346 300 999999232111062200 29 421 999999663726013714 288 67 415630863 149 117 444887089 935 886 999999151693578309 889 583 148095097 470 434 788543564 329 697 999999687698799622 313 777 999999434516443148 492 553 473930382 532 614 999999457029008115 382 38 999999880308353798 188 884 972762217 813 30 158157899 704 411 818385610 624 739 386472860 628 38 999999554128982450 252 38 999999477784383090 740 757 397413662 171 846 999999829983098319 695 392 691491058 493 879 999999637548549058 737 938 999999694437233071 718 141 266773264 204 684 823667144 436 693 999999761818482426 227 245 280621199 580 125 588931835 868 469 734678010 308 534 118175072 164 819 999999521108240792 461 302 137661011 304 255 999999291490480892 246 733 684563122 284 922 650713713 814 38 999999461986114252 432 798 7543793 15 913 999999328612138093 770 860 999999802947637955 343 604 521624531 571 299 356454307 842 295 999999451191498854 256 919 955632636 292 244 999999347366814128 29 718 218955254 844 693 999999610689732747 886 254 335279979 439 134 999999999664519137 848 456 999999224774032288 691 719 999999328378055685 467 187 983538813 465 137 452997025 267 518 999999230970451598 678 815 778324541 691 270 994530536 607 904 999999633591347883 45 225 999999944948657652 429 825 863322171 395 877 362461140 635 83 113805246 68 118 999999619082126337 536 767 999999789407948088 350 152 333715276 702 872 248812173 372 88 278371349 142 806 999999830290925992 479 630 79619830 412 418 552497417 34 496 408792769 472 421 999999296746673041 145 826 999999971243163505 552 479 999999595968693583 285 851 999999361779200960 58 110 999999282748947807 879 311 999999334620034208 722 677 999999249039630108 867 940 888787428 115 766 436621205 124 872 999999606503166849 726 837 270857107 499 326 999999760586606339 662 701 999999593692118079 559 726 444744402 869 865 427369838 347 16 999999253840766695 346 632 999999170239048254 932 40 999999496496725894 722 358 205144940 635 443 809155962 655 283 999999576131246412 295 229 999999141655004194 794 874 645539252 448 538 571755344 847 862 827031607 272 884 125290985 137 144 781337589 646 431 999999987962756607 23 759 999999465591642853 671 906 999999575707953805 108 347 999999634112143177 550 894 67457408 720 904 999999513416686013 678 827 4594776 816 442 197460412 239 398 999999796605336799 650 802 675112078 222 682 131392367 580 802 767812534 495 635 878339611 167 775 611072907 416 17 739858096 177 661 999999223412749717 149 332 200264537 126 468 530899867 143 760 659162821 330 352 999999051239019204 113 113 999999125437081417 359 865 978506674 534 213 257240 936 792 999999593549313239 400 291 999999422959721062 36 446 999999667304517042 422 622 999999524526948493 399 927 76629607 444 418 639164450 666 453 999999365032929932 647 604 690279052 635 224 38868113 36 703 683076169 74 751 268910014 885 209 999999036953178251 560 779 476469945 560 461 467956501 290 925 999999510182265536 926 10 928723418 925 342 999999578156770041 357 933 625869547 119 494 999999663204783445 398 822 999999810215746271 504 427 999999325849504414 632 500 169713795 756 682 999999983145095849 744 277 999999830668162820 250 78 540960334 280 377 669972348 659 436 999999738908533801 632 851 583842558 894 777 999999799158941708 259 777 999999839858593060 943 12 463697700 735 853 999999201600753786 452 79 362411796 321 932 232523980 883 833 999999868468826276 470 864 999999833016610188 475 309 820282206 666 154 999999742157372965 482 713 999999967832257503 272 125 739614044 334 235 382789739 216 687 999999819621519946 913 476 208305345 910 926 999999580634232404 15 500 208356917 898 505 839461994 823 330 586352170 527 615 999999968714169170 737 229 999999933128272165 477 105 410468395 344 66 364756097 272 529 594933716 73 295 533037317 430 254 999999942508776814 269 124 999999702774074203 432 229 246644314 464 412 999999917806792735 781 552 507901597 126 328 999999578099679503 342 846 732754470 211 432 807322321 266 540 976481020 118 137 624050714 117 903 999999967679220634 847 731 945187065 278 744 473485204 491 272 784714641 268 942 999999008330009950 97 230 234586656 705 916 999999827888870507 67 58 936301087 761 487 999999919657731998 767 408 666254730 234 716 999999250849532385 661 829 14049595 489 907 250999680 890 902 841650560 285 72 999999600170521111 81 688 999999715747070416 799 74 999999340063804440 14 548 626626235 511 904 619173590 215 413 576778677 414 233 999999170885647225 144 813 151442945 308 17 321119621 287 60 532096010 929 487 444280569 31 921 82246670 669 226 141408036 430 388 238767524 23 244 51805924 242 639 999999982654207472 6 242 651284578 808 182 578463325 886 372 999999563809327900 240 104 999999470804170235 27 266 999999509302912881 346 478 540764564 760 226 983073550 36 662 999999502274742088 195 15 999999711776324090 936 114 480920181 329 37 856711205 917 944 43647478 311 81 488292806 643 101 999999950449574109 79 238 784851592 435 668 837158177 865 523 999999223105952508 845 569 999999534211262539 922 864 454634253 339 868 962055139 701 79 806700117 752 924 999999628512261102 384 553 661711466 669 779 999999794032619586 21 95 999999022493807321 429 491 327745113 709 634 301402538 363 827 999999232723196504 414 770 429932920 440 225 999999205987840192 811 491 508660192 158 797 614339509 104 19 999999456228965280 784 308 999999125497324011 364 568 243954465 35 38 999999669086799343 60 243 999999706610155372 638 927 973951597 548 221 999999368799173285 338 557 849976106 547 152 999999346718664217 283 786 999999759605875613 150 37 999999729014123084 383 742 999999341338587091 517 883 395973992 118 316 999999305199517581 873 728 373478307 200 136 999999145891291435 409 931 440469488 586 230 999999627044983767 34 72 373392093 335 900 999999351402434301 349 778 280528400 3 856 756702713 447 360 616692523 324 661 439262793 33 699 7589929 48 652 595057075 51 683 999999648003683339 872 492 841857810 548 647 999999938355903712 841 607 999999320289904392 889 55 410270659 427 653 720430934 614 86 755121309 268 450 999999338112517479 130 40 50095367 912 695 805865802 411 553 75612493 546 670 511013988 502 487 286935675 657 331 999999700321284892 630 559 999999138818668181 708 854 143016539 99 786 558664066 751 936 999999117192378550 466 273 901054708 56 406 926126664 897 512 999999154030907699 541 588 999999911868134912 558 608 999999472425212849 623 753 18235387 299 578 999999773712710807 628 401 999999581465071029 179 604 999999488357396097 605 426 926121881 937 590 208767601 349 894 999999202661271324 780 352 999999026145798636 39 4 999999088260530012 548 636 999999596357947231 873 241 883322465 942 380 999999051619013961 487 528 999999517784081664 429 659 945427252 258 61 858093345 354 153 999999194841166514 206 687 999999381037267236 220 147 34857976 837 34 664849163 505 174 999999507015886125 728 699 999999302227341956 436 369 151932962 551 730 999999203245481529 32 277 999999895182176434 498 244 604451195 708 214 953089421 903 71 999999348589930898 440 703 617272530 9 507 999999135637052668 759 699 999999499630710996 693 739 434178905 938 314 379745014 624 864 999999421217965858 504 342 649469066 606 827 266709575 917 575 999999173762819623 642 359 999999646834347034 159 283 999999789439811973 389 68 999999464197642707 184 304 999999468434970282 154 909 105388711 185 84 551857587 739 552 999999875518938774 793 893 245679960 219 528 903306269 359 579 35824860 825 27 633178526 843 390 223300133 2 364 999999937770357742 403 379 999999594691214279 415 320 11389015 376 382 999999186129971990 895 505 999999858281574376 105 560 108041545 704 171 250452091 610 496 539376809 352 619 662782747 631 731 999999341972849141 264 420 413156168 331 742 254392682 481 67 395452025 147 419 47114736 697 625 645848482 600 476 571482060 904 868 999999066462416295 29 279 653476536 718 560 765372795 373 563 999999482822722289 611 175 618054462 151 244 999999506417429592 807 500 999999087060328529 180 930 259803855 810 189 999999558782097535 348 740 2916920 514 805 999999884344441532 856 88 399736564 784 258 999999543653636174 927 619 999999434877788873 555 613 765562710 223 396 325911080 136 787 822015359 821 205 999999259011099219 67 121 999999004399382397 814 95 117052060 861 834 999999443102387352 409 60 999999698836427419 398 581 628293166 487 836 999999963238671803 774 559 999999962612712558 160 370 999999673157326802 504 105 388359341 565 624 999999823803640420 596 429 163379369 121 747 999999771172741400 392 829 999999799243081781 316 822 999999095384744360 325 882 999999627497791212 680 234 269901653 238 796 933556039 667 846 999999145487346342 821 142 999999359391122746 372 757 224876012 938 332 806835961 251 702 349520733 685 888 999999497187969937 225 295 999999016232694754 162 554 937398758 580 159 792725605 864 697 999999142870607498 121 84 244468077 255 409 621658831 518 159 827541047 728 685 999999964530947359 125 409 999999799497947789 214 916 999999145856168815 669 423 243885387 793 348 566659846 294 283 999999891852321788 648 871 999999612178114993 741 282 848683839 842 284 999999234891656452 796 404 965937405 202 825 999999427619772278 534 766 999999783310884353 147 613 342732617 723 95 999999435914082938 739 330 999999512445507040 58 325 999999986339627886 862 75 999999442190675022 145 677 193987465 74 216 261883058 120 312 999999372924278062 301 644 999999433462076902 805 342 999999910872630169 329 518 999999730430006325 76 260 418766148 873 116 999999228274439636 811 323 999999210006156099 218 248 510455562 514 176 999999123931732318 601 184 376739745 594 185 596272551 757 295 927606419 253 259 364937528 722 306 419220016 831 12 999999659400321141 850 382 999999106873912333 372 153 999999711519678788 323 152 433821384 226 428 310515280 71 477 608612521 677 53 999999876972401266 314 847 686369473 168 922 999999582810194549 340 514 204037623 835 739 999999797806572634 246 928 999999399278820386 538 932 999999936086758437 388 109 406840467 412 36 999999123603005087 694 723 156746718 10 234 925019772 928 888 871872196 535 6 587875355 663 457 819471850 666 343 999999267302762766 345 757 143351265 171 516 999999093513584801 296 157 958480749 654 762 568899457 63 624 999999899448504080 435 234 999999945287897698 38 288 999999121267000760 527 926 999999629692842816 128 118 999999278242038295 509 916 780960276 632 129 114655480 372 421 999999760536083762 304 640 999999266463103457 617 140 467072377 553 925 660742488 483 124 999999435264712269 905 623 999999700379359592 635 830 306663688 24 870 999999188924448939 713 512 590396314 457 753 152146411 288 715 999999205765023055 632 456 830715638 448 412 23135869 585 922 999999426949864201 614 184 999999719744456497 618 942 999999992313436135 477 825 999999532077689933 206 368 920066181 660 75 319123673 91 921 999999937437262471 752 14 905446318 120 330 787202645 812 43 999999571317048185 455 703 999999621333314365 553 861 817881692 211 139 999999955280046758 939 501 871571917 368 655 460646432 246 124 999999524875247355 510 680 999999917867609301 455 558 938741683 424 74 999999959523496975 265 874 790914640 511 196 999999809940925192 412 521 999999920021914654 930 288 319856894 505 941 999999455797559820 469 724 999999178997891200 286 758 189653860 928 739 916187642 416 253 180159149 423 234 999999914625547649 821 13 999999337932369965 289 621 882670228 574 165 384655306 123 933 670450324 734 135 407417196 624 827 999999951095144875 541 532 204265281 69 897 352166140 681 553 999999002888397377 901 488 999999945017680270 30 579 999999718666832076 703 483 999999471814259029 584 123 85734430 793 105 999999827699460235 693 429 999999470044753676 524 465 999999712823897283 378 344 204782758 132 511 866548445 329 142 999999000831072537 245 818 999999384027459354 625 927 174754557 765 708 830932044 400 451 939967729 719 857 999999117171653757 216 98 50902726 470 715 999999712385467548 875 426 122502267 934 528 999999482948165439 561 753 379074373 116 64 154734841 672 757 948447181 417 28 35796635 404 58 504022263 418 197 260779458 924 110 999999104851417174 697 942 223723209 907 136 582058083 771 822 999999006616269006 429 477 961840995 393 643 597349683 690 587 615094832 507 864 999999755662379348 91 859 999999986305226767 561 398 497984230 161 105 999999284494985004 473 442 999999663154636983 243 398 63261350 1 126 999999761351258265 700 944 244489564 745 557 999999741223713146 570 515 607593344 375 159 999999156738581882 523 234 999999543219084133 647 509 999999922146900263 892 412 999999427735825550 545 72 999999239538516006 738 215 909695452 940 229 999999717584007254 289 369 999999487298834191 148 897 999999720942440470 184 151 470367379 351 701 693156335 322 943 999999859717469993 261 862 999999358839015965 380 62 940104195 734 872 999999076992250271 562 344 590299899 927 607 962648877 387 729 999999515863464686 625 519 310308659 918 180 999999377405777328 773 661 372921394 127 904 999999208360214547 621 404 854899114 16 731 583081582 526 161 999999710341389875 798 640 567269299 810 407 999999351013197903 880 22 767331941 555 627 999999997824427856 92 456 999999032517844766 733 567 873116089 797 74 24946298 221 120 563589203 176 435 298370609 589 940 999999610310988434 18 711 999999263440360586 903 477 999999343606066479 314 87 669107826 528 879 999999839506469992 530 499 999999487783366453 782 615 999999276454283012 153 917 529200949 275 497 999999180966936108 483 689 999999314123870389 766 914 536697311 478 491 683616010 191 302 999999441470173639 169 478 676719151 405 209 105480775 386 344 487895500 215 426 999999430011464748 908 80 999999121484613386 131 200 984820991 70 95 178719414 694 211 37168722 575 605 999999135474160249 807 570 999999567325151578 883 519 999999681071813567 877 623 869319867 371 240 783431701 647 91 999999507762798630 322 131 53133315 495 149 989616233 134 234 89084818 606 381 388842235 508 602 999999767669239126 113 268 999999388291826460 764 477 999999114513653507 887 867 999999663835857357 381 940 143996400 198 710 664104971 603 746 756547712 318 919 999999257976158960 439 192 356174100 424 142 740718301 501 678 470354700 682 717 999999812326213471 734 803 845666418 888 229 999999476886506917 54 666 999999555118271914 66 731 29377695 413 45 999999197272937355 307 640 597086242 829 270 302836387 49 517 956191395 923 229 216444655 264 446 56887764 190 833 999999650319234910 939 120 999999443735417393 350 589 970956907 530 825 999999166321628516 718 456 694279646 214 395 999999868748980271 674 528 927857347 453 330 999999985233544172 767 795 999999085085113964 741 478 999999796085153231 119 654 562481905 821 161 226764779 297 867 432915957 859 43 119663376 103 446 664438206 46 535 999999651824411863 636 739 999999639456377925 753 583 999999963558185681 364 319 999999020191921144 732 252 999999783559298555 866 390 553546737 595 859 229357047 61 588 746443940 722 739 378295220 104 352 589041942 856 65 713187005 496 265 570542736 633 145 568623782 267 47 728979762 60 322 999999605082175136 582 410 973901739 425 295 837424247 559 427 519049446 919 545 999999005508828540 413 200 884794297 869 566 999999817948502758 730 60 120025577 191 769 999999330957979999 465 724 607173377 804 731 201668275 513 179 999999938226093632 358 899 308943065 669 31 999999071965413156 182 208 999999617675014581 404 842 999999490198722317 335 869 908522342 689 460 999999034996193903 312 216 999999095800733188 622 309 999999751366766087 460 691 999999977370759166 569 524 999999307757579175 353 110 999999578254919562 894 369 999999347840376332 447 244 999999763559392353 782 552 999999263796776787 574 535 999999277312670921 199 352 152369689 668 85 59903273 594 86 596563512 93 511 485581202 915 229 999999492928363352 189 583 999999469282345373 443 946 671526484 488 131 527524483 94 872 999999256709422712 701 593 207292357 781 701 588681607 777 330 999999348688866882 540 44 999999922648292966 513 287 999999461467321456 474 683 999999564180855954 409 809 999999416992402287 869 279 999999251539808668 697 564 999999319376465434 525 750 999999746532657359 755 528 999999148953999611 268 608 127256411 509 319 999999165741631552 199 31 999999005107860489 242 942 999999920494641489 159 665 778496791 310 40 999999228500026923 331 460 455674671 448 89 612157828 282 762 999999598083780785 416 725 895961892 945 660 999999986267748952 437 639 999999657829699794 358 477 999999307421605884 572 3 999999748763245336 796 110 905127407 276 83 999999265994692750 315 802 999999357430115850 339 246 441168618 520 507 734846544 737 214 999999399471755981 626 416 999999816913358771 738 542 240486426 138 233 118238654 480 84 265292333 476 136 30782307 344 497 999999824475727754 634 739 983302038 280 500 999999865625771582 12 516 116139585 728 526 999999796052361519 891 242 999999642828776433 388 135 999999599284301947 200 940 999999450581629161 328 881 999999819058549685 738 2 179544854 207 358 240910066 793 423 167660155 445 174 167863488 568 781 999999449725329253 401 635 999999200969547384 315 182 887861825 13 40 999999925224117347 809 846 940774404 28 175 999999487425867996 88 857 126536838 690 643 999999114112983257 513 74 999999460967825028 155 932 138573253 847 581 607579002 711 248 76959802 595 37 999999534162478916 778 646 802105337 412 800 151078348 657 940 231842319 849 250 744585798 336 260 999999744518411348 624 33 818050338 744 718 999999843915312735 450 361 45812925 455 411 793600932 572 348 266161097 306 945 999999558977598622 98 220 999999789969560698 339 768 999999729603042336 311 400 999999359251683717 175 888 104221194 57 296 682767923 146 16 624760065 877 861 605504654 240 323 518902424 341 83 395823032 4 615 962777404 803 941 232588139 836 484 999999097199272348 415 605 325777261 208 401 104815904 685 199 756430656 277 837 630829969 31 217 999999171457711511 577 343 998344859 459 154 579925238 493 64 999999845016377329 609 452 999999983497465261 819 687 514460147 485 631 400384663 616 694 845608748 79 55 59984646 290 603 802277126 837 541 999999349640588898 656 610 145772138 811 121 999999356221609117 21 212 999999971696779252 750 452 763645791 544 927 999999742643063772 625 228 999999288024114264 89 559 536271157 882 553 999999234331233529 397 511 822681660 518 350 980973736 712 885 816209142 731 483 999999216346603356 590 21 999999647933292711 778 918 871595788 125 748 123883014 676 2 999999826110003067 349 44 181900473 905 908 797789096 670 295 169039362 168 543 999999932562176250 780 276 73675909 540 325 752138365 827 691 275648250 706 729 196313873 377 130 999999149649784293 721 641 76258380 750 339 104658550 552 295 507518478 519 487 999999018192628411 343 779 999999965586454567 130 391 338465974 238 317 671018859 637 733 761938547 627 867 999999425921849923 601 437 999999431271215422 261 516 999999057292970828 391 872 782314379 817 901 999999308619611032 298 909 999999985700003227 940 653 999999267653539037 177 61 999999983696784126 243 500 999999739980203793 549 588 999999451359094504 205 799 561020774 470 808 999999461817306531 52 783 999999422665537130 582 372 962400718 122 229 267320392 138 754 999999374751055651 659 636 999999012218566752 826 602 970556739 629 544 589350659 305 126 999999282330168409 662 836 375581056 392 283 999999315625724736 174 786 999999861412789601 553 295 570479174 718 535 628305831 226 300 50402250 1 910 999999740189946927 630 862 82197246 691 503 999999350992159518 488 945 999999653612749948 626 20 235857990 939 101 999999142812321262 299 364 999999656450097121 160 251 217057574 917 342 999999802063135421 640 204 999999860879339902 156 357 311526499 42 910 999999535587332669 85 418 9531812 557 184 959346633 878 460 999999759723655007 248 623 995451825 816 524 714815867 428 677 24592072 197 124 999999612102303725 186 889 36779357 364 238 577363018 880 73 999999477206456540 169 850 999999774534130926 240 578 999999885867699758 554 622 187281243 290 623 999999265773333469 99 777 999999671957064874 411 872 123174769 606 825 799708614 194 913 999999774300334274 332 119 476404062 468 603 822898232 385 30 787983265 512 194 263559875 185 261 718928813 591 1 797337222 101 619 999999746042956237 385 573 999999561473070259 749 553 999999704651226321 892 449 99620573 288 358 999999332154926431 537 526 999999426563307223 622 181 950305886 762 874 999999737562542002 909 433 999999609984645563 395 454 436430132 107 64 31506981 483 348 936208647 775 826 999999909818952255 463 276 214798720 127 171 999999342887940189 382 246 999999093588157866 759 638 211923514 563 383 999999095655200691 627 59 537089364 370 871 541675524 471 558 999999811961300193 944 861 319748935 858 515 999999596188706520 876 502 999999015042096423 603 812 999999037465259373 355 623 150582110 834 888 13131482 63 219 539280904 80 248 999999427893366521 884 350 587952593 497 279 999999565572295591 828 931 999999823825334679 71 221 1670703 312 80 971143511 462 609 999999397564879566 860 432 781237929 733 852 999999126332422511 590 783 999999163092125056 418 760 999999585367353328 327 633 663074248 754 929 420510913 653 125 999999671154268776 508 507 540123145 468 183 127041379 673 429 999999135493088361 24 248 999999943584264341 420 589 999999759577228088 855 538 999999948595705299 253 874 534406719 868 66 552648348 926 385 999999829910428868 238 931 765056020 762 325 999999976716331724 173 412 207078723 654 32 177430959 836 251 999999433736876572 380 7 139310295 162 758 999999958643227467 789 478 312874881 449 522 999999636265893713 226 68 999999649640937219 338 811 134303662 574 231 999999756005847059 76 689 999999729855329370 894 684 999999720677758098 533 35 999999101462173812 889 700 607019859 300 407 276753872 691 644 999999589813525681 778 909 999999142769277253 385 866 686719382 601 892 999999884179707763 531 922 846231224 896 327 119047804 49 9 862324301 926 528 999999028586455583 801 646 999999500817921116 149 740 999999245082403822 880 634 520528009 581 83 999999575889605167 598 35 262010497 813 192 649259937 747 220 878278483 843 61 702153124 655 44 999999979413065104 26 513 999999299806063947 772 403 517558397 273 641 999999085239701969 540 496 458366311 414 933 780574995 943 181 999999075185096363 485 591 999999319207949466 277 220 999999491224918687 345 218 999999758290973607 830 508 488579827 459 666 999999315665082550 769 83 870745789 528 330 999999688807325605 154 64 165313747 599 340 999999469595357196 943 44 999999689973185952 597 680 633482602 390 463 999999233074951900 424 453 339113278 724 833 249699114 893 453 999999853811557974 717 625 894751833 195 667 999999303794953540 612 482 122133376 131 244 999999799208324085 447 824 993231858 786 833 999999209133788029 908 214 999999670967338775 571 30 749749948 53 27 999999892318260630 664 643 999999226557486425 604 572 944377814 729 91 461740806 95 402 999999419943881622 488 461 442321702 706 645 963021190 72 149 999999643110280051 716 570 654155762 782 619 397357200 731 297 999999613766893789 726 232 999999027049226528 137 450 300406946 812 84 999999812926451603 639 836 961001959 660 729 88859403 751 747 999999874260685375 70 848 288120144 798 270 812282154 77 549 828135836 209 704 999999244542466530 562 445 239207551 783 666 656859456 500 229 260362384 716 634 638495636 292 253 999999681450054109 291 689 304550070 197 438 999999907293980039 651 507 999999356346223620 608 490 677494563 792 251 892848733 773 147 999999214341409170 368 125 999999598594752179 586 101 555086434 670 717 999999493817818421 371 866 999999302943313840 369 568 878551973 329 79 999999251681571362 813 402 999999821937579675 471 43 304450980 863 688 999999926315811571 68 755 944406198 707 880 757303879 911 643 999999647988566253 91 577 769919945 716 791 949231887 539 647 999999117237448725 584 153 999999947805309310 153 583 75514396 678 407 383872569 742 843 431500499 114 283 999999165291665886 263 18 999999428121903013 645 934 999999373169484445 55 9 999999637392663524 88 583 999999015973828688 767 852 999999973975764620 320 654 999999462218858570 203 282 261022084 172 516 999999148653795095 377 396 485711034 286 632 999999932453023901 523 64 999999409490937165 543 718 999999845472121103 731 623 216138178 792 756 759911968 157 253 218980689 915 321 999999500880206792 814 151 38813135 256 872 999999844459695549 41 695 999999920805146957 78 634 999999614543522745 859 607 468007410 36 853 991836581 564 476 159083201 636 357 999999679911116407 75 701 206939729 309 463 436951987 125 14 999999760878687505 925 660 854378310 511 871 900815541 333 803 70987678 299 431 999999586464736246 880 2 999999319369015842 721 192 935979623 879 851 999999093585417094 773 46 999999485536430022 648 652 999999255450785232 250 476 535673146 179 253 999999413538954795 28 159 999999076375497831 539 32 999999619457616002 51 426 999999911388452749 425 233 999999342506720681 711 823 999999359254190177