10211
286870643 47647036 502455247 937025461 756831275 325942269 382284195 884221600 899724960 419523925 145866364 347020374 731769922 677231803 648687671 592544188 833926257 351010253 29615342 259551164 582480955 282700861 640335313 992438595 412856551 989306649 178658730 706996382 164231595 51121926 550120085 808168343 638669107 424219930 888249694 411730695 428050495 334811706 512613817 679790544 337663493 441880443 523820072 204705119 769635907 274999759 982442310 209021429 617996355 654381763 67566949 994526299 62754921 548498998 629277926 644938279 507722948 147203013 517930765 548799668 903917677 932891762 507936294 484731622 398993899 826656541 498644333 956572934 866368874 157983913 475207490 264030119 946390435 622282246 919405680 188885474 491517023 696946364 439118905 147573489 126834362 841557615 607735230 328839601 317790004 619122357 506794094 56079738 787035361 833171293 274579061 490799689 193064769 171940471 845869732 747547080 925491167 798685191 936813169 234082947 44022490 895162770 754347504 278606910 444645232 434476240 240370711 778183793 317800164 834677293 81449826 794833324 205045716 862069176 518640949 400865989 84258109 662872271 963126862 541180687 768008077 57722940 946443682 720910990 733739259 751332899 330204439 635140931 920557705 124255783 88428334 506364211 525198783 235831967 275449806 412180230 959117628 285093060 715602381 981253374 772293923 282550701 973298956 894029639 926795295 790707031 316602200 161685169 29032576 794864152 598232608 148343566 348297548 469299859 454634390 87574401 909303160 686717289 229636913 809353913 652673062 971045933 957775476 674745228 225654992 925111679 14824669 48937786 946309463 472809202 887538624 242865453 486215591 928093210 840832506 944407527 706124605 906615877 264114007 221683804 794824271 336293218 633007281 680122225 819568718 507601539 786324218 116619065 79045310 142264645 856122549 221652695 817301849 80330888 66087024 481345355 500183293 520562882 559773549 704410995 380743920 456228952 167700185 972302208 819857614 464372113 885390726 51943837 291930970 182666543 721937727 425252361 290669606 833503038 183633665 378512232 396675542 394575280 954669131 262763736 540819114 546368195 539301032 867274295 66705746 527477667 148834208 13774359 879407162 862698764 188079887 793763504 533321046 278545326 939093464 896775210 521252036 132775538 900396479 573379840 799549476 958688632 754900242 79044542 561449047 500871996 839062382 310559046 194412852 366026994 38154394 922727235 705920871 90594735 448345879 982258925 594525639 760353970 93639644 427658635 199412 15861360 464920445 537788231 943294942 619189947 844280296 764581284 499749543 986089710 835835168 690164839 858096325 564587764 133582674 701888563 32702772 811620889 118979892 302191688 637395601 35862380 711801713 59077544 75240140 208874018 160979143 317651635 375281065 898950052 42980033 511457065 803350834 301162549 401091343 514512260 247436130 112281929 49906027 965983251 978167477 124762676 6987776 877274401 605236323 597477008 156351627 691520157 343786302 115913822 554534114 517212693 366933370 581573797 396958981 176979380 409483345 104406668 817102707 617989836 868705207 307837251 686730773 454659592 477952419 707542418 759155248 486910212 501957856 683907398 488193784 462358889 403837506 277319374 368598234 841547031 50758284 327658918 43369368 940297041 670066659 5672711 464091807 248528663 761804586 606591557 474718050 353905546 775201480 169188835 692467723 646661574 540247430 638088608 167255539 7643974 612940077 486688253 493122098 106873313 730675355 128721202 936948637 286877237 112856150 442939199 253876307 888916905 76448826 814986483 219045744 939502333 929780524 969944226 766050308 893241440 808768144 974918535 500447344 620892028 940103656 358104370 882124185 373628920 579372479 86574570 242436986 908331557 178291324 642376580 542945361 820754852 256269801 949567894 487044976 658171452 333408486 236568502 486991336 775157412 140307418 950903677 825801225 980790444 807059957 321240709 561664715 2031480 470521877 720056974 255535987 449341861 455899276 973294121 883428012 734227114 415408282 603336999 112482672 783891194 238999578 921944945 509053740 600844235 810425588 431741980 323260232 895735266 651502389 660108913 896533608 119237815 73728928 873525275 43784867 905858479 280811265 3271296 509837629 678278646 455080254 612180798 367337104 454752511 763750599 747483967 113585647 959039484 283932549 261779847 753487282 886778096 226131835 342448411 87588862 741372219 132556562 362856047 343223254 423152448 894539386 761595814 335732045 332350459 758213668 932296907 157305890 818639892 588075988 241414233 299502945 507692721 169012697 80575035 145131476 436188278 41812350 255103166 234508321 600610478 926692911 37330639 67162415 530487362 508199833 499920733 251904994 750303863 748161550 710548214 786335443 448190703 297426873 977222553 329660830 344881833 189560657 24339626 699337210 567965172 969593401 805734180 176328179 680662443 588406785 809216290 604578369 600968068 200240894 516572780 214167301 531087244 277746364 90038018 199983039 102364578 994451069 777741466 968809819 426346847 562895863 877303021 184952469 947835600 22659062 933573628 279529404 894698352 362403414 268345826 462965194 801298298 236608701 445222480 484072458 470323228 612834342 727734782 857250885 986698218 751555932 298529043 697572085 669310631 864208969 138274125 444525491 609802751 143358796 987678893 753315105 419865835 37028034 760267729 628912336 670856757 869336688 564107375 377351383 977345657 453704494 461579830 28453623 893825726 830049913 252399969 408424057 4957089 461506366 178282289 24643396 229319337 487860296 566199201 694874692 237061182 77675147 7439699 14803272 711248432 612036975 739479199 94564931 617919118 277621455 397943086 195756708 413154331 996842365 768334455 953289269 65811787 818186252 771517753 188962011 186716746 612877596 281629564 47725084 478598073 769537865 335658296 189233329 275903273 641514207 935989050 662035309 522513021 104334069 801878364 154527643 622560381 186898181 487320073 554397003 585420122 765659647 94798851 316844484 476514553 693073451 786001788 615864871 228493142 945832289 608019826 454787476 165055833 288971899 66083241 258394521 914094530 154182728 936155939 673333241 240293078 617336883 942883296 806366156 657440228 887909046 960549737 770291874 534355875 649300611 590919978 322333198 314567118 780009653 509709950 525814080 718414696 808256424 188504375 626809027 565641281 609682380 729690413 92291317 152292343 679204795 977450219 550890058 267954071 223957018 881760477 911417361 594939589 633223570 815956960 319109721 196146828 811382130 225349304 944790935 638573800 56606681 154617584 143609373 416709791 120344161 670580183 96390627 47141489 559994202 142625841 949447556 921918205 523711896 848136449 885842130 746325695 6581896 116606462 962184547 732533582 255317225 268617263 37453579 210613709 774367861 22547502 506219773 593502730 991263689 840287819 196754804 214039202 446156396 714778503 740420662 498979573 820965868 818166356 730731949 762360240 478279868 586022578 158052165 999919288 494829885 108481576 342647348 951525485 587486423 69875670 472688227 352083517 302917495 618430841 301492224 682439812 80758601 628594496 679848374 304382510 249629558 17469709 704307178 16967874 407090083 254540743 7413577 950293947 307068689 476135381 381759655 432793654 593555991 748665533 679608203 616990787 297893702 541260415 855875716 693551906 291583867 656192498 408995041 67236670 752303690 648328505 71718198 572299270 205752579 18026180 800326237 109337192 2979937 573842899 43938382 76218344 240511111 453199445 967432505 608299345 232997892 355004719 978319589 632440596 818847181 784965275 380693258 592759684 643183201 957201268 549778673 209077109 868672896 467131486 501094693 335707203 563464267 792571962 656450439 549888377 194188356 856997922 192886880 260608540 943963983 728958967 680874803 447737945 871948270 705155488 823957091 361303126 823035207 255842930 54131128 855972542 912729473 461570341 270117180 724496519 613393355 510466940 37402138 901696849 436998178 987321240 718006473 489942232 376644468 682559907 6120449 999966528 293323119 702383797 267930652 98113390 483358813 262683355 95295130 613713589 431373118 144210290 152151307 82227194 174706186 255664791 739958351 194384439 317200650 318407410 25684375 513874750 954032327 168956250 404079695 275462493 782144702 963941841 984351673 389952413 645453799 672742843 835796945 633144284 989099353 592764097 297413610 222511367 648026170 234671875 623100475 739359297 736498271 395052125 578049883 963529259 576743241 942913602 996458119 236878549 696620016 246487835 512761497 925649971 40232365 79480155 522495820 680349275 734455637 287605123 675347771 315916298 714723645 127243868 289898341 855515 862754032 915521320 550283273 429881754 675255583 514880282 503846946 643354438 804272125 389725170 471497246 971665255 162793682 247772696 901346710 373264352 748525294 833471724 928479328 372120508 531089356 139648759 870274097 849235515 422254297 850201169 788667034 205839187 211767577 908959031 174709211 585636655 466314819 960110050 736634168 755277303 283971979 213179800 274184316 787168968 435311068 73443475 713378663 587421300 887839953 286229454 964706544 972162567 566906385 936368151 596620651 319894051 110932206 464181369 250902720 818585297 358949445 582374083 278660222 497802220 479322568 260315852 619341200 523021424 888445126 43757356 327667483 633394195 927987637 900935212 861912526 609894737 909466531 700099630 614100695 675547839 915348539 803143472 213913134 448554076 913894532 548059630 171938441 509650814 779269327 897128776 975264190 101486207 289943412 228853496 832113978 238558906 579565966 707545416 174504242 747705068 782304468 37227685 290159173 840991938 186962642 823936752 81005848 761731175 248236484 616813962 856036774 589033081 837399071 675219356 43443006 437329211 186934856 711093552 61792779 917542186 366516499 284349942 964669649 161000550 55099043 486612685 533804707 856358445 155317658 632509398 81146019 922813245 180236897 107511244 305285682 421809175 835584530 317811557 573756815 46946715 600949421 227209874 785258609 370067329 481236298 414191205 700528422 95687660 358693769 960177036 284694913 799739459 575099996 211727380 918875967 242563446 587108835 472171742 6649032 463375617 512792292 255255812 867333297 516188898 535143976 59516581 203018446 666701206 367822396 827122200 425101653 95386473 175845674 402712094 948119502 154390015 406170945 324021261 47372162 51146239 570528972 848725033 417135893 133323667 513379984 535796667 276516950 787217737 653757429 767028081 491977824 319602614 86700213 883373757 391349860 39044229 185224090 166352101 881779176 314424400 80070736 168865550 3630282 779790370 50291020 819524537 830768792 187730135 894204009 105669907 904199138 141509210 625968567 967777151 56480988 835597177 782877571 421132268 534581435 964390058 829688920 28014306 459416801 467512268 65907185 134083053 465631276 173054406 745746126 234698456 369583401 886857316 42735018 219789546 848056965 242384411 783165456 143483881 759225079 193338818 654301781 926249607 838976167 146644002 662464724 181781614 854488302 113149053 690177497 456708484 57383490 292951489 938144167 692089077 332528537 430349282 969881877 49843757 734409441 506216496 347344098 480762419 305673760 295647375 53861618 193404681 79066190 814540267 419361746 436914787 790803255 383775022 721195685 79679873 915874267 564814418 574995433 94843544 114399994 814911896 752655087 550230568 727370686 7637084 723557648 811784912 94489912 621251945 279010312 357711839 873617723 844467080 46889517 453046148 121867983 780427608 813414647 945191936 102162588 181286762 811861649 914319362 282857552 275317995 408049076 903477051 803229394 939045668 527499270 797708273 336111822 269124703 237929366 270037190 980087390 749080712 855724366 396509149 188045393 331855917 752438960 981049912 947575122 459192106 351415672 820707932 385368812 879856396 725444867 834894110 899312373 140198981 653287877 998831693 664004142 294342281 463409913 130477783 203763771 546316026 749276534 200715956 867794604 894994113 646767926 430951648 975943426 654365980 228694165 685562168 757694577 30972555 644120603 312395534 632165078 371339505 729672331 448244044 561160501 407100252 878533168 45236380 293771258 129399659 581748269 871436306 680843464 702625151 987514668 861513775 156379999 483936397 502613350 388915007 931006519 67162262 625790989 187340966 703699990 37271862 297171973 526252805 627929129 357847434 771362492 121724736 96711355 174447848 680763847 640490418 202906144 678123244 893631826 333774240 795297612 853154639 691878947 964541534 352803572 240084497 823640401 312784899 355487413 985491016 980768318 452675256 290961697 340124703 906114044 844960201 517082950 23085849 886611461 282975094 434525359 235863187 390232574 276651779 208961316 268403701 669281894 687034644 585830277 755083639 89483454 674086340 16441368 837379255 898389735 455764580 541786333 45431527 534524985 899428928 743108746 705281704 238330565 805986912 704768967 289876175 907572004 349661182 882733584 25706742 732306537 800603536 147043394 451981039 227293174 549107175 306066830 258440666 368706417 881224545 552293649 407161033 956759742 865019308 103488620 239757688 124635024 130524505 805876841 419564682 420468225 692582084 96120363 361819008 20683785 929480601 596806756 268146786 428970051 620648787 617651430 299491234 170183727 129045932 360890226 37002781 695646878 731187089 689880110 36984144 265208205 857657592 983453765 538025322 950229439 545131548 157405263 819969508 832064165 558037916 710385212 699195235 919781694 719632397 497702912 270658230 237723366 702690527 525608960 363800659 942924734 642636876 803049999 329215155 924285457 49068243 552808169 988067010 576721096 364450855 730167958 869035977 915014034 154548555 934700643 635916061 451697758 755362543 37580955 113298924 738610598 768936467 562254721 140445643 834264019 204596629 569949529 237185503 217350038 216048705 52170039 290817339 627206026 153736597 791123611 491911863 475090134 792192690 557461809 464838777 521943594 205719485 249012628 534135516 483014792 883452251 458169620 490520843 336181269 304328925 957987202 143611665 689685053 846434283 503968387 746351231 586596019 642380536 185301967 651431836 985805220 762056898 294875599 912120027 222008010 37685924 63921293 41874387 40377215 561867876 615100720 32514638 490366614 131136039 301102201 595816587 761048320 895078397 461405351 827578549 856112052 980593092 452594943 748876820 320679705 336934750 105805563 155113262 8245574 887243197 113878954 237804478 73833203 71310463 963712457 449577695 457843738 992639265 677684034 505031528 478500069 856814097 161760813 116165134 97978226 302793691 355891779 138157872 121227675 665246410 396129375 703737020 779703220 585725932 335474137 731262549 384150719 803480308 445332747 735062919 804236925 420890644 527086573 187167013 359446091 847932531 845773440 400154791 170065579 753317058 965123170 834029938 513411478 831422982 923050982 469281352 972811466 593304908 911988887 703909699 838077333 899173837 333587749 684515385 399137273 455958525 251039605 704069894 417428718 283386334 377187876 933335060 313098963 583091742 212059121 49173847 90769608 262847512 475525972 657868644 962514227 649351997 62724222 665141589 877018821 927582715 741168918 951041279 375949306 946262874 181204546 813457635 811637023 642972666 975790904 54637826 945251799 6444204 648566398 25144862 793029565 688875189 428498821 172767489 460435195 992587558 162862614 744597442 461345742 19485133 26179136 941590084 939478619 103307223 69214629 601956603 949832889 967615387 263277073 483205437 150771528 312010023 108800944 415503356 391939383 122788741 934004104 369698446 264397638 953288227 843634988 344190210 515327162 145408814 833365123 219221840 611148070 920310366 209655800 586725124 656252224 792072129 417071092 341482054 37111620 438317486 724780168 435024674 801285978 265593404 394815938 242103391 579713849 961975529 933106734 211743297 926899369 473737664 693411798 786247887 767174211 295831837 798813262 268715225 298469224 258577552 115113652 198235694 388812120 41623193 817267825 994064301 265731535 83510527 546578937 68369354 875594379 182725558 777358433 739613881 111383797 849339166 25146054 495776527 729164417 406699883 223960228 15725058 98442819 754710206 781164690 525413488 875514823 709213458 208826966 630344430 916170201 585726396 65346961 966998192 196568120 603067822 981369954 203259356 211557526 37371881 699128156 152993002 44428068 964864937 822625736 749577973 78181486 728336972 780483315 864938745 458587111 179450950 175313996 252740493 612998997 773307652 809779325 682928683 284133231 733575335 36629667 800818251 662187467 843179075 77355576 559263113 728016317 339606141 622094146 847600043 880112915 19003794 680748308 748500098 737914625 412285577 527687456 498474258 693615966 286264225 523547877 648919905 760763310 791063015 993627164 92237432 519433623 161215105 672238578 821363900 297165571 88792646 414049294 971814337 727619245 806576843 751915394 161223264 17025699 909282020 138661968 804135206 2180391 777473255 733502057 644722705 404389973 443089394 784679349 509358572 475767514 322910243 290571785 910960505 595700751 371401290 301364975 626143649 696850158 277420484 147820828 61159044 735436470 688465722 86033640 392664575 435839275 237099462 373754681 340191506 502650509 413909865 996836532 712064859 159271071 128710247 2822626 239337536 239101635 349228314 873890006 341765426 929667607 433194835 91021491 118221104 185202949 619094651 405638241 355459019 513162484 688546936 880968399 309364503 553200909 129411994 255863516 981958159 623997892 670457448 867300578 752561271 958735073 810462831 426154534 626020543 585131939 375152342 700334606 826151746 238852646 912625339 654628200 654302347 725988789 588214858 848808627 231280159 629642849 668993244 696596586 603430469 940096814 772901386 309137437 304098111 676887728 908801060 370489464 413346018 481855480 426982781 471210797 252734726 793681296 856242570 76803966 14400177 54634719 445077645 156922832 570917338 363097406 410640519 461334645 534946400 337066947 311119964 409386686 809190681 460685070 520940828 487806947 670813961 616723473 731076806 899819179 414573625 690815678 79551594 444784528 215492964 951930660 515239513 413568612 878306641 270817635 893066811 887387683 278451597 450432341 897529240 188244456 689173572 330432767 137151125 381590880 960642901 736551574 599701957 569006509 67749674 875950718 165385212 557701527 497892804 757536227 954698202 19176689 124031269 353464632 914346289 178662723 346231197 392667726 766550262 106471788 511209503 286754619 264863 897945024 326577790 582422028 236862574 995433648 564664500 659941026 223945299 580943556 647659168 16780922 32844759 3077724 154183161 904496300 196674497 796122923 455346573 898194684 524922380 827071739 405285010 278536914 205945175 212809188 449559531 753494906 545676602 701926288 628046398 7377136 824537543 17033036 213624874 12554592 341699516 411312388 521770676 513804942 797860733 405698888 368580119 655544780 720618776 225998455 53503028 447645171 763453081 824055741 296581974 480228172 61578286 321367560 972977100 3897044 917687937 724386688 314219018 758049017 539119846 511976721 39971379 926751463 769767130 290485876 595434475 206079286 774369428 699058092 317177655 923174633 935471985 260867065 429411060 957793596 710804458 285117357 596181338 882488445 462960990 55343458 36646474 970932262 815352927 615516139 235998882 341302886 36927351 235885886 559404705 526565187 861902657 232818298 172389033 599568565 569176061 843710452 266094617 623815384 574707864 752742040 497587549 667145473 203241155 602513308 769889656 926751623 754011189 724766483 189292742 517436586 116215452 564811818 111481749 442966320 406488314 60693056 618267962 620559838 165415298 658163311 982897861 828527298 906437715 475822247 137068184 571891967 765449442 187711869 838936778 679563666 720958661 868492014 978980656 10275910 763666206 188501646 205737735 502483218 747466897 262027782 483097570 232534785 36012761 154640423 892895834 214758846 649956681 920389158 303774844 398058966 400241198 62025573 545948180 298743845 988437070 92330115 209906164 223592863 844871738 598507921 638418800 763403810 886758167 234891703 980297397 144446534 113947922 352300659 58791540 994983982 873387889 497296055 221937100 78069257 303999726 374850295 410246142 458513187 897153041 192471784 322509114 563010986 435868937 537195026 643573929 96312236 379401549 466048452 557268377 828160306 385667540 372799256 910940219 5724089 538547427 404972893 837550928 888660268 3382996 55662545 689566087 991416888 111742656 833754322 708125399 108264402 462705151 617180478 440930432 379289027 447253417 297740648 931564600 649883183 869104928 254206534 494403252 198526728 708821245 380750596 13374597 77346942 399512414 806656107 196216370 977594895 193994710 316433151 237582687 536763693 411113304 705787940 205669071 425261934 563145612 225654397 86183672 786055733 124844618 550295737 688710753 398978493 598143265 340011056 590170573 474451661 34124320 811722209 941244176 539333918 946309652 677064436 488849159 270041535 83772453 884075959 574908179 524224202 460194541 643875151 598384338 561901986 122879345 678638292 695194791 247798130 933664323 968278358 456331415 116860645 544695953 955510338 395164789 298573176 347636675 831032665 303982449 676462698 375961673 703838868 836722756 266426216 388180847 502734610 835248792 44288851 807931526 873109851 108970458 649403418 886227969 224435046 925371033 376647110 437075900 43373059 340097155 797326752 139167906 616750635 522662251 90165811 748815975 747275594 291565141 185908187 892187839 914209824 669538765 199089492 806497558 926007174 165422217 22300457 783089917 701947971 585846157 643994270 760070342 895118781 840438344 722213804 208735758 824741946 219208356 830078584 349184000 523684080 401191822 664486697 730017967 351969871 614810623 596162730 407037986 214765913 648352660 337855578 922247990 84865599 402624198 744451971 976815302 478701977 443936880 100217454 28297570 185800229 972070269 928167010 135984964 59576157 522539724 210011307 398312029 677441256 64623296 594660724 304402092 733883692 391193937 719483354 827198741 830446817 174453998 158099268 483245751 917478994 683656651 288272828 369820230 49569050 838915888 510323200 365725294 10155919 355113792 425638576 700269674 643642125 691795023 310074316 158465243 60829203 129229443 446659412 172088160 422917011 748370203 985795706 50296261 112282525 695778784 162831023 680753273 891327402 634376433 655533424 954909976 157497874 156127285 214006922 358042332 82457761 637560894 913563073 178870787 693732313 626243120 76126792 230884633 107379434 783176504 231983501 336290677 382778768 527088583 351549771 288969789 166775603 73583281 362665003 47888585 448041757 87710747 524173626 734975886 875960788 531719826 963957242 942901901 953374797 598241373 427801943 842981095 271808452 539975342 838475641 547695587 718294570 267650137 825212840 778672571 953131703 945610045 772534371 962548467 784294171 454588800 32833251 57565981 928536124 30411087 426822054 813559599 597415701 776164912 404547207 550789839 45061453 907556295 517280107 845749930 715084509 388625961 41526485 765906391 636825619 709028815 953928951 442514050 538830035 994696267 772739655 358898782 60121570 270964417 844709507 967767106 361289898 977307992 492024786 793099870 993657982 458908012 462263238 776564949 6400902 377496946 37630241 456219651 229607425 236067107 541590398 54733070 56686069 791982321 2440324 782678650 327636630 115044126 146687868 931595092 182747097 576362886 925543003 162134366 300682576 495564697 974189799 349260243 774439198 619558795 895001081 919475559 901810571 608773810 204856424 754683096 127356704 590862177 68369015 851329180 547624389 261685470 885101069 346290392 65865467 782114606 636668969 752487579 263492335 427650251 548221349 688369915 716731075 755814071 192188979 319946620 390217000 896879833 810487547 52216854 494871508 142076539 913567142 665722652 950813475 954157664 667691800 88503726 807909110 911284220 782897754 517602720 272219128 269366685 459285468 421900035 858444599 77650687 372307508 268723363 737721266 111469546 479234602 181541821 147630636 469466495 451552139 20778417 833844590 665709961 688618361 518346377 576148297 120527634 802169039 403365732 350811097 790663763 195485902 333307506 168443600 194379081 808428767 254664838 215678724 474851057 672270130 853608786 990527012 190612329 752625310 406319794 535421437 166058081 292404048 882671919 50987328 919464764 847626600 340381463 319719471 184982808 342925517 79071386 323990101 506513883 48391921 462621739 603777105 86518249 482862651 937165149 299940494 355911176 790504035 309414330 823948663 479006369 833607701 462237449 206840247 383852358 597191864 911082669 478749819 627003550 984676143 460943666 743164041 207923046 770511040 744487426 564544961 946203238 257202721 434746955 579451705 801121770 173352600 77899562 127870774 338179208 426066126 472396486 482107407 590743291 539765234 40700634 187481092 400389541 729821276 687391622 184663339 789050616 249932461 657171941 152292671 646956823 266447010 165963009 407984654 846970819 311990285 251022944 333639517 675885487 571448669 494281630 941769306 421641830 690677476 185801895 148140784 711364588 238144194 741930485 121200083 500653547 547983268 878276064 918577715 882257647 845556590 698204773 425223858 598550536 703439571 716225683 831367015 909136728 274995198 183744988 978549951 544907087 210157420 988665739 470523869 265515327 930099930 178183824 14721220 175191541 386386313 849664432 146118707 205593679 319308402 457644203 866569350 498260848 84021453 742860187 370063786 672009453 353394918 610984845 444053713 31894080 801356175 50144795 769368973 869583662 984300951 300516961 19265229 785671911 733707896 998897886 364318435 779132612 407432626 229774631 307002770 219572425 535571417 854866471 197402675 823171623 523578609 319217801 594605882 307641216 23027868 512511652 231627917 2350548 878815925 393034749 814750365 997388469 619936806 755431406 481158843 281107761 333650686 346298337 926348763 693284277 754720816 859304785 343271936 524993393 949481468 349564394 201815223 721416845 925031737 672497857 849511832 885191887 896300801 867687936 806741825 77940679 505279711 216699474 6197324 681031065 790084164 803527209 723725691 809797748 53442888 570998101 445129586 791077694 729732321 706791215 57799599 163982168 440474413 619373678 146361964 36099047 125130158 150423385 534768383 738761444 432990369 755499138 663064402 269946553 474841332 674746168 658616331 27046308 243963675 732899286 445055572 477117118 418498116 343449185 976701157 119371815 633725768 653227753 538052907 782706625 999573729 172370796 118881509 440799462 731186439 82701391 59573930 589189866 79229775 116292360 158058860 146204650 66144445 45687574 452670470 775504310 744650071 505223837 722921834 140478956 82886382 391153438 38182020 617042376 671652145 233291184 83274957 320606501 847708171 249236147 544217542 401101962 307809786 781757785 665341742 273210988 930244134 798226245 55268300 949520028 394132567 437148796 882314141 923342393 115353016 463279091 750277976 57595546 689701159 861022498 654628089 165013405 774436486 57459006 707522403 427677586 732725135 432417455 766210224 435148660 750044662 780863296 636399263 957884062 906929596 44259747 566727042 758720150 915385486 959875386 545447537 10055626 711028573 447660222 971796660 623284668 312439794 672518691 829833433 757790943 916322819 853286231 957580027 999091194 500029054 176349888 177123828 173924942 152782067 408929553 607980167 502360721 13140803 153994576 248940657 656710793 888186973 156694468 980235724 940525969 912549940 918305501 19685046 614533314 555116540 507822807 671076146 380539744 695568482 796743916 681375691 833256457 758619933 603728961 479641850 428287931 326046975 351943349 745140603 951082557 384609270 726149041 384841852 909105659 166562658 786667072 521455086 150260411 181142609 917151398 786077104 465038392 112921915 380172173 899526045 625370845 961143699 257542363 336743788 194555256 457114026 515797030 450868387 80581541 117125787 964442598 318118261 962606015 415353837 270317681 732252895 452561472 155567497 605106879 437061167 503539784 545922029 522741074 177012774 786716511 299919837 955427625 787316671 118977447 608003579 473442300 106990721 686609419 136903041 483308746 853189604 30330020 150580746 661335615 713915729 830378784 199831578 325086613 857806050 493658275 602536616 760501523 322646749 940985375 660787550 82313605 712222454 151342395 854306663 516951719 108447894 373673482 388419132 315007575 647125397 980372117 845436299 835316890 693433602 591446249 250898311 386289470 579792707 936050166 574836470 876222756 311696164 705511530 416271557 327589873 630742966 293634329 601215406 204749016 459312632 486089329 802278112 581586370 666174910 968809845 116271811 471052774 146101266 816942929 3839924 80051775 881702325 495238814 937324373 852757920 108424679 211081863 500800387 297543098 532299279 138143056 639939441 288572884 482075040 122311726 620893991 540046560 483321641 321631967 321584853 120489514 123047440 317928331 418935832 970233605 103199390 915899650 580361656 408424892 690251369 902203085 83611445 878641315 792869140 844360731 267969075 331459650 579765413 401380427 929068851 457312207 720979555 925417180 76609603 576552643 658272231 643396871 886941869 978036215 85637765 490085785 155555973 220653627 504524809 92732624 890046235 841021082 901288798 762313851 912183175 882262815 612150695 275348019 576550366 49345926 350097792 15763161 650279794 49538298 294776739 401898762 873517210 776360698 982056688 766034994 813706432 563691489 743029498 483542582 404952888 142009564 38939282 566139477 174544724 935055047 596008362 734465327 655154775 931846494 226468993 53794072 636506900 704511274 6661202 458988046 792352059 425471543 602596258 881180288 528097390 421848631 867908194 295215206 515923749 62146649 689566271 578896144 143437977 763625332 110420952 595037260 947257094 290216790 601206620 22451155 156460994 65757482 105720769 368895990 578033852 560069677 654180404 41390423 357845778 494691843 350991920 768056067 839366458 317104479 155925474 632471993 390306585 371463008 296484404 535472544 853557144 987533793 116151894 823556897 863987719 536933561 897764366 588274804 310287514 282711561 790398729 985141157 207978372 999525000 851492303 519790250 148764491 563147579 576529141 209734552 755676044 100358925 262440708 792258366 748096221 152755861 841786352 978295081 346861857 86715593 676705996 753029413 357779124 215830429 237200708 807524657 209872627 378181433 44697672 107873408 982220632 47209510 335574828 416379113 284103549 344541844 873194592 508933779 746117854 718548705 140047868 160184624 219736235 307148657 200490936 232945720 660129221 604008938 420629807 902540802 169197290 749175122 952021923 149258003 950676401 825690266 958345319 330200684 478236180 100713684 820392851 715550664 695730413 50292899 858424112 16207828 971668137 719284743 379057717 6953955 591245130 813901990 311855699 471331715 619254965 337518559 639273397 118101898 726095204 10479874 763094698 792031880 304274468 74457055 541988818 527188561 248943176 371408463 619525749 805199130 231351630 800321461 4783960 681865655 860326213 537275995 262409484 819850502 908215729 426057191 324054358 962710510 249141368 799448951 305316558 627817130 344112205 643763016 553430929 317194057 879426543 205746201 409563145 766699084 601829497 888283761 210396192 230117732 281908666 773321281 522564944 162442576 56208678 183542215 190239513 790358824 677536400 703787707 361177142 104189335 730495527 621970593 720158378 403863715 112153646 369843479 872643758 138991632 995331816 987349863 986681558 235200854 444453915 10378640 51220504 69662420 125278069 694350084 993296226 218377008 855624051 562626034 199928162 606539595 790290411 526671913 221394917 608333682 725610416 138779798 788660711 44737488 129859488 545598671 560051518 476256850 971322251 982858758 306528746 979383684 71610801 457928959 657435963 617323828 799272093 178073993 11327021 567939226 210744242 306268507 168714463 224173115 225217641 978703315 725614852 209948787 949378212 123366193 731224242 770939443 364563387 677868570 622384504 857420245 256945309 527188129 938626755 152659926 766899563 100095832 893516158 227867476 14895453 685962436 776203989 649329345 62119272 925953014 311557650 704954937 366010210 147972425 147865158 939251428 52667988 269821928 965722513 169466473 644397210 797224283 673148715 592140792 472790775 39724852 487401026 271474647 868898026 481872194 414716994 953911192 596810072 717341452 920738871 144641270 89840805 193966606 328739824 595903440 855828375 539150491 493913357 756639165 209340642 503100885 122389669 257329492 895086735 366431501 488159219 606313312 783679677 533462474 534636191 386066571 479765188 988347180 239710547 214138163 937195827 123024112 256582607 588686666 873483107 503691130 83169129 394772119 540733323 917622117 414408893 435494948 809682477 53477291 807265374 429304440 962570191 723125824 466771143 627665402 158288561 162768722 352786805 237342139 76952020 798116256 325498993 327274483 696337195 799371846 157340145 436364065 896005588 128371851 942011924 942103940 410596510 304853569 969393218 793844027 498003787 142295715 178480775 51790461 444070547 749115471 163011736 595233476 280387601 472533654 528627622 564502040 524506157 619314061 868769215 138761713 569831518 298324534 169427253 112287839 457875526 919101460 914527423 285103218 319434455 776929629 21699923 415418103 952708739 659304432 768484601 683866842 854146883 19495667 869944581 6929254 3673051 280611778 662261182 148259165 811494251 365213452 782283362 858032329 482382130 671147053 485849614 970013080 191623961 140761284 462818268 972224441 197318217 795659643 735533506 158036369 593463414 415186217 213486472 90291556 626395610 735381423 654644673 968785396 493157955 885953941 515649040 815944813 885928347 534514251 726704123 956035474 148092698 232460624 277970715 816381174 169855704 394694302 754841578 963034839 892816014 38799659 913189723 362289890 845562481 722091914 226223638 962693104 95540329 416057185 671145694 787035269 391598739 285008469 922336850 126446910 350524920 480911176 848603978 175717527 225826502 805489650 639760741 130337582 276601832 303627331 767896454 407596529 55164059 916112951 311182235 363274725 894153994 507306519 84800800 831351781 384458621 197338655 481756248 156463985 576652540 543939278 378246227 330464095 179147876 723393938 227872613 502262964 393821656 808106371 185714816 318151462 328578841 50061277 345670204 426664245 250373660 428002227 772883236 981122527 881766113 117166413 185372566 54561803 745400984 771087677 640659816 863345593 398660915 672884984 733639642 929399339 976526826 278055723 454206646 349985207 835141345 498378116 623863259 906456747 668735717 293848697 876141276 930647140 756753230 288719500 598768878 131525935 622212922 425540819 155315802 856218839 764515596 663812290 740406621 290430607 694168480 604147250 514442793 880594121 34483788 968715535 429916077 432920258 833207005 255342690 543049405 222981117 977916859 311831395 49197718 396074104 482804552 897850546 239148184 596419851 481940518 463558355 228078357 877218926 186068076 295232589 863310159 522925007 801899910 24789344 198895441 176390214 477662782 445958649 810958294 403454327 736276597 319586358 25273156 331241787 430035656 547670668 91951258 188060935 356700529 600348301 801064724 498979846 543267683 22004404 238457277 447510151 967235096 120937585 240459741 796124153 331267255 151111211 121099357 267745841 126540859 546780926 299493192 691109364 253494648 309698124 393689309 882653665 725337035 588288452 835234805 2578933 556083981 939277539 505146221 818261670 833013461 539962047 490881025 41992711 408265219 248416528 424301163 895866310 904181189 979258264 974758281 100630315 272558326 338345621 399195765 443138369 743426602 763314504 736427953 846664818 198043901 796930246 116588261 135708696 363938117 915818436 798316082 809566756 260812063 517152777 58082927 33617135 121881166 5878179 281010989 98561504 334377469 45040989 276444943 120449835 604184900 500729861 251081578 832022054 768737910 355286041 609431586 549838160 962521223 262099348 230647997 105827701 409312506 199674819 448433362 322316114 974429657 749666610 127974491 433760034 397815098 911656059 581597440 813441570 155800590 720243832 131007375 977670532 755328459 904892694 35345205 636644291 98950415 496411912 26834112 296896765 684021625 375417316 775047525 501691535 370741919 464559371 153424911 873642040 353828166 501128166 110485875 366355583 189752622 973930397 351084972 224788596 951674292 278319765 836942871 475909255 738356394 437422883 785487573 577829579 807053254 291215329 957578519 442721177 43994548 997151527 854926931 517333917 900506465 888401839 811464735 702875590 301834619 750872046 519667785 76836304 575212453 440915576 737209358 775136840 934214252 227463379 70334600 834027435 714545154 524954976 982826981 658252011 829904314 391838820 278527206 854567384 750968079 887137772 677270282 234165150 685337707 222566542 715478183 261449600 612530331 354874969 357595543 14011532 476117830 96898137 878537046 313859161 786452384 815434612 445404313 185838305 874684756 637887528 694217669 591708612 461095817 837264625 596261359 697472741 731005727 519612783 548285420 211236076 775809403 472319420 170759079 176888947 642814001 268362301 413454935 645478434 842130039 631707483 68266313 400220596 41645730 489081595 440052310 134668985 238280491 400052855 711159475 893990044 521576871 209168011 318731664 850278818 40267060 550865888 84165624 352390094 699892762 901751687 346809163 372818494 531347446 512794665 104512908 149515187 430333907 784099076 405718958 666669569 941226584 442277097 366792937 957353693 85341274 386616425 947962263 228035650 100404218 949829194 90899057 625905473 118064558 34213452 379540272 70747132 70719429 713717809 823517885 115377820 311117300 612986901 859313214 1822558 989889997 319072896 435852049 488634716 211237801 541207574 807701823 598446014 480334107 386559186 87804380 974767467 932312109 532899389 644678874 419875378 918382273 633814063 430567372 251688225 261119780 498378423 137568130 120370241 953858027 290377022 421497930 413449044 487736235 63376863 609329724 461645198 141669555 788347137 838697376 595029892 124725254 451847586 514486642 306165426 174774776 278556225 460494184 251866515 776284956 536998146 853834718 206326655 349486043 228700941 687809997 815816684 17175879 307991380 242667549 100847363 205789721 161995791 712582989 726613832 348761131 768410517 787675689 953427117 893161611 576106672 184991946 462700883 636249465 878319075 37403219 881813331 791583285 847005447 299429639 861257416 794849215 123125952 392097072 176114702 854426941 179875642 721755342 360142655 907105841 362075404 256930891 577031273 751351032 293311687 824857553 950185520 47058535 244181622 858432049 454179569 84944075 4250653 195990829 321903415 384455361 712488722 957343134 6791003 448972682 814655449 900661739 930789750 111673097 380328047 55274226 31976468 617741712 422268434 912504561 139451384 99717757 890867944 821804492 400016918 343206883 378465186 560121133 992629474 128902141 929404789 661466479 637407072 657026278 278824656 559741208 6501436 747806082 371586609 511608361 599218149 12039529 972676383 480926137 310259130 570656005 426676493 30101395 727395453 299184506 44850531 453254570 702161478 540239365 807484332 618971450 752231700 860984806 509879228 3557161 902566857 270287596 633258323 580842076 741808416 998941732 66352524 167652060 915245820 632307936 10926419 453088623 375688644 92607712 674656718 391994056 841345718 261025832 497734520 619429349 478689055 715029877 876183659 896130861 824881823 410824228 30509844 984797018 121985101 117165437 8600711 793397353 627845442 682608590 199699009 643136996 634954071 529797277 84823883 816802528 365614409 613655681 819775728 780616294 396987707 334038616 560612734 30054972 503808435 884725923 509165853 345981993 699052142 943645290 891215292 199698480 938885649 844316126 282543099 87443433 155177174 580246345 738096449 564685634 926311327 47487942 614213741 648587099 55238155 992932454 445175006 175269554 222857385 434644927 574715841 265458833 643360263 964195062 317996006 676364987 142064417 466487850 403351881 142592226 941670206 232787219 547984852 196962767 668114647 283169726 975217706 915017847 823681546 627963985 921082049 555407182 470202302 460678281 985923677 642656538 703060836 17321530 287948667 124726099 732876925 4714294 659191908 670474347 652955728 232615651 756555162 780332047 785694494 454659237 749267037 714112360 764337154 381945416 401341546 246327538 416875084 147542629 993781453 941036236 903351364 256041738 342422892 377351194 148789454 321672345 852852150 10365937 349486640 145222168 761285111 255587049 50590220 514797396 745935085 263091406 732703312 769645338 273952672 173415271 150932706 771013026 157618572 935024131 741994246 174830725 380437403 252264357 737761988 83321066 176707284 508220957 179668348 410147125 138458021 608275719 283213924 19450842 168231976 975819563 659512988 536632147 528067997 845665945 289041191 344588956 926956040 342492936 223505852 69733697 257725455 757169271 891746016 211648893 516780456 658229002 473951003 669443316 807404216 796213498 859238944 625557207 818817812 57297418 478417279 888021618 732890403 263599994 62873742 637117277 587577834 415078826 485703976 862741213 872977692 267727768 296606861 6865270 414614223 790313658 609529604 223816453 579309823 197086249 31898037 197632081 772326217 504528067 905355634 635215231 103559113 857179604 343423263 91862840 285093107 620783436 97328143 888121484 703942895 33485670 110661279 265298004 842236903 719630943 211967724 291842481 868997575 14269599 466123596 405151015 53720218 551248467 631937071 872795477 580378777 98989399 138648259 571544451 683471646 164444332 329761216 967514386 748416768 251564145 766481532 19853588 402900243 636614180 799936159 759835017 199739701 952593847 757676448 531111055 841485763 194993865 821197062 576617649 922037741 805451376 793999738 478417679 479245937 220564344 498859140 501898313 834329248 319863004 527919514 731135309 26637259 455164922 106697335 157370250 621501902 782473607 412777658 268368329 531990431 14573742 726263531 261359238 390742191 660439960 170893735 266198202 576802468 412534017 105753212 223669132 508728787 798400449 103610403 297528322 204397345 801480492 382139905 431424225 464852727 412159708 253924873 135559901 582115427 110260856 15088536 92318022 21477806 61660783 582469048 90068760 869135435 450906797 644832305 568521533 382788897 319994186 918187965 787302010 997970349 381626554 490494456 249475109 149758031 519927914 919886228 101354310 699589432 384504695 728442738 737401192 501560241 54383475 467150878 129647172 900062421 611539313 850169945 301034370 602548164 981756838 985581051 320703533 186342956 352598629 794371932 937615457 738957108 357075939 814998235 896079654 912243774 137227238 478562378 230168799 193787236 388995989 647035808 306078523 536403903 204887078 654409599 246986682 857461763 282944566 366266800 3709958 794133557 826399248 150608249 316159608 512886839 920773011 210825189 848260615 34359121 124481791 204806311 751488419 746783310 15012780 917614632 48784991 496962045 414374154 879821212 103165847 574105198 253333123 193839503 20351707 714955930 72661516 369113659 118485006 468359137 955325623 298406631 495340455 379168866 982286773 339679559 38686301 211738431 504193665 401579858 870754035 959923474 79100358 322277725 219191947 438234895 605685849 775704432 277798735 816154740 608558956 809764206 696886388 643352307 672367483 958441678 247977464 360971969 457604386 439253133 850260720 159430516 705616467 738583341 959212222 265206213 170757117 64243891 54657512 686131725 436678616 286234979 370482559 548049411 802551825 284461537 205385747 377891004 331199477 554661134 735013046 788893372 413414123 857836660 84599380 363060645 559658897 835753334 71738429 657055290 219349589 129088902 404566620 641568585 361104675 804691008 454607080 871938729 653711770 216621751 257708231 525681481 604795822 785198502 302390664 242726377 101165821 591262469 851704302 226273299 383014035 453584053 838451641 300937633 352823257 800712648 192879913 355513755 792931194 261909089 63003847 968024741 761321496 274220043 801737003 217194521 437389698 126927278 993500784 502975067 132157867 702732733 423916448 734342797 190178386 216455496 957883821 246597178 266212085 121976475 475135123 417583415 906670252 62929916 811451242 831995833 215917082 826051448 45010154 37401758 746060742 963968561 774487240 744675280 806522315 404386241 456016376 264945298 140253287 62270306 738533304 369532703 983471149 748698578 469951519 620237411 311384982 432392926 402032822 328147555 79792330 267310862 309589795 925724986 736528989 40645283 972336383 193668601 689866091 176348488 880635989 547696936 359981053 764839444 228137641 63836896 915858106 401011270 262784709 539625383 740569172 831815083 845683815 19781787 470490614 959745919 549337209 225299221 343979451 159103981 325738155 324379122 52494797 125935566 767772129 214186303 365150295 718661502 287113473 276913771 237976673 170452108 878659168 392508191 540926090 383334159 730821136 2316858 784886541 983946889 570444660 94916028 64974148 942624547 247520832 7906424 660540515 972583474 33376715 901937775 567497533 326594634 3894712 17424712 88194896 212473655 556451743 679138475 779618688 530183767 834360044 384579400 110417627 671748493 995439273 170265376 88731737 202278470 472203907 245932835 945763654 332201857 945174529 670920103 170399780 2142038 762887914 97455429 122874102 947192290 409351011 359671778 342471760 864728897 322319014 821745218 947251285 976976480 237954234 129587932 804173160 168854620 763329495 595856649 184598662 409300450 241257556 576283908 785696047 18212867 165670918 698306127 470305443 312533009 538465131 307939893 903266101 955970099 253856328 662941316 82998172 666534395 59204197 384847295 227579920 820983085 939056756 139784547 441576357 977961407 298859255 585106612 972895345 537003395 477837243 808951826 893833496 768956225 273906889 639148437 961390799 196292936 379198253 463597312 266072360 924959832 889590370 844916900 948167426 602660892 721446555 464930102 32523686 857359947 88316074 459010310 645019021 621889882 887280415 136759593 874558658 577101405 610356759 161395150 246493634 6395217 318045295 298921051 551440884 54371962 992944972 375328359 830365106 276936036 769957949 473495022 78601360 66308304 223718334 758751163 750555964 721051609 286914941 816337733 961773984 788026006 329729009 874726140 108097146 154429722 699330755 640125840 217937844 518125040 639999774 366123185 331419646 707120098 338486131 377781887 440178193 821931175 96921392 449139515 743342575 52889590 157940666 746271761 530240715 620641879 143486903 708864986 717340221 981156120 661629317 426945667 375046077 331150849 610942498 201587826 702535106 823880445 991870474 310920131 726489947 35774629 170213483 44157278 497786269 834917443 298778766 431839186 634452550 30872233 294618851 233221970 700139345 779324970 313229071 9569523 730060606 291779513 922911690 141671272 333853551 947064597 8151211 772388545 76338993 810276119 246940695 342370827 277243822 912432013 566200472 574906251 972299213 716160914 103734153 235379224 682703657 474114751 206801653 678247740 435528549 466252545 351080866 283977812 628366245 909814554 886565793 765622258 344819485 698381387 571761012 724242289 833731131 89420673 635652982 818465343 788513849 288062643 6913368 363434467 68229105 148235509 901589037 393189912 832694319 660703026 629901251 115710821 565446940 328981741 460869751 654352500 985913663 570835086 409747974 724972799 58020465 228141960 266052582 706667314 605879046 907296485 282279592 847644069 90336988 322822261 603298790 680891178 187413962 943222440 939065191 209333828 820394844 805865033 274235219 387649294 404767358 973683787 435507057 933215840 307302319 837433187 513563446 29233039 363926302 923485971 705800522 841675435 279983280 598243304 586001937 282509360 577783703 998378464 184180458 267979338 194816521 492655398 198978091 59295898 41985334 82394362 817279454 127810526 711069804 976196247 74932010 149774606 481659127 796675773 497386256 248295235 285643548 528680513 925860917 834890949 981397597 508631404 326768433 322255499 993106722 892874591 274704763 351234399 91518453 620655320 542525276 927511305 669544239 793193795 487253220 417484707 548018777 742166035 978988409 661176348 351606383 7507914 16074423 661094096 863179331 524402988 487550487 372582156 902300645 888091270 592945054 895685460 567344484 821404299 635561454 543843211 384427639 946695811 823748107 783136569 547589549 659182335 255015006 687982613 401259871 682693631 507089791 380622281 168648364 273140132 864564599 753063078 10981017 623447865 204710637 224982907 593009557 341508385 698620017 779217100 857667280 701328106 310438335 884306406 814966433 888709445 888024209 301225246 140195860 955120058 395899122 761483044 181515688 293101630 823877138 778488189 214226274 619282470 677201150 827900267 816180983 148878900 195830839 154526283 547967156 801704936 206946959 439306052 476246064 180262706 864130020 191793808 419490157 186218958 981562631 631005407 600169515 581292704 305565756 171839156 678452420 569549167 893593251 409714510 207548333 832575048 848501614 404358423 420353538 815283593 937893808 681591291 74703611 987992432 971640897 839726636 408742569 980019650 305522870 40634139 722465020 451165377 97926441 335725647 922517928 899325615 570165821 931177050 739006517 565380418 43115341 714651105 574326291 647075100 465684262 487859700 563202510 773092130 412048212 65969683 314524803 935838862 580893083 870654125 41273237 344436067 886374944 684178898 112634030 26680616 913713513 292058072 845374125 405612448 879925680 694958166 10237146 664671067 796682275 554968049 971350032 776873810 626145009 912982364 599230828 341060850 36804694 458209439 942985315 102133150 611348520 794376558 738233000 604389690 377224341 91831120 322531037 241249603 223934736 8592407 696152917 690695661 483407206 495623029 186124996 747196205 705649462 881226640 14316753 936949000 137283388 492428841 764456502 243474485 839890121 198624202 962088176 246943043 827628514 973905440 874256893 809214860 339162948 589875217 740811626 571481639 379082056 73326981 659208658 841101833 239424603 294837696 457344305 42469947 914353205 342877109 744442176 482722198 288216574 593459881 611064178 177131026 201597104 599181257 448551899 678631700 728349974 69878815 532598033 349758142 78064915 488876579 271919331 631027087 353662024 915788485 493472171 224900112 979188433 542828781 623571958 509848018 573655428 830920891 403574143 804224248 148173230 980425438 802617861 980388728 968343851 530848431 376084250 726875522 123728342 731126725 573515884 783159048 479305158 331906260 981328140 322760797 396989471 192855997 951848051 713391076 521555673 763778254 93138024 500322132 25373713 873745153 953163148 998725369 999218708 62557268 287094058 371270010 818046285 807810272 507797548 659581817 934985010 462691770 118263019 369110336 566727562 532717069 325470580 728286755 838489915 655100657 399084254 921378351 646659978 257375885 453042992 392758975 154585216 299543137 504438473 354637567 9448708 574186695 202572182 364855803 576837709 423121141 499708421 888957705 224829018 349231739 606869736 588182439 745775034 597655849 93335445 395371831 362454553 134092295 348963549 314675247 274709420 737153468 326105667 456592038 707167757 914290867 145649329 485372794 36420606 817687500 197637639 40542389 555036052 960710162 49222322 591463420 373484948 131647707 333429083 591741273 572020395 359907853 393144640 232477802 782519992 935074975 226974242 14475007 552861465 598260167 536807515 925649172 187089558 299000110 229283639 752224241 904664159 359778402 227871503 589724288 270351769 857600831 551049162 68208991 99023139 20549821 193984890 775387980 310253433 575903058 157048692 991021447 988005995 841301535 592704898 828475478 241823145 564783569 596271441 742776413 191078654 253840924 861600983 731883312 591154599 472876330 84025455 317794505 370401175 815118222 944888912 412076796 827146225 614064541 724267699 738483843 149620538 163645304 492201973 743099216 917740190 359680967 478279158 758020849 641269812 331552950 11462262 366665665 784408131 769574691 679880658 499229863 967977559 884997196 704695706 902789435 385741692 835079281 560708718 941865302 95255414 48132312 788461193 695674168 314005187 164026310 991609406 140920690 184046977 564364155 185631357 118005882 607043962 44679894 475408560 325895880 578114667 252036707 804520308 549066753 930704177 90180809 991862820 128943005 640457175 648555407 240385846 806999056 223602450 61034613 888451661 639808114 188086363 18792614 775508643 330030561 126771550 578036438 297102489 240098341 104652453 729005781 19956616 107001587 853861261 838541201 906623869 31216230 768899806 604108033 99957455 105317762 927304493 948241138 327173701 724677719 325322019 195413069 958708806 711647785 759670332 133723563 612403330 85023980 556557833 235207628 864852712 422742485 720775866 962046713 643361081 763210463 390524714 791400074 647263560 144195802 23507350 120494101 992971703 826520158 941106576 886495868 28655781 943557271 990187317 126454136 925327928 670915487 564078696 476765230 994652567 199993300 180570998 551418586 158343452 474194588 603066634 975200492 175228533 445593060 186622361 343305243 314794026 806892181 834163880 389342850 540407491 188659039 272654461 815779478 903199851 352368223 893038322 474259660 573625566 157584361 710302047 787194484 375246868 960251484 718399365 639518655 465981047 759804721 102940593 139557642 18233566 198036711 279266557 24404423 324193340 763004993 33588999 348213845 957547280 835704850 25322262 702041642 737032461 685943235 812374769 898021162 640921185 604226218 17954573 98612048 609171743 445199849 725502815 704273796 437379834 694552451 554975536 616737811 415649692 352893170 609904106 844211265 600446538 144123719 302505856 999877891 936451545 353663638 718386413 935858699 586480637 251696600 313220504 902521523 758141676 410089162 437530815 579577434 18707416 156431492 916941386 313017209 77768866 857214395 826512601 866837448 4436951 377625541 613928121 386097373 546183623 294265290 241218110 654400235 65820161 833590411 362715393 460999421 797787686 933559289 705329715 334472144 374345989 282443729 663638345 840438882 149425501 936346161 890049258 827876502 613775627 612392250 117330462 549435491 752004233 916167708 159126648 789408958 909094582 366020934 747537301 81740177 369015812 530889665 854534700 883911730 435136342 193684662 292270618 974929947 230549427 322978217 907955891 221391645 202574714 209971598 658396811 47155783 381636335 234336180 822101949 403403830 401442380 340204792 279707247 220028704 342930224 738587617 693666495 4891834 659186675 83417016 262207893 814707735 3608096 341522 63327260 867623902 692636993 394850242 720211170 379871782 297935765 703290207 15754748 926983872 792450310 9501080 43065906 782946811 124454318 661733903 735350067 214815567 618534217 296103777 229492864 884299725 266662162 886698557 496609162 739007026 112116532 79101531 397986079 65801274 8999977 389060353 230996485 386828300 889300065 332965896 878161370 435810820 677138575 209029524 226550437 748348901 480082559 320216638 782331781 488953307 888709385 658564714 86728321 117391978 46441077 50392016 177916404 724048738 770474611 52658641 697699723 449418697 320039974 275391472 235673784 372718600 597198202 905263184 512694932 738353837 914122107 19548282 207974315 829622680 794656621 148771148 725596575 148589571 302359396 333307703 151063494 723495246 894836282 335474138 20766501 148398009 722614204 140709005 578834019 958904623 764593664 619955595 43035172 379967245 75666358 675713546 359514559 275583674 953526218 465914717 296764494 680398008 486950902 248514960 99129757 19196688 118388584 338607338 380240138 872450983 998365753 914649351 679236793 923408541 668972693 951342179 977263555 532459312 804216507 535982722 293816227 934941023 934329053 112792843 972168804 399868679 434517878 81754209 853255840 515734399 805097357 999910469 199985452 318030118 556517078 442125088 131985127 782352689 95333957 285757814 993926659 836658359 688569990 381948705 436834237 874406528 999007389 349640168 511202260 687149956 183169447 100141542 969927397 852918975 631531165 688059669 595223691 677248910 85967723 267038945 63517165 59535855 943403966 690028718 702847307 159014321 330081207 557727887 464772724 918361889 922725683 928811753 111307501 568028835 766250943 337564629 5822396 140635518 42329266 440699840 979158552 951596687 206297128 977782382 808711834 967797955 346433303 778550666 673997636 578459442 115033280 132104293 590746126 596790116 147874186 971865066 25044973 110207812 980396908 306954293 164895451 875147337 103170626 340943611 170659552 370581084 161964200 735515120 728689098 706019376 203140264 559334932 819636872 734669773 147770050 735410321 349383951 750317585 363806139 644600625 63672306 862572054 649734471 283487812 510130672 297087186 123181234 776207788 880502478 44583208 430745908 675222093 190061739 478309768 842531266 834548193 747014499 938861540 27594976 825191962 620304307 495187959 360408835 90164970 539101517 847486040 441351699 4807994 592446377 316281527 525564113 22410305 827663412 299239814 429505158 479212668 209287725 502048182 58858695 670575517 905537683 844202254 297203723 380461463 221922741 456742571 817066880 120645820 59210529 487787970 313987227 34295802 855991272 347506608 740528129 535375890 172152977 172560102 451561178 610762597 133280806 782424144 47690364 573644231 347999673 250435093 742864058 958934232 743372314 108425320 184049386 341126490 441842565 77681593 941137005 512824552 449142554 20196627 400783719 146506680 287073947 486180148 690299077 169800480 172188063 772403990 34374498 406602949 972620172 97441332 563316666 302028397 585388139 225512656 278639976 119036309 232347252 670870999 198517388 147577497 589799604 665304202 405404311 536131530 799194558 743092873 60616950 20916015 714198236 969723547 534161697 660466688 898178304 666398985 430111844 527332768 736627560 393583314 44424159 910582518 140747502 367937404 686087334 284464432 617076739 982328835 207333416 821428498 327937702 168779000 165371237 750181120 53709297 720840916 530049764 976595824 572034849 130403988 642234309 692142232 817410422 215124204 762297752 422351200 855034198 900931895 994377166 55322243 788984461 898183539 552968337 509253230 339524236 462538115 43914784 947342287 430135966 885994498 202912666 801485263 978541515 75756139 548288947 732306590 290601540 103988220 645333460 156677197 990224435 937630142 105181328 275451944 709867265 766090688 228068306 847477697 932510763 193836409 590822396 385645791 155971668 475884279 964575194 420883876 712184115 726190447 103142998 401138515 349192974 445748762 961208242 357095127 328708623 742393634 716452560 705194828 84149109 464162856 157719319 848897222 609324947 432445538 142171792 78673469 981527375 138759869 779698404 654198339 228878824 59215412 406045462 666447290 845863375 58831149 118871578 668975214 697705182 159442533 275298229 420526060 1215798 78618808 796712277 418314653 618007993 446902035 412865439 638713069 823612556 392201252 126409667 572777717 47694881 112145087 89967639 686296235 934390902 563538984 428971402 471088179 308017956 780123046 561473063 817872063 969453708 184318702 407813235 136056397 329764069 220888543 545196927 207708188 319590307 745838058 363504032 117170682 37936668 874812155 328081692 71748603 852939859 973539458 52945074 864749303 700044089 59089475 650094567 634640074 1628278 815688812 592543345 572532425 346969729 930094653 990823506 171956352 684528924 336752866 427244493 524993660 411494395 938333364 187338249 750581631 815447742 875133870 657361999 490996095 440879510 894306563 741794919 820049348 350827398 674317863 768398257 244898029 133890362 900288886 706248529 650597149 751777112 261475627 324611142 273462357 347118958 594786633 653766146 69452990 724956169 648208664 563898623 320962288 464491941 799282187 528208804 719364189 457757484 601496079 150506391 646821368 455171068 316923604 617979605 2545262 219398927 341441013 702013531 482219187 682909491 936403393 321783097 395775439 334924337 20987715 97354678 98281672 235171448 571034104 441340810 282585669 23134961 526473874 522973340 370194884 161274299 341144799 381220484 534445308 488013668 684358378 665552096 280638020 705706243 866270687 979017576 343778242 402288540 429773554 132342198 957013583 225952261 539800260 566453608 406070221 418380499 470476665 346316239 760882249 793783727 386251081 205093333 819700348 611885329 226996012 39115344 731058361 246781054 437826398 426454794 751814340 296124791 38679417 818731067 99491408 481670702 565928925 87980932 932761242 252359259 596789359 511315394 646041412 587012733 255597758 264609582 766381784 890563157 948532960 657156460 56798731 610176613 552018368 750088101 237124558 790709943 74612142 302861902 266766415 178207592 683009288 535157296 452931832 174984019 666539967 446513817 460948617 528890585 301852583 556199380 580841559 107487244 915803274 586317153 184844930 876223238 720231270 730114411 685793840 64133450 853468171 145128786 949887941 550575616 897098153 375694521 720590571 189355885 418507859 939087681 146507409 470534897 72844912 532042348 234508146 919587041 878840937 86097861 255611930 40035216 763845417 750633093 262319004 580448306 286096346 106817670 617599765 885167928 749436061 186987350 938343417 513624749 395162892 774677503 809354424 469290602 655568503 559668070 751726713 297566700 388448288 796936233 442359994 4581605 204711659 127917669 731668408 301050855 821489867 881068816 233423902 410152344 266112948 192204183 477415497 305233632 332984750 826241935 105257145 686482182 965597680 896644675 40743311 282782370 130470934 186695230 722422968 922690087 868360576 512900960 530571767 860877487 789620758 71773118 561446802 570598504 522336470 999778458 579774547 651767429 259528528 255722202 660639310 337314242 775880350 336420524 641634814 793145635 647865071 688545760 670288902 517063644 268746720 826933455 647479636 137363955 447604963 54935417 999278024 408550758 121444010 678979291 6007771 225843052 379826189 131480269 354500987 125513739 182770891 161905525 279133049 131596740 57195480 322614434 451845275 656436613 932461001 575154416 637938997 78431341 438536705 253662452 679288177 995111223 154977728 489060149 797960039 735213144 935635719 286069213 111582097 305121709 454332145 63392199 40573167 3295308 644568907 242307894 815030635 405953088 918952270 441609053 364191159 603784571 196904657 497219884 274716260 739998292 163015918 658007834 736377954 389854335 37161023 197241665 444659722 575526753 519225726 791148282 449531467 54725967 813895851 224185371 898244744 171041847 84303208 539255642 117971736 178268848 857112821 611852478 888714858 950182607 279930752 864290931 641044005 444966213 171714799 868667406 211852467 603102204 190422972 537495596 200796104 127658320 43615762 12867827 513838827 277701758 462485772 427835574 849064159 232691183 273522553 855953430 729934046 435560761 310250805 706791401 567550469 335687935 743579427 257511802 978734838 808031495 212427386 903646991 624093098 549694992 83043279 505465920 146086343 378247385 70752651 218671560 522527966 98020234 519839781 202867508 54297982 168875696 89483172 812566866 987685735 817542236 943675861 198744361 226044949 923546075 545836602 14526969 424624258 585768178 718218418 833230902 179199539 950078077 213468000 230219250 548011939 21144703 700902196 61543487 796023511 659923841 392205789 567497327 432515482 401969099 695617036 239132252 188889737 170206373 173289919 863292462 691362111 635154174 376135991 755088693 949480605 90418120 513653365 646279552 732785847 859129298 635195654 797127527 766512550 686808523 349511710 967156050 389684365 138372093 419009082 3237660 778876985 786002784 916488116 502011234 590741372 757883846 771051456 693358054 956823749 669190522 464645826 506500103 849638488 595215722 516176374 103488404 44885450 330022086 683788333 57527678 736012270 140676711 651515982 77016037 470063839 345716707 390889271 778952348 483165784 273012385 973931772 653356548 337076615 385022737 519143572 869219682 225547088 491094511 899122679 151744263 358697082 49414032 655745409 342257298 732213356 317040727 76266018 748976269 624946654 287846350 841237209 889448631 102691152 562023045 300831914 473335442 50738144 938854713 669709536 376053221 611498874 958127273 247834941 505762297 110790743 242408050 121693004 484353532 376186289 787857440 384262141 5045002 174868133 477735379 136890480 144491723 572311512 806877909 781401026 119790016 800497075 123222276 372554941 487546093 237931583 681493649 854476569 550214800 968159533 65474202 587548747 820729378 911987370 670703627 886942633 223308226 606382813 433938009 752171908 717446877 158440260 353174737 406755986 638685088 185249788 203811432 587026081 908593966 265818481 70209680 337396278 53538606 610175777 868214898 321618796 349737192 198207340 949799066 528566010 162837029 701046953 437425382 846156376 971564339 349669033 633490774 361986041 947767572 890649373 25157221 20176625 610877105 53295315 470484519 267445084 841154186 706680249 881782066 545869174 599638132 770581211 567695359 712579828 536175138 267214627 947975541 639464671 322507861 976162773 838127955 628348557 118279887 787709750 440707150 172279622 309838764 618837860 478197926 696657847 90396460 285269777 887055354 518944888 231544255 536951287 969315013 591619136 63096931 20090356 390756355 746291748 352800338 726807253 878276832 889852542 740831672 135674314 904025578 405955135 864927552 936667987 930117026 728253699 393948279 616584949 508050313 520864260 886359095 570393117 216959821 704177600 480640597 88549191 621922195 410845403 54518646 470632854 237947722 117527339 732979472 396675077 45602220 124471503 373491905 82358557 666321105 60789361 942006569 202320887 614535444 660212686 649763710 54597645 211617599 391760219 710822118 194587554 326287294 6350137 226577113 274132031 366857993 835047331 603578120 587657669 32801672 866272861 541664903 942598750 228337572 93202705 208151241 340085347 505025744 861962400 796686628 929834285 547868801 308724747 641992436 154447277 442089587 322665758 938843033 724588686 697166731 61132546 595293130 219102515 162811416 825772088 364560136 916280547 557444921 164773572 311055874 388954850 795877009 571305444 627326674 45196417 211074822 185628740 970307075 230490717 968848200 252790641 181643289 398875308 790314420 489239545 300991152 889467463 555099407 265467458 179059637 634877623 880975824 602526022 256717646 348224893 920582444 889981833 586888518 286267210 659468455 997462519 865298902 98447283 902419735 170351405 858025503 228070564 825525982 748049855 747080501 852852423 744542568 183547211 154549298 889799828 141840364 175630584 900660646 899863158 660396479 879457976 423860245 604563278 73089191 329016914 82140920 600302253 732048160 995592247 651149743 323401664 240483380 14764107 433814659 117160357 640106336 336687741 652604027 656266336 789574959 742650668 504814607 680824295 205428242 774490770 529992248 12031805 199315449 710832225 186332418 286474176 528239903 780190247 145935979 93502589 762779548 665460537 721224078 241614418 599429759 502774774 396090697 968041597 67278368 31831342 759299982 68577289 758195510 896865813 4806015 466535274 976817387 372711064 796148428 557390003 163374191 191421938 686141261 411874308 675299348 336506699 359620651 189117474 38072354 99023769 400554724 675180272 327957522 430125678 166699862 582017069 66927082 174518779 19776482 371806562 293573674 795412110 839069200 953269630 52743591 808973983 106909477 433918402 518171660 189357816 609281523 739230068 527371632 415848521 847892186 443927236 254741745 525968750 274064220 730451731 642959542 824757197 380551673 40088204 255964025 747944498 419444950 171552993 824189548 882837120 685539539 757631002 639975794 763533751 420198240 235245025 715854134 177051423 794153869 854801231 865560645 211617137 80405016 628165944 197197578 706910685 162426915 888417272 13899382 21451510 819255889 138116486 337514173 772249864 279588086 827853656 709925059 502678471 356934970 1506371 456805048 609247551 265637272 289790003 904599031 658982840 918035072 688097817 727511545 550919880 795573826 988406909 897725864 250301515 937103913 124006947 537463623 670716621 304379291 373320660 230911281 88747482 254856111 439753361 560357416 868620989 146763860 298836923 62706911 416073265 716557782 738280066 109435608 809435497 80043252 555115293 746467357 926517475 220275290 568498351 398664035 429849718 592694949 796344944 242062036 138957240 846395066 761405019 202305283 95518686 82115857 488245967 399305098 752539119 719157999 423923131 405751725 283093247 344917184 143437471 740042722 20985064 245071586 214310885 840656646 967307157 636353265 967973762 339190684 184761544 577967564 803886376 356743409 557736957 518454940 895303695 933551382 93662541 886537653 353465797 185401170 574620754 595570307 686048044 43227085 903302179 535144548 873803119 830818824 86894513 169482963 388090967 307607796 975386429 235038316 813859468 68957415 816597570 161202349 256589774 444227703 734223867 206897973 363573470 43527244 430972467 316728944 48658891 363347206 949533004 447288104 27017865 478757369 598804027 952967627 230354235 652213207 551283429 576450476 178606734 953862500 958620237 141339089 988794959 940443642 832801372 623474917 936872124 757048755 627461433 514482124 798146340 447574149 655012014 256427530 501869842 999829131 557256118 139213603 219848475 624093807 556882591 577726388 935198027 371569966 963002341 55859163 147985194 123619723 666393284 264487966 571484018 529500458 710841518 579540938 731999591 800797420 664791125 431384135 297177588 775348528 663383725 905733297 575289139 534159571 981714950 194644471 346321961 630371555 580453979 681374361 184185555 509316895 971605137 264444804 698582814 367162260 232430503 951002136 223056596 227212580 855761535 865434306 819224848 569910986 285780058 405366973 487042061 889654817 532218774 572093240 275002320 71873596 978969864 518050442 746530269 171415475 723736362 150904310 693056319 769930822 899122623 529730200 683367172 896009550 971539801 120013908 195605841 126763685 830567068 422464484 437297449 75102997 443163897 492012361 593904715 855876111 244650184 540290399 785016632 567634202 439516779 74552768 114484905 916423986 840493454 998481410 745806967 698843832 846795508 138856915 978029067 240835770 63511530 924098419 369069011 734233414 209586514 601506579 663049680 584963303 201429311 938093704 180835440 844489682 359030032 847358100 743184869 489505651 441313084 336773808 508327912 886010692 105122054 697841872 230067418 895260418 518580124 413713854 68665823 944878863 232241079 772689092 795598004 4392541 766886767 238624606 128437271 881267435 168093435 505582157 943104131 496935930 842574190 738828655 466973733 998751049 16727259 770611718 49201424 515723766 635603031 192472882 958361536 775376970 870071140 896314241 113245699 127331901 976217572 81565872 17641073 346273829 401753963 209148568 915896155 976084547 256497585 947170249 77587058 949057529 726692543 583111730 799186990 83713899 167299714 15844406 622015922 438899975 189055965 427665044 503520244 659516903 853818788 216333606 761721071 708449105 703286260 701565743 234001606 793906037 993221157 816985086 612874572 897196160 420776128 407145656 692960361 665797893 458645342 910509337 408506218 782830134 227130482 89244084 191862062 40737031 782257937 875428281 260508931 696719437 473988136 50586031 733792703 426459964 891606446 649414181 711905595 598866395 884177402 314329389 301733729 31872731 29458378 127480765 433945101 706184643 890224097 918316223 750323106 209704982 329985371 894384513 354597156 262869523 289947521 131471858 576012817 680331359 294222928 543629685 173132672 353679552 189809876 312438482 726042033 171746004 102711775 853002950 984478107 606600309 962256027 571722834 485382186 993644359 404747864 726585212 673543052 180095545 905802811 782230286 195307739 111623856 189518479 534682972 32925939 737007434 630916615 25864130 678198694 378281090 25274176 31965720 643034166 704254952 458751106 905484482 99406507 763141985 620859966 900423410 407004042 73568793 411780563 248379194 217718404 380749321 926329707 438973318 407560677 189641498 173703295 648285161 645711522 224094963 779580270 956626533 857095575 646734362 545489023 215968461 578499867 375216115 244045763 871437706 789906539 96106575 640352662 192775885 717530801 760461869 512449474 256220649 204489540 218601820 881682682 487331665 148007625 264198316 696416659 36396240 41088235 538967258 827313401 708631682 891432312 34002729 381600579 334536850 784454211 448941428 457771090 542353514 606723252 98748194 106451280 281029818 683631902 976411043 1278997 476973684 926494716 73867631 740730509 478861328 937538210 740822360 822707791 654264464 412249081 728972870 121773304 326873279 859055760 117224395 662668321 119237790 54445267 113382470 609630511 211403469 430249555 260227207 483705091 248652644 669234 679228821 978757461 694351457 218178619 563372627 742823029 394689821 497986300 65058702 797538491 378508148 717519531 404620118 248992231 698520088 55568640 131510432 527433897 668604841 412564473 764699857 319102824 969629225 305862930 49958367 46610682 408598144 572086746 897940874 828133430 868546105 406236459 55201781 719851902 775771716 999702663 994138132 181918173 903400303 733936912 219537171 777915934 734135616 748624414 785635632 802774190 445823831 919898570 666360836 572143788 496734737 866837305 225874372 477887311 616359979 274755285 377893147 453069986 428861036 278046965 866483407 508749960 301230407 14276586 586063606 861261993 753679959 141709650 968803862 226426234 800674368 385969098 643898451 795613851 27274890 496909668 754148497 939548925 996105508 753207352 79860737 539604974 717058703 179724557 813311343 964596381 855444242 170620529 576848671 168091271 93869840 103116978 982727430 108247783 499884247 540641856 314111633 631269807 703631006 872153104 819595265 969966433 93648020 322912817 37718505 389043809 131172975 89750429 290487240 569653227 471961738 945266862 527102633 150018749 993704383 961756932 733514623 708210990 883027490 754634721 670953861 659101330 163909607 769524709 915438537 830052324 860752271 187825412 360520831 900080049 739454166 568581959 602205363 310709571 195329323 643635111 227658975 269012674 408930630 604185921 69551477 961965973 182078264 442597237 879747036 298211127 760279432 838723512 796941340 32242259 11177491 752435103 191502408 107360479 109187104 672100270 405736025 789596867 506200318 421866029 242825256 586043783 724207794 632249543 275417777 688810194 902653632 717355696 586685872 88616154 554574148 369920859 511524344 592415170 816120540 890547901 915224827 754732103 576074116 431477640 34623813 162270837 863406389 281107517 33621940 772777067 973209509 28793263 925815503 678637334 161696686 201450736 100363354 744332672 65187104 11610160 83209310 46291967 491203378 62077231 226631894 121547763 737317202 313104609 739645603 536930748 350454797 119529900 430716070 802847151 77996260 188696641 688733886 954641112 939000692 617504916 243757302 690743602 868230171 54252054 328122144 733603945 614533384 432347251 140821741 714558285 872210188 472980865 705964807 527665379 255692890 274005942 684877421 415004367 502297348 927099263 321541012 217914515 952726079 535488710 824222247 515155291 544148020 150004058 451722557 86662789 803437046 850776284 894986832 179554385 589783944 672319076 370328065 731697754 14837011 67444279 778087379 214101075 558792458 907354418 712005508 992481655 779451032 288542302 932840508 674917733 910634723 119051820 969745759 332145722 325149719 486835299 332980837 510785021 80160229 889172768 180112558 448388855 657366958 549099647 740760403 804252359 917848001 915603203 56025670 60827815 909808823 648777076 484202041 472217074 78716333 752973649 451102671 638118377 480012334 263577730 16533948 225478287 274263574 899207606 444255882 463505775 162209493 267675594 300923154 941699829 399904377 240884333 276692684 678139702 227862123 366087069 790593680 584876285 89225619 246556750 541813859 549802751 918438136 550170870 655520859 641156235 448922022 297941258 468739875 74311413 841333593 729590300 225825746 737771166 954448161 812762295 17297568 236425322 203636542 913002502 740012798 668845605 154430090 206666080 648470821 601308182 88104208 302558553 812345149 70750988 176990665 348014571 252449863 155707497 369189594 925128688 916229583 833366543 253539492 203928109 279873783 835045555 512505112 215691768 122691086 50928177 977313001 371474075 938759738 989176856 540194934 354289538 772466339 511687111 611543176 497126547 982656217 580908261 682375408 759375336 985290876 175483585 852732354 30002485 930990155 863069071 76302087 880049001 882917622 578736286 203593725 85103205 543662555 776010319 249654754 256217001 954633259 693389692 330017316 563347770 264904824 193880922 785961863 72079728 478172998 244062836 200975154 286431546 728337753 762546700 871741336 983737692 439667579 2410363 868036813 89702154 158901379 343728315 14290476 818666348 334801649 318439089 184395761 764831269 634535356 526825858 189873611 412872221 46425535 962209435 68865698 385832494 844310168 462032075 665567885 541440217 60143572 480231551 9888987 758742778 228959934 628566118 78794433 265072932 241980726 370661520 355408015 452658912 157809494 261867928 614753321 670702382 217832534 847760409 746725335 891417183 42462282 251988668 428726985 475609380 126842124 471821366 607048056 517179412 971815951 199356059 716746975 101234792 203581038 11366804 291234142 268104566 385760205 850695218 123649418 459165290 708102926 792972209 410883260 166491873 493683016 117504951 625398503 336988836 786962375 952997270 462701829 273087233 916518881 361250326 414384503 553297017 69897579 805083531 71142069 23950674 802727530 399335043 503874225 528640826 444020727 940446847 774728421 659340960 58610391 226752259 847726310 967811864 435157535 153659867 317573606 293709986 307294682 31461568 337876761 987995920 89742618 573281667 697970007 152642329 967497525 939233021 313130378 26202855 470872693 38771277 26423553 627418065 757920013 943432792 799555516 936378377 448117266 254051681 548463979 916291548 701045853 906997821 765673550 995941790 568041547 903118899 279740364 48025264 410274592 593060748 958006660 324431394 998147698 990600421 235033261 284737989 845566961 155734688 992948346 843587244 917372176 491072110 543507925 932032332 712499074 113165216 729642597 964215125 220562701 542081262 840070880 519974600 461484912 767957109 357369278 788973439 205011722 560583562 314102193 18499013 280269302 714071234 985972288 479216166 475489531 387719795 409380826 256209922 692483011 774079784 587548203 38615330 961451777 800650614 919005844 170409863 511348924 932274511 433862371 100676675 61949570 860316686 575850823 566101449 214810797 855907929 166724335 894136739 562621978 526062233 316596506 721478371 267438356 956345962 65587838 716105360 446567517 936619853 958814131 222262787 892950642 376900516 189638191 735637959 870167149 913677204 787837024 805504548 899640298 143846932 689871591 500848963 854424265 274923952 756078433 211284341 636086072 184281028 425465290 813453676 547214484 104060686 243547547 893265149 931156185 30231870 664117337 769234321 78998812 615023473 532373379 190432888 124041629 869832884 534704391 471722049 127970822 545001883 323377064 754634070 748065862 957897621 758410035 303433818 14895366 982716404 968462640 302201739 121239610 573700867 442250000 504142941 860192321 140301923 12522831 668801424 725548249 583532157 548288266 703413327 49469549 363353328 724639384 645881967 862396188 638323718 786107560 503101935 698008835 368325831 714164333 102546735 969835586 959965766 306977232 854865213 61690106 104953431 136247342 826009320 3835728 855248226 125316715 340531916 237277242 31485253 397871574 920913889 289617425 787057632 869521977 460596178 829268261 611399922 390826781 208610847 521685332 456737404 979780216 6956895 529624019 44036072 506649916 140923868 455148013 24152809 144090670 776618312 894861546 788955798 552633174 198865645 669142943 165787160 472733567 365617960 572429448 260872194 839305088 908278004 916999682 939516656 55119042 955477465 554887465 619802461 243063871 590534983 806996762 599038989 468232256 485216660 331303553 372562607 620580662 496166790 255647924 677906966 885261268 922315003 823717290 282907437 781242335 15513601 798859681 760260885 846204306 188237535 509842 518488947 111893701 366270569 859603082 218971466 994172017 543677502 806137501 369755223 137980834 847287420 774465146 688236179 401610918 131340746 819577840 640002455 162382437 966207957 588323381 397621841 714756581 956683863 653744884 738300340 570335922 204512409 857982415 666277304 5128445 594337645 187104768 821992149 309410005 929392364 774089794 646986686 533101151 743637064 352763914 951515522 618007753 657766635 305410860 958975034 126034054 492728376 759881935 462996868 795626775 178116220 719889785 287035352 728652406 736695315 999770175 298248960 126529714 934414567 786862831 588680930 647869294 398021032 111566253 715155007 749628335 175545202 481704444 646703860 909958934 4875919 549549306 39389921 876038960 327096132 161315538 410835320 498745122 883621745 431686471 678166041 249657604 135046986 745145409 671998796 840102270 664528493 653885799 494524424 66277542 823979679 714069058 52487495 155049959 6693679 296720427 393387782 363078701 914709338 83425946 845767912 886024319 908927181 235294881 505332134 882010913 670071070 199807986 177589848 493820622 936620960 706173555 725662476 192399364 343126032 222512091 497872675 831624896 686145976 778856687 132726107 398822940 894926908 749125184 459368465 518516291 801928295 914831637 750311337 330883979 598065166 198835469 574285375 512340601 458104649 280286463 751777703 771596157 981534722 203646634 518826187 5674168 453609308 23018612 345675485 808409507 363505989 95445467 468557999 435588123 870253757 995045456 178568074 694366144 127471354 438122819 995734654 844647414 184102994 473500214 309444253 110023933 495324078 191711660 999532602 887155537 272234008 839456491 900760695 885188070 173295017 28182830 405438058 703607288 35551857 260692121 219685812 759279727 828806764 364338554 806930439 464780036 452999900 20697794 320126790 694216365 837106131 380794597 293119528 425921788 695111961 276258611 294050045 476131502 362002992 657741968 283274350 780307672 775834664 324331219 698487436 921743844 215134312 572946427 935728237 890746887 970235185 634957793 588686464 567855115 252873264 676601799 187400618 233984107 158781686 883303633 618373418 745517934 266953198 50518802 151738924 682701318 311847490 375931459 715419776 175505882 981148269 641231807 130740566 680979019 980130787 135232337 446300381 115689438 814633423 596875731 676739503 607439410 488815025 628839035 267688291 131755499 715434074 814042768 302514908 160732049 936012781 361817823 517656150 144391852 918421514 627624924 712073693 869952770 361536486 892177001 87635674 687357295 106930424 426669236 837501581 99157523 296982203 849907797 366124106 50122929 955535567 515140235 545404777 844820332 953178025 504325385 245745287 121558794 519946580 720516611 200926398 822485894 93858053 45657135 467824345 870735541 895166088 644635432 68437601 425345717 916356432 66432659 857396550 778465895 508709507 285252391 161368756 820763898 251469662 287515176 669800965 303449594 932202414 315956081 620059790 828049297 255092513 554811259 331440546 176081392 219346876 552186914 416425279 995412834 904255516 689779405 404892587 976585166 670864963 183512811 117636110 975144409 967376289 321303638 464103964 16583176 845204032 165771828 235072869 992882040 669528255 480568894 278717524 898643781 892632771 122106221 795600128 469865089 902436334 54372801 849814157 323835174 6432596 593829610 227174572 135596920 987494498 729869863 336350360 265933565 617702170 704973666 822133593 750828328 759056163 771697841 539011639 256568272 50099154 237543538 802557824 277300362 902183606 628480173 110727014 208036823 278780888 393385530 535780751 763812588 266435019 376912974 366584400 754278284 702798345 304890679 674748697 509638370 425888509 83848590 15207890 729668091 262945368 660907477 178916540 411814900 128641593 122992412 763071956 558748458 749574686 553786290 611150227 626810721 828209817 843511153 149273289 6026107 479115376 147481325 956182406 873856247 579844923 203139657 181481235 759780949 752665745 977637236 564764799 49567784 130706305 695465004 742441034 196980374 222839484 729101390 602413646 277104570 150046286 30256071 250157678 923898811 168873653 74497423 241539254 591113909 903602798 288838763 126866072 171623320 569914280 917806451 32700490 417615236 428803421 478940261 403319761 299953673 682452168 935127814 260379793 391169425 868251623 3571973 44788687 609533693 445220146 558952632 731685376 562723665 99543868 502932082 376951878 963210940 701742903 554920122 938419806 129933050 855758306 329919512 525230724 7722645 340171787 817784291 353632876 288063051 557178674 36628399 577078940 625372095 89494467 447967860 424768872 811410427 327623797 195407753 210638547 898414256 534825638 840739913 187046582 525776337 537672622 10590668 309675942 416137426 84463952 794412309 905971180 439427907 547969793 128742711 843611761 653788034 355365591 600267366 198203281 982886587 607714775 263005941 173243627 413192656 378389474 737995078 860746475 27681747 160310117 482488312 751140887 221484100 97947414 898971672 192732175 927880527 403989556 869868040 91680742 618120886 836231272 912157248 114774983 991301366 941520319 233217257 940465418 580335834 103019616 717167613 228984369 864207732 718555764 969904623 113749371 787430257 597353553 425304773 870684371 909234299 928193592 367401879 824747765 697729260 873908688 821773781 296705272 783118695 895832313 828806832 322087235 727674272 437386291 282418034 496611463 829395468 775656498 641154996 296656861 153083073 387349982 46641635 132850708 492597186 29539796 886582091 164421852 205730556 930402658 159135825 322125738 566732446 106330829 611672948 915913594 482939027 61067831 298398253 408043021 102025285 821677647 39074984 607770690 839477914 120647946 888983441 599013246 202935636 778072198 150123619 730855282 280245836 28399419 916358115 373066590 38708640 956250866 926816308 253999091 843589126 819793107 354305431 454583121 257071923 509999424 833435419 863081547 854454803 56878666 356741054 765588111 579872738 124819730 276816275 845448503 8768567 698945999 384406595 226941550 98429270 824825257 850142553 519676401 455727154 39999611 950435910 277570462 225422705 838916095 580167671 428097318 928003623 10870179 679943533 719159408 459420722 754116762 226904818 80743206 609321653 765246750 67557150 643552836 663582816 116524193 771362914 848878852 917104997 236447143 311157173 332642488 605447675 542239482 593288706 426240390 23403386 430039533 742310778 468138870 403468005 631629186 26709250 334589730 117489788 282639014 569934468 442742673 466422593 403515642 556604239 887046990 481270495 406015432 203243086 62017781 571342798 774616492 117606168 257697557 67740123 162469556 427870788 929016904 370240993 42791755 596835760 991297481 612633579 982326572 715637683 598270200 428822247 979057085 228666882 633761704 134904074 327159804 610065890 326535927 856790741 183519727 889897599 288287384 68236347 955615812 11477805 13496278 447109932 243646664 404330979 703744480 206774580 601417781 474311837 657004388 924705675 448730373 645849198 851646860 987825692 10730938 686262535 91731697 742988048 584094300 722677114 414263780 857147077 627511 371394285 304085331 851208760 503470112 767333177 334469954 604424113 348422668 330194571 956749455 776780421 750465701 803662721 802866956 776681687 201067626 198452444 260931121 932625245 157780423 972645774 91378583 764497468 850734234 341015663 105984724 526714174 214692208 771543609 442496398 902313811 958155037 981466216 886994191 996925041 621176845 77328410 128890510 196758325 166247782 199548155 840207860 989573763 602952000 87096724 113872028 402203864 904698023 577173076 446658025 979510030 731155187 698922441 730824005 756952789 535290195 698098053 993960016 642351172 573854837 644844172 402896869 460792740 232854928 77436695 92828527 67915951 549457500 724171981 303904555 813180982 88539233 244800634 167977145 17256433 132641157 57897957 618678960 500021537 323186576 912767261 614629853 495914055 131304948 572612696 621608333 657528080 69689624 991737079 166349011 220460102 698789630 111326793 848153669 444845640 68235675 741683499 57841794 103660677 16994280 973341912 164251687 597836523 425279214 472360896 460378528 982667779 205103348 781049321 667758845 991094223 862225023 491212612 796307006 626010014 375077407 718495420 299542546 453242858 839958857 316193478 788230101 883622841 890116374 443648071 918533015 789888345 902694103 943274611 780356536 922512649 495077031 188030268 51930077 370569020 248942369 606094924 545947563 828369470 775781362 578532496 22265129 301747733 264494721 913978120 309382540 326120600 586942587 329378867 483123160 584085748 7929115 137617720 471280006 263625043 622668898 366507028 813053555 470325380 455833153 311908906 835074614 460096411 615101270 861298436 766292631 463067537 660382903 234217573 132869582 212545560 713079225 862723445 499851199 11272411 207515415 488832875 214271210 352594753 624648254 370134001 701334200 396931075 620012956 804763319 384668602 367869567 309250606 877311209 324289043 49674071 933869251 552330178 457550093 554372674 33185984 929023783 914957267 559002956 91324435 320817291 86562688 782568340 990710333 822741758 169165063 88312888 218620101 704256479 555057908 756891787 611936016 135584828 902138779 760014231 103407552 110746875 34863426 585811672 501297153 705961420 272728557 28180925 97302967 895343948 253844729 970872364 401243360 870577553 402877274 705839361 81446446 421270506 402744120 518229854 441811879 198181437 221208463 879557542 636745274 224598141 797339595 477356418 559090425 23515922 338433900 18738139 93868045 145304209 247913747 165364253 712748290 623415332 931135794 586327535 102836481 931634558 962076986 298205060 646316731 708608704 986394421 11916153 608830722 207730544 51222586 959183829 503509945 130913627 666173015 258535134 910417792 105882674 55661121 871117363 6550050 382875321 181196771 320287643 148594458 805743550 658490947 141049386 781932594 528672836 338704840 559647581 999305196 887567547 959837852 180667210 379220721 538434329 780504846 989589616 576735231 408673422 18390410 805878430 303267261 428069631 186603781 397169050 997115539 998343756 189814356 775592507 165965392 5778958 843461598 804286954 905786802 985666331 254602168 962767726 110159461 457717627 771994981 103497495 205202122 30745795 334219768 237024240 7974221 606107159 384199635 995065359 484680214 568786168 994420359 635798857 620583514 500985194 861740414 657324273 98824706 482434364 14078475 644286283 495287337 773022308 482570922 461915227 465750237 67273279 484070278 230116680 484476099 486430239 326097187 156222546 567490672 669040135 836112329 343474024 377116552 916089642 342058367 123756842 196676734 25327071 23887896 762552925 133661996 613767740 541189533 693691794 33895456 906966971 937781322 276513088 276943903 855320677 148937988 667655231 324457078 999641814 960469574 703720236 698819938 563863617 952229835 616030000 128990017 887927259 936718582 524923998 189620342 231037782 75756322 318787652 699905895 73876276 123542251 463312996 114099202 154925567 343724356 972084642 157123099 720469248 620516423 455536119 451081528 405396357 758931389 863194492 644208570 113504420 376223957 887634543 233720915 138835970 324986426 176954576 182533146 743353691 943072789 652674784 922979452 232595344 704916603 492343110 826823458 235008585 117904140 736767645 374832620 342124434 477836957 729719165 357901226 895055688 839600597 954610967 535284616 376658504 395098429 444257560 86062959 688326714 130258980 478248145 863941275 859912686 276032524 247578786 642702591 593211434 270788781 478751999 439877089 672638700 103504688 554985733 607976795 194050953 482578352 230941557 493745428 594499103 975840453 719052577 280376495 335615386 918846299 286019421 526339438 629558858 168606391 752987067 434677715 624031110 664678056 582746091 278061539 533329362 288102515 635537381 716524898 801852861 228247537 697531374 968565010 940384873 19851007 533255275 892975589 533254108 322454600 660055977 453134386 201047034 113241915 744034625 906430032 423436531 254928005 135374019 668041090 451552752 482651432 665153965 518782306 592903150 373869177 246293818 819413966 30799461 596914797 69233304 289622139 666155681 210610299 984273712 889197650 38421952 400507785 497398673 763425084 920393407 252286147 704843609 647082478 992561965 502103136 975684188 706858017 158835045 539231977 534681465 841758051 731977454 47264011 684575674 20544322 486225246 346591807 582908136 636389955 712484581 58419489 606021967 435684331 566917711 751920027 324663873 635476085 872593801 31231994 715332976 84471016 196024054 872097620 802660016 483660761 309198040 211243088 557315138 639073240 625592252 131858469 103265388 928376880 274639009 391109576 617016287 750222696 948291841 436305660 865070699 681074750 173580048 591804842 241971910 60322185 258863326 303491203 292879645 453477166 380846215 846426439 272346961 553791382 837950560 288956639 402430541 839632468 446861877 887103687 251894693 210692562 138689836 163718640 667709647 594967990 516501234 249544942 250336143 838545810 71886506 335490923 774351844 739350411 704551238 654875066 725008173 286555341 625937015 701183015 403501222 740867888 320770177 510457966 459915046 575613651 569893924 121748335 211402633 468821487 283685476 215043480 125552945 597442905 575002272 30289622 687304985 219611509 98876968 90834755 622981354 352455954 526886435 746659378 960754215 443946295 977151275 37457421 339887396 959841749 220153193 151614908 7922813 211596794 932497623 418618639 537550443 577168828 853466092 995441977 937990269 92874981 592673044 436304621 485253763 143867545 751256210 341798834 278951440 387298917 663949146 226984532 781965457 841667871 407652118 231133116 297991327 290577826 514446577 668561814 103901610 153770334 127333150 532631640 493897965 387020935 224354813 61760326 905838606 993152067 123134615 352935273 663413623 150723092 696130489 454674540 346072274 527807617 621429249 527422451 615551585 473667686 946470859 345063436 448363318 927359786 251188442 509569560 964243165 318763645 219787483 773729363 884086670 269679705 888515280 670734545 448961871 585382830 548164984 40768483 854326185 388794935 693368824 58861247 386478798 423842742 340290244 422427112 363759457 108744239 963189241 568786083 789690874 546765176 902519765 737790174 378288408 549109937 691152592 157924425 93084377 110220425 284855785 276781313 472270027 357826910 950971876 69355966 897242747 800180768 856945134 514614901 748067085 647017286 408324643 59971525 463740106 357004808 335776568 579973617 412914593 898898230 257503675 894927383 363491896 618549947 354318267 599553216 982714356 548932872 742574270 737896807 384058155 77358552 663201956 486985883 822483601 322514 174899218 767339037 605487261 735769695 538813078 532169285 476340988 183323987 829993860 551372785 583443906 573094540 331096437 993716491 376495152 261972918 19995389 414967169 942433749 593231160 450318100 114393559 144641566 194536151 788548520 967700419 127758541 498942995 780227991 224486991 826841111 166800553 109219934 495924632 872992022 174080589 480850877 65983433 191867943 654368750 334768815 861999997 219203505 410542357 877134464 104936149 613545856 17547519 413541241 809173256 835649676 693532742 241046314 19035668 792794857 477727003 786220708 428027480 916635069 421345646 509066090 986510721 810652190 636932920 198651053 204997824 777512712 742759063 326589925 454997785 312647007 6494318 569053970 870599387 493499609 548587661 94431733 652620224 260359488 397972777 690071205 364018453 804960875 445847252 250084833 235132472 451327766 587313767 151893836 507278443 781421624 228707379 368458990 137536904 828808527 335138933 433208908 257340873 919523217 909085355 895409558 737044467 602262062 350201263 214048839 526357030 741798610 254397076 193870063 471193742 702409109 208197728 176418002 912843708 139894288 489512048 602584976 952805108 910422790 644631376 511275757 826522787 169403378 106619981 725534915 199941362 976825661 854233655 550170872 221890398 252953029 351560139 107788802 235060123 208534913 340469930 312297231 818001935 887703957 330800550 715689897 712518806 166273000 990039513 942109292 214275179 895065489 506078174 822240115 603527565 688854147 826945280 367451279 359943172 1658836 584331628 126529976 375497660 388058677 131680254 753006037 252514268 23279749 686362229 787265408 640294016 909736080 844306646 866565217 37184969 85358113 820050519 215627946 772687101 836483284 661049749 264256910 114649146 320280068 632485307 134563050 192961370 215335769 61027966 224831913 781061004 984011674 689948903 882123545 408209978 949703110 410357164 116028203 825835371 86615563 244796641 55869321 953604465 480336734 200861226 308993492 13689499 689183237 946451695 845477889 606295614 760613691 273373663 175596210 295053481 954861820 58548892 351903370 393593087 116321222 344627583 178392732 965740999 889362728 718183793 886961308 459995315 387603759 887757023 731587507 249070837 538868250 739635996 246525108 688871378 365932019 515270657 127931926 61472514 711759238 4644135 34121696 459857356 54172884 182886318 164677857 824719277 661201331 656818719 950731738 905073998 139650442 625019940 886161118 924148177 274504099 832887171 75476738 840222694 590837293 40695317 4731592 66074050 703497487 535600568 49642065 564546171 666432573 449498029 982459900 900712448 378844312 486756930 598360190 208899162 326201037 876574354 455993298 913620218 189717472 437011358 689194950 970887223 68647123 723472750 245595160 298646120 504749893 535173758 877924248 203867657 857743117 384501145 518942571 182613448 764879013 2536865 379392712 643224601 981519361 59986874 651241562 492503745 854715294 933425220 451449365 718121464 713631636 54530670 10240162 147623252 880624235 687519650 468168175 199559660 673270455 988256125 204398770 456976017 612901862 712383916 238178652 96527577 487968268 319589395 496703164 97651684 908425097 569214050 410311095 87487959 716307493 993459210 594377637 464149304 571195085 992421272 889145373 123062694 76212048 577089032 357567844 148360342 969836226 508128811 68111294 53824106 163791830 887325047 589715834 387159300 665422953 70297301 843775239 10424604 341209536 631595526 268680859 613452696 87242359 537374775 4646121 147563322 364823055 559420850 602638648 325512303 801080428 116855754 215274284 688369184 575127556 413073509 749303923 361950831 254824206 661213363 102848751 274826817 349320748 172980794 70857904 384362844 879104198 882021048 139054491 850234157 885899275 112406233 992898463 923806164 471183736 697509612 662269896 557454591 838489005 774950023 290342533 226541974 664245462 324638364 668066911 84804829 231863417 900547483 28465781 967716558 700142615 869602251 991276884 422999635 266244372 414437107 57020977 508231193 908954591 982181437 518839275 920113673 426617352 802592977 561488669 730448426 513128319 673177739 224351234 743912923 274793724 463804526 601533167 726745550 581768211 417639486 133773273 53236045 27337702 321360558 366766878 860286013 351225302 8415419 578910434 135910997 180157932 434175230 844988664 887642915 960664839 617849158 765157601 860164408 410026630 353838241 964781017 588988183 531778559 859253664 629430638 494712978 643000261 684222333 141635917 40611534 97510253 713194245 879164062 705366682 843323776 185171235 213412029 710222040 848540174 145227683 695321307 32627975 569387888 864235332 152907474 191555449 797042559 594191990 365355577 204296081 343805001 866409957 585299787 766723006 708514331 466625880 465632796 729149778 72872106 593177770 983258195 572682252 115107990 355540208 458526888 49802761 736797564 200546618 225485464 269049859 244482334 95846785 190405240 9284904 712202177 807661482 156643444 2735662 877981025