5000
340953712 550147568 690335110 198902597 101144716 885251920 681900556 312535461 560897819 613817929 910296274 100060197 258777831 33582489 299080786 728962821 110164873 187038164 278864897 600221158 339647466 99093226 581780946 173242535 438087915 3798507 543244718 709307685 627581937 507588459 495399208 275490594 133426499 173251554 306764924 101087587 298537522 123618925 572536077 517311647 346692509 930031151 348357004 376759084 869434111 368589681 923665583 737726344 310681205 288288227 507020970 839851596 322040383 749266551 423828681 408876332 931869638 658388884 475984254 29530204 322040383 242601378 307139372 509503023 82149770 177618506 86448211 455737802 998152955 740118810 445150061 122721051 659233511 364240882 297553723 142002831 389348604 863357234 144973054 803160225 516465536 110949211 328556047 121524304 633866177 591301590 998113193 654545476 255624033 895102004 129256847 375695357 700863788 163081128 508229230 603010391 532797534 695197526 956129571 891231480 25530308 974097206 580007729 184227330 373055252 638188021 429767602 717327706 616129264 956956636 323958326 209020566 772571899 916330602 582823891 692571834 777043567 197796869 403677369 159127961 362981631 18735928 259929625 520533951 479301362 841336653 693653942 304033047 430140199 544762905 721350389 214626001 918429105 276858390 406555410 60313042 366271575 453263576 12974354 858284965 336147829 33187818 655594561 680858262 130193247 282350466 249832687 494841710 225660688 799842595 615845128 720476818 5082464 801143272 740150432 796114668 984388049 586836803 821354761 850748827 735607790 798427760 972307316 817668334 430480277 470248247 649258300 500784537 411974338 681566720 704164413 825225958 695974183 566066977 480421639 817945475 179352652 321842643 199424299 286418008 955127636 505192617 425649891 82794945 747003189 673775242 76502149 41456492 678879733 970024929 130193247 607385845 880236308 687255083 336181639 949813078 161464352 822265366 259278686 436332799 589555817 811295037 969603936 947572356 296589392 228493945 354556981 796542117 146573614 690073800 76768157 834016274 858257737 256018517 612508804 624561468 506703025 97310168 637591396 459037102 702739393 361601728 607808601 504488106 32755130 306446856 970375188 897242354 588884348 793211182 486422307 89052387 225456007 753526278 164910519 153185069 857050568 45226323 398071993 743297386 209518762 177938450 711494661 967908148 810670399 898691492 78453692 463366106 392069782 65428145 49548823 294503509 795851360 937136080 9957924 884471591 15921622 15835780 546626027 782812770 434399260 102008847 883274830 433091262 202427712 818993356 126709 733873819 476751717 631539884 546334433 978856836 253804649 124894666 416547433 221180291 165928362 676458637 807997829 41322168 307272355 723169065 623378918 288877153 865786005 334322048 576278996 605367644 642785984 742616044 610433058 323724287 420055755 562260977 192582186 507250316 905391094 215656064 804182727 681668964 612392091 6546303 831388579 985547218 387321061 805121736 906274377 326396949 963017653 308770597 769519265 414335578 556588968 115043166 982912948 585515558 656738035 129508328 355699682 691624759 329044404 568436164 511144892 825883256 684773623 115767136 40985790 593108773 373508522 419296162 782886552 24502829 285541293 817733501 635122337 989650960 85077471 372117577 851626005 103158975 688739134 820184564 814505031 603010391 335406117 884714929 161250309 17182477 486731095 899086891 875319426 677103198 145983998 771721738 824838266 150145638 201354185 570025234 109114417 896791415 608189579 555635244 381458529 568232525 491086151 503032446 395656036 113087405 157488918 729236339 184279641 432753261 292443261 180598416 313732538 586836803 920500809 42254768 171378789 463785844 304566575 969092896 488243432 101041312 556088029 983602133 620307577 806245935 558827825 370873539 945399444 288428805 10151312 302656604 813492115 292008773 42163459 486969546 520431707 309769808 371947755 280608944 643700596 671018701 680822769 989847299 149936533 405879972 450755949 583874712 507362358 780809272 66545163 117483897 759879019 512944442 669516403 263168129 910475916 939241094 595525374 15824119 546168873 202270056 511144892 791540525 92019489 951403816 50608113 246827841 425026939 624507104 587774554 272694758 220476022 894591998 466336029 382955832 612923045 307024661 283270408 418567630 553205593 76768157 260257189 888833719 204233858 954041688 730500709 26819963 513705892 794280663 645344187 42163459 354472091 155982590 627581937 657218024 704082479 763610344 654198081 389609117 645733277 807033917 967619211 391677993 498954115 803415525 953657967 949451286 702957689 524208386 853659838 408206356 126904647 166208210 988850424 57419173 811285205 281184405 744446277 846392514 499735981 178869661 102573361 353531903 436191450 778265128 931376032 199219238 893429200 329374703 190145588 738658026 358663417 867627020 616952894 779124215 199424299 170691453 231785940 480731505 14883625 984514740 738507366 964663564 794152530 538758499 817358644 184208082 52074264 894806161 727253996 861074018 899253025 874205066 715059661 66739443 758282942 326580775 938599829 822615466 871220802 325693022 576277716 673322536 555635244 862759061 750653043 985112163 240432615 657521345 178988386 17882678 734235272 760533272 267254638 49836290 353560230 612150797 230094457 187684965 51587490 711385990 991607246 215656064 866618382 658388884 742293626 678031441 358061922 183895796 912561659 712941033 564724216 145520283 843343754 104168619 752508383 385122580 861315667 333473709 54346276 12059194 312538744 466687269 63857021 153185069 94298336 558827825 815176041 508315109 528240714 862104025 446636197 785549468 585226608 502390296 377754516 435816239 884471591 23560755 643700596 973532602 435962648 387934387 519615720 964788559 46203239 809419099 735663853 743746093 57285659 228912311 970442827 890069705 204788666 310681205 594053767 604285488 394309299 529995339 884968321 998999778 207040947 79609705 572074249 986292041 689197101 890355978 765606520 516465536 402001375 358061922 359100495 688412809 54346276 892707918 130522852 227346979 234126380 884845531 749278903 776533253 361034923 357843257 758913013 884282235 603463575 97213112 247456503 294763988 934784780 364829303 18022200 29971926 423591720 444854237 815191517 38913625 582278101 464461701 409891175 884102148 18623896 514889126 163198029 317763900 86707875 587313242 215419347 475376869 151997345 186508745 175907797 696505353 432883108 486488803 677223439 989742948 584386874 743059399 825762069 390975263 496556161 580007729 426985760 600410931 41133673 465465888 902941787 971229378 166292398 229165562 320455806 54297227 198207331 530712317 746628988 591189148 957438454 596344290 912682738 244772522 9957924 796981661 387404981 652794421 272695369 308011708 18623896 394638952 171527053 666813751 45444650 446374842 90973008 859348858 286915730 635122337 358851096 939934950 281893682 584866764 818993356 663102559 774472364 529997496 466519760 920135502 504238547 813788955 804795392 941189887 862163613 203000220 83245973 388810039 489733811 748813492 793678712 971930275 853985657 803037464 327065781 772259265 595634487 2608929 969055046 19316285 465798732 763317584 789167852 962783666 569335073 72876795 952600918 690194127 131037713 511475579 289073499 640698270 190497909 680822769 970497330 767880993 39507185 370426045 408127493 674073308 706834577 880236308 763317584 831340168 205491633 430140199 321386175 172602410 687255083 86198552 940713690 916463555 709459393 453299246 481490319 354267789 294706095 276365428 647879056 493869359 814978457 598046271 432124061 693922048 320455806 637216496 174846907 214306952 92867193 108372919 501260882 909722842 224216042 404116542 131024242 750289944 216347021 964247730 835367855 674959803 121994857 828482181 162311613 272551377 494584087 353701867 154055505 740306964 898141782 647670702 72447304 81886310 622414183 804995447 520181510 199286340 400659062 998734966 810038459 585272698 82024501 51419085 23560755 788228442 775369608 604017382 906798518 96515576 45444650 110319403 354472091 44629284 885193522 853659838 355911103 188803928 566996398 662517871 622896076 361703399 168588323 931908178 944731119 486981650 62869922 794182830 240432615 372671638 352138102 159836864 628482031 883505866 275869797 813756596 859946954 640495291 649017435 928719680 770541380 328627651 782447195 154568604 108826983 559264936 671362186 510414680 882551082 606618619 612708941 810048471 368131685 452011064 268383551 569874355 411680024 861897345 801691883 836550905 496649227 819334749 374752662 788726585 373778473 435211887 684773623 911444914 258410910 44571792 429793249 590052654 617744504 202716618 498631058 691351451 730443199 114450373 311893117 241228740 543443908 388567865 167806967 57121795 796981661 163070656 507390118 338614971 54297227 580554460 39546434 921794760 951803411 700777657 158113476 796860816 384721853 458703045 204091209 378024797 188347506 274649586 575028640 683226903 115868762 707320100 587774554 194987295 407508986 308966000 556742863 981922135 141723948 540900466 342290031 490876 388983677 992856573 889691116 893679989 317339528 605329296 529626586 71654479 148256027 243247398 687662633 656341468 311814205 235063812 979464435 266366547 863582748 648262149 938345434 782886552 133410605 454047422 487879513 413789638 315064287 808136691 726052092 113174000 402256096 433471842 153514779 813788955 640462202 567623690 684783832 498307560 558676511 201507477 581234329 785305385 912923151 668983072 76405609 72460474 345185142 578230392 136210141 538278239 198262440 562283390 849409286 491605133 164386545 52089280 54323018 353785750 507390118 316188498 338971988 145677773 920612916 868704275 569993743 77803985 588884348 921015095 420887891 771423017 802624821 1338339 220208169 309769808 279743842 905619655 848947539 773952141 98540820 236754730 734909000 866618421 883671390 834048611 807033917 881367385 537352929 815251633 570025234 584639909 119248032 631991497 998734966 324804613 606618619 862384695 612567908 451379986 974551156 130246332 970280281 933817761 253599245 578519679 231943789 413408254 844756535 820199017 653157797 420887891 264603535 783377311 743678248 520682658 90136874 250119561 145292274 789081923 44759497 337334497 208048413 866717053 605000310 26360196 522392849 972437470 657539436 159331058 312461279 235179790 166292398 503225001 93065240 13714025 50608113 998152955 604285488 402826812 604712930 892229922 36807902 375905630 319648515 699414638 481919750 98574732 628839303 903844541 653157797 312110842 573575633 202193938 560889001 562156166 574801864 928466580 212727837 39507185 810615122 455837261 298691695 843038613 419195196 409531071 762862542 936916894 1862766 394638952 645240337 769078639 289127187 817733501 823273032 72810672 187403003 138735536 748748945 503914742 484122427 796114668 280844570 233253202 996950798 760086985 852729703 961959123 701966750 478921925 17077653 926766377 336181639 613045717 710144441 48631299 374716153 331957522 538737567 966149988 949451286 368494866 548517667 885193522 713667748 697325906 540880397 304033047 763353202 462254025 766519801 404789924 478106866 565906731 229776214 342215047 843935219 971626296 190132813 900327428 85077471 572663 742721245 219934100 809419099 9868707 711494661 46643772 502314344 681900556 600846489 181972308 490019617 463377066 666814281 871740539 707815468 727796632 49725035 338786671 268432268 407140551 74700541 559237720 411264062 691311571 707808104 53724041 678433606 287904428 822453817 289075968 743746093 585399516 915459883 31480949 779197801 479587508 897279181 284389238 518086496 861897345 483835572 67369097 241805698 969092896 922443956 718596071 710391737 750038912 69038212 890353418 686384557 889407433 430063360 585464545 332159530 479587508 122820191 895686059 251516458 134266350 674216148 764889387 217300877 704082479 674583740 27595338 29530204 38281957 567109943 870054043 841645266 534990125 805121736 227216975 430728537 84100788 722339369 49444988 443708857 984432286 134338447 96565846 259747419 72876795 962276737 605000310 248259559 770666975 774545830 1029028 213270453 490364116 753227077 77803985 365121301 766560635 425464904 516750035 488142617 207365777 15824119 32701752 110319403 325754842 606681403 807371941 653953006 454675033 416508737 179352652 51464219 257125752 50498140 541415340 882269195 181464461 929606321 166304030 755027443 483941734 832115323 734988096 63399553 991284308 750493804 241565663 379520109 974097206 925665831 487317753 943975240 445710124 235093277 680765506 898141782 910456285 922823988 721938450 864494621 956431012 863040359 559937802 741034697 362786778 574760333 737726344 786674947 421297208 631875638 9816420 30624 762481945 542883437 823141914 582429698 904750207 716350083 465798732 662040755 923470725 137328937 251910221 506279687 304185060 900724107 243152822 766367850 284143189 393682775 579342884 264022175 70389901 953758217 321746706 272641356 743059399 521207407 167356482 78797543 106909770 283529495 866208204 534553809 742199093 87643485 465974712 202849103 413785840 397264555 452619697 710783168 155418409 189756003 175480054 480061366 548806285 492693619 553780967 937988905 169052851 442695878 46413858 181459405 30287700 927274256 275908147 573803153 711164302 294067402 957502051 573803153 820121446 312110842 210618170 895718509 548210157 388783567 582593866 760433620 649889153 355860290 145397495 824999417 278615602 361984616 64714146 755753507 956431012 435937566 498853541 592723611 432256615 111540875 98842637 175860002 794074966 510388998 285803096 628853484 370218806 229884278 888309644 195006355 629484975 578421130 933228641 382955832 712866343 172268385 171216160 461807388 65205946 853736453 765733601 299080786 30801155 925978261 557374263 660999834 128898045 332158157 64538506 76502149 86763454 626271583 898868598 717063708 503579895 986302021 230652726 766560635 692452086 57371595 5182251 848942768 98842637 667885407 485534587 521428379 543120515 271614648 172478928 685203259 129077066 643383489 37419433 428751871 664021487 197900473 455349918 266342912 632781110 665554067 880715019 297045559 275552941 255209512 110202054 47360958 811295037 901431003 222314010 985544914 27490549 445710124 56788900 188765407 627424079 72447304 98574732 556377916 304861797 503756572 523794076 860554010 769406989 429216595 236754730 548038454 166206298 359304952 952586194 393073170 357057570 870314359 639272947 388871426 122721051 151289773 919219849 39303464 703594360 458814991 330952427 644724759 670847109 159696132 607743520 586577403 902339233 857937052 106891181 360876078 219750801 784956598 432256615 634493647 576125808 44629284 419296162 166930651 871922062 755911937 386735571 228417769 397303247 94481594 578421130 879468961 316188498 916829861 20767688 457123782 921441916 783964997 768643036 129420132 700777657 372234099 742660674 686467536 607159128 237639372 46193346 730499807 297226961 732533181 871220802 696663771 793758419 63019913 224847728 742199093 225433101 637216496 116458824 261293188 116444925 319562624 860554010 319705111 908291929 742616044 824999417 877943893 232286794 604712930 761686161 797894578 221180291 130669383 57402164 494841710 486961266 852698764 15223592 520977447 900996650 111028169 964663564 932528716 5176700 388877081 776729895 163081128 867627020 811615745 504488106 541387677 133426499 826101409 283289966 733702529 157406284 637473391 542076257 489971809 575786872 814626113 104966975 219935988 220649502 857084705 210689695 872909652 993272795 139235621 548167502 460575939 441179358 914510389 865974287 999183163 648262149 488123915 995734442 873232494 320990900 17676457 753396141 447159015 995228728 91757123 798865369 274642567 377814079 661949817 303247098 746940243 737156999 265543992 8457756 137701751 952821901 354267789 866208204 57371595 926148417 846509506 975027613 242723411 707839672 734305593 757453863 774472364 529996514 553205593 125276804 44875237 766579709 751099493 590640054 818637056 350094499 187403003 964453544 560108621 162397452 666982845 605367644 251569556 989352384 112552839 41867108 175092871 138441982 932192047 817295332 587885309 45937423 924388087 280362068 41456492 588259231 71859412 736525325 317908677 562156166 142416377 16717923 79057406 781044973 315543662 275338366 379705506 28695883 989847299 5182251 764020431 618742366 630825144 674216148 735749803 872321966 948442143 214804196 40039330 498531645 550365619 548538368 57311248 822933559 885069094 439132846 556472386 251516458 858284965 332118429 178872985 797792936 644985063 236501020 853682036 916799337 323202799 978958423 505590295 302532816 677441412 405823454 459750011 716355619 619348349 103158975 664021487 822615466 905489698 483157267 499318416 444567457 836550905 670886045 738590551 18370514 394260604 83193646 884282235 250931621 673062414 116444925 991218001 712941033 556088029 849304711 236301451 156825568 538505847 923470725 497675815 209181530 841770340 631326065 847232048 145520283 462567021 898492652 596857292 210191111 736381993 625161545 119820312 865974287 844172237 733536462 255126079 715812325 313896063 793500010 613045717 816371558 363379469 940030316 904609958 440654411 863529765 476030253 600613044 674959803 441583289 447936263 690056534 706530843 301566213 23218498 514889126 749155028 443708857 158182553 678778596 661283605 807917051 617420901 402321718 400940807 724636852 552283585 502390296 774704684 985452479 722581663 230734247 516495731 844240323 613035362 898431512 698553617 48397192 99225148 161941062 224677515 358851096 637408150 212713198 184219733 130223919 239880340 544051220 278282060 883976603 292582353 495399208 794280663 462764591 906246058 16842269 287670176 395987606 467958750 171395898 538038277 621175258 942676061 932260233 475262519 54128623 231877488 818061465 948562171 854169481 615274089 418622896 453263576 402001375 947572356 498631058 297553723 361086507 282619641 617398347 96515576 28208754 283599042 883126506 415722135 143886404 691351451 498621356 507362358 681906456 391267749 212388306 368848127 867829320 625091364 516682827 933165891 44771242 715520199 953655462 862384695 825734162 7987242 118106296 555776449 507053950 825369450 352687044 609818179 391267749 906109214 839236164 299985383 98984432 488382429 938677072 454863148 166116296 634493647 715619899 9556551 565684353 169407336 808136691 8576622 750289944 10946013 794432058 666207284 60056008 124078489 861509148 169271141 227575600 254629137 112552839 405724118 190384026 10887137 32729541 924861652 877760948 144085246 35952925 418081837 338820179 628225222 651506880 6745660 419375036 140301945 67562811 560889001 820422117 720225296 23876078 357208152 8416955 344655557 922443956 214990519 306825757 891349707 53208498 616380674 773952141 226498523 684081233 367096924 294744797 80866368 575264967 574760333 410212573 937988905 941064321 892950751 645018942 18189469 650495323 295146407 298691695 809658399 27595338 502314344 673028549 799741733 342553190 778007175 849491316 556614794 238712763 536496510 19573067 623988222 548813585 486961266 929221138 83290908 425285184 158602670 573304345 774293684 171395898 331591252 147770081 33187818 6649154 332270038 953752384 515958825 837215065 239611310 689943696 464354695 150902689 789081923 423828681 381374709 213431760 63442031 345185142 883976603 193753803 657927415 573306043 343944770 425464904 45486506 676594391 269012930 875736447 349575980 629884358 437673282 934784780 624797095 74724846 836031221 246278558 384611151 241439357 49525060 10887137 619180150 124612698 655770000 902339233 920556457 745306989 920425933 50070839 746773617 616022514 609819407 166742834 917583893 387266202 504575438 32572235 340573789 226498523 705663383 238712763 846378517 106524209 471945921 679808514 85230796 558676511 341702021 131024242 490603882 762345919 655704846 75591208 567246575 672439872 873393776 439272822 714374325 224216042 918076957 294078487 360765218 50042952 278917295 716681433 674073308 598403141 968186049 909722842 723935138 633868990 342949018 440540628 324280797 459037102 511993470 986222544 61846862 849409286 992843759 843211500 890238310 755911937 174179800 257478537 63823914 37071530 727595610 915244378 76405609 208820232 596865300 280362068 948916069 472349605 150236165 976041655 488283819 190384026 439280673 236894894 768046239 135262334 925635330 216918964 287791009 313732538 146578295 354705786 533604050 686191674 85257385 803774165 681906456 99266733 938549028 236301451 631539884 805916055 936016195 973055889 738662820 796646731 19351635 106918567 680837376 13373765 908514173 849419257 799908262 717102285 162256647 331957522 245991331 358663417 317906784 133628051 665554067 127276547 520232702 67372034 582981339 349222226 720910497 869837683 613817929 238432175 263274967 301620685 695171604 172494984 46319674 925553559 751099493 317339528 426041975 365993603 712155257 994412044 50506344 577575932 23695550 278130680 718273776 388362102 155777888 382588736 288428805 668357273 67279768 57453451 620518611 304034992 825860287 548038454 89214511 495513173 517108285 996230356 284409908 423591720 553351597 892310252 896650813 979345374 44465418 973777842 103304428 800335749 438566087 439147583 584543156 872466820 755092775 712456107 267143796 839851596 352138102 423924319 503445450 634576820 344944866 667564716 227411377 905903509 577696598 549611943 906532407 901087605 542194464 490019617 299324676 904677 316166315 816127073 944613126 816523418 693828644 710783168 84100788 789337091 41581256 193985176 576478431 154055505 423194919 498352519 843203789 754008074 832778413 715520199 861509148 819795197 731076963 36069182 753405406 235093277 342390348 220136920 9194547 149192565 64618805 489757094 524208386 743578117 897683671 295584930 885985193 165554405 763353202 63823914 822633398 748699287 910605509 673028549 820254304 116536600 188803928 163926479 796542117 94171267 321337795 239463413 661504509 179930137 62513912 21160715 446591975 903787651 439888204 989494026 683779641 73588088 301247559 194987295 947413726 834992544 408910634 663102559 119249751 907217837 947314190 142223390 895686059 897097486 98810037 141661031 885069094 447159015 459099073 827074840 854448802 142051183 925665831 603463575 627424079 203811623 79487647 591799297 408910634 603734066 412669022 957969822 646328429 466657460 412859070 310092655 827074840 624416092 150946239 547468978 49739334 709307685 852719173 865565600 117473790 986917728 114025893 402803161 763041274 35774457 979446463 7987242 757404596 295146407 247366772 858013928 759872340 35774457 531816571 893409051 182278184 885251920 9556551 727198440 681582883 576316973 678501962 738899022 497068141 761686161 357057570 86526115 521009540 802476184 758744931 306780698 894461081 633866177 428675774 471240519 319424469 499097591 157540190 825893458 764097943 782447195 910762536 271614648 23218498 618981978 918914371 544762905 888005014 228384360 639753564 735200626 492814028 223032783 868704275 229068299 227193057 693922048 910456285 193724188 429612637 235063812 510414680 315834921 540973782 82098610 206696920 703948376 118300223 112095981 24051319 925978261 766276164 675221648 51587490 946123803 731918413 596003639 766276164 398995412 55785090 2837173 496556161 752610191 404116542 85574249 100753368 812401002 774704684 40386626 107389355 214909128 909983291 283270408 821830143 951015623 46939289 97411693 74448052 490364116 891486926 232336130 880295244 335024665 697355368 677220105 268192877 676896863 542883437 829577428 98810037 181690061 444092919 778204165 313996452 910179280 422597538 65205946 32755130 484887128 745551892 947128217 284346073 271454194 984514740 952156783 642608709 815176041 668027001 210191111 44085305 514401194 117428799 243152822 432506844 497675815 677441412 229670980 212289722 382857798 727253996 753526278 155966843 707815468 613243286 896554481 345644838 415402716 500505734 805501602 174710066 186263518 171216160 156394736 722688601 231221995 665612136 862759061 768046239 472404490 219767654 631226564 697762066 814148213 713986739 906246058 230739192 642033222 924442124 490603010 277568249 304515412 105755261 698248651 295270470 810357431 93792966 733257640 582969963 66545163 507588459 986846118 50708022 106340995 784956598 24807398 306825757 59976920 852729703 869634976 782812770 974549667 476250198 121286306 776172825 617744504 181464461 540449511 59281153 823273032 551398453 573955492 572867222 798220609 297814780 866545300 114392586 262955110 915268316 734891170 286816871 416080816 349138775 783093588 390309869 857831269 463136948 627211757 814505031 332393902 933228641 474991558 505026364 356346004 348012691 240954021 104966975 709459393 5176700 478106866 559237720 612923045 36807902 983165133 762290983 579368285 670722011 826628352 594053767 354604538 788726585 617706908 23361553 479536607 99778147 420798041 996153400 755231849 92593381 656780100 829474788 750493804 145698078 269012930 953752384 193284306 817918645 248155677 157967599 270204565 548806285 261709739 728364045 512548379 227160374 666719050 307272355 673322536 81553374 630925758 424993053 644972113 989494026 843211500 644678464 231597464 746773617 772820414 962276737 441179358 683929394 119820312 592723611 317908677 317854135 538642594 810122218 980764371 865343729 175480054 501260882 596568971 532013618 478191747 453666515 680482810 518134700 874186756 756212025 291860395 721938450 793018734 758292760 217333216 237952903 587056887 36975243 313046536 822471902 518312349 981922135 647073402 54317738 338820179 609818495 613605953 328288048 223864825 819979717 690073800 275205598 260038712 799498103 523421518 349104197 795851360 431759341 276639107 232649954 727851380 964682812 156825568 597917899 49016262 289075968 303527904 342290031 326259781 955322320 238432175 289454155 527702953 958368434 217133109 251774488 994970024 174710066 81762437 817918645 977867830 504757644 547468978 600577890 16062425 617398347 806647387 641724557 762242440 760762428 315543662 549781332 78797543 289127187 500880783 104576793 204788666 214909128 750769680 820288497 617386415 709614974 827111128 940708010 381458529 734904825 55251426 771967124 753078431 764107766 894356426 212713198 868720795 303991118 543982435 30189537 826628352 53276977 385094657 994412044 731408897 518170640 414170168 800931996 64594226 540900466 72399745 371715111 173242535 836178650 860767573 945822440 256807589 867527962 506498167 337698630 265434364 966841582 922582347 871037515 181234581 797792936 775790550 209497645 553780967 340744906 500784537 582593866 239955907 534552385 988129531 122216284 6377694 476396405 158373717 855471099 653953006 752845811 940030316 174792844 348012691 864914693 254948165 562330667 600807490 491291374 217300877 83921157 674386696 382555348 657378904 323202799 779457706 109059941 553848348 902941787 165107137 987330739 493012850 239880340 659222711 972307316 425905612 744361017 204729784 544051220 478362875 52355725 210618170 556953623 232902146 397951346 478837141 309389345 591409074 628482031 993275324 283689644 823032501 563216653 2837173 442985707 823537234 783093588 302532816 210438322 962416574 302264908 865343729 908019576 973532602 514401194 974642191 121524304 10946013 337698630 983182768 399865471 618415260 46667598 505026364 504834303 684856839 907200917 488474395 235233552 382588736 718596071 175860002 321386175 540370317 40985790 828915431 520220275 214516346 332270038 527270122 680309542 529649052 193349690 194350554 227328057 800612885 132850790 412669022 995237021 193284306 123099909 136078384 439589266 181323671 221092804 443756625 476250198 393244028 187038164 669635411 4671914 380177538 587056887 134266350 842859831 900323536 578518943 930340554 44771242 985452479 839923398 918303314 50042952 416508737 859946954 803046139 25788982 425951788 555776449 318570606 633312369 505736005 50765208 732501762 271141010 762345919 476904894 917847417 243249833 349222226 33582489 115691761 161613356 122820191 824378232 968922615 576277716 157540190 177565404 556439020 113174000 223032783 584386874 38913625 27490549 196325551 472801212 530668481 732368455 112363796 1645850 465650792 176897652 834563701 594901977 140368590 639516277 680432286 261709739 476456150 684990034 162768028 329905177 572160423 297946972 411186694 888833719 487457018 832206499 138735536 227328057 390309869 16359697 744812012 966412887 778489835 10237175 236297517 86448211 172268385 968245309 291597564 435962648 836055215 503083146 490523312 443909572 3339376 722978664 546168873 239611310 693086504 127303391 310997821 876361848 162521069 807997829 879305994 847393957 981306977 155548313 365676379 196230848 328553183 463955376 56986528 298344306 520682658 643267719 483647807 213270453 290637767 870054043 399865471 432298954 651506880 194417023 644749693 223235910 746940243 328556047 192582186 524240680 316406142 231597464 443599389 190337363 151289773 529754581 132016454 686467536 188086895 3852634 229884278 449448616 442695878 229964578 789018769 295267523 775566903 854448802 983698787 360765218 438242994 930951655 977688450 47360958 32972397 502783517 681179255 473864491 188769057 72460474 432327434 418155316 977688450 453070931 329962021 423924319 8695253 260310884 173251554 528959721 126217774 117893526 434902571 630293038 534546595 817945475 924388087 816523418 251003816 652218386 262778860 528959721 396182061 283599042 925080897 167898750 180190869 722368722 69210080 208048413 550147568 221699743 362786778 611754734 752569409 131139834 590975409 991376906 816599160 928549559 515705138 369522571 491833136 672199402 737680407 861307123 484122427 331924841 365561118 874215403 333473709 943137053 2496866 835058053 880715019 469960642 50304827 939574905 220628337 307496603 558160970 355868669 140029453 660188183 595140257 191260334 349138775 379882787 681582883 430727183 343224963 715059661 84455615 348357004 345232231 936916894 178363601 839164869 68512609 426608862 970375188 242131724 773250799 447680508 832552708 49725035 500505734 898149548 109178443 384193084 261639916 582981339 35592775 557204524 920260415 905419680 561547556 372535687 634398542 969055046 810723948 9098968 563821073 695197526 591020598 878699395 793091449 802476184 970442827 454047422 814148213 238477836 668519094 383890265 915244378 668027001 974642191 924543063 666992212 384327061 358905246 723935138 33929479 316880794 227216975 517311647 429767602 39303464 599344933 720476818 452011064 963154351 201736170 549998814 763041274 507053950 920556457 920500809 40039330 96954477 667500762 666813751 553914221 727069095 891231480 516495731 267143796 546691855 500008489 820288497 469860721 231785940 750193869 573431773 240954021 123515542 311893117 19415319 781725248 231699426 651421240 59976920 282462741 273679131 595140257 135934535 872909652 585515558 995237021 835367855 405856841 538038277 755925887 462567021 736381993 864494621 262571851 430630639 732080567 851626005 281373173 210819404 255126079 449478890 10128688 743396432 367140533 305260293 50708022 124077528 193007205 552837487 465974712 512465969 4068928 515958825 945303963 209020566 269672920 451981967 832652111 394808968 387934387 817358644 759879019 72335463 586526838 680095215 627963588 946556288 93674778 640234426 522231127 326236683 217063070 171866517 212289219 8457756 979446463 238812459 504913924 591799297 547654412 561446542 403630739 19742482 803682594 781044973 436071681 82327609 395667340 593108773 162397452 213831088 402250709 823032501 91066108 585101458 429793249 722368722 732080567 377173974 601142288 334850361 403246898 698385308 906800058 998333029 914362183 565831640 636937811 853545593 507020970 741018348 588855617 397264555 726596442 862121952 466519760 699582269 475475276 656846058 417007197 824851088 395656036 129264207 693617831 87226643 981392313 575028640 133203926 767976339 997730283 125303981 402179223 726687416 33793466 962458943 305260293 395446342 690854693 360079874 413046924 929937146 111057002 332223929 534552385 120269850 603079557 130669383 478082792 706530843 993571815 970427696 677423464 118091308 517687789 778204165 932772262 754652798 373169273 335195110 111540875 699270433 760363389 884845531 116381851 648996783 857774066 611835833 452088869 931004790 405823454 623816195 732067081 549553537 203000220 162521069 35245369 755744522 488142617 253599245 88109457 98118264 650495323 148002607 144835298 746346297 966412887 387017575 910645562 547536066 976266357 294078487 311814205 166930651 925859178 672976710 894806161 930589733 165218145 811847980 166304030 783195676 107073150 177938450 848503454 325693022 585466398 354705786 21826455 363315545 985589151 249262909 841770340 133712911 731349700 858746734 847757603 517415632 930031151 746361228 699790856 995134056 316334734 684909974 163198029 170450156 696663771 498621356 618030914 667500762 509863500 527774547 803037464 255209512 568232525 229776214 11462718 857273630 400153689 720826659 236894894 488990071 50070839 85883697 788228442 390429789 271192865 936958358 304233463 253232056 488505029 779009554 578518943 600445224 12987804 488505029 790506681 666982845 108372919 458703045 229670980 888309644 354329202 595993633 581144868 544706229 842114381 148134375 614611081 124078489 883274830 395416226 450815699 686495139 30801155 286775289 156661040 172151090 604933556 896791415 826937298 496649227 10802946 278836576 478034187 966149988 784174420 229472499 385122580 754652798 83837224 344732934 781725248 721836017 570738912 751950530 585101458 127924215 677707431 134584222 169271141 111057002 332223929 508390385 467958750 907049543 920958716 753405406 217333216 502783517 816599160 695325727 406263700 380676844 107342882 354556981 354050280 11390004 998333029 8524806 104902094 614611081 136336561 239955907 891408251 623378918 580500124 892262941 272872066 678879733 372639030 892494404 226087619 372117577 786084025 456340839 425285184 225660688 725826543 857713492 306860145 727796632 838240780 997822567 3102825 836214108 793732003 450156857 823915922 199476392 900323536 914906820 647894280 995838821 5370654 599344933 306446856 654946515 644035358 743396432 441947243 457986239 785257291 527193452 937357889 45486506 90973008 563821073 100469994 879180038 294174167 706401667 459750011 991216087 550832710 854025132 526739640 324798505 98118264 534546595 942727827 425905612 676896863 955214115 824265634 496855987 430692564 29845911 954634338 31480949 717102285 184219733 527054954 286775289 860822007 600613044 403630739 983182768 209518762 476989029 393204009 695085503 283090616 872010391 140347955 214990519 950469883 295584930 713573043 871320549 725506704 142051183 596003639 707990975 832580557 654352301 668163086 640495291 85308931 914609797 303192182 282619641 847374266 590975409 689943696 439896698 161748887 680552699 740427854 135951656 497170990 303542899 909754226 681103119 898157051 41846591 799613305 807717240 849218566 794014457 105312203 1645850 926766377 674583740 99079148 923895587 754085067 906403323 978466078 852523304 435937566 393682775 936016195 956717024 704006837 931908178 511411633 578650357 462760797 527193452 938345434 696505353 451955219 79842756 72335463 894071108 494952026 472669222 630991511 339151843 686191674 694116522 969505919 349308875 476618481 297866958 714374325 633663001 983892558 722239947 256724658 732368455 26819963 537858010 87015251 797956387 886681434 215109520 384327061 492472429 216037668 276915559 909112544 127437101 117473790 225385781 901005745 749155028 252936623 796646731 928576452 684102988 331705283 418131419 662572929 591076156 590370077 415254458 232649954 298478363 996229897 189115013 165554405 425951788 40489476 636937811 722821815 903566575 517677572 429428009 317763900 67279768 874215403 92606879 585430481 182996688 676542862 977655535 745274157 922966386 329451569 680837376 388433031 685811678 784091032 322416832 861307123 19742482 561520703 438979947 987946025 117438503 255838435 252646876 807917051 291411136 958209379 12974354 957502051 986187930 810048471 485790821 439002727 129508328 553848348 32264333 217228114 271141010 803058812 148134375 644035358 830374819 826403272 212388306 486731095 261859036 898868598 175707396 257892594 870497551 824378232 292582353 644678464 826292533 889550939 584639909 296589392 537858010 645952287 304537668 453258663 739008041 732812505 402803161 366978211 426338239 339931564 918914371 664942347 823200165 754008074 121993265 645733277 718905614 701471955 296647545 585627 124077528 530227471 730455208 83815277 298537522 185783334 199308155 107073150 757361048 307306302 126904647 581223380 584866764 897932572 21533038 813756596 931004790 627224327 382431038 600410931 533604050 960952420 910925409 486488803 372535687 283529495 411264062 13373765 453426664 218046226 715515960 579365633 566312917 893429200 632165643 963017653 837114629 158373717 801143272 720826659 430692564 101144716 426985760 321096564 236455403 179574548 29845911 985547218 280322124 370794566 250931621 907175560 379743181 316166315 104168619 577779060 692571834 418081837 894591998 200057285 20913964 944936485 111638391 55981602 976266357 705354344 939239855 511621421 57285659 369907407 957969822 884639330 592317715 525403027 910925409 225433101 868399877 400679336 711164302 498307560 953655462 971496567 491086151 472884494 374669101 511977425 34635769 935389955 315139174 449448616 925060156 169126678 793500010 699582269 749436331 454675033 600445224 182996688 607576915 439522679 749436331 455349918 871320549 246353384 922582347 179692066 978693877 817796507 332159530 181972308 951803411 595525374 243190542 945399444 439147583 221699743 118300223 837215065 261613645 447384666 796860816 691311571 459149492 208610080 752610191 854169481 762275007 853605086 172151090 555627909 829382738 894234502 695566274 915459883 365676379 55251426 596568971 290077766 429216595 390829250 866545300 607385845 352687044 328627651 822471902 906607888 817571886 916615348 662775036 382046562 654352301 251569556 521428379 873880473 653843642 659222711 133274179 195006355 490876 343944770 800612885 771721738 87397464 508390385 118802657 324652929 79842756 819610746 612559434 759128624 392655913 954914327 872242539 453270150 310564131 983698787 787686402 935566459 327070966 868898467 546626027 556614794 751950530 213654852 932744339 744053395 334111686 804182727 673189965 35261050 720098097 548538368 682639332 833429653 86198552 435482955 812401002 290077766 419988658 619910832 900327428 831061636 931869638 161867431 478550604 939460432 969189838 936460233 293543562 618376420 425001419 531865131 442991342 68248516 988294945 857713492 206379318 254464177 868525305 421878456 348116702 263168129 136078384 473037634 632601729 21533038 753078431 447493269 462708960 205212184 960952420 710305663 756103206 700407845 308966000 967086474 692078051 272840907 908514173 720538524 62561539 278836576 728863182 984432286 120055467 32729541 695868542 449478890 875422882 732067081 427162482 50498140 459417229 25788982 813492115 765804401 780159805 466272998 601142288 244088962 821354761 622896076 508588097 805205480 14388398 184227330 910541252 674294566 24081960 521271959 463955376 622414183 377800882 147751926 979402922 68438867 418483640 631326065 622263533 331314201 486376294 76369632 45853172 265825934 855498060 586526838 390829250 910762536 813253113 104902094 175482771 173829308 261613645 929504192 170747025 532658750 583685255 362392448 585162272 576125808 658395708 614767210 329593037 821830143 977867830 538642594 981852719 778265128 342158385 16359697 419375036 591409074 939241094 486981650 361603795 508588097 948442143 49246631 794581817 691166253 792500908 577575932 372880390 952407032 799842595 227969092 174943461 46319674 422431244 154877563 408587456 38877824 384415765 594901977 870334042 401607752 449657644 485965178 962967991 612199954 245690031 646328429 634398542 885985193 778428675 251774488 973777842 874202772 892970462 219762545 47560643 585466398 266274608 446591975 751639063 76369632 327507820 593007555 6377694 260829471 296647545 549620840 432753261 69608498 736175759 460575939 416966051 84455615 997822567 728863182 189880833 223354078 545515966 131354286 170780682 559944891 722339369 456340839 485965178 461858206 450577724 149902644 705663383 575280747 392069782 220751728 942140796 838532927 6056016 904100320 283626601 848503454 605585252 269147056 467717931 407818849 695085503 824838266 745274157 730455208 453666515 800827008 650719159 338906592 555081370 598584408 123080256 961902872 794390600 10237175 795907287 786442254 860657719 961192048 573955492 793091449 248096662 836469436 700689785 851553645 435816239 157810774 254948165 779794994 834563701 736525325 705501509 334111686 993275324 204190320 45226323 986917728 854196215 763189926 924543063 611787524 971099872 480731505 374533413 503225001 139171942 846875588 826894504 572536077 776533253 492472429 174269209 189926850 148256027 388810039 556742863 825225958 466913150 496855987 783042478 997730283 336986275 773250799 838240780 676542862 718969017 278282060 110202054 665347276 529626586 137328937 283031268 878621606 679808514 957438454 762996581 203204802 882740941 776736390 115691761 398851181 161748887 265496907 213831088 899451488 225163585 415254458 605487697 239463413 711211879 923665583 851553645 760762428 382857798 186743904 166032623 256970252 621666012 864656388 49125108 446374842 727069095 517677572 361860585 402826812 79487647 589868168 990031127 166206298 163075787 261639916 374669101 326259781 488149263 917583893 673110687 504878675 310997821 416547433 824216821 519615720 680994470 276858390 355713734 178374772 374561937 287353968 393244028 836469436 386937263 100469994 451661865 6920047 185974186 636960051 873714900 448564296 369041155 39546434 82063300 440654411 725783379 802567794 383286418 386937572 173796761 481428047 784113556 159696132 133203926 35261050 733702529 582889690 504238547 916829861 175092871 354050280 966957102 312446070 430630639 66234788 523955495 543219206 882551082 939460432 237493098 595825734 402250709 518134700 220208169 109059941 251244596 7622902 95242454 582429698 157967599 623148175 355699682 271696011 807717240 892262941 604017382 544706229 217228114 253967662 150173069 316677790 346489055 556377916 48440334 323568583 901005745 221538632 313896063 936958358 323711733 518255233 892707918 1862766 866196387 930541273 111638391 799840456 673555414 738658026 644985063 148272459 798427760 313046536 620518611 638188021 827529982 150516083 701921810 849218566 458980593 458975713 315449150 516682827 64538506 633609539 327065781 755092775 268452242 384415765 995228728 513899027 878699395 56079768 175907797 49402662 16224722 904197191 947413726 47671284 84830738 918766332 31135951 546334433 703594360 250436970 374752662 374531225 952156783 841645266 823537234 924442124 166208210 354329202 295596610 466272998 875090902 991216087 577779060 684990034 945901900 421297208 432327434 33926210 256064828 515367275 674551997 141922582 506703025 984185158 551408565 249904324 795439930 630825144 785146305 38598246 227267062 946591429 248259559 499568189 443497188 595187840 165312087 863840294 102901656 509291540 900996650 193753803 16300919 12032504 111695942 943715020 241184441 807371941 758473531 61471231 774293684 377730808 530003530 103168867 129264207 490603010 650641719 156158386 33926210 101041312 413046924 146573614 502192036 760433620 384864579 581234329 689600130 553836527 156661040 433478826 769406145 79609705 115868762 625993634 973113110 111028169 488382429 118544381 663753982 279791726 485204337 480762763 344570565 101087587 464277260 480421639 923849168 813624815 880295244 1385700 686384557 232286794 432043279 639272947 16571694 876121320 481919750 44875237 575508257 805237240 537352929 822884694 315064287 109114417 906403323 99913684 470548099 269672920 106952380 814664035 208418100 789093497 695566274 184727112 372234099 270625804 722581663 164910519 288763807 213654852 981392313 494115676 425906759 700388706 909304499 228417769 662775036 695199794 856602547 382170439 224677515 248155677 969766932 566302026 275552941 969364540 227160374 304233463 932772262 898157051 22629754 276637350 730500709 256415902 813040339 972437470 612708941 67369097 479045280 107284901 633868990 227346979 225817079 673110687 464741382 449657644 233688549 82794945 69857960 746581658 55785090 392740278 488123915 804995447 530227471 144973054 825893458 92867193 749278903 66739443 665612136 364363833 331314201 632781110 64618805 699414638 281184405 500404433 386531832 548167502 962416574 959485061 862786051 410999725 129420132 44465418 562549528 934774787 707864931 660481121 960529727 99913684 166032623 853545593 75490900 597917899 358341221 301886541 665756036 294763988 333716122 142348575 746581658 85883697 383286418 664109861 626271583 307497728 833562139 747413691 117473949 402321718 904609958 434232915 898691492 229068299 296972940 792655374 733958212 121286306 890355978 921625213 706663244 275490594 350094499 637591396 595825734 890238310 398071993 114450373 847487066 181234581 953883384 287526791 748813492 500008489 606398000 738590551 786884924 220751728 562330667 513798137 908019576 59729100 961499670 870005633 10151312 600127435 192800702 775790550 190337363 915496859 645597429 832432347 106909770 572074249 172494984 251244596 295405709 671362186 180653476 691197695 384611151 565921919 367363940 220136920 530171270 483601025 715515960 381374709 793018734 939239855 906221250 818488850 168121501 764930479 753340057 534636624 907007326 842977873 161414868 445931904 969364540 900450806 498758682 642608709 326565622 382046562 483402124 973189590 973055889 504972331 310851029 93674778 207713361 753227077 120162719 731515998 316406142 159836864 187707893 120162719 741372985 815191517 622263533 926458935 521442469 526377767 689146057 641166692 324757578 565906731 184727112 706834577 69608498 856343661 970427696 260310884 576989719 972158903 483395652 429763775 829474788 528015251 898492652 231606962 518255233 764107766 462764591 123080256 342699780 245690031 957732300 49016262 55967912 912526203 551831816 898672792 283477572 288763807 963671805 465630095 383374371 642033222 726129155 842114381 12987804 626585691 320990900 516750035 471005960 955127636 557834645 209497645 741018348 786884924 364829303 919608913 312433621 463052483 51129747 205804615 453426664 663744420 696445146 496304467 60056008 221538632 24287231 871500191 310564131 415300448 890586765 787004539 843038613 338906592 708114981 765606520 507079199 331591252 521207407 498853541 481227774 842430372 585162272 792239653 777788256 297318515 843182959 317982144 227575600 947139759 105755261 20529910 505736005 836031221 871585124 201507477 477377528 751662635 316954931 175707396 775369608 198262440 214516346 357933359 188691560 81231921 747686090 597594456 306363843 912833184 952600918 967538658 600127435 485772794 66608958 772184208 931690325 470787758 885220185 423194919 623816195 759114160 646508647 470787758 111695942 341269776 801491766 618742366 3339376 477139899 222414513 558160970 540095076 235233552 594869533 735607790 345964842 745906740 809306116 462760797 707839672 26811219 642563808 313996452 345644838 639516277 749485629 94481594 518086496 969257680 620753944 826403272 954840979 752845811 475249935 203321858 40074357 259278686 757577722 78599934 745425143 50506344 68885432 286419484 832432347 218067575 684081233 530308186 819979717 611303613 135934535 290094804 673062414 475984254 412936956 649318133 365121301 604514279 358548648 321932907 175482771 932033445 986244897 304515412 569293423 179768180 515795217 797957851 387509839 225517592 288842496 667885407 41133673 670847109 839950815 213827225 188650515 639872946 849808477 479536607 319451839 650874602 518536074 801387155 325071867 218046226 160547776 720759707 513798137 213137122 475475276 920425933 262778860 645344187 390552393 42114075 754158362 355713734 232336130 302656604 120592064 188347506 371508020 35173209 914317111 321784451 713491605 241805698 432124061 891486926 435482955 530308186 835506052 129077066 689479177 321746706 761795129 649878975 854217754 749060420 286418008 750038912 83193646 778284222 983298883 557204524 698248651 742999319 412338503 844172237 93387292 538521020 15921622 675669152 247797781 312472373 759114160 870334042 595187840 492652087 764930479 581012040 767976339 421878456 178869661 853334809 577696598 246261803 475376869 414170168 263234638 834653919 58001470 434232915 601944126 895718509 436332799 33155492 256724658 825052601 89818357 377518166 504781330 101895777 617386415 847495573 932087604 665124316 541234934 341351286 359100495 82149770 19397028 310663380 204233858 411516780 34172714 826937298 46193346 746628988 672439872 865565600 72426315 802624821 499097591 792039017 204550807 933165891 533630804 172318788 905903509 961959123 369041155 818637056 115767136 178988386 905489698 489991416 648996783 139845710 624561468 472884494 59495979 765733601 458302100 20767688 6056016 88109457 368589681 74700541 946229463 227411377 17615181 643221798 227267062 497068141 130246332 9868707 832309690 82024501 523794076 661283605 190145588 306860145 613035362 88726604 353560230 219934100 236391637 934774787 527774547 610389153 568014389 297226961 82496864 948989429 395667340 133313656 742660674 530733647 80247551 966957102 140029453 672976710 295405709 40491014 772259265 362988898 606544192 984848459 345964842 432483008 295089769 563516697 896554481 593442571 680482810 352045454 174917603 959485061 900724107 210250549 300419194 912682738 613925713 622101392 496476006 627963588 122100353 638458853 743578117 603734066 694116522 936991491 800335749 327726347 103168867 578016484 38877824 228347484 511332282 999183163 960200538 383890265 208820232 142223390 852155898 999219706 369907407 772184208 932220016 865786005 738528127 512133909 169052851 392655913 779051722 306021217 500404433 192904819 776172825 805237240 887963166 842892394 839858318 772820414 649878975 263177748 845557319 959876524 876361848 848931261 941064321 834653919 778489835 925455178 488439577 715119543 375695357 579342884 875319426 172602410 556368173 847374266 303991118 856602547 776283121 469860721 341702021 396084318 370218806 178363601 634576820 621495661 180598416 997582978 824958499 927814245 362988898 640462202 890621083 665860197 327070966 452619697 358905246 211646752 792225389 524367243 258523059 188650515 204918794 243247398 289454155 652218386 548813585 197796869 688968637 182278184 820675316 573306043 855498060 408206356 860822007 713986739 776409247 184253646 928549559 284346073 46643772 582193956 380177538 315449150 818061465 290094804 557834645 618415260 66608958 195121279 733318897 910179280 32701752 339977078 286979287 567935628 694723985 567935628 810122218 404951858 366271575 335195110 715070460 916615348 454007958 647894280 541924649 948916069 156239937 21160715 95242454 797957851 287209987 543244718 430029371 177519186 564701777 418483640 692452086 763189926 596865300 82708419 345232231 520502787 963865233 485957292 237493098 655091978 139649868 667534863 893073012 283040969 370873539 885220185 737369827 257478537 87226643 201042812 904455171 993706269 732812505 478191747 872689336 82351971 238631244 569335073 899086891 894979349 503083146 377814079 415041355 59755678 149902644 208324503 304861797 504878675 618324602 862786051 353773281 71563303 540449511 789981295 131037713 11689521 467717931 226631695 698826835 760081682 226295063 984388049 985112163 240058352 968922615 655594561 361034923 775421802 511475579 16300919 438242994 239003612 920313542 105011891 382289417 938424501 297946972 451379986 229009890 405724118 803058812 794390600 99266733 36975243 606398000 643383489 405908612 294503509 828009092 783195676 934940131 884102148 580554460 822884694 466657460 16571694 164386545 782640518 405908612 487317753 512548379 603079557 13392085 422261451 904677 324007472 428675774 866815378 161250309 838923516 817295332 205491633 813544607 590640054 705354344 187793617 179768180 274234058 619291265 654545476 668136116 366837844 287904428 784091032 507250316 641724557 631226564 234244084 506498167 487331420 154877563 343647161 603665555 377730808 4248150 996950798 966058017 943263689 581780946 684102988 852524547 113703334 616380674 91797754 798309594 294067402 71859412 543120515 608407842 130061686 29984397 966526875 35803488 279744510 415402716 727164607 692078051 912923151 504757644 244471351 602348510 511419649 760081682 757456672 233129832 711457179 415041355 873880473 231380954 161500949 291597564 193724188 846533202 237952903 426170777 461858206 634935419 340708328 288202823 733318897 111820504 561668480 822633398 819832036 371508020 304673683 858672146 989352384 582969963 689929388 782655934 189673370 744446277 488631963 235833291 151148107 668983072 525811803 105398824 598046271 429169431 341269776 877760948 870171190 612150797 310663380 319387997 595781810 769519265 789167852 647073402 172478928 743297386 38539888 397303247 712155257 278864897 747560128 109178443 734904825 298478363 838923516 466920624 708114981 199819526 590370077 548517667 530712317 155966843 117438503 720547181 183895796 706646605 319804133 33076868 383548329 291910854 557114621 123618925 893073012 730768709 466920624 871037515 787189370 925455178 110164873 740150432 275287754 355718713 819249826 49125108 891867681 801884481 543189274 746748129 323464124 40074357 25135251 676458637 186743904 416947982 567246575 306780698 859442839 541924649 980485038 167242405 235945792 329593037 825860287 451981967 731515998 421820436 430727183 893409051 49402662 172318788 936460233 55221651 290637767 107434061 227504262 174943461 374533413 645952287 596519223 741034697 897393909 448342784 515705138 898712853 947868078 770666975 337334497 895500400 409442122 314226365 408127493 823006288 884714929 953657967 112752443 834441531 499568189 24051319 144835298 412338503 425649891 81231921 813598307 671296125 37419433 756212025 511149232 864914693 286833855 752498550 822933559 482537529 619910832 229472499 622101392 758292760 981306977 694072849 922966386 222414513 798220609 751238614 910125518 631638767 827529982 18022200 661150843 243856857 505590295 604933556 85133185 779457706 483601025 861710234 412717341 891125606 7430152 833429653 152866567 323762184 625440422 268383551 357843257 611754734 863357234 648708532 361860585 649639357 831219666 606681403 781109593 486422307 392740278 72399745 372880390 711457179 282350466 207365777 310851029 919219849 661150843 178374772 340708328 308770597 655094764 754399833 225456007 395416226 595198575 8524806 855471099 448232234 787686402 552030830 871500191 441947243 528240714 47568608 793210782 538300443 135262334 439002727 235945792 369522571 17182477 503756572 805916055 983602133 837114629 256018517 912833184 448232234 925389268 836047180 803682594 688968637 117416891 663744420 677103198 587842688 323952923 36069182 832552708 654198081 2496866 57402164 617985958 572867222 98984432 584620499 848947539 535452501 928728815 907636656 562260977 520232702 512381608 149192565 968086350 212727837 409442122 985502406 258523059 223235910 156394736 235752480 585131123 440358089 422195555 209165696 345534392 710144441 315984174 894234502 77975139 778007175 662180803 483157267 437673282 260923498 174846907 566302026 485957292 163075787 956956636 495673460 691624759 912189141 510388998 938424501 7430152 705029905 785305385 593442571 286979287 310482760 298109903 751349894 465465888 932260233 232420050 220628337 216347021 35592775 636960051 836851377 41322168 882740941 991218001 767951959 103747460 233000562 468653583 910541252 461807388 313576149 832522019 106582885 978594807 331705283 520052617 20913964 630666394 634935419 987330739 56788900 36450673 520533951 33155492 51464219 716681433 907768422 486969546 680435298 275908147 963671805 637725783 739831176 721350389 793211182 2565289 46203239 93899046 750653043 928291346 895023511 678501962 300457611 236455403 867953124 553621766 528820081 478921925 249904324 903307657 258984699 692307842 199013247 426041975 517903288 885981721 513899027 739448341 615273061 387885323 425001419 925859178 118304660 762290983 372900855 644749693 48515996 298799097 563216653 177519186 887555903 866934659 138014049 289380772 794152530 738507366 50765208 643715946 241565663 19415319 758473531 749867123 552837487 215419347 744053395 552800424 158602670 221991093 912663626 552800424 917468705 655091978 223864825 457803280 434887959 572791611 102901656 774556056 624797095 489733811 69898680 895102004 278130680 185783334 14150952 560108621 117893526 113320251 570204859 338599666 491934918 792239653 538278239 973189590 323518121 163705567 474991558 465650792 478362875 236391637 669752837 861074018 167806967 589220083 619348349 799498103 941286410 165928362 865463990 399786412 464277260 693086504 218208508 971626296 499143959 818202521 552283585 283626601 905391094 343672921 731076963 436071681 92606879 400940807 277767126 491291374 914906820 339931564 698409218 458975713 712866343 803538755 372671638 754158362 111546112 378672515 414321652 388962928 841512451 787004539 726687416 775566903 962783666 823141914 942727827 688680090 165107137 85257385 509291540 490615346 993713304 670886045 706401667 443756625 680994470 799972049 831061636 465630095 760086985 745548177 624416092 600846489 707320100 515795217 112752443 979245165 234568379 871585124 803160225 971406187 529995339 580500124 698553617 640234426 598372487 288916839 358341221 125303981 942387770 780765587 365993603 429169431 499975180 445931904 993524249 692307842 83547713 324757578 717063708 202331003 829317796 723621572 644651392 314918209 647077610 186263518 14388398 730768709 806245935 959553052 800827008 811615745 188769057 797465607 681179255 623148175 476904894 61405336 699790856 96785611 139171942 981690932 257892594 418161579 642563808 539708797 468724088 10128688 907012561 344131374 667195956 907768422 367905007 236139034 758677467 863840294 544262030 612392091 200057285 989785687 343224963 918242666 613925713 47560643 382555348 524240680 8791724 34886485 163926479 127095709 190132813 732501762 480016661 693024175 221991093 247456503 78453692 521442469 13056626 732940469 932528716 650876041 53724041 312538744 69038212 710391737 191823737 722978664 978856836 484887128 798309594 840229478 543443908 917468705 948390708 920643426 303192182 733325210 289443111 127924215 401609417 445337549 556818108 323464124 559264534 680552699 35336691 150145638 677423464 529997496 809964566 142002831 113703334 241228740 169094149 167789557 348116702 138014049 194350554 754399833 479098958 69898680 471240519 317982144 503507057 418134806 695868542 869576646 892598579 947128217 954195532 220649502 231943789 711385990 49739334 499555836 388701878 982056889 198207331 219225788 739008041 38281957 870191195 595251950 657611377 412748898 563845112 835058053 77975139 711224278 825369450 828587491 366793176 70335936 825217232 715812325 543428 898672792 680079505 742383246 864278370 920135502 499735981 167356482 901880408 729340947 17077653 734891170 107342882 416080816 255117043 430480277 57453451 716350083 142348575 909232653 198376154 373508522 853682036 418567630 543235690 628839303 201354185 884639330 393892572 158524994 946556288 637823869 547536066 553621766 407508986 414433078 480705573 816874145 336986275 956129571 243856857 460112087 485286911 474964192 551408565 556588968 683605886 434399260 749993255 288877153 732971079 285541293 788226031 618429484 786442254 852523304 923750060 57311248 764020431 906274377 340744906 944936485 145677773 406068682 677707431 361703399 208324503 597794175 743991435 760533272 494115676 541212491 901431003 232376883 127095709 239003612 552030830 73588088 878455547 160547776 797410421 735200626 260038712 260257189 353773281 762275007 228523008 418441173 530171270 736072439 485534587 220093964 899253025 817616034 498352519 493012850 180364382 820121446 880512316 466913150 545933462 805501602 355200933 813278172 175288461 575280747 524367243 879120434 130223919 24807398 46917005 669635411 646508647 930951655 780809272 555199760 831340168 204918794 37007722 642293603 59729100 556439020 605585252 910721636 912432262 494584087 962967991 317080926 711641345 681388288 499143959 826113195 291411136 451955219 410999725 73132912 288086581 193933032 928719680 942676061 616952894 196639411 693653942 723674701 725826543 594869533 912910752 939934950 854891862 799908262 800883961 228760466 781109593 265542313 103747460 280608944 329044404 403677369 26360196 288086581 150501798 918429105 846378517 141723948 398733342 372226979 161414868 795439930 706663244 202270056 832206499 683226903 17882678 24640025 814626113 786478308 292008773 283477572 373778473 169126678 818019295 435454942 470548099 981852719 433478826 998630653 928186161 482741128 495673460 839923398 356346004 953758217 287526791 430029371 529793205 441429414 952586194 636390086 681668964 935507883 53276977 813544607 318570606 353531903 436191450 541212491 892494404 676138797 415722135 280581282 549553537 514146816 235931120 600889673 428259264 948989429 665009506 195132356 139700033 650874602 568860178 784454476 925553559 537245302 618030914 989025701 968245309 474964192 215109520 417007197 874400124 174917603 586970681 698385308 193349690 398733342 379520109 800688928 654946515 334850361 685260368 210250549 446288531 989025701 917847417 186508745 478034187 586970681 839950815 124552574 483395652 983442609 112363796 261293188 726596442 193007205 809658399 20718876 483941734 139649868 898712853 39698911 801387155 280322124 786342645 277568249 725506704 673237718 81901519 602348510 677220105 479045280 24287231 370426045 871122387 204729784 174643150 568942002 197044263 543428 892310252 881014395 689197101 446636197 339151843 849304711 673567795 44085305 33793466 718135442 663753982 667875651 505649861 435546286 372711144 310482760 242398696 838532927 229165562 525811803 630760884 665347276 709614974 79548459 660481121 947489559 359311860 276639107 3873849 12354825 802567794 423664907 677852091 422431244 187370562 45937423 996229897 89146121 572791611 321927105 524435651 701210625 387017575 457521990 145983998 68512609 829539082 272695369 607159128 631638767 150946239 18370514 863862797 355860290 254016516 618324602 244772522 344655557 88137554 948828571 671296125 42114075 363760739 263274967 22723166 46413858 889407433 295089769 473864491 236139034 790506681 195742421 749867123 344732934 778428675 825217232 451661865 945822440 463136948 742383246 441583289 312472373 954472157 952821901 119248032 405364400 910721636 435798854 180045643 960337894 472349605 921298014 17327903 28695883 428837719 58195456 419280910 799840456 625993634 425001506 820199017 110414823 384362247 560291188 259747419 528717078 759872340 659737942 952208933 816752807 383804108 16224722 716355619 432298954 762481945 408587456 161712252 479085694 776736390 649889153 927202401 91066108 24502374 609660113 443909572 483053121 179692066 145292274 952808170 737369827 628225222 304537668 682639332 722630147 362236801 457521990 82098610 680309542 957732300 475262519 683605886 983625423 951403816 158491218 463366106 117416891 361603795 484620991 979245165 715119543 657378904 75591208 333716122 175676277 322416832 94307512 260923498 691197695 492014964 849808477 315343666 215481950 549781332 564724216 565921919 180364382 324697864 630760884 256360958 962797050 853619934 616129264 435211887 416497081 301566213 395931292 897279181 324007472 619291265 910296274 959058723 146027424 475249157 993706269 131354286 108826983 3798507 779009554 900450806 285741818 456501413 233129832 252206760 447493269 831259031 35126737 81553374 363760739 83815277 560897819 891125606 269147056 450755949 737531632 907175560 479085694 620753944 578016484 423664907 419614642 34664381 561668480 563845112 691119024 199281829 689479177 428837719 238631244 832580557 388362102 637725783 996153400 529649052 116381851 47671284 558067834 262955110 374818895 726957008 86877110 492814028 645952882 575264967 361984616 731918413 319562624 998962791 345534392 357138536 647670702 372711144 935389955 29971926 657539436 124192223 444560030 37491019 733873819 132016454 137701751 487879513 321814943 233253202 928728815 46908149 152921865 56986528 401607752 28208754 762461120 163636540 454863148 780463125 586577403 907200917 680765506 349575980 149936533 820254304 763496329 414335578 418131419 971099872 777788256 992856573 673189965 986222544 612567908 452049103 217593909 283689644 824839599 923750060 382289417 19909805 716275748 159057942 684783832 974551156 986302021 772253460 769516891 408876332 563516697 582823891 909637004 161712252 232420050 490615346 35952925 54378759 102573361 674386696 390975263 740118810 502192036 120592064 550453489 655770000 918076957 910645562 684437264 713491605 552996733 227797785 509503023 972897663 745548177 569874355 121123572 13056626 221092804 685203259 550832710 319424469 187793617 745906740 533630804 288916839 666992212 312461279 919608913 435454942 206431332 532069573 370794566 35803488 606713986 712149781 814978457 846875588 986244897 414321652 718135442 86877110 17676457 967908148 42254768 797331456 647077610 512465969 492693619 642785984 522972255 342390348 176897652 115109328 595285963 127437101 321784451 738662820 707742521 368958754 661023684 650974143 171378789 930340554 694723985 843182959 244088962 90136874 13483555 384721853 390429789 85332966 836178650 536111091 764709342 193933032 691761345 776729895 587885309 649986330 906800058 477139899 903338189 191823737 289509299 743531206 396084318 459417229 803538755 972259916 159057942 377518166 870171190 631875638 327364360 502323680 971406187 227504262 145416680 583874712 820422117 138441982 870645971 158182553 388567865 99778147 538505847 580506181 383548329 757453863 405537569 47568608 678433606 131139834 285803096 101330779 815251633 996960867 584543156 687662633 857831269 536496510 224847728 824851088 637823869 914510389 644972113 379192169 419195196 543219206 693237342 175177109 634699202 577955149 321927105 385811082 422597538 87267349 664713934 9194547 662040755 834058407 217133109 499318416 245991331 512381608 956049248 346309631 128152605 826894504 59495979 178872985 920958716 199819526 822265366 696692612 202716618 177618506 607743520 742293626 284389238 126709 278003524 106918567 523837564 476459068 213827225 170747025 776846018 730499807 728588082 866815378 93369432 657611377 639753564 613243286 581012040 96954477 907636656 922605148 595251950 665124316 298799097 56604552 368131685 430063360 401609417 935855490 33076868 520977447 850821841 952808170 234244084 418528997 817616034 462072530 278919493 922823988 260256362 665860197 424381158 592317715 789093497 89214511 85308931 713573043 911926461 944731119 129364419 964025759 927814245 870314359 548730997 324804613 757577722 362392448 893336336 253161234 441463543 197044263 464741382 631905364 868720795 818202521 732929080 158733364 6546303 248021630 116433645 813253113 286816871 881014395 970280281 532069573 605487697 879468961 792500908 35799098 723778025 776409247 511993470 806285583 750769680 771295263 573304345 150236165 155777888 664109861 492014964 480705573 386531832 128188833 20529910 188578330 618429484 744361017 362069132 604889525 652657643 288897496 818488850 998649443 253804649 431759341 931690325 512830237 979529896 89818357 220093964 946229463 945583844 867527962 581661133 848942768 310092655 189926850 371196088 119076557 272694758 781072704 964682812 897242354 212289722 661949817 718273776 993571815 926183220 890487814 878455547 825883256 242667778 439280673 842892394 145397495 746361228 800282523 855912610 82708419 888005014 903844541 195132356 684763627 856343661 232376883 992157912 144085246 162256647 555199760 199286340 453299246 18735928 218067575 386937263 263234638 15835780 730291158 187166688 858257737 268576260 650357610 715070460 987946025 597794175 346309631 217593909 986909629 374351790 920643426 522972255 63399553 256807589 959553052 785257291 695974183 895500400 921441916 73132912 388457311 289443111 329962021 110564697 515104217 376759084 285741818 295270470 573431773 962797050 323711733 705029905 825866755 695171604 960529727 486376294 928186161 932192047 707742521 468497937 139235621 279744510 429763775 914005984 797331456 57788660 842859831 662572929 717327706 511419649 369244992 707808104 886681434 892038767 357138536 949299230 255838435 321337795 416947982 346692509 813263650 896966364 918766332 171866517 904584355 476007906 720538524 568277984 120269850 83547713 412717341 866618382 755753507 447007155 3873849 566127808 239315798 875736447 526232217 52092085 121993265 928576452 611302445 62869922 3031770 921794760 140368590 52092085 910125518 158491218 63857021 178640251 628853484 82327609 230861627 358548648 640698270 38338251 782236244 693617831 615274089 271454194 754085067 514817624 250119561 251910221 624463324 399786412 204550807 105398824 879145854 507695795 250254420 256415902 97354186 16717923 195742421 934998283 595993633 35173209 396313112 512133909 210819404 13483555 568860178 437845552 225817079 351126699 282462741 907234240 828482181 851786542 366793176 532013618 61846862 998630653 831219666 759128624 585399516 240424947 422261451 101330779 879055330 208488358 53081243 209165696 110414823 116458824 901880408 461091665 265825934 411186694 723169065 384824422 212289219 109050995 884968321 964453544 736392196 374570663 728588082 144806124 979402922 480762763 49836290 676824593 440049420 202849103 169094149 300457611 512944442 814004767 124964587 755744522 444854237 545933462 596344290 720098097 73641266 797410421 578650357 986909629 708663641 461868854 456501413 263177748 683929394 906221250 916463555 275338366 421820436 210743089 283031268 632263532 749903738 256970252 476007906 667564716 832115323 531864587 271696011 343672921 575906521 106582885 31135951 390566596 396182061 886817715 123374960 457803280 46917005 538521020 857937052 976209257 979464435 566066977 272551377 113282846 834152275 688739134 847487066 547654412 65986882 165828289 169390278 939574905 101589758 611835833 45120478 769406145 189880833 779124215 329905177 630925758 167898750 277767126 617420901 250436970 863327851 633312369 754897713 996230356 439589266 792655374 633663001 93369432 323724287 298344306 549998814 863327851 385443735 969416785 870497551 326565622 938597610 304566575 627224327 650241393 394808968 671018701 25530308 317080926 707864931 598584408 746748129 522128355 329451569 985544914 765087347 141922582 48440334 857774066 534636624 739448602 496476006 741520179 800688928 854196215 899632159 206313526 877943893 777043567 618376420 91989804 846392514 29174004 464354695 814928596 971496567 947489559 250254420 4248150 789337091 319648515 246827841 534990125 15223592 793232762 170482762 719909000 203290815 320680585 79548459 278003524 246278558 899451488 490763640 873714900 705501509 680858262 228347484 448342784 238359655 690194127 655094764 815161910 299966522 934940131 59281153 157793203 382237980 297045559 231877488 485772794 866207401 520181510 989164533 19351635 662517871 800931996 1029028 378973306 770711225 872010391 432043279 96565846 146027424 43633657 419614642 387509839 10361293 440358089 280754579 526377767 230861627 792225389 988294945 523421518 620130351 140301945 444567457 156158386 697355368 758677467 752569409 799972049 943137053 916799337 289073499 481227774 772412913 650641719 894571524 991376906 353785750 463377066 738170136 346738967 964247730 617706908 881789597 10802946 566127808 246876219 62401715 453270150 484342763 763610344 264022175 912432262 319387997 530668481 457455502 652503653 192904819 13392085 940713690 469960642 259600239 204091209 388877081 483053121 844240323 710160 285817339 757456672 781072704 477377528 236297517 749060420 214626001 226631695 201715494 439272822 326236683 450815699 291860395 96785611 448564296 84154978 231380954 278919493 522590796 484342763 894371943 947139759 255351386 960200538 231606962 653843642 531816571 752508383 846509506 611303613 961764684 38539888 909983291 632699584 241184441 210287164 976041655 553351597 476989029 649639357 458302100 944613126 115109328 136303908 148272459 731349700 287791009 865463990 657521345 858013928 57788660 330733817 272840907 836047180 50304827 595285963 528717078 935855490 528681062 581144868 253232056 155151590 649017435 914362183 373055252 649414674 148002607 227754693 451467215 665756036 468497937 700863788 43633657 661513380 859348858 737680407 864018409 29496474 792039017 793353601 413408254 810317420 476456150 393073170 485790821 838720238 447007155 777897253 711641345 265849845 691166253 447583406 969416785 165312087 483647807 894371943 79531641 808537896 455737802 680095215 164478458 372226979 966841582 426608862 205212184 388457311 757404596 37292795 535334907 97411693 961954711 806154223 294174167 158229825 3031770 732940469 201560736 641151635 37071530 904100320 810357431 375905630 897097486 247797781 914317111 476396405 883126506 701970463 249832687 19573067 733325210 584949883 906798518 133410605 209181530 203811623 197859510 228384360 11390004 974549667 978693877 793353601 307496603 476751717 46594807 982056889 878621606 585226608 715396303 118832507 601894669 136336561 278783955 547425230 123515542 569293974 264726543 963154351 828100749 945303963 787124573 246876219 516277056 720759707 382251480 485286911 860525186 143758280 165545890 684856839 925635330 980764371 4671914 575786872 199476392 964792346 923895587 429612637 45853172 230739192 303527904 503579895 669516403 929221138 40491014 48515996 701210625 54378759 605196886 182999665 458814991 316334734 561446542 641172336 312446070 897147712 517108285 648708532 954840979 147770081 869434111 620307577 491833136 388701878 565831640 782640518 535334907 831382936 52887674 283872997 681566720 673237718 212711034 9471656 553836527 127303391 588259231 429428009 181601827 632263532 380608200 53292407 294706095 897052657 231272552 316677790 537245302 940761488 472863781 227969092 372900855 956717024 531865131 932087604 621239876 854891862 87581364 88932735 199219238 709020441 608189579 559264534 354604538 429382079 117473949 828009092 948390708 526232217 869576646 936991491 907007326 963865233 245075375 517443635 418134806 267058919 377197284 128077112 806285583 16842269 386605894 794182830 772646425 533558934 351126699 232902146 419280910 985994396 153052922 256360958 410212573 852524547 281373173 202193938 928466580 755925887 751238614 233319793 439522679 122564888 711224278 268996687 956049248 610841313 211646752 722821815 19685934 780765587 609818495 163705567 896650813 105683339 189115013 53208498 71654479 772412913 332158157 861710234 442985707 1338339 377173974 41581256 995734442 124964587 398995412 672437347 228493945 504834303 652657643 230734247 336147829 187684965 750193869 887558613 407744921 486851683 517443635 9098968 129364419 783042478 344570565 92593381 763496329 177565404 503914742 657218024 732533181 340573789 734473911 240496506 540095076 327726347 817571886 635753782 420798041 587313242 996960867 51129747 850821841 168588323 439896698 402179223 995134056 511977425 240058352 811707679 385094657 185028370 606544192 111546112 38063902 817668334 505649861 435546286 55826214 109050995 683087522 836214108 930541273 19909805 926679306 146578295 188765407 867829320 135951656 774556056 614767210 952208933 912561659 589220083 954472157 783377311 836055215 427162482 418441173 131525521 37491019 133136376 816806385 762242440 117944916 813624815 937084775 776283121 649499385 672199402 941791078 346738967 184208082 948828571 336239281 54323018 723674701 903307657 499975180 63910655 729236339 658497147 565684353 2608929 121123572 38063902 797465607 113282846 780159805 549620840 572663 414848055 354937385 391677993 912526203 323958326 850969128 65959782 22629754 31041004 438566087 689600130 726957008 934998283 810615122 736175759 46667598 295267523 440241538 752498550 758744931 331924841 53292407 425299238 250896595 894461081 696445146 94307512 537078558 925389268 88137554 985502406 35126737 576316973 130765395 416966051 579365633 685811678 44759497 932744339 601273522 926458935 747413691 155548313 970497330 743044404 600221158 778680657 514817624 155418409 652794421 701921810 410746635 634699202 292443261 556472386 380676844 100060197 778284222 412936956 255624033 345967741 518536074 264603535 507079199 71563303 531561202 964788559 440241538 574801864 235833291 486250225 511149232 342699780 548730997 384864579 518170640 307024661 857050568 258777831 556953623 24502829 99894714 652503653 253967662 891349707 724636852 924861652 785146305 208610080 720225296 74724846 898149548 751662635 600807490 601273522 777897253 751349894 811847980 316880794 859199886 180653476 152921865 463785844 374351790 467519958 238477836 834058407 429382079 541998277 603665555 734909000 989650960 324280797 216950041 873232494 349892380 97354186 562283390 644724759 49209443 395199912 514146816 556818108 886561899 881367385 668163086 857273630 18189469 170780682 256064828 225163585 321842643 826113195 526739640 590052654 482808115 202331003 753396141 335406117 859199886 114402984 173829308 41840360 266366547 462072530 180190869 83837224 765804401 383374371 995241161 468910113 482537529 517903288 314226365 387266202 559304081 240424947 487457018 734473911 426338239 542194464 170691453 362069132 712456107 829577428 161464352 713667748 827111128 814664035 521009540 824958499 823915922 442746455 444683290 771967124 829382738 737156999 91757123 780463125 720910497 482741128 228523008 367096924 203321858 528015251 557374263 816874145 199308155 458980593 40489476 504575438 706646605 864591639 151148107 114025893 353701867 404789924 935507883 854217754 503507057 278601286 273679131 486851683 598403141 85332966 321932907 242398696 907049543 3102825 583685255 938597610 167507481 102008847 439132846 624507104 755027443 254629137 83245973 678031441 54157410 908291929 851786542 816371558 428751871 711211879 767796909 175288461 124612698 326396949 299665884 548282966 158113476 235179790 18787924 794074966 543189274 775421802 288897496 593007555 972259916 961954711 123143859 253928672 757361048 889550939 280754579 319804133 231699426 325071867 832309690 736072439 535452501 382170439 911926461 386937572 206313526 608407842 567623690 991284308 461868854 397951346 690335110 666814281 650241393 29984397 825762069 437845552 73641266 784113556 9471656 34664381 766367850 368848127 19685934 63442031 958368434 87643485 534553809 522392849 151409989 478837141 980485038 650974143 212711034 443497188 532784551 568277984 989785687 320680585 222314010 716419485 400659062 363315545 906109214 850748827 979407881 488243432 746346297 615845128 142416377 890586765 868525305 81901519 456831848 589868168 412859070 369244992 801691883 793678712 747003189 377800882 511411633 116433645 734305593 287353968 755231849 976209257 118802657 113352722 152866567 853736453 874186756 909637004 954914327 741520179 666719050 179930137 185974186 824471457 967538658 238359655 581821166 729340947 484620991 62513912 133712911 301247559 721836017 407818849 658395708 252206760 497630846 166116296 315343666 105011891 738899022 169390278 609857782 818019295 700388706 892229922 758913013 795907287 600577890 907217837 589555817 941791078 121994857 379882787 38778241 996484148 584620499 106891181 10361293 35799098 14883625 885981721 867226201 346409702 863529765 830374819 385443735 87397464 54317738 166760177 35336691 45120478 178640251 875248918 151409989 998649443 502376899 632699584 838720238 209942950 88932735 52352721 381243165 249578573 456831848 405537569 715396303 231221995 532797534 813263650 722688601 98540820 894356426 475093213 243249833 611302445 252646876 832522019 231741490 265542313 797088150 126545727 497170990 967134402 816806385 969603936 422195555 797088150 402256096 118106296 504972331 558067834 527270122 399939116 667875651 355911103 227193057 394309299 272641356 542924852 36958707 445337549 74448052 288202823 438286990 977655535 213137122 432506844 21757593 707990975 228311992 814004767 860767573 826292533 659798069 104027185 210743089 255351386 338599666 722239947 268452242 596857292 67562811 46908149 844756535 493869359 23695550 289509299 803774165 673555414 332118429 237332067 381243165 778680657 454912717 383928603 612559434 786674947 297318515 70389901 649318133 639872946 704164413 124192223 543027439 32972397 495513173 943715020 527702953 831751353 632601729 511332282 728364045 497925783 342215047 488439577 240496506 972897663 621175258 413789638 820675316 99225148 110698532 914609797 959058723 37292795 952199053 541998277 398851181 187166688 960966793 643221798 998962791 955214115 163070656 319451839 201183304 18787924 529996514 992157912 825734162 834152275 596329864 472669222 64714146 388983677 847757603 886561899 341351286 293573987 439615764 241439357 236501020 648888314 907234240 81492326 379192169 532658750 166742834 323518121 86707875 869634976 591020598 280217834 267633163 625440422 563395404 894523612 380608200 786342645 823006288 604889525 542076257 185028370 779794994 188573184 771423017 999219706 880512316 619445460 945901900 266274608 621666012 425026939 291910854 99079148 323952923 544042466 1520300 388962928 675669152 824839599 839236164 582278101 605587895 349892380 770711225 483835572 573575633 430728537 485377556 866618421 82906097 793758419 395987606 907012561 178393264 278615602 198376154 169705950 548210157 630666394 494952026 264726543 853985657 447936263 897683671 860657719 563395404 559264936 656846058 769078639 342949018 656738035 119076557 371715111 576989719 149310407 875248918 48397192 522590796 905419680 368958754 457455502 283090616 442991342 776846018 817796507 443599389 434887959 498758682 863040359 472863781 849491316 379705506 605587895 689146057 585131123 606713986 130959138 316099749 659798069 873393776 793210782 85818222 650719159 497630846 319705111 725783379 298109903 275205598 619445460 820184564 189673370 85818222 702957689 518312349 870191195 688680090 349308875 227797785 130249278 229009890 771295263 943263689 210438322 226087619 118304660 962458943 159127961 553914221 897393909 568436164 251003816 346489055 489971809 483686672 712254798 206431332 890487814 544262030 887963166 868399877 656341468 770541380 852312837 973113110 938549028 274234058 813598307 83290908 75490900 167242405 117483897 85230796 308011708 71327474 161941062 984185158 965198181 955322320 661023684 424381158 940708010 747686090 543982435 673567795 68248516 12059194 476618481 828100749 597594456 170482762 782236244 388871426 869837683 279791726 158524994 19316285 680435298 969189838 52089280 208418100 853619934 55826214 920313542 738170136 219767654 645018942 80866368 605196886 958554585 515367275 897052657 278601286 199281829 989164533 425001506 568014389 235752480 367363940 896966364 886587621 855912610 39698911 542924852 37007722 870559173 129256847 576478431 93899046 525403027 20718876 118544381 81492326 893336336 609660113 676824593 134584222 232794824 252936623 216950041 667195956 49444988 317758662 483402124 879180038 659233511 733958212 149310407 739448602 738528127 726052092 262571851 250896595 834048611 453070931 762996581 162768028 894071108 372639030 345967741 451467215 651421240 897147712 210287164 368494866 986187930 787124573 953883384 993524249 231191207 442746455 444092919 1385700 482808115 54157410 668136116 8416955 55967912 831382936 782655934 395446342 242601378 910605509 314918209 134338447 117933045 731595435 674294566 418622896 285817339 967134402 522128355 34172714 832133266 991607246 233688549 979345374 672437347 438087915 165545890 265434364 784454476 541004706 561520703 11462718 903566575 444683290 745306989 864656388 960966793 853334809 35245369 383804108 950469883 561547556 268192877 158733364 234126380 188578330 811285205 508315109 94298336 89146121 490523312 743531206 452049103 876121320 227754693 242667778 660188183 480670777 643267719 154568604 488283819 306764924 866934659 926679306 93792966 937084775 203995365 862163613 691761345 596329864 349104197 249018043 32264333 904584355 4068928 378973306 304185060 407140551 720547181 804795392 906436048 978466078 664713934 547425230 104027185 676594391 835506052 128152605 103304428 61471231 295326860 748052140 964792346 899632159 983442609 45521300 321096564 875090902 960338913 722630147 612508804 789981295 325754842 327507820 160519592 984848459 280844570 819334749 921625213 286833855 882269195 155151590 555627909 201042812 635891924 612199954 743044404 768643036 444560030 364363833 879145854 276915559 591301590 646445958 645597429 490763640 299324676 126803688 621495661 388783567 214804196 58195456 196325551 49525060 228760466 749485629 105312203 989742948 866207401 813278172 585627 151704262 863582748 130897303 527659995 253161234 297170588 206002398 872689336 439615764 728732312 529793205 461091665 696692612 338971988 955252500 344944866 265849845 190497909 457986239 31041004 400679336 728732312 730291158 946591429 749903738 742999319 906607888 834441531 58001470 728915280 896193904 242157530 328288048 897932572 631991497 581938941 207040947 499555836 937136080 875422882 678778596 29496474 110949211 650357610 5370654 695199794 133136376 921015095 242131724 207995848 476459068 97074773 394260604 548701786 139845710 93065240 128188833 336239281 889691116 329121051 533558934 55981602 254464177 504781330 531864587 111431058 270625804 78599934 422387522 24081960 609819407 857084705 772571899 905619655 747560128 883671390 359790563 745551892 676138797 374561937 852698764 133274179 624463324 418155316 106524209 119249751 803415525 457123782 405364400 462957804 399939116 871740539 739831176 176407164 983892558 407744921 339647466 181459405 453258663 849419257 114402984 870559173 176407164 864278370 894571524 674551997 381518217 740306964 794014457 831388579 929606321 646445958 516277056 69857960 723621572 41867108 661513380 872466820 985589151 195981361 157810774 295596610 853605086 570738912 425906759 208488358 479301362 260829471 630991511 852155898 579875366 741372985 118832507 971930275 85133185 385811082 149185562 540880397 841512451 520502787 144806124 786478308 801884481 862121952 23616148 650876041 616022514 772389366 23361553 492652087 886817715 961764684 951015623 59755678 751639063 718969017 140347955 929937146 913734217 301886541 541004706 970024929 93387292 847495573 598372487 130765395 783964997 231272552 852719173 927202401 167507481 406263700 157793203 12354825 384362247 803046139 658497147 712149781 549611943 629884358 201560736 219944931 708663641 724881139 726129155 500880783 305508488 373169273 86763454 528681062 374818895 480670777 101895777 52352721 468001798 246261803 297814780 918303314 296972940 604514279 732929080 992843759 276365428 438286990 249262909 36475844 411974338 377197284 267254638 998999778 244471351 685491255 117933045 36958707 527659995 721367305 582193956 480061366 995838821 847393957 287209987 504913924 890069705 824265634 117428799 97213112 922605148 557686294 859442839 414848055 447583406 996427119 528820081 36450673 758282942 591076156 486250225 922510208 166760177 283289966 434902571 799741733 82351971 342158385 847232048 745425143 870005633 480016661 636390086 524435651 111820504 390552393 219935988 473037634 122564888 68885432 84154978 734235272 701970463 688412809 359790563 595781810 444341522 874400124 182999665 243337087 926183220 38338251 600889673 649414674 575906521 915496859 51419085 993713304 655044488 100753368 870645971 365739647 411516780 538737567 338786671 715619899 156239937 996484148 225579800 588855617 816127073 94171267 330733817 311623092 219225788 520220275 104576793 610433058 462254025 100609024 30189537 550365619 675221648 938677072 961192048 675828488 26811219 21826455 559937802 411680024 466336029 55221651 822453817 324652929 929504192 131525521 736762231 986846118 585591440 635753782 233000562 245075375 91797754 150501798 668519094 825866755 864591639 382237980 128077112 334322048 38598246 68438867 823200165 143828885 641172336 928291346 52355725 543235690 46594807 966058017 125276804 681388288 643715946 180045643 158229825 130061686 409891175 181323671 787189370 883505866 967105448 555081370 24502374 192800702 632165643 219750801 6920047 933817761 735749803 892970462 149185562 749266551 365739647 8695253 607808601 709020441 359311860 435798854 517415632 111431058 800282523 327364360 638458853 159331058 686495139 440540628 508975396 880054894 810317420 130897303 552996733 566996398 355868669 749993255 556368173 489757094 217063070 123146246 540370317 335024665 972628101 734988096 704006837 567109943 471005960 485377556 110698532 993810413 541234934 62157161 91523803 330952427 216037668 488990071 952199053 441429414 609818179 153514779 418274522 207713361 174792844 136303908 346409702 11945085 204190320 716275748 952407032 190098166 744812012 33929479 570204859 366837844 520373722 539193597 819249826 785549468 942387770 468910113 510123312 463153911 806154223 225579800 789018769 967105448 114580059 701471955 202427712 315139174 890353418 937357889 488474395 53081243 249018043 143886404 580506181 993272795 831751353 825052601 206002398 502376899 491934918 24640025 833562139 472404490 420055755 108936617 415300448 754897713 280581282 730443199 228912311 731408897 874202772 544042466 925060156 523955495 581223380 11945085 843343754 404951858 197900473 506279687 767951959 683087522 839858318 361601728 649499385 572160423 66234788 645240337 591189148 307306302 595634487 468001798 195121279 739448341 295326860 700407845 972158903 689929388 617985958 282815263 961902872 994628372 834016274 174269209 79057406 367905007 344131374 736187718 539193597 539708797 49548823 395931292 22723166 909754226 13714025 972628101 635891924 467519958 386735571 850969128 903385922 17327903 268996687 383928603 126217774 162311613 481428047 798865369 954634338 40386626 913734217 355718713 903385922 187707893 930589733 293573987 278917295 70335936 360079874 613605953 297170588 545515966 611787524 30215686 316099749 596519223 374716153 922510208 48631299 836851377 203290815 954041688 403246898 201183304 814928596 132850790 178393264 637408150 948562171 231741490 806647387 531561202 510123312 612324620 54128623 56604552 927274256 219944931 307499585 637473391 302264908 904455171 685491255 723778025 231191207 468724088 766579709 585591440 741235535 338067396 268576260 362981631 265496907 765439864 352045454 925080897 471945921 259929625 677852091 809306116 733536462 184279641 454912717 367140533 940761488 764097943 432483008 610389153 86526115 441463543 426170777 69210080 395199912 906436048 317854135 470248247 406068682 379743181 197859510 23616148 91523803 280217834 475249935 968186049 63019913 360182266 700190633 123143859 472801212 961499670 641166692 405856841 997582978 169407336 680432286 203995365 328553183 994628372 12032504 381518217 649986330 444341522 879305994 447384666 440049420 718905614 445150061 237639372 143758280 360876078 192974779 912910752 969505919 578519679 879120434 454007958 607576915 87267349 845557319 138702455 81762437 988850424 378672515 779197801 312535461 569993743 741235535 113087405 272872066 311623092 429757679 101589758 270204565 735663853 299985383 304034992 569293974 113320251 248021630 303247098 949813078 243190542 920260415 323762184 41846591 721367305 562549528 209942950 793232762 898431512 576278996 800883961 196639411 91989804 727198440 19397028 133313656 62561539 679378324 19099335 332393902 107434061 668357273 764889387 810038459 728962821 958209379 485204337 831259031 418528997 941286410 756103206 863862797 541387677 418274522 565381335 416497081 193985176 363379469 266342912 802437092 537078558 32572235 743678248 52074264 286419484 990031127 753340057 760363389 615273061 342553190 413785840 382431038 29174004 774545830 116536600 128898045 446288531 339977078 99894714 891867681 365561118 196230848 198902597 829317796 63910655 943975240 214306952 384824422 114580059 949919206 896193904 226295063 316954931 868898467 824216821 126545727 11689521 767796909 845511975 740427854 585464545 189110970 190098166 507695795 910475916 662180803 189110970 669752837 289380772 548282966 5082464 189756003 700689785 581821166 396313112 433471842 38778241 23876078 414433078 275287754 819610746 886587621 826101409 967086474 173796761 748052140 892950751 382251480 271192865 148323134 909304499 512830237 285976959 681103119 423229277 655704846 699270433 117944916 958554585 584949883 490603882 998113193 252549002 359304952 364240882 703948376 736762231 666207284 400153689 511621421 141661031 225517592 577955149 255117043 315834921 145698078 6649154 644651392 657927415 648888314 842977873 8791724 575508257 374570663 432883108 167789557 274642567 767880993 923849168 620130351 352279028 214088867 932033445 357933359 786084025 230094457 761795129 915268316 235931120 685260368 300419194 112095981 466687269 287670176 299966522 488631963 955252500 667534863 727851380 601894669 762862542 916330602 46939289 969257680 498531645 475249157 7622902 343647161 664942347 736392196 324798505 975027613 656780100 148323134 541415340 258984699 143828885 424993053 56079768 71327474 374531225 163636540 153052922 118091308 532784551 603635214 97074773 675828488 25135251 65428145 633609539 578230392 228311992 909112544 866196387 459099073 145416680 33463069 175177109 386605894 439888204 122100353 120055467 170450156 213431760 206696920 257125752 769516891 947868078 772253460 959876524 263601425 887555903 210689695 259600239 971229378 82063300 996427119 62401715 191260334 260256362 649258300 914005984 45521300 133628051 926148417 764709342 338736314 931376032 988129531 188573184 92019489 665009506 819832036 805205480 794581817 810723948 698409218 697325906 845511975 719909000 625091364 911444914 305508488 733257640 150173069 82496864 627211757 82906097 126803688 864018409 612324620 886167441 478082792 895023511 468653583 428259264 557114621 629484975 871922062 867953124 893679989 579875366 84830738 57419173 521271959 690056534 903741964 623988222 792795435 406555410 317906784 716419485 215481950 155982590 87581364 36475844 161867431 307499585 520373722 224122951 123146246 954195532 297866958 610841313 85574249 384193084 3852634 30215686 904197191 551398453 508229230 60313042 587842688 301620685 985994396 536111091 693828644 983298883 852312837 41840360 710160 530003530 387404981 157406284 201736170 65959782 903787651 219762545 168121501 106340995 261859036 389609117 44571792 225385781 207055807 459149492 498954115 912189141 438979947 661504509 115043166 491605133 810670399 793732003 387885323 62157161 6745660 891408251 626585691 832778413 965198181 809964566 321814943 872321966 797956387 338736314 565381335 201715494 246353384 712254798 585430481 409531071 834992544 724881139 981690932 168423969 266266613 824471457 87015251 811707679 748748945 887558613 765439864 890621083 49209443 762461120 450577724 67372034 979407881 360182266 788226031 478550604 65986882 329121051 455837261 921298014 79531641 107284901 690854693 72426315 993810413 164478458 218208508 279743842 949299230 748699287 113352722 83921157 874205066 945583844 323568583 99093226 324697864 460112087 879055330 433091262 978958423 393892572 171527053 230652726 769406989 819795197 538300443 450156857 390566596 843203789 609857782 307139372 181690061 247366772 52887674 693237342 846533202 419988658 253928672 165218145 585272698 808699536 181601827 581938941 659737942 808699536 284409908 276637350 464461701 621239876 462708960 354937385 352279028 306363843 595198575 286915730 605329296 932220016 839164869 258410910 64594226 679378324 239315798 265543992 880054894 559944891 313576149 72810672 174643150 543027439 695325727 630293038 1520300 772646425 299665884 229964578 867226201 447680508 80247551 105683339 903741964 548701786 645952882 179574548 16062425 160519592 673775242 481490319 894979349 303542899 463153911 169705950 527054954 187370562 772389366 560291188 727595610 557686294 361086507 982912948 281893682 249578573 6741764 150902689 21757593 564736615 483686672 618981978 697762066 947314190 479098958 983165133 220476022 843935219 538758499 463052483 203204802 802437092 736187718 892038767 903338189 237332067 147751926 861315667 275869797 582889690 278783955 633041439 338067396 30624 283872997 941189887 157488918 168423969 238217279 487331420 194417023 283040969 601944126 559304081 742721245 17615181 30287700 508975396 848931261 205804615 151704262 223354078 815161910 797894578 641151635 371196088 832652111 207055807 509863500 986292041 691119024 357208152 387321061 794432058 150516083 8576622 529754581 680079505 520052617 254016516 49246631 195981361 371947755 942140796 920612916 886167441 520431707 860525186 684909974 412748898 700190633 766519801 326580775 935566459 377754516 694072849 579368285 808537896 633041439 904750207 446069503 34635769 234568379 564701777 983625423 792795435 123099909 340953712 304673683 309389345 136210141 832133266 841336653 19099335 188086895 267058919 161613356 698826835 130522852 765087347 106952380 378024797 307497728 410746635 124894666 829539082 199013247 647879056 737531632 161500949 184253646 81886310 263601425 743991435 505192617 728915280 238812459 14150952 960337894 452088869 858746734 619180150 192974779 243337087 288288227 496304467 995241161 423229277 569293423 550453489 946123803 828587491 338614971 892598579 124552574 701966750 34886485 503032446 214088867 497925783 282815263 175676277 122216284 294744797 551831816 684437264 912663626 388433031 33463069 61405336 405879972 174179800 266266613 107389355 949919206 108936617 502323680 123374960 224122951 631905364 660999834 284143189 89052387 489991416 683779641 670722011 216918964 462957804 702739393 517687789 100609024 642293603 242723411 866717053 429757679 206379318 906532407 393204009 872242539 684763627 389348604 566312917 267633163 522231127 894523612 858672146 130249278 994970024 188691560 779051722 355200933 854025132 968086350 329374703 503445450 130959138 252549002 784174420 2565289 540973782 732971079 268432268 966526875 881789597 816752807 530733647 488149263 581661133 727164607 710305663 918242666 274649586 693024175 127276547 964025759 288842496 418161579 979529896 446069503 564736615 306021217 523837564 312433621 475093213 960338913 165828289 366978211 57121795 248096662 938599829 813040339 677223439 54352863 568942002 285976959 110564697 801491766 362236801 315984174 842430372 969766932 603635214 425299238 139700033 909232653 6741764 54352863 422387522 232794824 238217279 515104217 791540525 901087605 88726604 293543562 151997345 967619211 207995848 799613305 871122387 546691855 97310168 862104025 317758662 138702455 242157530 828915431 9816420 731595435 513705892 233319793 114392586 840229478 978594807 625161545 476030253
