71 39 439917778 849986562 91009841 58184782 799959378 460251922 964453394 673872197 940461141 484232557 562640924 353724594 472386137 881569544 244916167 827295481 992874168 898211214 324263121 50753836 548126503 403120259 135583261 478954488 2579591 405787433 828974186 62158824 394447327 81841040 624754406 307840614 512191597 951666282 198134480 321204359 490588090 534921489 340572465 55 374288079 49153649 717975106 474794341 189073832 553397021 866876175 88969495 936983349 642036406 766037470 599854306 697270157 10847094 406948062 560312730 634880194 132023425 464768032 903038676 847378263 836784611 845984320 921215621 334001251 725699016 565983207 212124593 11047328 925507197 699791506 73010 820118139 188371965 400069920 362199982 349340058 428304758 862382586 173277213 137547168 848476704 154425572 519998161 927870545 282303325 201420481 845009236 366710223 227545541 688532444 684203381 529019796 5059400 521363831 4 138116360 952215764 726709019 479584607 42 218856202 967837971 281341039 593081641 725178398 630236613 154079061 640193101 637466490 677631231 617063824 77949474 278065597 892061894 561170796 952501961 648845963 145611770 21818643 478253652 489189410 295100812 675561685 620034838 884229407 85058121 787621745 69201606 704520512 630303438 401708152 442386059 62296860 741384364 577469041 589499988 787679153 602406772 252776713 238313172 79597187 110286046 65 269708121 804336790 148790526 787492431 484347114 165523559 602100284 996411458 308178026 725811432 434467157 920405563 876192013 1959074 475893906 13118282 587095218 335013786 159797445 470135982 305175120 632931915 305043010 295948695 670807631 22252055 141446081 999026737 857711610 10178849 342823034 92866621 597989149 788058181 540875251 775605867 913219705 911472577 384666712 278287340 823553786 214602608 499586856 374721334 94871144 396786672 818025269 551568176 653352837 639692868 607238593 528460947 348314750 121701367 115247347 956549032 281838634 917713230 712318112 995790986 711494224 891749592 383920158 258630208 205969832 40 775358735 189732606 469435907 597928297 496591350 86263950 175462111 56045975 307414714 103267969 324419274 217856195 915418274 14577668 455168639 526090570 949923766 815205047 997262592 641286993 462516710 411981075 87008690 522206726 32747134 532053385 89302661 402207106 579987729 270700772 998014270 274250708 861603153 558099638 506714146 165394965 395329825 98990019 584058078 981411553 94 790995757 799607323 419015847 364954697 504757424 435099285 791387134 661937729 680828044 970959947 857448879 376635422 587803510 387750594 256820004 630827260 300778696 951685292 870980914 383059745 347718243 626347015 68722204 932750461 422445712 155853011 415220576 600118133 650634295 787974597 161401817 357235867 842322387 814699608 452990539 479044061 161038395 627325345 755844796 108127235 991800752 940611164 842453999 423033309 993996586 827518046 656389814 295517843 858289617 558527663 487104589 676824639 539920364 653025798 170701243 742921306 799808701 552166277 739127782 520772292 501610122 242792868 249645906 280555014 29398405 143297531 450028919 356792139 684565902 25980711 391116242 658808475 463202643 979623059 876558111 338493528 693800215 960172177 910591994 577419176 779927855 921625156 982786721 534206958 300058958 328386223 85666460 214089304 251853708 845178553 418820335 361155642 70329806 997622289 95 750948311 187585574 49171937 422424132 299051800 857953902 272569272 908784860 423236424 842087612 352833977 418033115 114513550 831956505 304016908 315185796 611576549 110774358 715850360 346714256 34945882 757993421 399095225 488172213 706338418 785577453 825507923 649151949 490246588 547256173 131783572 656004430 7151698 134629116 498676479 194655987 832557858 934099271 477872762 536275662 758142565 102308674 395850095 243764956 582424452 215645715 796516625 644992731 208963487 201321434 169857995 735474003 848420216 786149106 796037478 98922056 496899677 849541777 251000443 413378003 263741263 835422886 786856597 50323180 626292753 459875341 807517576 1276808 145141948 823898647 139204198 58879343 864546165 524524350 683160954 314048247 965446785 654989634 934537934 850155968 661068742 906212975 38470630 863975265 645642388 578651779 619349862 153500826 481286592 84014932 271050781 260934891 450749094 82080553 714240106 76 833902914 203771648 376954476 875768899 956928031 141294361 984996103 525969355 291467549 52813190 857482899 821864577 550495356 252701846 970550233 832468071 919125642 518420607 968651668 374057353 291029173 991492443 286422308 263424348 603188798 422360643 52088635 701888139 353254849 863222267 190608266 270454022 719051413 511505716 465952154 55580723 527601024 670697402 387344172 674128939 694309128 631532018 158585462 857901649 60221020 185281204 841364985 629739422 381148782 931883895 665702857 633851110 942951261 759381433 498839467 447156673 642368688 376880426 454038576 115655930 298165527 736057442 219739516 121870711 736969553 455704970 941327714 796733579 801830142 807019145 631039705 638609629 876202068 574110068 690613150 854267402 39 627029188 12738354 270236938 347607178 688242924 140017690 893940016 289880881 307526745 549232774 612402963 350867734 523145107 758881374 592221022 835953621 360386717 542342116 474564509 533271592 323514361 698575790 9363116 798357580 844583043 308260358 248962548 650336078 260840313 148873951 667496191 824922318 657654430 613457955 101414026 877232066 916854371 108408493 60300214 25 169997954 625448961 53623316 395331782 434350434 709205897 578309273 544495915 798735878 143795566 499991467 141421453 239771854 544413789 948724191 729640946 596068187 87046974 497401325 441244905 528748960 143064169 113272392 443966561 755741672 48 190753690 152896713 896291692 587141872 595773197 68663411 52668544 641737516 847418157 415447642 592497875 458050127 225998 221037713 932003427 736632059 565277150 457780916 541238530 475674915 402226031 465662942 927201737 92672741 108295810 187742462 990948069 620386090 710025459 530476026 604024210 388967961 279408461 651733218 422986116 879640921 994706347 732595700 499259350 160688992 973524018 701453727 439909596 164125953 919491986 137501360 140610960 52955414 31 760124386 470576197 192419934 444366100 507435281 929324851 563409360 580775669 273250566 936109258 106421463 352073905 735850 372032035 994188477 243815198 89978571 839039666 639712823 504951260 500313413 49118649 315221909 510978366 423833257 820854169 732863722 832556908 302847366 479765483 206685508 9 186321907 222495013 258333216 329516096 144551643 415500823 475267760 866314659 855150582 38 160357702 525160038 517769135 849729717 510370107 700095995 954202457 762468227 794253650 361506275 520554985 26645369 859442530 967927617 740877818 950296537 75420123 174969962 205332542 328300569 525312838 941246835 94697194 584040009 244126371 100757287 854762347 885485188 597381011 936388275 857508480 965380712 868416229 134484922 867773161 357646469 196765249 475943202 17 638806609 319828744 718215524 452025109 127109636 175114668 26698842 170991106 839190899 99923541 987904083 373450932 86582547 258000523 261026781 192919707 211825567 63 692817409 573458279 756858289 949075460 516526999 331415982 408568393 116597978 114973788 10720532 711998153 981281173 419258435 657878227 821478177 131833795 805868253 264370859 373894200 630248874 497807158 414903473 648219379 85770690 582172536 130970233 329108030 914484701 962655243 277361156 120604208 622198235 813013308 33983566 177574942 705779338 749869631 155067497 468747912 472795262 897819382 707839250 819361973 878932195 89534580 717823914 960049058 14134938 754806267 459311222 897205307 332138624 492831609 351497642 962513898 14329003 314989276 666615166 162494674 839351278 155329901 670336758 30049457 89 158236206 521553521 937089810 121003727 61283003 361830930 659047563 645146252 925822694 147704891 810879986 997552255 821895170 108344549 772174560 535088827 678695362 859273126 291574280 479745969 717598685 821277231 775779828 605906112 892386707 547649157 208441345 361106555 229944316 68872528 771139313 273698713 545070608 652186212 136781780 679772632 391021466 83439443 364373065 779611103 66443702 606216949 461878410 707332406 991807812 267525141 306694109 462411558 818842543 661338784 836311966 198701865 107100951 709863260 814477909 197597305 776003061 348848644 113968595 490515721 554199390 983758469 36667319 404298669 901930491 26575599 834974465 704761723 616574330 852265015 939887230 673487930 326099721 778625849 857658774 922049585 391208751 310008151 583259096 181863322 364522800 799573823 674548340 806427118 965575878 146201211 14081996 149327580 622101349 62 614408132 238545217 493711614 638559625 576827341 13138446 642116283 847651503 991973759 557387276 617478202 55676480 822061037 122687973 753609499 63391897 672011234 850913263 637714689 825095743 724892055 714012433 108162343 925149790 539030521 199128982 460134191 63908650 811853335 949962640 644193689 698348912 553095032 93992343 949521752 716383519 463540082 603131938 797797645 475349053 752391380 480618483 755992573 22221183 977756152 533626987 17536230 297092121 978454528 624813718 746080023 12476411 731693187 614260011 236926122 502043357 183515173 386279791 541888138 71795436 801505163 912710446 5 757780833 974469158 577765203 903114598 698609679 97 642685317 547910816 336157563 312104861 149864702 60344148 723679106 392205110 527565662 182546151 370691909 794013877 461532376 974739281 289527832 931112082 105655557 586171596 48553752 745632877 126233324 652096735 936112248 135457712 576564809 815340310 806783225 846156528 482836650 58564394 995755707 96284791 354836342 863515780 713691490 486846512 440706427 445414788 618903937 471493673 846311083 974536641 25553962 466226465 320353335 209510093 168809245 263002801 143521123 502021996 206482428 185881054 738665165 644001529 921831627 668631172 818277132 647674868 871567715 345594819 685691071 481270992 868384333 729556831 637601014 556679513 620048603 928462656 949693367 946308439 815123097 212374368 869321219 906798425 247720012 494267371 233975928 316793746 607885529 282135711 229491676 495414092 401643058 745150733 479575183 902540258 185918438 445898400 372097976 175289427 175007822 361939508 817982401 377875072 24018061 770045578 40344917 90 240066977 221985373 654311129 869214046 259929522 531990834 756332291 396880648 706170649 803951311 851255141 378374023 716633798 700477970 952412437 317836707 567743039 206611494 460227005 760999916 180242183 159128176 66469959 981986886 902266224 642921756 884512850 862659048 339734638 494429270 508727563 618749190 157931668 41135733 623569092 632361557 687905665 35861463 273106318 55394051 531191381 552510148 78675876 856208698 512045998 810906117 894946149 397281085 689242954 968693392 737344562 861741532 532521271 107680776 959703311 89836308 919396817 164842746 41133102 237118087 329359849 803294076 50732068 674145970 970444353 470757719 785095042 487187152 75516105 844459820 273524145 442915794 521563991 44346427 357993394 568347828 373163517 964613868 444079603 610896688 123076170 152799843 494327911 892399365 478866726 458899174 290901525 270662474 690838946 984581709 80 316671858 586163439 877965898 714272545 947976966 412798898 999803847 890361846 438141079 613481033 796841320 46597886 296549199 826396726 712319742 781645626 115965667 278831795 92359620 91317593 757292530 719977229 165949219 207174688 871106883 955827522 407412693 885204921 984714661 34985899 909040096 301216321 283793713 621191610 335959218 320727016 334064684 869206291 302255505 832377695 41824175 90228458 572275618 317300626 60896482 543498219 823827802 273410826 120753120 298679505 109677702 340999276 964245910 312920597 691033035 967421684 971658302 356957556 72558409 948987852 677879258 316328670 98164358 422803216 554792835 272341507 948601359 209569208 438486367 69699470 992895820 625085144 827624927 185982093 130530292 429335472 923115249 151250307 798350541 857096690 80 383287216 324742694 790516096 355058549 564774424 663570011 304095772 724920802 228679490 871762986 908729952 455082975 332020345 707701189 496375890 772297669 726057369 114974340 177009218 531225706 144199740 209504624 406720713 826098358 643293713 186968275 619981870 25976794 363081452 957401801 834690603 215591123 363508049 624776888 933620541 956652334 766988310 793087984 151379799 498809248 572775717 980670324 718936221 138768382 583883697 984741715 646572208 275511030 672695511 921272768 849167362 769204539 654892845 239628991 611572448 344197134 618773967 631651413 400457297 759921008 467284993 331821476 730209041 601566506 23901887 236576441 799712706 353454313 804668501 960531064 737004133 322315669 249102900 589061924 887806237 287726906 415018434 540195472 406743986 714986495 75 494055466 584529457 809377280 24482606 330650543 325791473 667258656 288793220 403627755 843053773 403972255 608517007 220971305 750170045 424974056 734348072 847480041 943642228 996324837 489658482 848238959 329549061 258136015 813143019 956423149 203786152 534492383 896782107 236350042 334707107 776180156 458133099 390815352 355212550 906228290 665799683 550741444 179566824 337939657 185215583 893045220 153858611 585590519 545543296 388460533 654476106 103966369 561397468 818293372 215091485 577135854 788629687 988032569 71718309 695433692 442144963 503656907 797290287 87612254 945683867 41965867 568749260 957381181 738777462 78741552 488242374 163211358 661117633 50886825 623422518 377982515 576292651 784141790 394531272 407394197 80 822852666 805523385 182306864 992625445 973263683 315149770 784080258 786122651 534399974 74758396 660270361 158943261 313926926 877185611 907054017 707712673 838770899 773675784 55873233 251754400 999930233 907848484 318459616 202610294 862509159 133035680 679509526 213765111 276097234 69292665 854038182 624848464 524011665 48939891 414878402 228831774 334403193 46182457 929528278 650190747 509434882 285028009 875337729 714662028 718728451 321020225 902166740 710506476 708132786 985723734 333183965 283446180 818821070 685967256 175943079 133088050 988709673 872907165 164356242 975637788 660733921 680580228 64797506 108071095 971685312 634301217 388382869 362835281 820779335 66084025 746302410 395495288 623680601 652076037 235383398 748651900 5329511 259916870 606382057 317050293 58 393500076 236609068 791716849 486054991 859756075 729012171 523363732 526260763 718756540 198139334 533875060 859842237 547964335 460174648 408235896 24137956 23786308 752344270 543635110 653142740 393721134 190289183 901671990 79054803 423064311 4199172 398227586 477665945 805553113 819403524 567845055 981766036 818740512 631257720 841379147 164786340 428994913 672237497 15001484 540032788 765541038 554247205 296645941 521452240 811263857 844685373 146188941 89077789 895123846 496526376 156794934 704420266 23084395 517327336 799766944 565618404 222740782 48544130 85 643621570 286937957 165207178 622880186 335080510 803370715 451728025 3825614 943953544 586805345 536408318 534666727 527980021 423385757 388544394 255763052 298733348 949103085 165288208 542367238 249264994 34104208 450968201 513121351 212442077 303508141 195246045 743736218 368728107 126778104 422316434 490140432 904681325 175166317 84023540 49631424 219091364 724763130 989334765 256786235 47608414 179378226 367820306 217546081 333937028 750240798 287086815 127444822 737661414 116785234 191735450 707235140 819677083 181223273 740797081 701996983 477437232 28523050 33096384 887100135 665420805 313531679 30591518 135995487 314341884 139611509 961064450 481890732 561566967 649540401 216208179 359030109 187355588 77651968 865842473 22824722 723419002 406987431 553496872 841797231 659758222 555055272 819165458 682404303 256536750 22 683750925 413606611 30347146 290660153 299175780 762192054 467367327 881930338 312755477 401348469 549602352 31923641 236277046 596596958 211489306 157349861 790871782 107828240 818966017 593475083 613517905 793478466 9 18286465 754103030 756614014 626008907 308850658 399243590 528453168 545586384 227703846 56 540825396 71243821 613254249 122114372 575135020 509009205 125911239 163920208 655576987 805373666 467969236 922321580 481663743 449295322 180954851 103488986 549183111 4721849 221407367 749744638 761487836 587360516 945319557 154524130 204131431 71221346 744196185 677100049 700274715 432567952 946863940 62152054 566323307 952397700 432510727 125076521 963749875 819373935 771657785 979405907 25707327 730111402 405750252 533471283 675752482 665925879 248073879 789738543 715000809 919845858 950077880 782122990 716798964 485033328 677807375 22786395 15 798594594 787087809 482068873 17751740 164234259 970527990 749609784 434642485 10603995 854265177 256870041 371536747 637642258 522163097 897858679 41 401904365 263323717 754366417 788289513 236588958 948545235 337883726 549765847 230421515 799305853 50137379 256170621 313219445 508646379 507200303 769324325 483190269 18897711 449489049 660190566 434111616 683899523 445197063 211185572 18425160 881653575 62763978 193003701 336009352 233526861 348092943 950539480 665136671 737307324 926986192 487959528 118168345 940202998 631517074 162928709 887379493 91 969229512 966690030 980369501 37530183 734601808 731152201 655623455 532548367 209405196 296815257 897203460 225028765 580781053 709072510 83161151 861874231 546235344 440137912 973683394 912174784 240579663 103720427 170455252 170286504 928640398 859080617 468682836 735884401 903822639 15366823 165302147 142196161 88219675 25315937 213793705 887004695 614885886 233535275 208478143 915858297 594708751 513041399 573824148 937114819 214025609 451033665 60016306 133442361 800783854 958694229 117448823 496521820 774565305 349139041 555283107 235494266 540398054 860815727 472135634 911417630 603602056 100673508 154928591 379369102 485829031 994696570 178391191 1352783 851734798 666106261 728754255 814887477 658877014 143838244 121593303 416076999 881827747 993318207 696202885 43030098 174397336 436647783 185023263 789084499 857993404 782679506 699108427 614809737 413609526 20077997 18956921 25 76587990 443590344 652908331 333727691 875967173 229006377 369140227 2706380 432781009 404514379 610249794 459800970 351853229 662904462 630659557 388820069 289937655 550261847 642435682 351405098 401854954 176426945 882167600 864810266 593094770 72 182090921 298611569 341443365 881199057 131104189 129624273 791438529 113287076 376950084 822127605 101513603 97094624 731315209 368179926 302699759 124409489 498502423 348341856 517847976 973557120 344065642 415729168 215346799 49392165 580058334 776537502 771717605 254254063 558976802 576246290 430967541 353513659 42715241 428110939 650671289 44234787 783198505 735635974 416537894 472654241 810373998 364294502 373461473 262401676 792305555 280794837 852726335 876935674 783021275 848927024 541090481 620423756 917090223 23785892 571375611 84150425 521214905 879355439 146487547 778833484 84985 288707068 8333950 351468266 358036967 500311970 985745418 159861919 283083828 88791067 233362852 53828789 52 538907144 704829400 726712379 771725143 278246336 279342564 40158029 374682783 606745295 691019709 148447289 588111337 492499330 523826148 839184510 122323609 669278802 545214995 392271481 67040174 588973622 80178422 45214494 94134758 801990509 942023558 390296449 526543164 344913549 596226919 346530843 484862544 63696052 34667305 560424151 463364839 797209588 836500850 676728777 321853897 683717432 457330434 615725393 480243736 994750814 55405769 856540971 710952897 953979198 278401045 762857268 523161193 66 296255401 265055609 980525179 16091218 596417728 419043118 527689004 609982204 729228084 752177772 434689471 477621838 793035568 313529139 801268159 181438164 678646672 52187693 50358806 368940112 963477502 35774771 153459536 499964719 489032670 58442832 532757721 101755714 448039919 561306485 141625694 292565332 506038705 289216016 413167660 233654812 916176526 72574063 341319273 652018616 670562488 80511047 661056363 669582773 431969141 764813815 811670364 419816651 984850079 833517337 518538426 704483759 567585717 428280780 411873840 353487799 471735056 210072550 179448697 262079914 940065168 998219238 926381087 147853407 762827414 334420450 77 512648644 755255830 925099462 494323059 704671660 693189783 195820460 619152832 542606205 865282321 975450481 319005761 163754397 701555050 205586994 240997834 734345530 742691486 471886075 569803161 678599783 705555275 554561536 363932116 765752870 574351255 907317824 421804936 109023481 77581265 389072240 61969069 904213121 229640785 411398875 363867061 343790357 488952278 316055030 16290823 827147513 870968232 719064052 644816521 633145261 165174714 149575514 825200817 514812460 50188387 681384350 611666402 727584534 869141132 434006584 793015859 823322835 541057047 152228181 646405140 287098088 420036497 285868347 862130260 842914120 936226522 617091894 140176776 290187520 66216803 89829713 59327638 847910347 783398907 327599895 781741344 441171092 94 518498697 423266353 911804883 588784557 747795284 927479628 329239637 751601149 256208513 747446273 763030281 182880060 866224211 613658966 170392997 503787034 913307909 635972604 482472580 907158191 789109450 564836694 564258846 167053572 705329727 590109104 81074748 135399241 453364452 8142601 259086310 706033048 674455929 926686913 927605085 254418779 716019736 649695132 561556128 590056696 311647919 723659976 44292427 291555042 750555791 402640479 832675775 674765513 34091703 527238964 752293221 964687270 336660335 218992501 801297155 464682789 492258660 550698127 684211743 421768044 807643570 681089573 169319891 607667886 100971157 588679351 738054956 488965436 309155685 400276637 482961959 210545601 579218460 814164102 73620299 752650507 422595427 360152736 486142195 735607854 85228785 893611950 999022845 745093530 41700595 460814798 260142623 195257343 123829957 412911865 221516245 737605738 743053246 857455296 16 831798750 204193558 821899785 368739387 855863225 817738327 423934275 753275848 971439422 473758204 972753479 306011267 27881200 768865320 398979721 766472261 19 584669989 362496711 615569120 528353446 683006589 87756646 806536372 810527334 428224158 394449076 230514559 549961017 310136474 168516818 503888793 534632077 616547439 980036874 429205081 95 510911669 636218947 759508629 615319117 670177951 197691833 684660635 333186440 423228046 662129326 656792662 709374558 452845167 128266271 12706192 182350288 314268125 282535822 717663342 426192448 815271736 142332382 527068181 409632204 683557116 904188942 796210207 244767599 821800656 289007625 913002269 589448217 905680374 916718414 604029877 563083582 5169875 806905882 849836962 533646591 391766690 817658699 377258562 391754851 702665176 772391585 269054433 558105575 4221578 469213980 13886435 174146817 316932006 958035780 802218211 879455466 822569035 792916978 645762264 248888480 246129988 112180508 516847242 242330493 221382249 518964644 694353913 279139396 720072720 814089876 110762827 729017282 527165607 801862108 414760670 150760750 586796336 332489409 254740500 181552943 755340032 496432969 220609695 804581790 487303230 537616621 756157378 423272480 252247659 74413096 349842331 694017339 620335307 151351697 708194892 100 85668538 64227519 145134601 634026101 154083500 41308777 994001905 884273158 593624466 517194045 326530945 492027099 929291139 198033196 28625201 145152687 885444815 989867185 37793930 797057056 574964067 30812415 542789942 501497148 769900120 65074273 657743533 193266602 778631344 783165004 983797672 483907477 12011779 161512675 925228791 213118906 777371178 508324736 167319086 284974056 462960528 849080916 158019834 606622409 619032188 660809433 544680596 556314918 874423310 915001399 370369651 836315497 9547606 144469379 427787538 827701216 807362071 600186844 334638846 203243491 347446954 64423769 267944679 661530490 403726809 130092789 820507355 827366928 666624462 134730543 743854114 258344905 119427788 989370423 441704343 664553408 595197594 102793024 863176431 530507785 824138375 79120412 70061707 304292757 833790388 990465983 933147857 195267399 454074041 750236954 891134730 543554439 80943536 499965537 122027523 577814632 930123180 964035203 27700292 609687931 41 909536395 330705203 78665850 92442877 105406697 320887009 133756589 795657168 409893198 651642439 224989081 138177936 234645830 177999331 108398061 125591763 574276342 861037275 664932205 193026960 656555129 307078502 336145394 967477579 722033669 452465335 606595363 808883380 274626570 499020068 202326836 207840489 351118057 434465403 843092050 234581308 713652130 415806780 268289241 187340574 878473415 49 345239273 363751421 220477203 471044374 384187674 620235589 386139714 615646576 354938005 280985012 922812941 356579369 359173955 912852052 836359917 552876333 698972856 461041399 952583185 659293403 212973710 525462625 512664646 853669160 621827447 541396146 529746823 183393405 396813639 715964196 205499572 197878655 705672353 332323410 879450886 744718572 842005316 508290836 985868179 909087590 842256659 309012102 520130168 866150632 379883774 752739363 51010994 225058416 281702307 34 302995067 608623738 433758186 763360226 998057016 289500486 35574681 771870150 979215739 253169578 241165964 154400805 587721897 224518488 779917015 769781244 354588956 205208057 45322883 197629218 40626778 398660474 204153895 23667706 546087319 667125866 218805873 931532752 350668059 412547069 351444066 593711603 908245257 400341920 82 892667859 865785792 734162860 676640573 951424605 286451426 128752250 884852643 381979821 737755001 300225165 448036773 472467048 763417782 337679423 245897943 957627136 40528207 878562159 671307670 208393938 853937912 516378955 108851197 915450789 488125295 100316271 522781544 562788148 104845360 813164033 352414908 169203218 523208132 848866689 277964088 75374516 338235033 698351032 382269695 880531145 324125361 825115109 966054719 967768779 687391872 797958533 351668269 742487185 705058418 734556082 491738320 150825694 375451477 188605551 549323209 826155598 577151442 622401789 286067285 665645258 511530623 446246284 634231272 438466298 892702722 796302450 904531521 89807637 383153380 12401984 329975192 307125143 760672447 918993591 727133999 222721127 487407281 594604379 589800342 915573696 519952252 13 437536168 818109434 6314331 293691773 423607161 559439593 403694356 920196700 138144107 77898303 941072455 416024362 81067701 24 663364527 922031954 741494075 933583240 116817944 946509576 118983781 766093439 232470211 815786052 888339650 559049867 126876282 787705257 97848552 828545450 653406845 31072419 333280642 796858398 85140889 739844467 880252255 273207944 36 420501413 768622286 354616036 873982734 840996689 81456016 385200245 454701886 209325585 8824629 881642272 425040479 170685930 638564464 567502144 50500418 876235447 737612113 292469069 602984747 866454267 608710069 336869540 136717825 743205654 581009316 569262373 196791868 718964056 520834176 351011889 736560268 96794832 232840969 544822630 213093873 84 778651861 608062193 735771372 680844865 781387984 927524333 879691659 773437384 310621227 771203242 488592285 971056120 737435230 798321313 765905094 405001869 509529037 356173781 121769502 532254643 650150095 174381283 186987352 300776956 305863577 134582820 486662822 606121945 332052083 646585618 420952041 722955052 246839706 478739192 529106543 526288526 726601234 736168302 415533369 247025301 826581570 843444036 340800220 67737438 785336781 463585376 959593905 270476347 470433368 490387194 568164955 385432316 488786495 226900628 748926088 444110630 995093098 477198702 804452682 788705639 128661793 463238731 565860930 326459503 766210374 880327320 723853707 344513379 996245282 485751149 34599779 876002399 779718425 505490250 928037163 9212877 97650313 836295514 580053727 318853317 970138983 896406430 815037493 932736085 28 768477956 368395173 832371174 787613453 906857564 80570367 391717081 133698567 776562083 497165531 830292673 833550109 673727928 786636873 444661436 123594466 599996171 389872943 985902912 994345135 401521179 816087308 209229060 744537337 746479386 241148429 586388660 756176770 79 434630063 875839920 457344675 83582209 440666249 557103823 243189409 477228771 649497510 506528660 686213499 949805454 827331787 192770966 966888229 926889258 167254062 125604018 929697115 571542864 108235443 742618918 957160138 918903545 873161961 373182052 952079121 890545790 305733263 548629482 521198919 171815102 406163913 703194484 869533234 622599493 562705631 382860327 475826689 69059651 404934922 992698450 479205803 731546639 435462955 751041952 316760900 185073148 729010545 680388006 582818412 614940506 887807324 510073283 172944225 515551361 314733503 310373590 991822934 494775730 634011167 11563353 985195563 356912004 810593523 762164895 730123468 81895559 280988312 720703790 191309255 351130586 156551401 374097034 942199985 808909216 807850413 418328716 188195698 15 339585724 658112226 267228159 703093769 421780033 371729428 722330890 53365522 358423425 96574786 408348955 579961574 628477986 82365327 934742842 7 665590084 13326817 961033752 643802018 625011318 341702398 645840877 88 87363103 907954946 154460754 619916407 147473592 796723715 113792055 799220940 201042269 502109189 665078153 846691724 981347400 633863394 374507968 818145834 306454437 27081661 608853265 274949354 607742690 698046304 332076213 649185438 411322962 671617812 407015442 413006849 572162417 289216348 216086067 932726782 706567841 946673465 132022486 592416080 400238612 79627278 851280823 560985281 514357929 508821540 250944527 264992377 415365012 561638652 905999092 584775301 86132169 956516780 612361448 29568528 150647146 493939219 37885382 590471237 691421442 591612768 743168002 658022175 713260120 695022747 207795353 350144780 248736066 448964468 860526983 230376156 921792538 109511846 128724181 799546796 46910042 34228776 912893461 619456602 148570536 902512624 167165361 555600590 207508282 565810912 760566616 807617754 440380631 746475571 745424247 180689981 84 412556555 668309690 446259322 670820034 131595382 330768834 842747354 866593120 484656974 924912578 431384651 812340751 878593754 448229038 945291915 812216527 496113772 422139478 873465549 507535351 252530550 444876577 83488968 561553055 813691258 681990557 93929579 277912508 353694712 646888480 986245572 487527574 174318738 405275433 89474281 514874704 967833200 434240200 730980830 83563474 276332427 178235249 865414923 906566723 46465324 917057062 549758997 358007907 518657259 305132152 327173703 722427559 196431406 395023057 740263441 824457581 573255721 982712966 258676624 481442397 742430397 613134667 337483576 554442682 328016471 156258864 496674691 909291419 871035921 713899266 711587461 886604589 976103825 315113155 981080380 994035654 610910720 464328216 859415093 310508180 209850769 859442921 822657118 645191805 59 557061419 808307657 244755092 808477386 640921923 17328565 218772150 860983099 773242235 126364509 41983509 28138506 588671457 696631226 526893640 314251545 421251719 109166502 160254207 202526587 729874518 283253749 928971605 504997363 330893702 368560256 308140249 416828396 433895003 906194685 635972013 787162622 205243567 388276927 424843255 38166028 927130028 408790208 404446319 51403517 131829535 487849066 675351147 122563767 458947783 499760169 857785077 9040373 651490090 790725823 966658933 830607674 210580305 649980064 207492441 94109275 729611241 252119680 806657819 60 737597683 266442281 338608847 261425433 27307228 590711466 172715903 862161670 819944365 56472978 615342478 691995426 765348835 70122677 643323444 95355555 905247934 456283796 805353036 246626676 158148995 589599942 176868257 777327814 160719945 258784123 181014942 171072207 167111054 822162893 843958253 871236964 13400374 333156130 978971885 778404601 269831884 254841170 159088622 547168999 664025260 978651110 692310362 854447672 643070083 293458414 971269260 660738545 39693926 711521457 68174087 489218212 553981646 277103041 311174388 753262214 333773522 349692926 636521785 114137540 16 618039418 131426351 990446064 471777285 664919189 650761750 328706288 452520340 518318858 798995625 263556475 394927756 112808103 705623610 950337238 84637929 46 126405693 914464943 143880340 552143322 695751798 808445738 836831187 27332534 822834403 503579236 544328803 659262520 537067016 633418663 718759364 40486189 306707750 710048913 117133768 388058071 627285548 276809153 278355129 890159919 864030646 237714325 79945772 19332957 228625130 311660810 758198148 427994343 229265410 882273290 445259464 710819112 356453197 543997079 618397070 658719040 403153012 368022649 925699101 475220384 644736657 238964795 85 38064438 468154382 328763311 307162728 893153958 489363699 533370 62681707 454633509 188661543 265328337 260001795 876246249 784062856 117538797 932470942 85260824 548830139 395559002 352455209 221224757 950217943 359466511 616553810 98933007 160356912 469677154 175132422 706147306 375973124 50505475 356631029 862744125 580721306 686775464 87144769 316972 186455162 824064978 717822378 567709478 653097890 682409615 835955546 835819067 945441727 812642157 974121747 296763045 941536465 128714239 683559557 282180802 457471413 481964887 68498925 472293144 22687142 728916822 580409660 742957355 625030176 853000814 227422627 36462693 365638636 279096670 849835095 522062926 218163560 950196192 825739908 912833021 674936219 147163977 497699555 283213076 610031614 719247668 769094014 432204248 146311149 612912854 149951357 522896088 72 977437433 115917975 959372912 171021307 784991201 346141854 99743728 998439550 87670517 632961170 391396491 459820276 787806214 229055495 571477365 765590153 108116311 116613663 940554121 15055848 408763616 927993382 181664330 595040519 274928714 85874682 570163467 58122865 349526240 729676975 382529711 140495131 812317746 678577818 634465261 872146159 291036961 544094378 135917915 319417381 421994032 611135150 152931621 704038449 841509370 678609697 511480423 842454168 411746568 278286448 338540841 12221461 708800343 603876242 258783035 224373703 424966355 56301396 717393403 258048127 19196581 658142464 46659988 866423796 109190549 357621210 122481919 326506361 674090428 240116823 634640648 791947142 51 471605489 258956724 24535691 256841985 256609313 963078292 160564001 886773977 241042944 282408114 35472461 301589922 302186566 196488909 438937233 697685211 793430833 58293758 700587440 918497059 394752483 311947041 497044492 534886659 818672580 205321275 570180445 652726991 165195391 89325775 195986588 827065136 495405012 908271598 451852620 304598509 669897966 717012627 265694036 916620647 649547062 124166104 654648232 421787899 962243607 934037290 827846457 471413253 496962117 205222002 154870775 17 647571307 109044220 489233473 383983225 50430047 329770995 298575218 197799577 901785617 922699637 189046894 657617868 557787504 260987510 731172612 203556139 138480940 90 799879521 830908953 676529872 797953032 463506031 350366708 293129642 762686913 538362453 123770308 576177878 66280781 302716777 600740255 910293719 424370680 931363741 560972803 549974400 511094888 171632121 108626660 749173006 313798751 777598990 55561218 49875669 172450842 631060736 160358801 668985240 719141256 899553176 881115338 184819270 109390298 549840515 164875832 674286280 299047185 728993492 296062765 771954480 306573349 88781891 247742669 551456801 922137120 43208644 29521176 290810168 2623603 461697487 449686377 419589842 873243594 450396371 826723959 110198173 431926395 88475418 128781614 336351355 245206488 742691244 43965511 124348724 561415434 446994467 708564 339828083 79931579 132010323 971153669 865250446 969863485 325854614 610659567 337884013 906534222 697769407 987826944 353050953 99885601 288881891 441641097 79817528 180330723 416867933 337586061 52 805454869 420632262 24640345 238724037 564181725 635618537 737625306 160286850 17648400 312113952 210869400 321122671 969682299 252268648 321549693 460049498 99360039 604821664 259824103 251322401 897714429 244951652 151574319 546046706 470876762 421509862 897274542 884597900 420829250 668490307 140267425 44938287 809964748 910350444 566148206 43112721 566359406 47256017 851305287 845156057 902026271 301197691 497706839 786373145 701707544 464765809 416891685 609864870 27344758 63223638 117112142 511039909 46 883041973 626237304 230750569 958746047 609746222 738487111 142893831 139649439 901632348 60144537 640731752 708104820 622426428 385612761 493305321 179660395 910943380 532357806 506831920 835722262 16180942 620627011 35398191 102351667 877918085 882886000 788644128 325364792 391606192 771067557 267748017 189564955 976835970 313459404 670699887 875774114 171045368 516172340 76595445 862908739 642389455 551144278 10017257 222938256 825012259 196037539 36 719236715 308028939 363954334 917480516 594499685 298910661 635652852 344280836 189440423 899146960 753432008 51719829 579374107 964311923 863297161 897943896 398757950 811225456 140060369 188004076 451076417 819367868 357467485 593150397 71490167 649740201 127308830 96028549 914570898 67039535 987492467 443932790 774593438 511162681 926020726 175268358 13 952348500 405677947 366194983 281279765 912965874 414550088 466562656 838133927 9187212 357089480 113086239 890752341 120145835