23333
68736004 246021776 654304376 737168218 486392101 12947358 573965935 858823375 552167975 963525291 454521948 210445293 485815800 958927778 44088692 178599929 211953924 530989345 317465304 896494678 652490991 930360164 72086210 529267488 212559488 208870763 897972498 743021554 93893791 908662666 733416480 963834158 675644157 880086541 342632302 746734250 530015322 62421764 81654578 682430895 323963901 152140159 717946527 606853733 204499575 903725206 771175400 443720749 807364576 266552702 604403213 216699399 662213149 165462661 780309424 750974887 571140402 14011803 684113412 458951628 406417705 257832708 166255952 676705466 623815738 504671198 303259065 969657710 764243098 282609885 746376961 535384991 728617437 623492264 515278136 353678258 625739829 289396025 110385201 898739648 380337866 328825652 607754886 536160218 483444700 332688600 738903989 243968412 532598120 60293449 876653008 909342589 593032456 850971113 398338981 670272746 396545668 379075261 928270360 41068455 645649079 950984333 871418513 534707875 88130705 965019911 161676833 467106337 891505222 164953082 60238424 504049933 442930953 525239437 725251738 918863118 582246375 80682142 550453586 969330649 694713715 765475645 965988835 919908562 916397335 154212944 701835031 84822604 909793652 408921448 140843738 715311809 483811134 674943474 631847323 275874052 501532053 531115153 775516574 741708213 796788871 274988488 23243408 990673945 89666962 625000683 418528448 906291382 129874513 709332064 316337133 266272938 62344262 402020980 810204913 199393839 277308241 398360423 771315771 344615721 559319636 411050269 645243853 288782683 939544142 486350475 956027488 276887104 121657135 954477594 511450421 80831919 500889668 996442503 264578871 770741342 952455306 479027440 967769797 597223100 870119613 699002183 128366840 37499913 20777710 856248009 869255059 272458342 543148473 652091275 213312614 243982536 62569990 138630169 215417633 492249785 602240112 416067191 685546907 943072513 893443565 620382024 914291636 417959702 663664884 74250815 469504253 880740745 267543243 633736603 534001702 875170470 632439356 568658537 371921499 880132840 554480934 492707185 683408281 102708120 111570376 709942611 127778852 353908770 300636388 945477561 720320744 968249372 225577030 772405212 931577557 409084753 802525265 989761301 117178661 287929601 317222712 239715580 944291021 460616209 691790639 842526235 731974121 536907907 814373641 156626066 370060563 251893889 841606585 904017307 846845511 338540028 381024326 416903 463223874 611040493 346266770 575668681 96683465 24971131 892764025 621948083 440671841 870471961 438014432 232710265 210107222 93159867 732707238 851556970 585005586 66548236 961991433 562087906 905387639 198261254 655556288 429642388 842660508 772073287 908701754 554119631 529678173 326447333 272975038 102382457 684986216 928584769 685805600 284685694 906756558 400298952 521335876 810117554 651524414 989413457 177333009 429114651 944310475 359960788 173321674 561713780 754014384 755629206 277283715 912569268 856077666 101971888 277201790 519571645 835752941 835832741 218043399 456701514 675707267 984375066 60479000 767286451 594267014 772172080 938436797 55802980 111992778 969452093 340689466 534146254 729372987 809486092 911775496 225576309 119096457 101189935 526041360 181954313 681308115 503756353 413144113 850521642 333864269 544994696 793157875 781604657 29091227 23780203 364531358 182334901 268612129 445279884 664828118 462325794 324004623 974005961 610035517 701834105 768626616 59753989 832155870 9140905 35448685 520117700 865489202 777039543 395410164 600516095 926594394 955203576 381855429 301979042 862656372 654340769 430184216 708104160 786065342 218516952 885263458 532912818 468916304 838280610 487955843 460833454 576552569 14217784 501679404 460378823 819677206 333020537 364855523 620951499 79254158 514026974 197468866 916789847 122582240 287061674 730794391 862520680 544762957 514126105 612838958 958681372 929549492 995811914 414028792 548243190 884122356 357117876 448484109 77895015 299685874 107746202 840275347 307327121 212111241 900008697 428853949 528579446 378355105 672425055 932724769 841659015 99284120 136408398 158653178 19742193 571440974 353537333 57240464 108069461 858881974 404676738 806617524 399858755 6527783 47779064 633030185 156162535 483313596 392027166 349614505 508679165 736139151 812312342 216645933 538309173 135530007 540117104 447442483 446609361 535401667 602714817 885196202 327293876 181843959 546775773 188216215 709683519 322903111 869728427 193111758 349961762 970516154 478905994 824731902 438290271 558562324 61909489 886258251 432410340 403783011 915499015 458583144 497288433 733758462 223941000 164258390 463869510 674426940 314106351 93794744 712377574 390427954 786490790 454181704 964237044 928187297 230106974 680702667 373172163 449527727 394194281 495096063 485602300 479445065 475907869 44374572 310935117 338030776 937787847 119430333 110902403 800343320 541482893 163961286 256176235 94710669 777113577 952474291 649798689 596434479 759445108 401660112 537404373 392818090 862399530 786545907 979225974 908709207 630108765 169983178 901460660 629104697 665239533 983128980 982122411 12899175 914484581 515569464 339299271 317355117 413141998 671116858 195105971 713853946 65999155 25410509 715518555 543189401 627060098 519651794 594972409 452153788 217734903 170452194 449110950 260433814 668666343 226278257 294728133 873276788 249252235 630135064 242765391 856841970 162487253 424135389 190471897 409804328 632953811 513744967 483778865 640916407 643773021 805326554 491410480 511640279 974222747 724589895 390390027 48371943 872642025 628215206 496852785 303240812 731819832 478652862 956619430 499431675 677588285 482878224 458200267 460567039 600694082 716496483 981469694 858915847 968747626 457136185 882094350 753223608 675790200 994666825 481623506 262874430 170665500 912941154 289372862 731077234 918328944 681710550 894867717 761371333 590861602 205737363 185873057 149550753 328183790 415322662 868214859 82635106 686330636 358694014 664393990 332208615 480800125 142900469 754603239 30368247 992507354 374012837 635099417 970931322 398530139 385160629 218189528 240113926 433172941 243352738 29078219 920971525 869261552 62080573 472827893 511385766 623924902 132808386 440730116 404695751 70403727 55752362 887299220 803710162 259241502 888852929 110719638 142996716 96765882 448464598 285525049 204992523 985535662 455882525 695052750 575410099 182983412 796222981 90174372 235674355 260142053 756546327 315430413 50533445 616449026 787634630 572206552 39371172 413505618 662880475 539877023 346078023 809145303 246862228 504517539 624624254 656924948 542706802 367065645 638660411 341600411 44655677 847260063 329708768 37216428 731637979 872851513 387254084 218010323 18314101 91527218 200128726 57291952 973901085 573054794 824123360 429406110 803536879 409953933 374184820 890597812 547679798 614989509 917457577 119873036 296025969 883913358 372857286 467562066 599289612 213454776 463383789 12536833 771696556 865731913 856084674 502464460 871959734 199191813 559486191 347459487 142317505 364881891 916910298 757815063 831687042 613786273 576970230 715103086 992568445 404537959 56454103 376338015 724621828 832726077 537814422 812983137 306493606 962293879 188084751 667260829 962445084 985117977 270776588 530066115 220492130 647734291 893055307 245392261 781822246 879011361 595685364 186405207 651388309 567277046 559766628 753448322 604834899 930967788 613839289 283054227 725382219 23957966 833474642 618243427 690024624 152861389 650704168 230069974 41228100 816668207 102183271 515701468 324743956 837503944 683025366 706106181 895827928 642422106 390996023 77190282 502576431 741762736 58204089 302894213 556418849 544614959 492200305 895778450 438293625 492518980 642629262 702528245 216412026 685942604 421840841 541354140 125292388 564071126 835802270 997651902 789480610 842863526 870973371 689827904 559931233 697227525 584067923 875026783 212115774 873344964 24507675 480537398 498229178 920902085 92602081 232353005 646008805 749780335 914090000 417305448 904613652 692644764 652734585 981208043 870182466 182022120 877861728 967086983 576803555 880779156 781129715 496882733 379514235 246473691 14243617 499643064 522083402 561088432 346134242 905662099 944141998 550961990 423369867 414649111 66373954 402551940 279439601 688775181 828771647 274978460 204305987 175296695 223739247 930950986 639422828 70355737 889794241 639269723 852914055 716037101 102320726 551517565 609135066 551050577 214293661 870894186 950266500 606982474 907189663 912047156 665654625 190620525 658469059 206792834 743370650 186249891 651979009 569987618 90682590 393259403 741113002 123791817 31875786 309674377 662763371 675139101 250263766 396983091 305436633 280996416 441033873 947548642 779237371 771927188 167183235 412535456 67135453 984203743 609002633 527059581 214009034 367288972 250196806 33377792 356194224 662905114 284469027 621700910 562333171 172783027 276467477 690179212 986266859 144523008 201722014 412257820 217509405 108570463 199179971 376268743 421241237 441776263 236947909 717075582 46527904 694729312 348430043 121375758 630525095 580951377 824815070 271645995 383905656 566804046 860487143 927424310 674303553 931531523 79628476 815683402 725760335 910416968 888225133 908950097 987897272 834953082 960062663 994331142 165937080 553316956 798178192 73310232 134098818 511631603 574422929 62828611 609447024 945977640 181267078 610252539 941187363 613879136 188190829 960798338 678510305 985208946 424095568 828746159 679063854 254622040 943536881 53578221 280980397 844255814 240336143 519837851 29302972 252281499 671535786 885329048 309589832 150386908 2339323 413435877 614035636 495553702 671079270 306189002 293832642 58104447 420940935 16968253 579366632 920930750 207975054 538748243 348092028 256181294 900167942 137908498 394883656 734111326 710480213 376809179 468206967 5529350 543408707 546600023 864331654 535083671 661177370 449849709 63537407 602213709 526071366 449586657 525303711 538746822 928266363 917210311 562906777 72076606 93766114 468607212 112917493 798481834 304874767 766676741 623106837 236079734 278093788 913063479 346750422 59057949 480828119 875553883 975976788 282808749 946981411 208331059 839376019 101985718 428401223 66841404 130643046 44098811 579987612 571888433 950582400 759667957 583316893 983058613 670100091 122942794 590935451 403743915 318152277 716523369 168682196 37962794 873626264 961169930 430882426 920174570 155239025 702179958 921316227 811090556 233563176 4977150 973594743 825718656 531280939 59429887 55222454 529781742 311471061 671507971 120777842 610180475 828406013 319280544 756833588 700062342 608923716 630712562 957249343 909921758 738953303 307086511 368839672 991027448 856866464 636904713 848678887 742062288 766209583 463370338 915878344 651355611 113952625 509798707 441378351 929057265 784311638 858919826 320732927 111750129 23203504 118379202 738317199 945140548 873541382 238776156 122933901 183440374 18250105 333070548 40689392 158827750 392836244 232336231 765770634 906456446 157261088 794790245 797823082 742069558 4456997 850497959 304636899 20950027 350656952 449634310 983049214 447922406 527953723 543376987 544719583 962865615 116986607 474348650 842097224 253675613 686500476 881978795 978932773 944302401 310873938 180830624 379634510 400742208 838637937 128793141 618923493 818688982 819023773 781013136 312610853 971480655 812252859 414318357 586072638 643368444 589309907 118336327 195395834 707170244 531992197 572201621 975829708 250395252 292392148 938088869 125258893 931123164 8945667 369986621 299748126 760746233 93008979 318084948 651818163 142039881 897757916 635469195 533790685 897728950 784348034 138039783 699191081 730234773 84245376 868798738 474374784 50357285 921659824 740048627 376365019 484798557 139868605 270674909 144518130 484417357 865235965 255708698 469285120 80021476 132143347 161918467 422374485 929355190 967410647 167510989 269270902 626672323 761397451 512148765 678428158 49827348 408903504 168109100 952379994 110949782 622176024 218510984 435564551 203227195 317337297 110218749 824104343 317737652 875390982 169309009 883248722 487032855 245507424 932040629 812078344 833721705 923227153 959312671 412757602 133134107 95568768 230240616 735050045 103077627 380159122 518220545 52179961 252363224 448918158 369255513 520199685 778936750 763708796 229454168 600349479 169555144 949658043 119152450 572920545 177635196 360837241 735198057 462394735 247829658 245070842 440796280 378699712 326441905 644627601 155464963 812878208 903114370 620417505 816577703 225657200 847500453 798652868 553682644 722811772 4221004 895897142 665731186 83328300 738225608 265754994 652924635 690327653 40056645 927328876 560163249 305945852 127101228 325948842 495850862 412974901 788729601 77206557 104350188 39802723 258827094 345439373 879478401 381200377 473566281 821809359 993644984 598061543 924121325 265006487 501760400 423732237 73472100 960973248 937939251 886182630 679919259 212406864 787420880 239480964 878614234 722364059 543892440 966180904 509480445 183259993 848563458 530070922 170083341 868139975 261104199 530406130 548886429 450076127 927540183 194899634 586893600 157165536 724228411 906828506 319008659 470533242 944466961 580969012 468414334 544847871 614137103 518917482 168380048 964340463 867015470 560063480 767037718 31971766 504029351 75190766 471226732 574463991 652413167 757341755 23258678 950629723 878381721 539464231 509895377 906379124 26940217 179169535 450547116 292219797 464013593 88453575 506608140 711037936 644611486 885928322 604432589 713685514 676310324 796649599 766318672 106322806 804759837 852654135 888796896 484717088 722416513 267149837 31607861 795217471 795002079 114381001 467667378 4301332 210682934 300972688 109286357 930279870 931689469 143551571 216820425 957236037 1978269 409676299 747344346 360781533 426759186 879428624 324880330 975438010 832372025 22551049 444535742 501038627 187988127 898598578 610428341 224132167 972912243 864413402 565808455 449879873 122322290 588969749 134229937 699717868 367325133 371888718 658172601 271634679 716293160 344643280 826059724 180998655 302882626 552578822 810396395 725908375 128599577 620292855 100963533 604441481 192283353 951250715 862921907 428242648 847246489 758720682 190900235 511726603 221255553 31074755 289544248 136533877 257298268 50239823 996964330 474695469 488310395 530747554 432482481 453746480 297179436 47072370 45885613 173802216 768031968 304609199 357904475 133631441 181147152 927535773 465399862 719961262 988744160 651029543 644541388 955223212 926125671 184407354 414480039 610684757 703462749 698767000 131957719 904162341 264230308 783695013 834024784 802040202 60617407 382992857 397491982 336417705 464553697 137455023 902700828 691380485 54632766 790086117 438708912 582272727 435095010 548142712 30915475 108809892 687982591 648121870 969408436 566222811 159153785 584599580 301294587 128120945 56173135 398133694 218663742 897726922 126700141 795520593 879647005 140125159 519450724 389772798 307728782 597418672 643597437 279454957 772138923 418802230 162775039 54817391 287476881 598837353 16392815 693187870 486014131 441490584 117335122 642756578 668394342 205142086 359062834 161479836 407565206 91490721 516270349 986836516 125690878 403203834 232631920 200202446 292202683 848401928 552665869 271697774 114285111 407574820 988296676 242766902 626958656 915179223 569019577 449497494 859382257 135096327 428080849 595801835 796649352 976647047 842126235 846879078 48369774 955996645 224794634 738248044 919370584 861975035 865635007 903346914 756662425 578465989 99031106 61027873 474370773 594342172 742601359 871573203 354060644 393976987 146810395 967467071 175213798 641637334 742599473 599151985 944434355 154582866 626208903 664374745 696805080 31158377 588468216 68974153 661985055 66822109 768738202 917838340 316965464 657163381 69882908 427350516 95743027 452062036 517625996 452038139 156057151 561616116 612715415 625097793 747532597 842569297 561906823 708091356 859154893 815402189 30621754 44008741 435776777 531549263 990380306 109851091 93549989 495079472 477371624 22557833 832643400 488662227 520210479 376006820 565886101 337858225 127578710 567695483 487220624 569010143 517347059 409799299 834240653 968539107 612863748 763229004 180524703 898585341 91045781 519803082 282269124 377513057 717933048 990892716 738370235 138579152 293191485 965142360 365446921 715904919 161040090 480328120 832120793 524566474 805441711 333095127 443590417 275117743 77376897 229804270 890024785 160216061 455842011 184995752 236244476 787076427 88429651 716480786 200607942 345122797 72753839 110485894 888653846 535307516 682072999 811591017 852903275 463430281 459542997 321722615 556477209 605273048 63435055 305656801 653405675 430273581 431786188 869223380 583749578 766989613 906729382 274225045 87497687 737289268 320985851 362668253 601290603 595778334 480279821 801514703 44467728 675592400 446079114 195069503 907447035 665721583 786141628 32927586 10478664 802428312 157697006 455032640 222222977 248063625 607228841 428603324 214166534 7696995 117127064 331724509 594269318 780264746 171052922 936821035 883651782 94119934 298411315 508684207 554387277 762705109 619948429 811907029 947400006 184661080 129092459 47905677 456478933 411941778 636517620 955336913 527777753 683799415 158821019 991238697 994674049 48244451 885235203 384727346 308913011 588859530 487742047 391246761 660918723 614234321 750798362 12288964 402436531 314278932 307126746 615199691 895333406 475217942 699983055 285865853 251667374 659849904 404392078 385505908 50287988 716953263 236354640 241111172 399369593 749971270 258501192 417818877 414811188 382580027 859260248 905349516 217361375 749142041 608499206 80879723 895592389 830953261 910201659 381644205 497537524 909495697 913022633 544083226 140432229 390424757 26153037 664998556 832085170 102384807 343673974 694315554 539648205 668954969 500799361 783407989 852013004 785733046 228381052 94469935 398599045 120199593 329103451 300747886 588399374 678922966 953533884 837126094 767930642 237433171 868869934 383725209 571396722 784784615 726876257 776408010 370945137 605314935 765090336 904539469 423223368 882979259 326377115 428036992 530534727 655612690 67246157 162630245 282474248 599723621 988268377 805160803 651355564 253464488 663691426 567039737 847263686 996545059 768416817 755917492 19832010 92516813 900923512 266759187 842726126 759173916 132652505 293536474 470131997 254201039 34614109 352868301 148469078 857487163 717536258 425511231 690627144 584044092 552978012 627099808 874681783 869870399 847045431 599732655 192296206 416120271 407325116 68168629 589870672 982231423 861446966 566032070 160645197 32628213 493478182 514558906 973814894 549951197 645525902 511903472 460069394 22198528 934278336 527748360 265890374 926814338 638239451 597732986 767864913 35536672 380754100 545955829 701553162 378022187 465419263 803896039 524960131 178781573 188621979 163853501 81964315 46121166 281678749 24757904 48860926 652145802 209311015 243329309 326891198 451069462 431636216 198000127 794892063 758598922 403388034 579440681 945185472 184649097 570437580 681851111 794257332 715310997 709764409 207333203 438832111 158915252 32215818 657562837 348559443 365361467 328446830 859121515 960590003 821588587 344196330 679178966 203211857 777993442 255804822 611212835 252670307 833246278 286838464 272639895 852113686 810549593 808703230 402050357 390323231 266952679 66248436 932791478 147215382 718929621 316331163 824476821 197247801 190863820 982511080 923476783 849033516 964184060 701932190 191932588 344474846 142581675 191836176 525139060 920896713 440424312 279122093 802018992 902338917 388968611 758459775 176104686 6069045 497393941 302913027 401891055 947445242 160248234 713337075 343315236 161039079 329299940 743545842 853488673 303159910 740067342 189780878 620449438 173235163 541302237 102114459 684568269 525130685 523764585 603413098 647236721 238914239 606013236 460438407 703458044 173139105 264132163 41431041 36518187 502314690 515770169 736661541 169707251 113596704 597290251 535852189 551104498 362103158 208004156 362483029 945578827 5891099 890145729 837076759 949273581 341102491 277249768 759076673 318843321 812187655 667466558 825298982 7963346 611491915 38980474 192849485 9341440 640227056 976799496 860344862 579321264 876520936 768125596 631008699 888880892 571831781 954146217 642145757 899273456 936863682 900554263 496227782 555172480 453614548 909617269 854933565 388041585 516440608 816433701 706307339 812814014 732521742 127939945 632472951 296231630 943364475 126728024 877919901 510153426 93426722 188273026 229633731 35678235 301994799 455131022 879223674 75091330 501326916 444303802 199279100 308269093 671339938 796504629 367923441 909406904 385154286 537935981 523819603 632382271 85724717 24536458 200729149 388605955 730791709 407857576 771873462 509981837 97170002 938237665 526402367 396745719 970803809 737074620 613242734 828526191 106146723 705714757 912292135 375465442 642603134 456828491 676150160 915145324 331197868 559535533 803794271 393769694 224090914 269981180 969504330 891144724 88000933 345147548 228866814 96531150 925367923 107529468 772736130 999624282 489654849 650672426 967707117 842475944 260921511 185000798 835003927 125507122 373163507 287250627 814832674 449106938 895358233 879859758 587725594 369382843 741268602 190291898 37705626 491229030 804634222 501756440 567321396 696504503 415997802 175345450 294971538 552903623 613578483 92323688 987318064 355432744 270140149 973208273 610203027 682032945 405516923 248687797 824310782 169555328 242580869 414833518 877718897 957781642 847568515 782555920 750946350 663762442 281467037 897147217 718174366 58094540 545206869 702965018 39108430 672664767 745962656 995498403 965590675 462770244 573389175 263307421 914475389 520328354 650812662 784074618 43848184 221026776 814071221 459464527 416469097 512593454 991598456 849343484 584867304 886707380 794821206 897593397 606771908 146736673 947777653 58773006 844465307 566984061 441243553 787455382 668318114 92556995 261236264 9736381 246360184 730966868 112281918 377447473 341231005 812169264 973950708 478958792 848254438 241786248 623184491 801657797 794447419 19107482 564086794 295072751 110825064 231562580 997725858 162216986 281621914 537576391 964894947 72324619 879460575 462621158 603061967 233502568 436998434 417250945 309877790 475330386 167152499 422210989 614488736 319898246 461882253 782865622 69785414 754438376 535807023 123869577 684777937 668786103 48439605 653464779 377357027 742168158 608503149 672466233 656520803 291515601 177863055 824506428 24691203 67671820 920427237 530996078 490171365 767589330 895228655 658959658 862488765 915876214 280739085 911700841 900427784 196667369 264484971 589505514 494939000 516778608 869012229 206314498 482596551 945251307 227643964 505352718 582363949 123815742 255446084 99285547 443103748 433663762 993827241 131473268 104117085 61172115 281090526 334969662 557419276 446529775 633315339 755054669 657285513 26047449 519165136 910882688 358313544 897929120 500287357 988337589 151417651 433478434 123727044 916965559 647405984 569024585 468276255 236307877 223190450 169085854 389768017 496891042 557805888 529553911 700074910 620234278 773540300 22487845 283366301 899085200 778716226 545261952 517274083 284397772 424289591 554158337 154711118 550599977 729223460 188921400 955719009 535328143 852009397 23589555 831833154 558067805 60348468 217820108 663794954 78097978 856887181 466222157 196005127 718846302 70414191 993494134 973954067 293446537 32262508 714905158 656703164 379227305 827206210 552016531 355456578 313443236 691684366 470704553 847166030 240646593 239830290 16214605 406621399 65557531 815634512 382391589 303571762 780032476 817108054 470256020 734226364 337654095 705684595 192002425 999347224 667565989 38362541 980137153 102629086 899951442 579774645 942999268 84062674 822186088 976792942 559006609 953826083 479607687 244872237 51278833 901371698 783175569 986530541 569935465 462804894 682890072 549035548 207539868 966067276 345870137 519883538 709635117 422554071 534367982 134201055 856454682 749039249 947655104 435412548 698447571 978372216 228736475 798874854 772274860 624233334 788089355 936569749 640379231 506407709 245733097 534391073 101068606 435697972 310494032 684555712 233427678 794145058 362335237 650950058 568280401 730935130 589067099 257162898 671906846 866162490 180311598 659490961 347579345 43457614 275769350 720383284 385403118 620736033 887584056 123833734 600431068 490969236 665825311 453802543 268445863 741858274 21424453 401764978 521306223 939945734 496062589 553117554 253459813 388224847 753280174 862315042 467412647 729815400 750829088 363347304 41612719 360904363 426359228 576993860 520605759 37111261 992048013 873204188 61843980 749060018 66136046 49222675 55134814 831651973 195844424 282266722 694738717 114214301 370954631 211717274 94488038 341885568 597288899 709393771 328784104 350842604 900385676 336294993 803840952 452483817 272432191 887388118 660382771 559757375 842011159 868090700 890232508 10334483 342673081 976020429 860752346 415840624 123465584 347652254 525369065 281712497 67125091 402455526 890685405 908477547 453014333 198925265 224296264 2534331 559952992 22290141 280528860 654175388 696385695 56258869 177536145 174925067 71093151 268170572 596116869 320139121 437943082 73008568 668677775 794098615 856896388 363627800 125331292 689686739 911619824 593775753 468694390 948687987 210074669 609322934 939507146 10661173 700995804 484666161 563972791 739748560 964523544 925638706 584812861 903173237 777968120 931440870 40745677 385829149 295873208 286950365 487859199 867945104 757770344 456438919 465916002 524523841 133535671 327515709 860614854 578596240 669259168 264942672 905359132 301999262 576893007 217503429 110078469 68623920 160293221 358377514 853191252 80189554 794436820 493608693 783277693 859322517 796903309 544119557 214741931 343860979 9325082 304555715 932504600 568120693 189853578 89232278 140252295 720641131 754378851 916980683 890782392 481874108 339547981 418479485 500030855 998213300 820965237 399087376 812953335 73728970 522087252 632529267 810301646 887117414 305152669 759420189 89958470 933120898 540340099 888325524 128034570 874948021 525127910 850008323 238179028 548247180 862108245 810456972 275898558 316469374 273767943 8619199 747188852 332958759 606154330 504930198 536847096 911319958 806237694 229818275 817915681 193321716 683312676 915310776 249684536 866378299 811594968 992899002 787475933 98025989 142665859 596725599 37323242 157887684 338492068 35270084 41539763 813576397 47078295 794492000 702310078 669158627 208056541 648208504 363107212 244522157 215171563 742809024 647577949 264143699 510625629 491576887 503663940 609343358 624506116 106568526 400198020 922109634 314775743 102846203 895750686 21160728 670838431 548462699 107365838 692256657 729535828 927070486 214223483 713492079 354671401 275470466 983614835 592365301 757175145 602711154 402904035 779929046 606632904 939433153 401434746 20947420 301381565 309252995 891524764 278919473 94630525 900726646 491090246 378148298 346052984 325379717 224764368 622747788 395414108 737555399 301377610 4056109 789495658 714236998 872389047 31152149 291692088 840282570 256620861 957767807 561110462 110838298 113070966 52259474 290234372 676263392 255774368 985067255 226851897 872495268 598329964 122317476 690795956 119008084 594109185 993932790 672552674 941011014 289041579 422153491 629715123 691906714 189800590 207420405 846050300 761275889 78885444 328881084 864573580 99202631 425080068 734945245 740505410 943331546 739691180 733709797 651198001 164900917 87360655 539086150 94937581 67813038 504048353 330952139 26907294 388141595 859303504 974209564 389621692 300573651 306359920 228091562 968889563 896308218 594076480 121411678 559392359 142109233 165459186 8692494 959191284 638901954 603603617 430497217 676609477 710994006 758733269 560769982 814737017 767178750 195367072 224349823 728708400 116354908 191745829 322084672 732119974 311958019 149529263 124692201 342229142 55961752 257147271 801497937 724873869 87868235 325088252 104834321 816217441 997294338 807688302 758319125 596580275 368919515 399671086 327043940 654344071 91017457 711738608 27360260 364372071 525420776 824339344 218586490 772968679 640998414 275221872 188081135 206074503 343474777 235337884 641293513 812905973 982877762 26790223 755212531 102196337 749182313 380931488 57509172 711805899 815379513 421545334 342111084 341562149 639471222 371348569 741366277 801302034 397243239 18754809 111553205 938324185 476511824 716239558 789611306 839154970 710560051 221134532 230120431 164966423 335011356 180494181 583551614 1094293 180016292 34084327 885014847 893550936 511818662 194903003 617123509 948461979 980107576 656173503 647986325 551146496 952363307 715675455 816171414 998137468 304229834 26769290 2561017 793751683 434545119 265335292 462301365 535822009 436371182 93056774 417134924 934274602 6331455 506106652 68503029 980253683 483134725 913525952 907595887 455395506 853526867 493525107 734948917 751578840 289276524 163453502 402647498 712499072 758864865 363542015 694524586 164781296 298263499 775528681 592614464 53918280 493058067 648051622 168501011 224615311 104528490 126696911 848952107 185927681 579587672 261827796 976556130 912330650 768840280 403824209 373113993 702694604 342260716 289021227 721754029 655688137 276292441 134767418 933046532 637964238 849017760 209112697 721753865 619233451 258351148 384531457 900768149 280695395 890649835 857433102 257086259 754553435 626919101 686272873 220015134 343922373 516102513 487371965 783244923 872945603 984505799 64427938 825896894 901948219 929254707 380491945 683819517 918111044 528812363 107544479 696505050 848142868 912355601 380588277 135297671 808958049 704638839 71782882 872574063 68422745 207634894 389237360 14195964 745382828 782827121 132000460 460570698 644313800 674253589 65504940 625673277 400122935 574501354 684984903 844717858 534843888 999959172 20139270 978872050 961953449 292730378 109312591 234961649 639414229 683907630 13026262 688748941 491713634 770941002 445840302 296486221 495687702 810682864 464368458 215492167 42340942 228629419 780542553 264412903 423993748 188140479 98573042 422093570 594617954 872753290 852167074 29616419 701082692 609172785 524240651 365239428 264344937 564566411 184330919 389222158 324291983 378089753 556490625 479209987 663399272 983946030 809651207 145172676 535127336 937584608 825256086 740890933 448617370 778784562 223373398 790727321 545177881 772278379 613707545 584626966 9486886 886749439 405111516 413821143 424876789 330134766 638668528 699746727 491698330 466669308 560993194 952309346 991326579 481222182 724507925 359707692 651826807 186549047 492832582 867768542 814727038 46684981 972037497 37537820 907112167 641019859 704542250 358690570 906673718 920860370 204281620 787819530 56961005 402968554 924789706 547731929 343879276 481003846 900662796 532383484 447785213 442140757 812597669 730121522 273838912 473305234 852386991 978873933 754789394 165076085 902339559 705161140 378535609 576044246 623441874 768024993 128417154 321375639 374189682 567449685 15634415 822495480 20551212 365122683 793371011 626229545 207248730 370746209 697494413 689512460 803657217 206995467 763968326 967551639 836421433 139355447 3069807 901123790 239928796 476384420 897639263 819396561 158373644 54800288 843512941 691830068 207463100 903842111 410618140 194041474 727332075 277240341 574284933 723481343 85121813 537883264 104199383 488892633 249809377 913282961 686334971 60293257 674269975 64111038 322226887 225559022 707347558 825050435 815265604 525372438 34557314 975417797 109351555 585850303 801118858 199687222 665964315 282670516 664731305 15682068 278629349 471199253 243103860 491312015 172769973 444685480 289803307 96641019 392559186 107909702 817838920 819721320 551984850 214254627 50135182 709999296 911743072 402198600 353110057 503201959 215901679 870835580 933265637 153333021 550213050 185668828 509707501 717170665 12414215 21111899 501572687 2567446 496483146 92735922 80316142 97064403 522040274 868126539 625053198 514274017 615464884 73550771 756369530 122358992 54298712 960905620 580321770 565175192 964190125 289208565 128435221 995122845 277829775 329774496 929106206 37895224 508443943 470157053 402530256 290442781 754412116 158018365 549496272 310452740 5696220 207065218 783016607 148529060 664680564 719791026 753122213 412597507 355626821 912646317 71263117 460037602 71617988 491116290 909449168 519985408 433750779 494931912 71796347 65472204 663863199 972139932 160443659 861520330 16347195 812902009 492898251 157900704 751006784 822161838 750771120 780194434 859746630 522966203 877676540 455922097 762713944 549299904 324492251 480860069 390161544 983898627 759809051 438909243 973089930 865396223 72164315 344868124 661757236 615561467 424093915 204436065 402911877 8413965 209459127 865301835 278042530 276796766 452266692 302378341 436654563 844558999 636044450 176312001 703078706 319176351 793772749 804083862 855957538 292777096 117001793 604618123 597607986 337779446 763957504 685082888 771671975 15530747 768445125 741008548 447762913 421960088 325766304 198242634 524362577 528980836 418010781 352639396 738121756 630008741 649002830 824313197 689093707 299384719 179081846 6679717 236857351 708010234 33127926 660537344 460552176 466935692 872671511 770196112 465319206 644407148 265088558 675961311 637033039 134073948 732456231 326769203 490866034 356033925 417953342 956294768 489456223 649103665 613942470 852442648 879568440 804981445 517180975 497819520 894787744 730967411 452943361 565854147 862356963 283089672 765458631 866321987 217686493 1740457 117192911 30710819 646372869 103921763 118244013 240995792 385100318 355803054 637407983 128336564 978804253 44145580 230405000 763449572 546572784 310791188 780358855 927252863 966937604 360940176 756091329 842961463 352232134 534957648 734108414 840442159 838194199 930564046 122376354 387560737 16728203 475108449 943474037 586745144 912633566 930001771 954025574 747932565 731544330 978596090 956434232 425320035 891061043 213828785 996256083 14663208 535817080 50736440 975177482 748085868 497118051 843595705 932272583 547510895 514141129 945530304 602114704 311456515 574232130 126486418 545719754 107460072 581887290 211361457 468732930 365315478 396895414 90569364 613994079 611674901 352092148 243004062 103896659 776515553 11904041 918248807 834836132 765744748 50153452 906868357 308248597 96303521 428162557 714509769 620219904 642984718 688729655 115115104 579464827 381206622 930689633 181442179 621833232 410537304 369801824 782726392 929795733 413471318 664804605 958709488 640335583 352660768 949594707 510404519 488504382 308548190 678175736 22795504 874681089 855723820 917263614 364554002 737424832 966556357 942024781 195927429 570476388 893467501 892734002 60142220 696510758 297267635 272535133 408221177 444461649 857386049 30122023 75741730 531996488 983880829 20846045 773781188 227410806 877317131 264676298 768388729 998138428 220587861 406184947 322582694 862614483 292129925 725122293 302819566 306622203 222269462 105895412 523685264 921218251 276925076 256801636 647878915 176103540 993822046 363006541 172731331 458364360 833671582 382621859 481961338 281316434 926996441 610336169 762751246 441218896 951642664 84992984 495413922 903907507 588150509 2575002 107233012 653623827 894471394 788738323 496349345 911308414 62956471 975179576 643647308 327993753 44500755 86852066 371998657 176738741 560017029 71042999 937725163 349518102 290556941 379852273 914862484 419252171 821861274 360126434 3078378 186580597 386406735 541894169 668285681 971993620 326329421 301298120 935045801 687253673 912384726 602445895 105911926 649518136 423648128 947215111 299009461 118984224 847170539 468445130 507845107 681012019 985175585 320323378 205299879 565031163 540283105 668178087 621675928 457285530 802727846 926602181 460703958 510103685 167666908 764472228 115067602 183748032 986556073 499205967 734323038 556657845 710725686 339855268 876353291 743273141 524683338 893207400 740358667 552397093 324615789 729687456 208377560 123683263 191449265 360539339 228285312 25878571 634477634 745963117 147413560 220074201 46699058 913431717 501737968 388472437 815732829 480969901 961361047 840206606 819168198 795780821 676391578 440419904 138374811 187662299 761463538 106925845 738030116 344055876 704528432 869470077 967613540 961849012 773702065 808081107 347376042 845679298 670795765 798120101 104809000 126796291 860741356 171761996 312093181 255451209 274691384 939118875 900432212 77660051 804701968 401610817 574251337 513405922 412291388 370990896 803049739 65844386 652470282 436401557 200304316 246357644 900123710 54760150 19313116 692974279 852391233 741096547 726432419 965262965 545932450 822653055 521904808 953111072 3349647 101319962 325656029 732217217 993956462 128498686 428340613 485018082 342281431 859495296 592017401 948981821 118014338 990581521 742084266 330392816 708923442 570615808 752551856 767868592 890733625 548365871 582676671 162002736 296832642 17812152 596656675 953564467 403137298 422772187 571082667 575376627 758527593 602310248 985962138 954735034 132528601 358589700 675882514 629605508 475779141 815815797 593616739 292501071 484082634 52899301 883305456 562618103 198074220 223653864 797454985 487645302 628855803 134083405 141186496 225157657 886589782 34286413 57394119 442773473 871083189 216642231 232272788 67749474 825740350 881238155 528862558 154706182 643921127 6297757 183134726 645236304 515956042 74117734 838173831 273346924 963321245 184884975 145921837 912245029 940006238 924152582 214425938 777102475 677938120 225630801 346785010 801463823 254725788 787389689 227123444 789598943 527419866 605088093 528893102 266488871 162918284 611860955 736423692 277430970 896522477 627428430 518295771 262392493 986553177 856273352 979295585 596025750 814222010 391207205 414713294 383449063 508720636 778134895 891168671 325749741 944443920 951075912 970705515 80511003 604051251 250594057 410784978 275982319 405235418 266648604 659464296 737540693 462443444 920378365 833465667 172748848 366286613 517658465 11579270 633962304 59550619 230251792 807814225 817142334 798608174 153764714 630498157 290904641 89198620 411280236 884849838 466189467 359075954 135598362 590406539 885622968 446432379 106495411 142036016 809583647 931029599 973115216 479612448 511652489 129984032 763478957 957875195 513863378 107238209 272380641 725340794 460795598 24250165 694836651 301843868 341063376 889542694 238173338 19921755 696169397 489850946 71108623 728030434 171727776 483969889 101881846 305593685 356330309 899720680 245515989 369352600 362565218 863365968 790012848 138774903 887858794 126682410 128592622 285355000 328508402 156600112 445876186 505751385 281484933 161034410 982228337 124421457 950733534 893423630 131201257 279446962 955675216 504832765 676681464 78092766 387535205 339149237 132997215 717027160 384637014 284517061 304547267 245586065 581074331 239993169 1035154 757821132 559314834 939733379 923229405 129581340 300153198 152038229 725677735 563219728 691440789 957985697 427757234 912182170 705432160 263813812 638193022 527938560 934850383 42787362 227438579 195554676 789096441 532996171 479989861 235088803 605351136 256716298 902763090 608337242 397990604 524837114 130458210 535555042 628763523 273023755 433004901 658082652 907241616 336413019 615684716 855024299 852706853 117211548 316052162 719379168 459731050 147622361 785542158 308432868 676722335 838902082 883019833 129852877 104887474 452115106 809596064 359555722 729417681 736862206 486015213 641806623 767338132 185124029 698671867 480838579 605577479 985549617 415930020 54436583 49386745 73118429 562809513 38533271 573802717 643522681 696848881 807035039 979921429 983654798 304932962 79322165 73947484 356759367 939401655 887722393 454288042 313589861 40686699 178425587 698979980 19331993 41444028 475017434 443427475 447599642 673550522 629264068 812209619 59972505 677539275 665263535 401938101 90813356 551475826 731231449 996953315 919051784 211111437 344743135 44410832 535502331 919821603 672449716 382924742 539123762 102899256 53720653 286537507 97805676 99496300 190701292 179971654 841337005 587780121 79944415 9031302 30953245 975581944 90048247 499901416 787401967 531281635 652784671 827704468 416824166 873500092 878318733 357461644 11794558 739349720 954765731 93215047 344559019 208221562 249978465 764813479 268312937 453812647 764963665 360027376 99207635 675565870 153211579 537869579 151052057 931378301 135398026 286923591 855981244 8340869 250133783 292346452 629583382 369878916 63706933 763144372 767763443 316595295 12232761 377785035 771975897 406052747 834904343 579158339 116418831 688309629 76004373 252100443 358553694 887880270 366885872 997135360 290054121 329706480 374557065 910030312 757687443 198319494 551681878 953757061 896456619 512457020 310284187 103127363 4963537 521970179 686593313 258947855 234097781 177750847 781917781 42243002 734460110 956064661 58544199 614168565 784257898 226473739 98878725 631380508 908844633 309308384 205046186 320714077 140834921 397656492 69173907 317696414 825036807 720135497 826289653 917581266 458110858 875313326 515624139 773264391 723047698 540214447 272234875 853356166 65304646 122207517 675824073 44429292 258456212 461795418 477307463 906917165 312052957 318683066 724026105 407006697 382721370 616971916 13974939 916545595 255710305 241081620 129125149 379625123 753781667 885515720 700961439 117499485 389748784 168395296 861413528 36411613 47705621 12660928 703404714 860087058 290731857 822093420 326756794 491864822 735985017 15381402 483378109 89344721 807705015 532191312 506156161 70214267 179570528 283454905 500409111 280772978 403497485 621507374 295692419 954562431 55714866 370116422 695998776 471463791 26958151 199988279 823154688 426994082 94572511 492255340 258490628 852043071 468597395 524331200 32938052 834671463 476096915 507081737 237301932 827796035 785222089 899469221 796118186 959492043 576278865 371743167 585767933 350308430 727490009 318110247 866218434 488704003 512969020 733507587 514098092 269904180 899904451 128508842 301246462 997556462 143558728 752655963 125203525 739434853 787820701 290559769 91245635 138358607 983477592 317013025 491319900 634045978 56599036 395496493 100214934 569505370 799507264 506918071 986545208 988104525 822516072 171619317 238296995 514689798 678125505 709118939 199784233 527905071 308624065 696298272 878306680 963887521 674507068 626968051 699542330 241446562 829435740 196778827 315674313 963268351 589635655 607778306 940836852 343285017 201563910 334948837 950259744 556998193 214885475 87905286 911771931 226486383 701215266 143560714 438497064 504905621 280670141 321498172 301835731 290168313 57928417 882617563 513285764 499565903 730118833 123566147 136398807 108842483 671270155 440425304 715850032 882990601 387899567 761415037 221282089 773904580 257099664 513369983 957823813 347258402 896761526 69902319 110064545 564267295 791775296 288919649 384894819 189754928 480671095 947146103 348393236 858300946 915100533 709631338 386180814 968877633 930228283 772706730 865109749 922554885 7253785 660741306 263826897 277598753 928197460 809661861 739665614 330992154 807790838 956587123 286703581 338823582 984100644 358838767 463818258 263680505 990838357 719613708 759097266 312416032 141998812 310504082 725044109 624638929 487627439 934086050 892097756 548422216 286765696 263797910 477050783 60989792 422514283 575800710 500150917 846162377 799485071 850656450 417809000 492802324 384498737 828149000 646340032 596974904 766056276 22786000 476723986 484603347 939475601 222768160 637991459 904255249 456335460 690434924 998951384 945325525 27520567 53419042 570670827 168059463 687965750 419643256 319407688 867571784 663521367 593514240 457675918 123215337 849436831 656664068 542210502 191106337 838601884 652121554 128269962 89136900 889521711 714291994 798765843 235593412 414104017 464349570 706541918 830716078 694004631 533166957 343172332 247266950 473342630 332630130 92829713 194378394 189651694 131647960 436261491 411463769 22836009 668299694 559604711 993745669 868593906 698521748 962316810 639495489 480519802 72652360 439610472 315224059 251317511 537238726 335934535 181839415 388004995 525907999 216167052 731244077 880541441 452664616 21169663 220598094 183537789 620327195 37205083 197070809 764093299 696738186 866920269 23513256 940992988 171892826 905080355 883318301 670145203 532104290 348023017 925987680 71742710 946496879 842796543 392903216 540046865 82676238 894684277 755209146 342223750 97950237 995947675 723504241 79100464 837566528 620280848 459381107 728655362 718683448 905531302 300013545 369230471 509838688 884008384 597845720 89353763 440183921 26177364 991823399 966631745 732332817 291045406 787400802 123274701 438307375 14560761 582563334 546763016 331469218 716350530 362992817 218720752 215096890 383372944 480061641 825721688 955576435 644042947 631569105 763666086 260316855 834289407 723507631 375596530 243950740 931177020 828260399 485949379 135872685 206883863 450152945 429617204 670282307 568688071 537618338 810274273 190872903 697259180 276986119 86036485 638723673 444071521 103513655 852682963 969795624 996794458 262978080 762501710 441755537 202402799 54104578 211869541 235941209 247763437 106510607 955688245 780138969 11013607 252842565 8684015 274943167 505339811 449283535 72392582 475811030 662548165 440168003 333433789 741087456 437045415 977418174 818468371 622576709 590307902 846424061 648906809 444229993 861950158 703554141 373657199 786185930 792612811 249188932 398019761 889958083 49576911 930573389 987050976 520848656 91597388 569315053 806979194 28678849 536638691 715923589 952637598 556580893 841576159 672149165 420260622 855480044 870881547 28945270 959536119 902357762 26509196 479995419 313766550 66107 512146944 918278632 102325162 991067559 449008316 801817767 618684893 564539174 122158602 946265485 42587140 671492789 649611434 413168686 612454737 188905592 686811683 749902102 537478212 122111810 674086737 639587574 477840478 987055053 719446987 35864209 632918562 43797833 216198954 918639265 833484231 332153233 751445084 9850570 941616636 118386546 763500508 648247460 154221894 740974925 288285180 647401506 734130248 191830070 812679311 690042294 275618281 718774637 371858747 231790986 699340636 514102561 419644952 567940426 81082353 454794726 694466407 583603356 918185490 786709413 789256702 858259895 995450696 685711114 325092852 955485411 731693224 21542260 937052711 654479749 209538575 689791262 950597525 471261200 7606286 674738491 517277689 507230196 927894872 302675153 531173345 572041466 112050668 193561809 578180201 66974191 714362342 668603593 631422791 542665485 687742373 429592709 110035792 498110575 68462445 362433747 930599516 540379970 839603795 366792764 829253512 458983113 207125245 476041905 25117922 674656085 4639525 218615351 62513750 794194898 993038785 319614648 597603885 13916982 908057713 641168906 43309957 355696209 808294458 892997768 850753872 463945741 620552038 226382933 71756755 835008090 166389866 979795385 637960725 811624463 930166779 111646824 681426292 348754526 681446247 818246173 880524543 151415768 837034432 512083920 530951912 787010173 664812223 570502025 612434582 111096601 753357505 137394724 457232181 857619111 549088944 998141728 376370736 767915114 410693909 868531279 266694977 711900165 51759281 818292921 70963453 221864827 984374213 129794905 144172960 389593047 313983242 14096776 707902743 229891538 872410123 985487969 532739601 850959226 653525280 167194048 450052473 34064345 415462474 273101144 116326528 243217195 997191163 660739827 621601792 99134131 238981559 435725883 952701192 858934612 890816277 444027335 486645436 901134964 77462716 673540760 879568466 333374298 153982543 719712580 970752112 622183356 367579321 690030612 42699373 957291631 629167566 452699676 367065681 973240249 930700776 465347892 971555796 41992710 39394031 273358575 573489258 321315526 829849550 810660263 315451411 214428428 241849275 295078858 219905801 468128121 487841857 240480961 672893354 39644679 4013078 405709670 894261806 605619433 605339667 421170068 846227863 488108899 319660861 471984156 477788904 819734497 566121773 281229507 998566210 548144041 443703998 255982495 543652403 484113714 791027722 762615941 989218667 170582683 581730020 472337730 471477784 341489368 46388981 406520566 318571830 6052132 248737444 986564587 914729527 244807746 339564900 112774838 275961566 44273374 860305806 60338578 549381565 915025585 913637623 967766466 827162253 487922278 596982892 535319400 949822156 587720116 358350529 541486815 395457533 11444171 520752925 297167670 441174697 677025302 403461598 574037322 233639764 41260663 201118692 526510478 134982875 43141007 653722303 869194044 180894907 347789204 197659564 499242975 338809575 683622735 538446318 977318440 821305393 170746258 318373957 784854 327332426 715757103 477547170 932825200 13762274 15367286 527983984 101995758 415448126 440019919 964388131 964070814 40136017 911624320 825085064 410467531 282269968 601716346 533623021 885539887 742528406 786254307 340467878 839976579 874386288 509278223 3913584 210255662 445714556 609146333 302000864 595911042 598420107 244603079 425904510 996061888 329497908 985576881 420417090 984790543 674857253 553163376 734230512 982944950 711013553 821369144 383367056 422273740 336179171 713081564 962640474 812739286 427759713 694778293 456521576 859578230 220519423 528684671 123007021 581555094 261725926 994638180 252820729 633265639 810751476 997789678 343658606 889589034 852320918 727295743 758058895 412678297 127072181 404179898 479767602 366739562 724890453 220655790 762769133 922623733 343032270 314535711 752676148 725627126 617010765 262166178 511829994 40405080 829616248 956848561 365486929 322490559 461404776 723505975 287090342 679123817 802254090 863225905 935726826 947865787 527481110 707160933 699734477 584581053 15456295 826534187 19598922 928282489 440671979 821012165 470443966 28975706 38691087 854842159 714829554 42183859 377769093 389473476 46749441 351145372 158329314 103210763 131349696 908769480 784816271 519108096 857519369 819068895 586542175 988334640 436104851 311877006 917847193 168733801 232464468 906270831 613366543 956356848 576961012 898949634 582864857 620944456 740561343 119379410 849440442 310917992 699622811 55786526 372550637 623778496 270454460 297131560 350374012 402201705 354691399 566125261 635987746 480413724 732277071 792575284 369757232 582316828 373047198 927795448 540770290 388528754 527767250 880126006 630064121 818391645 104431201 107515487 465240425 894535361 765607482 736650440 682142317 35473467 594072765 349188973 276584595 357735838 243142894 967808284 973304145 770454555 196296674 329684089 67960521 666450677 936878314 352046015 353758650 379376488 790413407 154873092 854408626 659854186 914387166 295963933 256263223 565607680 609298454 356677350 934540744 92238753 744809247 203124887 143923316 958606907 399613568 326478287 821717268 918734094 961592922 454105146 149849835 407056600 314183285 808693423 53063622 555754429 455962435 677472346 523714819 693659739 320736470 340037105 353104105 860542203 36613970 72938818 400305450 884677177 974400171 149587775 222674769 443571356 31640415 207484690 718311166 493322712 467362166 719738827 748607277 511495892 58585598 752996937 532266914 200449543 879924420 722269459 382582941 336934585 394641503 724587588 771612876 455950579 966635222 677155667 683436827 952201348 477295944 673245784 822964820 178407988 285587190 754943684 387454128 602470475 335270862 46573313 46285456 517766589 534640232 558043473 774120191 163761974 368126278 722635439 369428802 718802046 681114136 463822610 609404097 393061797 691035891 363126974 991022113 603324628 70337169 478546572 76200425 602054472 597233808 711236723 874667703 622242244 23639731 895524319 474948508 68609235 77304833 905568362 833701242 198187439 986819786 522165459 875748624 778611323 980558150 618507062 536232671 30667679 109885678 33669580 453788692 831754635 720577216 256318342 607896729 809846250 734955522 967616313 277007068 187902100 702140902 645551269 797446628 447783608 840959091 223455353 119121624 834346242 904320966 308008409 956862725 197804100 810048169 266060517 495711822 266226714 542521729 374311645 371813227 454257364 434389611 440204102 65693578 534270728 177040951 350433279 361559545 490654745 503490951 879158888 408311064 418311858 847812055 814424363 345383786 450464224 944506093 711297454 328769728 652676745 808897831 362393394 696637559 256683705 80592681 208847959 916532956 923550729 784340856 577393520 596234819 482284649 93996531 822011839 956419765 465856717 653608888 857303833 836404950 661467120 641168390 413102809 406755468 87680052 142533880 282657030 802225840 791268529 506300503 955379583 843812432 74722044 701795793 809978532 99303155 346235023 261159504 157873830 979896254 196361560 882219454 51647342 811446683 6647045 355307046 498895229 411642215 119036087 702377280 720008747 904094772 448505364 428026848 151658491 617325430 997924342 624427447 124805104 29969840 271959337 733645696 941831219 483025327 488851124 297179785 960894378 611388278 527749967 620780669 717108648 405790733 189795162 741629153 211647840 421045206 82054388 528186697 936531130 50583850 115099218 684491591 384220794 185231364 726006796 881681212 511576182 955442195 65365115 571911290 373083104 728052752 930483921 829015580 196335365 420470119 468937713 517000913 318393039 521840055 223820856 239606233 596051190 158838139 278031783 401478351 89332763 979353731 393779496 371130743 636886684 604379265 31576051 106397179 278026326 459801567 543526121 84041680 710955835 848892973 241104268 298408261 826030365 271018171 405383644 907020839 120195183 774099898 754220446 515270642 953575127 269962316 282268475 190698898 374186521 669003463 682753480 793118248 857828382 996084473 42836900 454591321 589843129 716947401 157456972 188876652 850465790 506212840 388296788 563183960 71731344 81194066 85224757 65493365 66890522 648961723 115822463 437475881 658434765 218773204 306091436 664848702 616479853 655551009 694531213 346111357 421570508 740596782 313005314 52313769 528196759 450323723 500682552 262642555 240466912 9931968 83776331 484311746 855489894 834518298 509005929 549840949 194137652 378387315 756223364 151704169 272214282 99261820 675793066 54800016 573440590 295993341 498404149 316397334 208334240 116115270 149310376 499150261 408250191 35762842 61574187 517701359 183787050 593178632 982752048 460010210 420038777 164290136 670722774 101961853 591581567 959111741 641773919 994890085 691863796 979265987 552670128 528385853 435858237 176916603 562966015 745290001 58888087 189384414 890362326 470817198 966787947 19675169 978826062 119882938 546526024 727823048 382304106 48835416 969419763 978310173 377751856 453389687 560526449 946014446 182896915 723179461 891084769 2572854 700595769 338329068 404726660 731463261 609498416 781183505 155503002 593665220 527591014 167973344 594158068 30540216 22811820 942626829 229707374 14868961 985424714 783389532 530661220 151107404 397862119 268976555 164976105 604481793 753483687 980937491 978544544 573818555 946488503 262236830 937088098 38502403 633054831 440722486 697527779 995150024 477158179 489120064 698008264 529641556 343198631 369122913 909474433 894030263 880369795 70849141 495641503 449818861 566636886 981434486 71486753 606782852 512281380 993663942 554917563 268231872 544048692 587304556 114518450 280413892 954670124 277886546 192792566 93838359 462648445 5580381 683758528 984561857 809934054 838494646 955740498 798705912 635438477 152906333 383268996 534054528 497291016 495024858 716867784 517782328 634196914 685228438 219721407 958388773 276771445 116919054 546623859 793396503 42552265 633774785 408979238 767187098 662820197 627936096 991823941 807612617 854737734 609056217 596735412 381253742 255440517 695297634 119738731 211900390 378133183 219894418 796175723 383524806 357121367 844465100 218727580 120968470 402253108 816789899 798996622 253425409 852174661 666745368 103113075 324350628 660003237 774492568 585479804 620795239 60473045 138613488 810181859 669075899 56227630 481021765 361112967 263721794 833150153 965139044 420258086 815017200 976157914 105068624 828118867 715790135 754430457 817518126 537207057 85824270 682736058 21993285 375087051 820384835 121572380 409972375 131758131 487698119 599113170 295878524 759892699 490247247 860684662 505072305 657893263 494140016 22317826 853082365 946803067 96153521 792693334 469736645 562771430 638976561 515779114 449822080 314567004 18673756 695715904 152215991 219148201 284933823 463338343 453104575 81281924 915005808 588784667 892129517 134129444 660472941 297628397 955977425 144400452 504715563 343653131 534152397 461203310 6580152 907915278 344286796 820748220 656295219 710879395 245336349 902401334 13208160 431836909 54350272 85024673 696114058 177550665 818102901 447482430 550034320 868604118 726228748 6526288 530028782 400355138 740830227 220015959 206752200 738524336 721657507 600761773 981529750 573612284 76926232 10730342 405752488 983488209 901760943 790509308 951959197 10514893 937287700 907241875 329727891 11941171 926650829 163570131 716586264 716992991 725162781 281719187 829617272 403530162 887408512 48565065 175955893 882555120 479487979 657337822 462288818 299571200 67556424 574470006 397777356 480398679 71939650 608635019 572264734 293236778 161227358 486738529 906556442 662092881 175213423 102262907 122308089 875377119 692926387 642173247 126372206 993924115 740404191 312653693 675608799 909650843 547041808 754851313 93633434 149028392 159733451 777111002 338086533 682797546 226305281 193627603 621670938 477422385 99421151 927124518 509413550 735699774 854675408 265131697 242146141 673701461 836904230 970200965 755131123 344323632 887066376 532865210 204108216 468259888 405532095 376228441 179357575 969417932 718344919 666719598 40526810 757508906 194377137 395711293 722441055 724422088 281293028 976804758 778805768 769738806 75161388 402878668 895795204 114936850 853333531 996891464 408022392 399703712 33243116 253142894 350728472 269728419 242542942 976655246 362700735 12530674 594470067 634099098 433836088 960037399 225818031 438060445 979384893 428632695 283989285 70583753 63469766 998524252 354673731 96377909 701671668 797576934 687397487 952277299 558590287 732414933 875537720 556776071 373054097 485051646 760725636 709852925 406394341 202965793 953535876 530972665 722965062 937519748 424329437 469376969 64980517 258927874 665927706 812518344 658737924 831018254 135784186 135033796 993192902 249385569 482455454 668507055 126150684 781794191 383484055 16056784 53436765 232644271 189063305 298742570 310106300 997777897 177363863 647137078 611911952 781460397 21452701 784158194 874290331 248506389 548314049 406916144 100709133 328701154 165946104 560789710 190562868 191898352 162986788 781233298 844763478 864174525 185730514 167291785 16419509 749484295 312944546 294817578 74811168 630626591 7791874 245176832 639463513 79537846 949422500 960737656 658972413 686249232 869141883 33063681 745587177 149070362 600833165 719036571 451872848 806269052 337836430 467355257 411567546 461262706 813765384 285477377 582463741 872532636 255003139 565489624 555187792 478932913 577483992 359157976 200255379 845342752 34579636 844027079 870968517 587063320 311185398 73338765 875918683 973453505 783918899 988299957 843142034 292353094 404930091 972120194 524175901 481193464 427897502 527714319 581607770 280143575 549344071 813743434 623789599 277153920 354170668 243822248 550869241 257240268 884418725 878180752 156495402 535080346 867766530 994999957 687993063 468752680 27153556 472009264 716994368 427022863 36728909 62703955 82326946 567626663 662689 727936389 531605529 560309386 670933383 342933987 685132696 87520461 133552897 532306586 599379057 784191725 92938870 991900047 418986697 561551801 583302016 680300768 539456503 862311027 887997425 521198870 453962408 212786931 384427447 205663316 607703670 64489946 969000304 918517588 558302860 321635644 250399448 209364467 498378508 197708415 283817934 676852031 706979969 833519364 717355817 147654164 551881877 608629230 772728447 114502490 608316811 901060649 610833639 162584023 158261933 68057814 410459359 429433178 774039879 119117492 462798692 424634657 809039259 404757227 158680453 470378874 604718159 77291809 648475073 187351836 661533343 884934501 542125442 173277617 975027805 609012041 225218877 208365091 294538574 763107846 777992766 547485032 64009924 602100176 414617257 621188921 671447620 63564324 526402606 509765029 420524637 714649646 961956218 276835687 925923558 371398941 581672202 459262245 906394321 265884269 104653102 583153228 739364495 953760946 864415112 372217158 227913908 581445144 703832105 335072346 221347333 509690737 453242002 781352733 589857610 476256435 327559096 946718038 552322867 245989988 665011668 113508054 605646364 933831177 982722328 332651152 823000908 180457327 444536804 795088838 369499289 65164149 686204989 592979927 948626488 527473845 162432423 422075827 179360617 639006403 242991202 534837565 88960619 781670216 593300739 922423568 151149768 972499992 68574915 25313801 543148108 846801172 755805726 529297537 696609646 148444650 576852707 816903856 698649701 838615649 271712467 215698508 603289948 599465635 362806833 552064273 795058541 563383948 758996972 362269259 500867257 478193704 610830027 897776596 940335186 472336765 214574060 266105006 8930233 906277668 122349403 759557029 454821145 521339568 807768610 661009791 553733211 456272642 889848645 580402070 917946102 146586109 201462955 646999183 668808959 724453713 57551919 794722404 482947781 990485012 395040282 152654573 648447339 41574246 429093091 204401254 896166655 254397599 59749578 191448804 442722823 756961590 583704422 377049145 6781707 399190567 161198813 849926451 676744984 272100496 524010940 439192593 669025229 779358794 763692961 738153172 119090237 422058559 556568515 161762346 597605524 336399772 745356729 744784517 854940324 828866121 562177932 240781712 248990103 620246320 236722227 869041344 617723096 582446055 513020971 279600998 124574400 551658867 398111525 758356291 498654602 86549086 603504939 63850754 433818039 678762531 771665176 150666036 811517544 593888779 669370054 707927466 124342858 594081171 115207030 173169006 123151596 580528696 739750373 398332993 128902089 398227089 707270155 72247071 163828840 78043526 632814444 84481049 921379097 693446492 490120495 112936852 930445060 783893585 947191646 230828993 426330708 240040179 726715610 979265667 493363798 455484977 259476011 838105451 56578394 517618392 693327742 715228356 117418345 93364181 406179997 692322365 213403916 886749677 86255369 480815768 605711443 156494533 774095010 121975173 714955360 361680770 274126533 142789396 393788605 655075448 884923801 433372370 824610816 261739795 528380004 320063252 459583327 956543471 372225827 199705239 514622957 308849390 356825973 911398455 810999453 137353962 338468180 917060089 265902899 635803602 994368338 817795 771367394 915766702 142243926 25949720 889125040 347660357 413344461 775056706 628827225 181632995 917007774 711776675 784985805 947115007 926643627 984963898 599046396 33169457 575914650 551455704 554507330 616916277 687445556 242964872 965741734 297100377 370625375 254754227 992965213 193641119 431535984 995041131 875703647 730569741 56181389 861544559 569285562 620741604 163013476 89141941 378146042 302944610 800116995 774381244 56833579 846782371 42569090 286312492 640868902 935896918 518389122 102988858 773117791 673420559 267470659 821614634 281361608 92415713 842400408 703095330 863030028 646951302 129873257 859627638 388853829 886189961 781408688 78928408 369027929 970080236 921120490 316147722 728155735 504640167 301493475 884138355 806480096 288731605 65012970 606832352 214870867 995319069 469070594 522962483 379359578 199445318 227376418 794723852 107465926 343304490 598434389 742724990 346195511 389566848 784679259 731348970 39593185 571163610 227589310 981907952 548928161 209587118 512992956 749479639 454963425 947872190 729169006 479004820 546677633 609159245 457236441 917122028 703454597 180210016 546524129 493961826 548356665 739210055 598817623 27174793 624599272 977338008 118226596 83267510 259932005 228670596 886301177 827828494 479801966 743682035 905301211 426455427 212563218 662657744 148608949 308769815 996676007 935937614 630252687 948740264 597715491 512053399 403017283 648371442 490258760 328723268 425257734 824750834 337855351 82742381 832730662 522006106 321910157 982211450 347729974 950069553 341877923 252014720 333920860 427614285 215875162 420104531 358254255 690278911 298332896 869940447 762794320 33150232 977963823 36713891 868462131 69355983 446211248 960337339 403736867 575590946 490193937 300039964 136699775 522007055 100325329 668727481 67396309 610320245 684785258 414682711 838163807 881892612 353614730 228686385 17637435 633695798 196246439 847368916 902047665 949809038 776603001 289187166 964611331 475242917 462806421 213489540 579703674 65131638 606511200 426550358 815423714 899054233 368984439 577351987 306898341 66160549 643463692 78552280 379907232 796650503 371601390 47873867 902247593 611267340 185903116 337409545 433395364 325845079 458404422 129315711 920696891 157210798 117290744 175993084 413253166 412789634 100123894 534045814 205674620 571982587 996848523 123936656 753298466 513857588 257080489 928959635 25677735 600563792 990379231 766904242 275555549 708242026 531740463 585525908 967996070 538938773 201334192 100185443 72778927 697724833 593145137 548738210 364832886 453508838 732007353 341237607 415231615 226801303 189474143 272897148 517515853 356736323 779225526 876548792 119400350 398094163 856050326 861707071 322316043 91872483 578192931 383279033 300983230 194112300 916708977 452592624 60307440 956837730 426335110 696030470 968457831 736887979 673215618 641883848 492655013 265469811 953057383 516824620 794359160 163184972 307613520 543876505 129131876 347227305 241670615 703759373 463466309 140737828 58838226 130168947 767586036 850527991 415489001 619907338 630952466 642524737 62921706 201041002 307000763 241306850 372495244 770212823 237048945 354427411 603856649 2588846 60473067 570022330 300145652 301833856 12249780 309689602 155126261 690883248 513659066 947043028 87442871 344462925 810615979 433228601 485157085 342438700 622637703 476660426 957391197 223845617 89774305 898487061 837457416 491511007 820316080 717737760 758096549 712898583 192837027 972592664 11809470 793736216 583948070 651778403 53566151 805055352 142459003 126811639 934780954 804386259 191457880 398597261 803048752 647744884 8218088 48693560 369101513 521261043 44957132 861133487 682125587 615731979 849741534 12797154 255505776 51797104 346039754 158961413 784271500 804876367 648335676 572496661 290805808 444139848 466121593 258777186 335931715 184992836 320388139 248278701 216303508 923611425 888161043 663220087 980507330 331659825 946255765 911224600 274577878 957685625 44545881 595034384 492036203 196055930 807598088 859242734 272864396 987639912 25035358 986812087 819497904 889313746 725868397 969872150 552598534 550460118 894499166 232862409 107855275 164369927 513577511 331622111 936671862 988439450 78749337 140081965 499281237 802949714 447055992 905438972 176319263 86317390 614940502 183799133 279624056 121434424 541235089 186427559 100442229 346036673 826641811 783516630 368286639 472936065 716890978 790346404 527518154 643484129 998377520 553317036 731726331 476249728 414637937 545043915 389841391 98941621 197421954 547817436 215286003 401331065 704845698 276673620 957277085 850303387 463767969 141611273 262446733 115748820 110433117 588293670 903565124 787465664 659049884 790221068 931228000 109533418 296248768 44054183 324227404 148874541 485055200 736303551 26905530 25411658 542205373 633858220 453198572 431771660 944075498 41778349 930550984 33437577 954180038 663897188 75315586 247110171 666114361 436526655 283373563 508674125 59488635 560901547 863301613 750817742 395385270 600413196 333080315 443444926 533966076 921000762 277602765 82191604 589514123 913814307 557743167 363960190 46454183 94781530 765054596 345040606 891015116 684962128 977235044 486498104 855422034 999747203 742752231 963666433 900635125 113419215 343915418 792645246 8258642 645659148 27444402 392662504 974048971 505125021 254032835 219825092 317064303 474115335 952736277 300549169 830245532 851762263 720684246 675595512 180877436 324811839 882111546 653136970 703090084 527355258 39243976 950726983 654025996 394618216 658514368 449050906 366349246 58708205 203429193 304774667 90949967 9807330 290819185 719283562 912007352 770363670 535878897 232494542 357176288 201268117 497008933 567378420 260003338 158847623 296488923 933199504 635211076 87607856 143741718 875307322 960928609 898354337 36547396 211704787 32578313 25571080 457538938 785276751 470472174 116284297 683193244 545058296 758859111 99719493 497268591 376120071 382710119 768723839 448324775 448934391 453959091 740965420 616701715 428376931 923513638 983478647 223733876 592948457 684608349 447571829 202377854 576176590 523598905 858896139 621051224 60580789 873594427 866087383 81271033 500765283 708792699 361258020 181565194 991334118 836721526 452213634 99645285 689252688 755304752 713036658 749855505 604607092 240128419 611251513 672702478 207275722 658975977 197508809 708045961 711582277 314017453 756559251 684289803 844452863 839931161 864760575 46665125 284389643 478559689 104771238 319525112 709301683 85923872 794535534 947929503 39937139 550567766 670649140 243306214 695388517 143290729 976809112 223987599 239393656 84836399 401698744 361004412 938258328 461101897 546931277 671656912 239832273 668475436 488615728 655355159 854127606 602729657 820754042 48130096 619293115 894665326 263655678 200742827 182414142 483232537 991671868 533839619 733227726 632693070 539073860 653069716 166086658 811477130 695082574 446556181 333473845 356169154 490339406 990821371 301484446 334091999 298132496 31110454 284915714 157045817 212886727 914619975 528319030 356644495 875974803 958870485 121890942 77577883 376782768 581657142 901645865 66896708 841080264 217458270 76864664 163811759 622040525 355157125 267939253 294996116 152858406 555426041 224719402 48269252 261950774 479761767 537834942 895527354 993955270 584168739 905306806 509869297 878060627 23285064 381136723 149385168 892275586 576578718 575924298 135510785 624254606 790198184 336534461 682713171 151327409 87419484 595763482 159704345 95467304 149548717 585557485 360834417 214300119 204284146 971140311 389654617 672654252 914065603 600729133 573340004 796830578 775104101 30473807 919487634 58723260 893398132 832905757 467136995 81348873 711867674 739444874 960183110 583435329 875905515 849749452 869058909 605692942 818817135 802243490 100304638 353772418 752007407 59103897 573611995 278802353 524093350 588215654 588204114 550606425 51519665 191422162 687757518 911775454 975609880 245526398 895649969 580081952 603748404 639715407 905126264 524124502 759726577 38476813 236280882 151521520 270334928 305601389 907802348 923224117 336946839 761365473 616727906 646577147 597208537 367013190 492676858 113528480 604415086 958331692 689670358 609298461 502961651 207068058 987183224 417359843 492410814 366715778 93942222 475515842 975786651 7143266 971161998 267096151 374915580 628143784 478828047 472234591 58349804 258139489 657026439 353222904 911505957 195060906 773140025 42988738 330630852 73501164 751431051 386074751 969989495 284320985 592108545 154478523 228966416 144394569 798219809 168589010 455355537 415273034 910549470 855332863 927186950 460413869 310107178 995128384 126451897 563807728 853668190 383020048 879512983 215782446 886262070 609104091 588110675 32539361 884251527 545465903 689585888 36416877 641277954 743107767 437244702 130950765 335521976 857119087 334111741 287289313 357121026 613131890 410289930 334690345 759401133 526483048 600871239 492465064 68612563 753549439 814085544 455646364 508690339 640060310 671324826 63713540 310136776 910522987 803581293 879602612 117302887 700632751 123544923 690458187 932811884 822050435 553272009 29141181 395142236 970592265 485948473 342669668 17939071 332519006 550938117 461428709 495987410 698979952 875402365 537657126 922143356 71737998 326738717 431386908 250941905 661303851 174093429 953644008 835600954 373019468 510495375 546873826 828488572 853151700 482692403 929521038 366227293 273200496 903957262 777353342 245837408 51651569 605676975 728866640 510654542 938695965 915281994 305960649 722882426 509752851 33621603 221860461 339598618 446603676 843974251 333638647 700963069 984411107 854563220 221813005 643555576 230558967 979675847 18966113 477484080 7359353 22542417 487549733 218032883 186086096 685362490 402815858 516840180 391651025 997884168 923539096 318972879 80240767 712622779 452508189 782726971 413224673 823022469 226847746 560843131 774986666 179698590 228234977 624418636 380577744 892053534 294748924 557629789 558999032 123186308 401706704 709606492 764694618 191168495 762798644 214131056 745323399 751769149 665268018 661421754 144262665 342961051 149500212 904516381 486707910 595357330 728197156 869085066 698747637 633997328 645525298 965457157 483887327 51905933 777103421 866253120 786517166 193942358 514718309 932813820 709641953 985076210 913067742 950646570 505266928 821497170 891784299 154450809 400491788 25400249 249701835 657027001 741518060 183376946 876612154 394441335 26079212 29959662 151009057 365561430 438143589 261473458 130872606 873297817 595488719 978721851 85925487 903888778 386840150 598603565 3887908 703881253 243291066 738001004 667584781 696929773 704312907 710930720 435970750 373326909 416730441 382791397 466302175 63627798 717175252 989804054 126203466 605160888 149872323 896577456 451139650 384280783 570276477 775069201 698390910 123086042 850820656 25550690 107428154 159485065 30630045 641830028 238254349 762116098 766488004 641467266 223998535 478537965 540741776 853560493 464631358 846834498 159210699 424952571 447834665 481694253 966851884 851598576 688533574 625496777 232316386 665948407 130699051 837115881 259152680 843542880 251429238 844916359 482174088 664309942 386995508 928012050 79962298 817596705 905016699 917456846 966653273 264408191 408665242 936445885 290473569 566343606 844116090 634161439 918135370 727478403 770619000 792009305 891917499 21488212 908954416 767696674 651126512 439819884 137495211 777080570 280159925 860524300 605102534 582349015 529654353 158806511 539973150 174869031 822500405 459065258 367090101 550686410 83795559 48998259 656138620 415321042 448612981 661851565 170195003 990808156 330661424 361557451 613084925 387065487 952156498 296558632 357237198 583323783 126790816 544252368 225941193 192760686 998480371 527021986 704686317 67169409 155100671 275244770 969815761 162259075 43595294 649718893 69171082 501171502 554217708 187131745 384268441 790693740 554522006 862709855 514569039 680575769 59782216 18375472 373733035 619985715 510800629 375025890 405512068 689873245 815523055 596569101 450302865 985155310 477339605 977510818 705275584 727205072 723026070 580794405 1250039 202540023 735034658 35718242 574985224 472382830 376382179 655896013 206484745 406099847 235643503 825460215 255217464 973800347 352466612 417741253 659258186 102427260 236584904 835052900 77081977 150908954 674801817 835549574 514797913 235944229 554325098 641771033 823215166 457262641 904588233 821986026 336382588 65592242 268115485 168515567 103697745 963587449 307910809 9276615 570234650 247395405 122264798 317609447 119823698 244342765 991392703 407129002 979096051 263813373 988308114 53606996 450091706 193458292 702474040 139199468 467037512 124260457 481759109 312073660 84301530 766518725 667801178 566769042 829420223 412152210 258892317 403318380 341267418 786548064 547463610 438922715 185874861 827094476 764881730 613284649 102616113 616987801 691281235 189901097 331400443 507671253 663511233 383005997 426061368 940311967 487527421 470922413 663376350 222061485 677007005 924963101 406027917 190893926 860718307 317614930 921396829 926962349 506987427 311374589 941341913 86571069 613266306 283460066 415279967 531558968 515238494 661935489 899844262 866602050 932615022 621498166 379939356 406181974 686021131 707063757 923472885 928211030 15943656 234658360 273242046 919108100 572929947 958177275 293666283 176705715 280188573 525543257 431612528 220082295 422395594 398482527 827229484 169727314 705144787 222920152 475446688 352587585 315597880 708467968 496414260 536711489 388643980 232873772 741149481 623833036 170327988 592552568 519188523 425340381 753474401 208375176 209637784 50655096 670732684 898101450 100481019 161190346 19631080 501764783 944495639 137522155 386441179 472886653 855544281 351511019 789533354 106743647 788426137 408552455 708729583 436196681 709736266 912784363 107759499 562449180 425859458 453235711 669619385 777253981 349226426 592230325 160208109 948161118 952592768 209802712 907381234 393246300 92939471 279153574 600866453 681123945 856408866 752227577 928298567 888128032 441620512 420381848 687603454 574683629 125239398 675431774 439428701 71272638 417617107 774672810 911034867 275089657 616593905 478699129 59476151 747940784 803248437 848825756 101801976 216978371 842339089 742413563 966532299 500547583 100046512 104537417 291262666 685914785 927108490 523320815 996138328 606342642 914171764 963630752 959213814 322997260 102491996 171337362 54097099 398359677 836330929 258327206 962417281 417474360 889845948 115934535 848959189 2734250 918855158 779936905 26780096 927393478 454102306 648530882 208704971 158539420 376846976 947484923 632328121 41414815 217101921 679127414 220320039 252921290 177069584 175202679 323426475 102314787 654446877 210378361 677097780 819545525 61469269 821298970 401363581 910674186 181026931 393445838 107513890 638244879 169465749 652350683 815966115 960048435 281647413 581543797 478983280 501783796 743638698 615176796 177576665 241368430 715625383 447334690 261924958 225039611 28684067 229730740 304278847 441339931 410824826 778175782 622881654 484055422 679533384 265459144 351790337 13113361 387503879 291521977 719497065 466058408 267024712 935748506 255608610 803642572 681998669 600472252 804526771 144204397 981539015 285259575 510942000 634028276 983658594 396313546 946796518 526334351 863376191 387140180 724340919 465873536 324171545 303999981 996558215 459063786 305877318 645357789 954502220 81992297 226727583 699205930 712895355 499027417 704417397 878440103 461172650 37626240 346215035 326888235 161644875 501857306 185946862 544777764 678374081 479998485 886192228 761971307 786978401 23673367 529890749 94009996 316779674 59512345 378234524 609880427 52138625 638025307 551422480 842995715 196950493 8504361 603294389 630415478 703832873 187682268 982181812 878965744 918640119 708384526 644486216 668339586 465548219 661459329 343085620 128525489 634709495 549637239 592797489 790479203 477690959 551517520 12860692 855653343 612710208 615548921 379472190 473057327 575470535 684184511 453942812 226815890 720198197 958795388 558890496 328188170 79440655 621397658 693960457 959024505 740416073 104344477 262986473 809772435 800715827 211188080 876519027 943273725 503299083 328654346 242131365 142391329 347342015 673052313 53857290 434312352 372118239 79357383 288909133 829321909 922451649 208784586 884439573 592781538 191468735 417770227 749154156 329779174 236136426 11639019 626959764 669996492 735408994 45347234 862274679 639230860 63366331 795853006 777270061 484330384 562785039 862948074 197650215 835373825 527330338 733899541 300545458 651273832 218872400 144990280 228340503 900462233 328750889 765588679 185797387 693884193 715931062 908484758 541723856 45363903 194756830 977440967 456531321 271892269 994294146 456359765 124385637 562747707 402225216 113813330 471892939 629195251 715491024 578707766 845893659 701946554 418497003 875242654 912453220 655285730 522314522 890068115 63458410 954640978 942197964 473690436 748838958 451637444 256768934 677873215 982943129 32836388 664004253 754876923 771627186 314071561 506839962 465296784 160499817 143529276 246993275 151181578 385930416 758296852 732374996 51321995 278230701 340517161 201361037 360464327 499440952 95935568 681453988 359477347 275774058 674160629 708914409 864457431 588276339 480404055 596707563 935495755 938079885 760922301 374798063 392861503 781983924 670094026 387715192 495646473 791218242 518122135 181552582 359726039 17212237 902258686 575563990 84885614 98883013 669975532 327144844 338891974 436857524 4958576 552499324 189494004 12699365 878899477 824430456 395223183 810163749 969590484 388453953 708453523 243541728 123262415 47335883 656781411 395444825 403408182 70840656 66396480 606710547 722802360 196542915 931146283 812235149 539129059 799579902 629409315 399893423 512876076 773962474 770177885 918929429 517853219 966159967 944598655 930731419 429924313 16481966 304707524 267577670 70795848 389337560 72475207 133430438 108214645 479367660 913817475 990413663 597005240 60037593 292758821 814795611 854100933 675597175 830361793 31896960 732655471 361588043 241833486 367505529 506498935 698900537 928358109 565030830 66826444 293282864 73512479 328845370 280097713 848123457 650385820 164210260 16726159 222109970 638054278 743153715 691635315 25430782 483208277 290528694 821405811 864045785 934106220 399282052 953677798 688862684 883174852 287434343 692962860 820905707 481971717 483279566 13648555 613342849 890518848 43217425 234167934 860056796 928921262 178491777 778737110 311401040 764565833 455390367 212077677 536312585 707211810 544728385 622691490 243274182 680106643 181152347 524364536 95343507 625598665 209997213 361302757 344199857 636503520 399274679 372210460 79112631 296906080 447292164 520178120 101937975 571059254 51307749 595489515 929761818 166707517 722952180 514481641 802996575 418613673 215293715 523701754 252333308 225082980 859582371 577321113 856171069 555586164 698876898 739207921 847393695 869390900 161155169 307518732 448834667 656210732 941554322 536446961 194261721 338313920 188824895 972664721 313410294 35811398 582672353 228083115 34991987 704019296 712586131 834939110 720341248 674663929 587204511 654740437 984807796 335036386 506824650 345494145 538302582 708705567 695529095 82649566 767900379 165785175 825894176 67032198 450627993 811437444 568590546 63449646 570412716 949634810 259966900 691891912 394117620 242996834 241946676 816168869 611738337 716688844 928663091 713784411 109041739 764037469 563825802 53017391 475800863 113133061 555672178 402746767 482388951 510399346 313151887 89951549 398531254 734727567 541618172 601862105 140583472 184364312 215132723 350951932 695179344 862210467 752550622 209190015 86881962 441814222 104126993 303158914 462915097 629720134 630787661 542503669 742415690 473909835 849961201 649097964 296051290 533857876 144832279 452548742 855198171 186678474 653969303 872677451 154493440 830598060 335215116 985052897 172349100 922067923 380889817 611201931 10924777 450000088 401391030 502387295 389058827 698579842 384354345 702841727 145389484 483788878 246802278 6983874 259718996 130022856 638367861 920783443 22054419 482830524 972009975 674816532 571575404 39885533 626304742 737766105 505552190 797028720 552462853 198807866 160508209 845632591 624376600 184534879 494171185 800234899 555869433 391001626 561084598 411357764 781124382 540489835 330245260 396005448 17178110 297657548 885177553 126978093 968956449 920099691 688298343 435076874 38424957 690248729 671146584 756071563 977553626 720985893 617809700 514603101 632995316 975326552 933739818 992087703 581131876 27643954 235782972 451941776 140112545 346035756 837049563 573709452 193287921 364535725 937271183 646371162 957408221 675050579 606152374 265000480 374642671 491397218 651146039 545187646 34698280 682045879 253354869 798184292 469138508 906492822 250495064 639185700 676280850 84855376 996594335 696850765 679026487 112979122 797538554 20864829 796847649 654889041 46999933 865456815 771390875 720690704 223186555 836572101 859541645 521697428 432828733 583817593 576033763 59111568 864432412 4471512 86254647 361696895 316562891 760025692 761140887 842326157 536783146 728019282 850764962 954486441 868500799 655175623 471214789 338586745 470981659 357218857 674523190 310201361 152728284 3679716 248079289 334908570 711735100 21342694 162325121 494602987 511664905 302205119 859186783 144468154 723624563 78786149 656406959 4946817 273369029 558434241 703558330 924409013 274878933 226904647 340707640 799955218 573959728 915364492 343198282 411407329 824456001 620807536 857670908 587943662 230355269 563026691 672334597 238157244 506160360 940680333 667681255 555687507 595952697 816881719 839476759 449916805 436005275 547020999 995021312 431218260 209173261 52253340 574797493 926992446 599650724 818374800 49820139 926485719 586507992 230282617 900996701 901064531 56139165 913170978 787240875 260592493 217186207 433813234 652938865 598556785 197264739 369049396 536010352 546804224 687811646 319226929 398991580 333385028 205743589 103321354 321371685 770401687 550234187 30384246 809943206 864635854 504514931 928295701 29838912 988831722 292032996 144557833 432817942 406876652 440674378 448714932 968899964 76621480 346068521 993842902 699241216 135529846 579539577 423824298 416420934 334175029 324491458 148218276 821854222 192334734 497206622 705111437 275542538 1300212 64902853 248199473 738560951 449065271 112955036 599423404 611847907 576432607 225197027 745656093 610143572 495196188 379103425 104057523 393236718 382858793 826693724 495423817 236726330 908082775 136396380 706652393 786994955 448775239 516902189 542926573 448191054 394353677 629750135 432598582 231877418 20452674 533141847 857040083 713121373 100771958 384861644 376285059 886786424 162847230 683134076 678937460 488363111 54287580 533300593 876763198 720845526 320698815 812108518 187545745 310379211 647284787 35743804 655955693 478329910 393190738 623871933 190651737 599149088 222797849 313248628 679036684 63176437 734574026 718124060 644508342 352961906 36118973 577532507 425321601 771027116 544888094 27284997 96662333 498141235 797402317 289999271 568190778 655457321 955426958 962866501 135159389 638217969 804361818 854143783 419998035 559429606 928742553 415553623 472064940 827766698 704897437 479162543 571283581 416902322 407735338 907003755 548597394 539424809 937311701 236265697 831523617 733854659 321578652 180156496 580910055 410751832 72108200 768947491 838570921 909820507 698409930 189024526 260073865 159262208 429879398 349642068 409144225 797439928 285546687 580097608 61410343 470406299 341387637 228249870 490400025 119706975 133604482 90364141 593831821 878265233 830077057 998872843 906425207 655471131 756006697 854150234 11629776 541500975 855333777 953757391 242565500 691172450 793753105 921301812 969089178 539385336 29797673 83040671 804455625 24567406 328076048 701892894 678869197 304001337 204703781 84468871 886083352 907304132 455281095 322445068 860323944 776870703 749260879 910470452 871486469 98197317 409258367 81063874 567930593 766717605 211777830 175923259 245438913 85759320 985463868 204070197 610568993 691547951 524033340 291236590 520078198 752383427 232640956 903664669 501554484 272924738 569338630 326722690 875406293 797828206 532810953 173836162 644362783 687163175 558052745 111156434 975507195 415605915 520125863 102446479 635357617 559709560 259472459 774666775 109732064 810665420 613987928 798767838 568487071 153413846 483339257 601724040 399669090 789349457 916641626 212699909 678018847 328960204 908321673 880465083 481426804 692672084 536639111 968186174 255661391 805822197 506511907 111832208 860399038 745121362 458051176 627250426 644361569 920077982 550986094 757186727 701946725 566117928 93693002 374839337 78433924 843069762 869750005 611380489 693321201 726939501 210740968 576009918 307840844 1970573 439221377 882516656 520141198 961627225 771976770 980836456 862553903 520653883 743546100 540218490 380615748 709014682 191480961 173482777 444002160 103948744 940336405 594900784 264174902 822448816 114322271 770195427 231725830 312102668 700186384 371322873 63703640 214998537 974356286 989826626 661403427 265161650 102542066 764553357 188149333 508232356 470944864 312662411 904038024 336340722 766114020 128812077 689860452 130324686 527844328 160464631 101214445 333494103 43723748 651651133 96794432 637453659 512391580 879192262 657742730 617019188 259968438 109791527 536915452 770354360 795939774 137666828 196609609 857082373 453142448 76959381 634777862 762357075 522158864 705330191 309424985 683513109 279666674 388016826 381502562 521636010 138309963 284474005 650514420 146411455 749300973 266506493 88473268 104944001 869714622 922767860 180095427 122081188 659732747 843597784 843412965 426352203 834633204 401872998 848659022 394377470 615233825 123661538 578587106 300258273 588594316 53254874 114350694 960518414 313956293 43140927 127659798 10306543 140930174 426247296 165640318 611582561 655369660 208242412 275898647 260121062 471091133 185649613 810116367 369886416 632251421 617723645 711326278 236586180 614602494 923743165 775287680 143856373 778350636 459782567 327136778 836217353 662841844 133288813 72067953 180855278 980292159 976315626 1910459 419550421 119273587 325890341 592520836 256274366 381597363 201463736 954261355 218506681 660281542 781506251 73798280 879624380 987367825 743115707 622471151 410492442 526048584 633311387 585156669 111387672 574957740 425774173 365331041 194285314 38962395 923697430 154323752 446132236 959839815 302796640 852968734 851279434 93605044 86012175 962963807 467482376 935604843 565805769 893924240 416598462 635463309 65253767 572294462 481522762 448020732 613108392 599111732 939474895 795831857 195903227 740470568 527670060 596133760 439774994 625995944 561110671 428140603 933259699 770965757 238052485 926563887 662102352 874796217 294595395 795710148 481777042 286874494 498990771 860701620 296513706 921234963 61299160 378168380 396182972 75577702 511745582 441968237 950557674 534966616 638023641 768332745 428766763 238500790 772147696 377414995 628520151 755476983 867548745 572654414 669036896 460678105 788507440 869537903 602353956 876731292 202374973 666581140 832892696 818595096 754708836 777283125 69414943 269520695 963434999 438617816 411242833 307615182 426202731 825746190 511629248 443817474 278891971 17383922 209139153 379695789 384206839 908780448 961622934 106535535 894196653 782571758 341324288 487888778 132901495 993737052 442228124 318950563 144827232 180562899 835762974 912890885 428699792 955873400 621092545 109886152 643420544 499265949 267985401 366133326 463311149 266173163 728462831 620122884 982392896 86889571 956693320 939581004 712065734 257779383 554339451 489853377 633753901 453935808 718749620 263364453 745564794 430395259 865395570 872755619 297876046 833387797 817337538 392639850 335952720 496631754 732792839 449397892 986467888 179432438 386455524 754002633 669406134 649632772 633888806 605934295 884472891 182424498 918075133 739278315 75762562 418759548 671822964 144880734 83537665 226602628 627642774 823161673 214683253 309641730 813215442 399534537 728968699 424994796 951671618 499494582 908016200 940219617 67219744 585484363 755818480 384570049 253041454 584088509 815472095 371201055 974037811 299087785 655068986 930644160 365936671 841898649 501959459 364575639 329032649 292185505 585514464 694411422 626148601 87656387 500046465 36817947 99354001 768178879 368093671 724135049 833533237 226545504 852103091 960589896 535357742 694491144 524839659 878638344 778077204 763255554 832285202 597095814 651055083 703583018 483688369 672631223 637247042 815696031 139146878 542685997 445787874 245152318 808776197 720551000 563260542 895374600 782743689 5630554 441603404 408411652 465438248 122039477 47679668 980110942 645841721 543617130 594680790 607123360 983574947 153333206 456440398 926019077 247129492 771443373 497226340 737262748 327150398 437973306 642411683 78980233 155350650 921133237 632878286 545349080 690852100 900913404 371752343 179071680 69173415 97296713 740412522 257779375 749864466 783449711 312908193 963109604 896033443 818138392 74632127 471859036 608913758 834810646 185925821 214053988 614713147 837082754 394766601 212358478 701554691 396684700 513014748 467622581 452879997 23010950 274953002 578387489 449608173 954124444 339953174 311135783 710919879 375264167 564885855 794658081 734048128 455892898 115784464 313931421 834892242 839667876 152056042 526246272 938571738 177832430 263414649 336399831 330608541 619012943 313027507 192188604 842796044 280107753 215172304 660074342 482820700 159255510 541170581 81537279 221975474 367509349 62135762 628158217 265780661 873466224 819657138 351442295 678378385 635293438 449678803 211474236 693769210 545768664 314222573 587363603 227798543 245152733 766271769 297851500 799765433 360451759 81766081 147607807 139402790 473562696 209414084 130819002 619664195 473766165 334392428 804997189 982833266 574709894 271427242 699891869 93075917 530495517 371488411 105197990 435174754 85350124 688930647 822066603 446823811 987154711 205914157 181336681 457332405 780148612 477254115 880221944 175955492 421514007 882733326 303276426 175512027 485802771 492795176 643795156 87511173 38376389 322902514 198716784 273476222 416594340 30553800 611864436 749323315 249755283 547433641 681079650 739287585 912872343 808131735 572232876 454170118 211567566 568378153 925567688 646920651 809676340 334427544 356864391 713903697 100973159 189071394 824372099 406332250 267748776 217947048 130885845 594434132 750061134 589343469 434109845 947642194 50399289 257526091 628264351 622268792 586501532 141599909 76175756 186518482 347456522 914710726 295892735 36271649 893699040 861947536 709342228 976224630 61313282 617554838 133582137 110349505 896509318 747404501 101395555 683443511 403731467 252362456 417431581 537619501 609869492 996680580 141746743 314819217 988679538 391847476 60172256 769503596 588956451 949325488 19383632 668768274 356812530 325287747 52679034 207503312 355112528 491039739 845659401 597031539 466539650 361694113 389072147 535468670 581596881 199269105 973974273 810590253 603281706 140169979 413333155 860795032 722314916 268195286 434770492 833550232 530704766 989951211 865045649 650628207 966804647 507284381 452336544 848167025 21771138 940001279 586108024 158359946 702753961 518539367 786271591 83363969 45576683 384689970 791355397 384590889 44959674 338409457 663021685 904628295 679012151 343422344 968638157 129760822 157924167 895038560 608168876 681769668 67223973 337762933 327000098 357097378 150631820 875891488 952432465 14276006 669250042 211591427 447261686 17252554 919648526 132084986 796150226 262881387 250664361 168225968 405546498 289185992 791414963 715215743 71412907 563936320 336308610 177394774 194342601 656726493 324523304 904373226 215964048 384379931 623485389 770588322 329511876 853417006 588838122 575667706 56763414 867404307 367626070 90552553 234306955 98630394 863794324 611777741 724396779 761099305 724465501 926034552 502216809 331554617 578724980 428773687 470903056 529482994 849458580 896729519 998982097 907828893 15829007 954794873 782635797 985045376 706063429 405180572 493775246 464930778 161899729 795743460 176180889 427916938 997822693 460997666 991925134 391425256 319063923 124443999 315010455 179857565 488029489 30747089 11219890 928815984 428922199 600593026 550791455 388786677 677312483 811536472 259035876 632032392 509396594 998316966 326728945 374055811 107564052 958026604 323237487 848352948 624663929 378330453 147233773 933095428 817896701 406807688 737004972 39868151 779331340 968028240 132379113 398429819 245327074 22230752 836479306 240250220 639183648 258641873 624829987 222981581 970918190 727620688 593273499 223454335 892843753 11211746 404490816 702083024 924668246 956096128 752197250 82872115 306415972 907133539 156203451 920738943 143745284 699655731 517081069 139005672 20958044 448745022 105819996 380610126 265899447 949824214 289885824 230901683 891547753 894498720 689067099 513381903 980337532 718223284 380266858 637744344 813693562 140935772 968277965 784648566 370674450 467160821 222427848 593319345 688407144 550914543 787738769 629122776 311155831 360616971 568245575 124579320 721286496 129061557 689002759 595027774 181955615 696592459 710768107 188704159 144788144 963203870 201741017 406369262 680746097 355371503 483056002 266443674 417768979 275016049 215291776 957148081 332864123 906013947 901348073 369876334 678700782 37950740 483846904 497355998 730088595 256583554 71041600 880101466 792600641 269709546 654397586 611870522 891835584 149473754 274204518 477140935 856556448 687696258 871740044 700766171 972950259 33701160 429048143 758246628 619828515 459276573 210347602 600157659 198397124 617240516 545768598 94143782 488656568 867662379 355790475 88975222 675960694 130164524 740945115 704611239 220276820 490548241 284027261 150461998 468546523 479373397 127603785 277854225 318775688 429859699 287336749 535771586 163436888 653362794 475156275 718629884 589101560 88140985 724828581 96535366 467709652 377884298 888838841 103856820 575765756 639773952 491611869 915812390 979042673 78823494 795458115 991204880 307120168 472912568 747785735 552480111 843229749 539117769 921481561 294540304 991803707 980161696 593312697 13513172 899613793 807825598 588513301 511513617 699761360 914516964 119288584 622103273 10148170 830876951 335189512 412528832 597240258 727201138 283574750 836126017 181837046 735838012 425688977 278098133 120193527 855396603 844044432 827173812 60692080 298999812 647017921 441126138 415447247 847671990 498006902 684909638 796450906 985887426 179777966 827570059 834596962 560104997 185329782 998610930 730816625 317785340 632672933 809900472 845078959 979185327 416997486 859117798 461670403 296452594 735166132 936653186 825382589 296691351 944226135 513378260 492042308 776490613 141178897 582411750 817847699 504135232 238996155 627141144 436638991 229982189 365839659 927135289 239819311 982944195 58648099 720604865 118947652 584441545 850319699 891683583 289558984 258483628 264618249 902155750 898205838 997060167 944116925 590757378 995634799 573931318 40141650 944737978 667716186 417769745 180688947 617804152 613917823 641295688 478291864 973446310 209614511 564417450 290650358 203827504 713440413 534956392 96735693 13246523 566599844 317203322 899394063 893140238 264509853 978392949 349006592 569423652 785134653 409784989 817337238 680704128 423974455 41021417 80731025 449120433 229293149 544373209 830190585 298531039 54292599 700005243 348740117 255847980 318202983 410409843 96979050 640682037 262648341 425678985 678598088 382150474 581567695 836747833 896105828 131097926 209310043 772216539 459413057 562426859 367993286 369874179 764111571 528241107 993886524 845475273 354331684 172428936 624366730 621198156 62114412 24547844 478685351 20446086 171803239 576749831 462949907 33607332 797357773 368486950 763486652 618616841 379775706 71222687 149878820 330222157 296201315 404138797 961227424 182427194 645659937 42435392 538636704 326868805 978061728 215558952 658509065 964315362 126268892 650452726 911140166 146913835 35940408 546221593 978532085 216437227 295766939 30089825 204698200 785704588 683915652 122249781 662582184 562318385 560372287 349642309 943750593 155196296 36415327 896972735 672483823 543762301 675792825 90347483 773341039 756872364 914495057 690759549 98295931 221563910 498575173 262522577 815337938 252888285 162811997 686011344 825523004 412627456 972826562 980155164 932842296 920159005 674800299 273065799 739063390 945026147 763067495 914453884 126776047 356361647 736834649 488281407 258427352 669574297 579676591 123505814 965977443 188670416 734911912 831086751 737461858 875256636 876947724 391777547 529522342 300544317 711318106 90962859 571047364 745580281 785876374 636445503 234124043 272732603 924427837 705626784 159743996 974690590 710862862 446475993 512459052 865655354 607372336 769929515 273334114 104469597 735702540 889514082 510188944 744953585 296188854 372770994 81491992 972024394 685362686 728052984 284400801 884093417 839497179 72790724 819313658 730548887 717783024 981249535 321755072 354938897 606520262 674538658 427558688 679226114 865753165 782274061 83798369 635484446 115418252 33528581 779380320 84597674 921983643 964973926 799563413 920796479 379632204 994203424 679066535 412034380 826357179 887752362 749556484 590024225 849438146 325313352 490631018 551265484 930594232 449532654 661669867 920161380 596397547 12747223 480499649 903774629 122469590 267842864 838234550 909540232 591509809 820165906 463946890 183804754 433696876 454451506 250520877 171727418 905217817 370468013 628598066 502833423 442220735 808169943 582357118 651582750 605418293 501837706 640725113 214636298 477647264 187087764 611089584 899390264 681452578 777026804 794374593 942858121 585839920 41941551 779470710 844743262 418418772 175016368 51253161 200508846 88431992 957950581 737671825 640027652 538857368 895102644 738185972 18297723 418986640 616466044 713494111 470622002 237365174 33755269 169228431 699748294 597975120 269808524 703613793 156340700 447634469 777340264 625991714 730144867 450919266 849106394 534519990 79047905 435439835 949487749 562927943 692349354 482358076 724385134 821579394 550983044 910510430 961325547 636480595 414256639 460873408 696679241 51978713 696352086 506784339 870275796 987031167 487349432 371482230 714780912 473078535 661705389 137401985 451022471 448507940 623744974 408534496 3500040 401011065 728697088 325198520 937190442 595915991 571972617 990226831 703474802 161068342 92875056 500449469 435152960 757097043 665579908 138162270 128129917 656783639 521595375 915415552 402547513 278119536 305304184 886133305 962006185 556216138 71806566 662788056 108009724 64560471 735670952 463880025 429251575 964789291 91330305 261274756 259341649 555634663 374873831 248129267 605795411 266569929 467840695 912151026 486397565 101687529 648255925 648678030 466939849 794541225 688623471 363021744 156668453 110076539 267100474 436862496 36884445 591701003 447825340 352919106 634158197 170924729 33155171 124421913 569021157 24848729 607701204 966538626 603451359 107598703 913790327 750464959 704844459 403342315 160554296 1314121 697048009 349310509 48764488 311246553 441349776 228741231 425685116 649570583 153345988 665099900 897438271 400139443 731850826 888202740 390984244 134762833 424719435 644886242 754380943 112475555 292908580 847735497 161212497 450260507 508763428 391444047 462907316 642583571 190460195 526495950 867315257 190687539 889454395 472503619 137598624 638702162 473709477 366745731 131407805 856579462 377448914 420076822 441634580 538844677 442018022 915780870 58630106 253572110 500434827 831788148 809405284 751197109 674363929 85313158 330412055 813637666 137639468 295142676 388463560 543735378 155746695 77515270 430056947 977781472 138323777 830302641 74611278 124888518 567226502 580321038 162344639 861398918 201334076 448026412 61007972 198818715 305974055 716886583 538953885 964921365 524021503 633735808 953011678 748076378 17718007 639015791 659017581 193990341 682273712 40260109 415313534 21953319 658628468 810692815 347211985 505743339 87422664 541253554 924346444 895204633 504680169 687919115 708984003 145781884 326023432 461981518 376732134 12200654 891865566 921339447 439230749 140372108 518806732 149262320 310581579 917693016 41239567 997582365 117785555 837698321 742482842 210173026 475778966 858743509 325067964 286151463 765383905 796354760 529454961 521688789 604561249 131985238 687674542 345300128 606818962 264112439 25904717 982752184 678631268 966038091 475113811 6853815 734247888 661443133 722322737 600143063 276577988 149725193 76606090 850993880 415842861 952176147 182746706 66024909 910904106 561294172 795368656 360476075 908157151 937826532 270746168 801013358 486977008 998264262 750864262 836493601 558324176 376015947 978538672 227540146 289384915 155931443 845671995 333642174 467999406 863196774 851052886 109107503 673267520 180516767 384343033 695130635 127565522 551851724 789668535 678867717 32604126 540601451 20199495 619289530 854417974 981488243 326186956 61693050 129955107 96821901 141576593 77981126 567009717 558439534 896808687 136547872 499499773 464999490 61304892 287811379 368784896 128998438 768052874 169734529 839726381 578556095 532263484 557826789 742027871 142325160 783278664 369246378 158930615 183936479 872384533 557458573 584767469 336108240 155862019 653586986 934952888 685389821 267181217 369914911 80078949 930029062 257983327 703149263 66834473 378468872 771252508 397978639 330889490 75584014 873234599 537412420 51393299 498336635 752318586 261459627 419763443 979508532 370034844 417841435 969047755 195524176 418457643 915000809 258682722 10090547 84888178 869556536 839668632 449167131 942991221 713255952 846288791 36785626 334672751 729105799 836169479 221301846 507178018 338347724 910436099 17965527 157257572 722688359 657185726 86946456 990800153 794328780 20926184 987018312 925568 112026658 118082348 361513912 508858875 863512664 126616106 489454602 104989799 642620262 941137444 624277990 167030125 163121906 921661419 977027651 918759949 707024398 651385963 5315388 55106198 56117961 448451014 477181396 945453480 984029886 247609970 16342075 422306221 306128275 792183652 741236182 405035072 981333770 138321978 693415806 685215346 587183777 261859607 209913103 423053228 157186449 366599136 592278592 947751240 214100202 853452040 654918572 954596011 557085727 295417045 665418508 987040985 173623183 934506287 5333309 67247223 76683880 834031956 739093885 447840944 603254049 118363750 922576939 984548996 923543492 124234861 362298700 928211500 859910310 772637732 704725937 537063617 551039437 91795903 371010413 6578517 893444496 911468866 778862125 134499014 978559120 807214370 420483026 879107897 689173878 909276062 634812689 183580628 242405399 268612643 727223125 955675227 144877443 69690222 238243692 640966344 563170940 417074175 175159012 688056767 219289752 584704133 779017462 881647271 521719548 599857474 622322632 290967562 922369215 213485799 467261431 49507893 60120955 437720710 49773353 823243111 490052019 301790590 90629898 730437020 497363803 418497917 806210299 35412852 441045727 685241415 634974129 380912293 318240277 224472917 680458498 782621637 153842192 930258342 31207843 308434226 244828671 300348239 125353549 89995655 808167908 146222721 415456992 938924281 144837802 962790746 977546033 391861950 9854529 193741009 316587959 800047057 562462734 831041404 986486006 765534202 471456108 289423593 463702713 412360740 8084814 648324604 401041677 860929882 19243514 507079951 524612764 4603245 312324253 232861009 950441809 693970478 209454361 474061986 174155395 790028403 5367057 66397650 609606502 616428998 407743964 26812309 557706673 58791620 314048993 638149930 414268423 74622452 879922609 554970445 104326306 173751193 246570501 335609151 930323549 214522332 726812596 322795467 268508860 1716318 719975423 829806714 789166953 854444478 660126449 321412086 581527576 859372421 844603672 697098382 88306383 458799531 449847571 701052740 819070535 116427956 781067668 894139065 653087739 313276674 543048090 241362793 525419503 45792776 605313609 301951878 491262140 733168604 603956289 769715871 459499314 911800111 476517240 752763036 577969312 831413947 89768521 369037470 620332712 86652892 299595495 871128610 369246565 157487273 978249901 924638374 288743996 879891539 937297286 906005715 467327054 785460641 975017696 676856515 427643605 557094933 33063888 175075764 82197089 58636536 515863941 256781475 298261215 11981398 477833709 315268913 634905478 174016275 261614202 487392414 288854823 77856785 281438334 987320576 185490687 475152149 578420425 162854447 731005647 882052859 132319453 882701987 584590822 992223133 36619008 431659825 427502633 115540054 888258590 922784452 162487099 384553265 246459918 664578849 52966527 988675443 559698883 633635330 981147481 63967302 602976633 656938739 69530949 637333482 368210721 394431086 56877621 94731302 907322352 603964289 406120656 473819931 593921328 501464829 636273111 992169603 860245499 302379135 236742607 720755641 4452885 927081011 688913693 12519589 616333611 416255514 365566659 459996831 502861193 624909864 860813082 938631763 441119679 62360038 487964822 239711522 408980617 102245375 64559834 330533318 204274293 613436065 413310869 775567351 108317714 575821456 145161575 266804645 791907650 207987416 706792718 928894732 75921720 77536600 347900636 832522693 656742924 882620251 266885333 373665602 463842638 663266890 336964308 687786510 999981613 803074106 872949133 259644302 782427073 75399028 870482106 586189599 733333633 815599177 76100590 327856822 293726582 952749077 832098594 229125205 426706030 541155900 366459143 311477311 991882491 944615733 613757519 646493164 804773944 749079186 257821689 665035358 592127780 985435092 542114255 716956266 79142570 577047988 388122985 829783572 540733307 823955692 764783843 411364863 857992071 926063279 583433542 475034678 115303757 170512358 711310922 949415763 984185935 551441718 494928882 977064430 400177750 610785006 24175146 72473399 703256517 483917776 657263339 919481779 574113655 578526188 949092583 266152483 868403179 550739418 948274142 292904410 767984742 846482061 963417643 182591070 853108596 710792884 488235161 696606211 538844624 359873384 11481550 769218615 613209285 907849587 197028835 952361718 202849091 317499786 369186530 306530601 98423101 602018643 438652609 354627807 983792043 680252224 814481014 379319873 910817271 311355211 323848390 327108280 945374855 29188599 494128493 475515021 62515108 654623306 421594145 729899113 27857962 474529294 485996654 76659740 191689699 117351323 536950210 788500273 646961979 709358469 642691268 76240353 175538512 213328581 227855145 788686230 343798393 355352729 110179021 240445975 29600232 920282576 280072090 187043737 685780400 713251474 963903681 479716625 497410063 938394612 300527541 578679112 644534416 539263809 936968610 525194976 376969852 812712151 534029065 288830426 207985190 990966067 79985154 470212906 836508287 668016205 480439190 941461889 557900203 106360198 292042736 162997220 758718189 385991850 778527455 509038881 67567946 938368940 737770702 529194719 955583180 980403516 150321555 343944213 400944907 190017567 825955181 544177333 90588405 717846365 360750624 646569592 375599874 126965027 733551502 838632610 549398166 502096643 720896699 786860504 792662269 128291425 419917544 426841022 5432170 14868176 322386194 541233945 350202912 16193650 891502259 601881679 399948909 149410116 596772515 391986140 684324029 459635117 822262346 826708270 399475610 593128986 629149613 305174714 689971078 58270519 894758035 639975749 55420189 408176462 57750216 517267763 698772819 605396604 281106639 338528022 663165157 806543669 563627722 584061400 142896464 33406652 762452967 537507247 164168180 994614936 307132262 509480572 257007920 129523516 514700898 282518952 377694364 638497180 525677818 634696782 666497927 480729533 695323726 328383722 54038748 605718505 851133064 732771992 102796966 766066679 234365717 344532207 379952254 205828707 101061994 901174294 666169718 546862052 776050618 781735517 990381424 446989805 891388201 358949249 947014348 470826127 877945423 290999263 265485324 142761191 631588955 298732987 233859372 984114717 558700736 846521836 177610300 69665942 991287659 593571054 528656917 725829623 138893734 876305329 511857177 462192800 657958544 270633734 251235330 499918672 70081861 805368201 563261873 876614907 206519575 492538950 330007409 885916806 477066184 323234771 943824861 496135939 926592718 692967462 694459890 88533257 531031128 579880300 193695141 752739821 850183754 570876474 118527933 137615065 422551628 174694107 288470288 101756517 315495211 138669820 537763683 1856874 227015325 675962212 611133088 606709846 330096091 581526593 804832938 766207991 468797347 875924459 766873313 368276413 3599851 376404520 208745520 644054376 771537903 508403685 867575690 95349277 29157297 963733477 746752471 668117770 23091639 717394452 691881325 590597879 210218692 849100171 733633351 292865679 406718625 94144105 102955277 890797029 874889008 606095364 321324061 327163051 570881010 317944711 131196272 208535762 10175385 209481940 637672261 70022075 380827780 821236505 655805812 490403328 760486701 166509700 279193942 594146843 610053200 213279704 966488297 335976350 608570592 433900488 927420191 616431153 926033636 5997187 244980394 805101839 567482653 230379773 574329911 647423477 989667589 369404965 604404772 842844567 141120651 712510775 888416240 950611188 167191452 879173670 290059663 404513004 757486183 571398383 318782261 30245988 931836288 835357215 850342084 618923024 611222696 722235292 845419701 338379165 539884858 359453118 620102016 127101595 655212346 329223715 304676384 902690956 798407442 556844476 772897040 724008343 308660349 701632499 299874733 122496062 674629256 52227093 778081598 262575113 326325960 162716213 354857772 147929245 876404519 288687964 692837414 370448085 487187679 13569037 247080284 811361455 452680104 481170979 685870942 468573394 864203085 53716736 817728557 131227664 994921215 481630737 329502328 134858422 678705667 179627954 163904978 291114771 772663874 864381556 611943244 46081472 815712605 899501535 403449106 278597186 513075365 226098909 305512460 842752157 976907612 936068581 377732942 465349820 103059322 510667239 53949736 464482204 212466464 778330127 663905162 257099153 128352075 293249782 861810596 53155733 589305738 161077745 669820866 881710002 631667648 594869064 395729555 697588030 481311018 586290429 479756337 922931256 591266816 769020442 437525212 490887031 906117665 990222489 168871579 119830255 765079388 531543840 266093708 501244856 849380673 587668139 958910924 502738052 336265326 10882513 852548853 734556304 251823457 783724780 94372367 625621270 844204076 187025689 604253278 941651973 479534071 166927721 672589080 583095688 445545077 619868647 599419389 468503284 927006709 154852448 373624262 413607460 187154255 194234396 659497634 102783867 74202338 948221023 93135638 656378638 503067959 367180225 886997436 217453964 123759327 831413478 830343688 904641000 26462851 86698272 604447568 231448418 609638273 601490420 947475743 239054816 667964181 369225488 27305529 626826183 524514600 774669035 463651841 264476924 404204331 106300611 566872230 742607151 868539360 287424906 404710476 735201247 309736597 565748262 90774026 542075895 44202548 435382855 684807324 126486562 183034711 622825680 770117306 638285673 266623 95641428 904706866 797498563 6664695 699449961 735700557 819276135 334639020 139648671 463534944 844482791 158571439 667301455 70539855 165809188 714984863 918584182 113366368 626534398 129129156 990987453 564435216 17673311 108535173 427348124 959235584 968791191 964914508 955016397 550573451 359243114 820425009 421269819 306257769 73975666 742059378 484877906 542099732 153191745 972204120 757225258 516022500 876435165 941385521 893976918 948638127 719737417 161577093 264334329 283179366 488996607 533853403 546069820 244201070 978969018 25277228 985982233 421280499 101166751 469047065 731074171 768459328 570663656 477017028 673204480 670083745 722995319 464088028 339758841 775762520 117919506 700529960 851480997 355372536 211243243 472541194 23001070 841165504 650262615 915493883 404560218 496369920 809589420 248120901 838346450 881940106 792729495 862593439 635436474 977188998 711959201 69817301 572583890 620012617 975188716 854888813 988814627 638333594 825464920 906956995 632466089 112575004 474408989 155009852 910627158 792525678 938495983 952941935 4357427 359720918 336104573 278099078 497273073 500020620 870275520 720265639 723743588 363058810 8082058 738038392 800129684 661348445 356587265 413419938 818295696 174903017 56574570 268537012 474941572 804325582 769832923 782802480 609829079 125079526 152333159 415284983 225320884 627553335 89370097 242143823 300978771 588463424 205496521 61313224 297294704 878445210 265946467 895462697 56736480 201909693 280586536 770177859 928286914 985122719 694425481 66299085 473307741 94382392 541195230 943327711 200910279 601974203 489585695 354112719 455551067 364258062 844984593 373256637 235902135 644700642 143092709 740951466 605239596 271820991 160795736 423146000 611673362 87601711 931951418 267122996 438197109 847316625 63356673 536118766 753388384 167640180 18396125 526060850 244391702 391392901 387092290 134753843 602094871 409854454 255299156 96603729 42876298 783842880 567047390 560735241 586641688 190531656 602752664 727270741 730514865 409154242 134375528 75726636 214679076 626658491 389757118 669314702 710112116 446557683 911972717 192661614 4786176 763741189 512464267 731669423 874174050 530072502 431545490 154521961 172924476 809704075 250822044 905153034 550616762 678960344 634507401 723398477 230068448 859925534 462598846 507024459 437953088 37874512 490121722 574074061 198539996 171712800 724409473 971300137 492087171 801607629 762820005 372771946 194999733 454415947 166871861 927390698 308754767 123927575 803404771 239390159 889662749 510109873 941666667 579909172 279717726 768373253 113364932 493024147 785518986 530267133 787657614 148313046 884815222 70093246 261474244 607443825 57492454 456685636 20532996 345467392 356180937 675912545 864706722 389354527 956121979 363520374 600452903 451965427 75773776 699010610 532072661 420226443 161267401 931146616 411586699 84804268 470741153 633886952 334185357 163246347 986613711 868515132 981179996 806029244 445575691 914516993 196569155 322474918 610990357 522304286 124403788 408534835 775525266 556497587 531191673 888120111 180972163 594161243 471755399 70646674 690153213 962895477 565640925 58790134 51115202 753045818 739893268 822091415 595640199 322698092 938759020 766112804 231763751 564746832 113229132 919772587 166557071 198965185 999371232 608042239 307736677 733062317 477644722 39802739 539400940 956999599 314047765 216955205 920884761 993134767 523846218 553775999 814918574 277412173 559910866 826790916 851571654 163700858 476864202 679310614 969502578 396541538 228949958 229319424 164936487 972487763 51645652 54985601 544636821 157658484 552650559 260124598 324410086 684645861 783191909 278916583 16940034 23270390 74510407 567335197 983330583 588281581 807778241 902527601 54662580 637238263 332809916 973059972 570266850 861332913 274177336 291952895 26589372 277578068 815251518 311254815 617590392 820528263 826298065 2583134 327879988 878987449 117946940 83154118 886832369 453299107 123399158 546024114 952866735 916344800 911862711 230633420 517007012 920372078 154879324 112875225 110027189 201522868 775385613 711413481 74232759 911521932 880711280 642949317 925092778 987863269 722313132 165853359 398462084 370722651 622905201 547800318 501831160 36760667 732676348 780250912 389408227 656553896 298331725 586913958 797947495 357629674 178604534 471346761 658176905 158259788 270005131 702304928 861143637 110263911 343293075 788917233 763513034 107346846 338051442 968037892 501021891 438646438 237332056 316117640 461849995 673826851 267753999 670147225 335178641 240885258 834165946 343861363 830200327 867865692 169873966 924620760 813587211 298665012 107437280 894723678 686259469 218834663 701283967 480859945 592527731 923943670 404181340 51932431 201575891 206133481 872668598 561279290 502424192 323337840 781312176 732138815 914990645 172830152 855303435 532471535 227097783 316296990 425426606 22838707 198626673 336870280 557347154 885682655 336584666 389747459 638743343 548654955 413369577 944674767 527731204 751578384 252304089 512131311 108310428 222725315 114183963 263680682 618542801 882056427 596626697 986982555 71137996 159986194 505111465 931843792 867184380 161041733 410537140 837124816 234940178 170495240 476014810 716110846 914892403 167232661 399797828 360414192 457836893 858207542 753930929 402735963 127046409 937138655 866185032 208529177 985319182 196627255 732829964 223310450 55455057 473529417 67624625 236780504 627565443 24740108 244244657 546584222 156059194 926935593 233018134 110059837 859037229 561356679 429469896 596968177 40328560 533751214 146189865 9555178 556618935 785082 443666572 510345760 204843342 857966152 19177461 906502980 119969895 874750068 187403370 272605263 371256611 618042281 955124851 791326887 852694843 248579422 414558954 259975551 234196878 537524897 905041533 699037351 130989224 642775471 63211343 851292406 32990420 367441289 640498237 19642244 188255899 133019067 22215780 509449201 856693766 972123940 25218363 102874439 122502983 727190320 540498010 894838376 455345312 983698583 437505517 204846831 10781861 942384241 562493754 347966026 882221248 760597523 511597071 706013096 425007097 499573991 409131924 336797298 354066915 584661457 442936859 176184639 884356217 35944487 349609100 778597041 378583911 260226566 411290758 411407690 205291220 673461700 275572929 999714936 531916289 412906837 878443251 858623202 230530670 526236445 948817623 995008382 424798729 689472776 977787061 818522054 115917878 743834177 478106064 493118705 759215990 400694879 231241589 876245120 58573982 404074798 637062006 837767341 838504925 916755234 43722562 97170060 798028625 309352693 185059180 355565001 636585600 335542781 749690250 880086357 505667872 689729309 214004864 340630362 25168334 726129050 94281704 376726908 726071377 990394468 844797065 537532912 767869972 901456269 829382451 769690573 456527545 120314926 833806775 924177145 751565947 882565522 43353269 736789653 378977209 887497434 830148225 60192689 392715114 686563927 154070866 124786962 44238045 200898027 256663972 450005759 482966693 979586421 402579729 55546218 989419560 301268824 931444517 629314084 723357438 662077100 204622505 262814895 620614615 926341797 377202551 196215329 926044067 408057418 493673728 429537696 125148584 335938970 826282705 804120253 846748721 151761932 295880875 809779530 928159273 272923246 742299174 21117831 379952099 546809184 559650802 836398009 37139045 339647705 158363044 950867485 711241174 722721672 68319920 455873602 73686575 349179821 420167214 780151556 452674521 70180627 402971468 641846680 51737849 500838615 299811718 880173808 845570120 449926449 860308712 397684854 375610255 284662772 404792730 72231221 783558699 684449545 13275743 661449554 611794539 356128265 823478211 116915627 747082045 87626473 777572433 860362589 974446863 283468045 878494301 664180100 884096524 71194161 660104974 232300376 481578846 659610863 517052573 93383448 196412486 596401425 740977206 170638280 703955263 783603081 271830429 30033038 414053672 265693795 685036055 324070411 692925776 424107996 993519997 447488121 805655242 621116103 708953392 189391819 314652359 197947379 252681043 636135017 164223382 735533050 955263479 824148310 223543906 466068133 211021225 520801954 162702214 253628863 97253478 492460506 688180051 121240936 317389338 981439245 275273232 599006241 967586791 286720512 108589368 245592183 676666803 759950502 786938089 574593215 346362481 920255242 654459371 951545039 254325997 855114146 554814488 896212662 36356927 254935667 320373530 70669088 149062495 499056598 808035994 928268799 606229827 25102005 844973766 550024840 284022705 384892769 243018540 387955953 265611731 949478820 833619412 744603547 673663377 448411987 742569764 721357560 452170627 737908048 202298218 709663900 835692982 396454362 236315610 641059971 279308856 962846931 472129319 58557017 727760185 255936739 788010342 550755786 746286261 412255297 851405483 398104562 249673397 345725615 55682490 637324162 865219738 94564032 717908354 493562239 498461257 64547267 755499383 189606421 315167670 880241055 560359212 651919895 827721219 21871666 497088101 70132860 749471928 436346016 24838475 745235686 996757682 921201593 572032514 35656642 718708701 610394309 135260896 729083215 936246263 185403315 325642440 448291278 751973982 627918487 710545470 113941043 742492105 429131301 404660929 75700799 116322704 642759485 960453077 969627333 839910547 408670406 282448775 564737555 560059754 940183410 299186539 349510969 537864091 547678921 903584140 872187742 938691892 283597271 628659608 93546273 669453740 599783645 986280488 550569069 534620283 230991448 276290466 103963043 404441755 424682831 367564821 665971933 165363425 184868563 448998592 924369971 847111356 685140591 500331876 828364914 735148014 286759234 336581079 835793147 632905533 679772688 848980460 768071927 584065269 981820007 255277775 460387791 47356751 318736905 953100401 192390573 527899572 899384066 207104319 693261484 197430003 228926955 779038115 27759709 227844447 239421596 654426274 698550160 758896015 737312686 828327681 370763564 547628812 649970791 80990150 960905204 323214279 567810290 550268090 582193285 872981777 519906112 16180333 177516057 136021794 315779066 915590031 212185222 618308409 484862686 800861082 581079721 190983004 776153140 83018038 582270247 111397698 546667357 550431239 564223557 980384209 921140954 624847397 749095374 818920278 874929553 986734441 993342785 907902212 928877411 818660348 554801873 407728606 432050269 886778173 740070985 881415272 293631080 763109560 985618012 953157943 619559280 962223363 983512448 325428369 452137861 306013116 689847022 761181069 494247977 48816382 466372955 403043850 603805856 482357165 95704348 595415703 921869007 835288770 837519667 897266558 838079125 372636945 748822092 189447845 405223414 373748118 250113275 545366932 660295083 326486202 734548631 564547464 512055288 577068058 181017638 197814735 971417819 428150224 319277945 736864706 976877100 993143405 769860323 974764789 139116796 438511810 520467758 889511873 641716268 451386109 481258572 352178887 249002834 614090482 162692107 163300489 391922381 507644123 505253899 77987987 457754878 370118786 494965302 515909296 448756373 27653715 139203757 773108994 799160043 417346968 982427170 720795833 268127707 612343960 826678660 973330991 388047077 608906718 462433681 351883586 857230420 346523093 630710572 828970776 787345146 959449317 610565918 337893028 295748643 606847723 306333115 581252537 363421890 763684600 330640354 960342478 672903190 986452239 536048143 251698430 794265114 771754977 606709841 291121128 544325223 927426011 172478986 927480384 706648402 662505062 873151319 84994794 438142490 376878192 969911636 544519671 92740567 670907761 392185440 770497867 55451435 867418850 386063007 843365753 346295210 674579709 917498305 568321704 727564035 569818905 338678748 464070473 707586217 623447212 40294409 362561140 641966517 897252308 895826416 771122760 103946090 711043391 807195400 641384897 622565273 123340396 544156320 815320328 408826682 440915946 789629958 713504291 342792674 783959357 669981935 850175054 982705095 25750034 749532837 687200001 745303135 521143829 868902435 864340693 249617615 580319781 345429306 210973777 399820162 674406009 309680949 726643822 262758900 634255256 130251989 403422293 826648198 137313472 541152076 833451393 845149293 314722964 623276980 750813653 937783558 527521650 949102676 413205776 720222126 127669888 187871473 793488141 692262797 516519840 129498211 534173667 861696905 92748409 621827159 502277897 291394923 209882558 384177212 583621337 438032652 714752768 167103186 333175578 659719421 730271179 432645169 572391232 259202254 620881718 352784459 677097007 309507942 762650616 544384532 210561620 22132324 943205633 860507869 8211382 97278158 821858734 568017453 274734485 963208343 592892517 676621452 383586497 828805845 755610545 720937326 390519691 70450894 107593525 232204439 803136869 954898018 737529189 627333309 676721928 534433855 720744925 133952675 310359741 972127983 39117231 477668437 754516426 789740564 409672552 661086869 247583473 364846980 691179345 520238614 69132289 492420520 212623654 391028895 315120264 959265862 720771699 680240052 255141183 15738945 695209104 419583503 145424995 270201030 447787606 737217342 600448697 381003638 60868316 587725634 284597220 499213417 103097114 298701576 722651612 471721419 146921101 699524763 412152386 345696924 86828879 958368303 675023411 205453558 461907450 118789796 397101952 179319377 839702157 777761824 492270122 672931499 813657320 996975455 681707017 23643068 135366333 6153693 244898252 307714545 759352660 207397831 401043889 482983014 796235692 814019423 237797314 347014914 610472078 286281150 534673255 656146134 715819610 994596392 237455059 146327652 92089013 780118999 606990873 519536747 40035022 701850528 152931832 327494435 521518748 665805556 984755762 822024158 349158879 622513688 781050085 668953722 63926809 620917728 226930586 627745277 188994579 125170635 983894357 770012357 609792088 928775411 563366621 813789926 57763150 50563489 511262830 781781189 944026702 915464337 269555672 627891495 370532284 165460589 756837302 142414347 74063293 315181820 302056398 683778397 242287760 324663309 902621440 444690305 399214725 360068028 974028877 431529984 882898625 776204705 422868317 183176663 134391714 166659079 410167601 436554787 785466130 753315070 537263044 277106311 37942326 254742369 46886920 545891433 559537124 653814333 442786903 119764759 635926572 44691564 379697217 774740198 405876562 527898279 475141078 907067269 59624129 783756133 732931347 176452272 894881353 740881061 445089799 761043683 660800749 478684254 360652308 797742095 5540858 2244300 959606688 643017530 312806513 776862865 971174458 507179251 491765938 200119081 95539213 760184234 289559050 551985510 540625608 831848339 573769388 140021274 577702248 25222971 485202945 618188179 971036076 261219507 673495048 262672386 740795760 659231069 550200085 210257256 476879274 510335926 731207430 801609628 285464738 957785849 565778720 332962080 495524754 143813723 477445545 192660934 922384974 986109819 755382839 571805438 792117345 98104413 15988612 781253427 324854481 943458512 228230672 831166397 333848861 665101149 367926547 549634966 27167128 467771292 968254944 962677478 582928739 172104929 674178051 186579348 295583774 653994997 686516433 210918662 43601750 679243425 324976199 267564451 557030877 28468833 981945131 106000228 527404054 225358846 44515970 956245020 593791511 928460476 187085572 700344563 46561739 857432711 779743598 916245904 867593048 593525918 256936963 410863976 122782037 510539201 492730893 872369301 733697594 90904139 126187729 906941926 684712262 761804756 485241566 408983921 288710129 681207436 91372554 962762596 950339670 646042522 890130966 687759779 197861669 725243339 626046950 32659245 693162116 836120535 474267032 29598976 119194493 671436167 184896349 28575644 612827761 404932748 582686473 343555618 562865488 796755466 619476428 713595928 562841132 892202185 280502682 467530200 618431012 615262519 235288029 565081803 873595239 98501434 329595751 339596146 151920626 449394 564550214 216941291 34404253 446746321 29859749 352609232 46068509 9000432 509635512 809343737 974174871 537164423 580597491 61514126 576515930 57449904 838209119 872295270 885679689 505505261 788459188 395187585 68482774 879921825 602146232 729850650 309806033 77663671 668796385 273321923 17255297 490851014 924732925 292198143 531083284 667702720 144363656 707571129 864792666 487103508 175353454 795992425 160913758 648927963 732879469 214961603 181575041 968069338 208507323 984093467 941236447 149185197 142234326 442414810 120162147 233785343 970064455 634566827 746332213 822568711 117779562 944782533 756910968 447297621 553524549 982360196 221054708 561631930 198470554 300082308 854874135 362474230 459564507 519822675 666636004 583351313 366795775 370400606 583520746 743983016 725559538 766044068 227149284 131420477 263263768 850228538 150049112 556606438 539657050 92025237 34163976 439012532 924667523 380321913 613103292 860991648 49903028 304770353 454257246 120547678 545706986 646515431 124539139 967760678 519887833 733727943 527911597 181226396 988552130 727281852 475565434 317314698 918565248 116062208 361762437 8024581 444756133 861388554 676451012 311607077 176067161 673062005 193239826 853127821 103614524 185939278 939916862 368776868 983028825 595217738 846670062 934487267 421030523 104860315 271530245 329729936 477688156 485867225 623278741 809112480 562907723 814195594 761117490 754626845 976471029 718057214 360916971 713050759 188795363 884139380 138604914 719320087 301513407 969022713 160608437 130158718 722489361 462676954 227752899 400271591 766997185 442598189 360547211 297578191 478122383 283133226 843411931 127587197 48486658 362682482 806126333 685461606 372238080 889860471 609964386 330502432 488300594 264308477 657032038 713254948 616633952 825904271 913258199 803172804 315550224 116575456 162725068 158862083 885160796 595628410 252679618 174402956 152769697 617138753 876947166 790819001 817627128 475550045 388817165 705156772 83925096 791513228 612225699 58876594 458201925 852149916 334607108 587001020 990291986 997379425 920861497 47168037 65946196 657122538 771982475 656197103 910969221 668071774 807322487 384244939 780703125 815640389 982302193 903665183 752494517 148345309 585113103 429797324 513816990 357155718 926427147 209507730 518354881 671296966 57545231 561605549 667669880 490903095 559485807 243269955 769108701 562212989 264670378 578719349 966729020 560606275 225451729 986193178 823480261 901649399 75129159 179161186 505031901 454932171 253028217 262825116 947940356 53410022 443599976 414658468 984899772 433747390 513861200 306843677 617016201 11859362 688322693 378207602 718415959 407738438 135754086 560091306 233673865 515181342 679581587 962225885 416089235 724257911 932400163 534508638 201352072 265359335 436200952 92988653 363180759 849541058 138748948 353775933 509504834 950240231 833352699 193488618 760371052 76525045 555826847 542069217 374019936 362063247 962908794 235741079 41946634 989006975 837331864 987824368 416454901 18518781 227389563 272695956 268469470 50863619 405081645 423334455 479556895 87347400 758923295 637925690 210426373 687351205 880490776 715706922 810916780 541789998 44950320 697123630 477838285 258690464 331353885 308355016 322222096 698804814 232936227 753586987 142461189 547892108 205294138 410706191 973474996 690398286 31398017 656641566 582832798 820142721 395511147 13976708 458652816 424457073 72203487 143499402 336016 567633946 878669965 963611050 929400165 57777058 144704075 52671430 834165487 674875328 679814339 367924824 520264626 302275206 512874511 25217891 90340144 337138739 774506421 809021056 525636105 145822310 367900733 763672792 238678408 58154810 546794063 290206885 930630847 885919123 686051677 844190025 16128047 583339675 506473710 311281768 146093549 811576142 572748325 693581097 659328861 405026467 209568383 327176643 998812720 644808786 109667281 253928027 699316683 694488527 451740554 988486674 710504535 562676502 432585483 233951704 139948457 470111447 713111779 849284465 979781072 23101321 846798642 656400365 270648919 869436741 286596418 486172825 823245094 840119293 971682486 773360584 805107508 667880967 202831080 912040213 374478401 192480225 344420708 406342845 503466621 653571355 272376137 81853367 533386570 126008519 852241038 509225692 388464015 992782153 335788927 738776050 620943507 598478404 839392102 507427763 19216337 536081180 913826895 398705946 909089475 130567035 69375498 887886036 586077807 133226257 721944465 702793957 127393694 125947957 814674818 578441574 921685582 870501287 544331264 297458783 604103498 913452642 316301906 90291036 903244111 476783695 881937795 374631975 845332837 246870961 311305270 547032756 904637637 501035226 20892686 288044057 564161355 415435816 485139443 746602112 784991568 961175317 931910738 714260031 875700307 331231553 259042070 854410718 968622324 880233725 844117469 772333488 9682079 4535216 610492698 585148232 175344386 228968403 721075832 820070928 903787642 702938806 929971610 64345313 452656657 130418438 938455257 876002429 633790434 381237173 821888505 493129496 668718630 243302515 313586573 296605896 517032816 352537675 776879468 433715177 977716676 895395720 630371811 989396548 28245033 253622757 819762090 538159098 49635116 232860370 910660724 814784886 346448963 270742838 263243840 691122853 897409801 411127658 993755625 223451758 131018857 881116964 906321757 122112933 726488837 265577924 846038138 658026363 440785898 266587875 254669047 383425479 756615502 550882019 711687658 843033920 696048096 398145803 720719111 357570633 936335679 228910687 272270545 226373782 708957387 39523145 63524188 526035511 9181312 690869114 85196317 733437732 513619759 912694183 28867886 715759591 798489374 242584338 841866781 277314493 597198501 443229623 284686099 98520809 367034427 345965288 813435534 302595948 970543078 324782183 553794747 203020748 843157541 935127597 880044050 60459617 223601284 422813769 655816990 762370541 959662132 666657402 977015999 954684552 482687952 304286399 708206982 857441437 202337443 240475607 760003353 681915853 935157152 181177880 498513942 453213800 326440238 456945352 833324792 106415918 745036453 374652895 294345325 199888663 684229090 15688306 905081474 359081130 533303581 669906887 564877782 334469845 905411366 489920574 723683364 206170713 314787423 971871234 408337079 679804606 627652451 41157706 414263889 378606327 755222999 356857143 320109404 182030112 262398493 285629828 871588311 582574227 557680448 949452578 669370322 164300237 525668872 165557846 110109483 790450147 281124981 833479465 247952799 830985573 785725077 56338041 818739981 410956557 772386317 809369999 377041214 870470885 210062386 705992738 311778388 60901925 508328942 791859252 344779627 361187688 711632067 337108040 404105919 28176793 931397483 620443699 821279253 955200666 964082869 553974163 6806056 307522935 859105135 225985223 861027912 914065359 85940622 461779765 419391700 622436537 920898782 913700980 885894420 575654497 625105384 255974468 196055898 254612925 485130659 658521871 607769132 983567330 982123054 354174629 395907111 31850025 390023756 233256899 902872589 672950280 857023012 631447932 306028865 307321794 777099233 46658197 6204953 374614895 123797274 24732028 891230061 540607319 387796161 355273854 349494054 403186077 600500226 405405581 280976693 992904291 335088230 462600977 311210703 156578641 282579795 912729839 230860388 970226978 906620423 197523950 674597659 546734109 117942692 354826666 210952595 72245376 482531087 551909481 821116022 582701878 678764327 828806739 614391391 700746696 203172898 966769765 937535889 32534161 919101282 124150790 822417849 957197675 751343502 43890469 337995920 257447169 559080928 300147220 862620936 713820537 130186251 793767331 463309195 972323698 106387407 603883064 234649085 782000576 757992359 274089364 716862077 307311294 519729003 24748430 811363833 836831570 349711279 607377174 413822852 11855200 666896791 956652449 916300778 410355679 602255540 591295342 333370090 712072989 925423124 747504496 27005251 632893074 765962740 162450213 658844731 275858990 561342560 697631077 739668632 623819389 275379016 429906668 707802747 985592238 586490272 465406559 958232263 385939655 341045544 900646516 902575243 871627363 923834696 367361384 30031700 211241619 450722882 472270356 901753875 677313276 665115575 761581282 952357839 871480134 993714982 122226286 67144431 671297344 965520095 216456512 118378250 791962282 90801727 838156833 237476705 861905793 922477046 883439382 354601569 883040417 971475398 520910166 216296692 620734722 194902084 302109374 240906173 182554909 985201260 540886145 77284451 201138676 645349666 712341145 470125084 958504519 482284502 83547282 253870214 930203378 253335671 596340134 222005954 787172053 800231123 302589037 37943336 327346560 783625482 337432862 439298091 206741179 91004465 341857200 122955228 906514156 886699930 390905244 354198264 97503009 807409115 881880823 647175056 897056363 803461960 325892516 787657223 929962509 504508375 179307867 78447253 463446102 826329515 783045353 446391673 102730246 140163289 457561124 937504446 346532156 20217452 908570783 466299298 969882265 847564237 619948616 328849283 879621483 98886194 537444565 665599996 581206646 3015132 630638524 400961494 96339637 630439050 74958973 796564244 525290094 451898845 212587079 688838043 370492691 633778618 734816761 580229901 915417272 454821892 315288396 38417109 293289140 36631986 49533028 890344155 804417272 929566047 63742387 619002608 349461337 577945554 267544945 292763315 365688449 630792020 363439288 519692791 902806590 593944744 309178740 354647438 790398524 718889220 547874458 496423214 512646063 788992217 444760723 533165678 459080498 563250538 220524249 574417895 759163682 753510433 852807695 670458253 246826092 817661116 51196772 580601558 182325022 783979587 451058058 533727444 151014929 379136931 877638804 896202811 944007817 430914332 359949425 793792839 559945342 51599281 561631295 887439754 695976827 817815750 918053642 710536359 712827582 462395272 667933479 495632064 246809886 362732278 91361712 356264055 721698342 628739733 173275201 192307123 927124174 574232752 569867305 964182880 616770676 79120784 60944150 211776766 265324282 853020229 290109661 978931553 205516240 978728730 856279012 566521044 824182965 842726707 128217875 241787346 5715208 737281789 682636943 867135554 390569539 387349711 259023047 776443075 584005561 202887988 677283148 611889578 560699970 368807178 854133115 34836127 86307537 865296049 754985394 524626802 11508995 237720674 631807918 920226887 659320553 879605998 797789962 967961350 963493116 458211080 88639736 337674913 798157420 503050456 185438937 501544445 506170288 931237600 802034275 394686335 719836613 603532826 776219750 492131828 742823260 90025149 591475356 948296721 372240576 848114767 318496696 869569083 453690625 269731957 588172498 127719569 605499643 313704001 233439969 732426387 611772320 188263150 743871729 912719636 647468558 826145817 615801762 496656609 144657391 12950712 496590365 129167099 79925736 27012574 664220780 164377720 805123966 708994707 301484226 597810967 996179489 891039794 928926044 627421811 582530515 569021695 699083485 723294118 708612759 508632684 58694739 520208756 215068846 637347289 907948055 501260360 448952298 368480403 66591710 893462060 286447345 929822035 706001096 645144880 785991099 18280248 825781910 551638424 850537911 259424486 987384488 77681724 319339979 392533800 246326625 77166265 606817851 812388943 686618666 851319006 569843714 172469531 214602813 595091756 694278785 602710576 421798658 732528155 409565131 723337727 269600478 912167071 882674787 429313897 657945016 577231568 329184740 651804125 601825960 313524635 169623107 768032286 686797774 684768957 954438822 274258022 324961430 492219337 188431056 711893307 172914886 870253530 685576354 853431311 163272217 782692338 33101130 140547915 406260493 971894614 404687796 451625688 99390720 611468382 460592810 267900304 761114532 611861474 600270631 64363836 847516083 514878092 924933308 219854460 698784080 708938882 500531280 763180470 173461591 733159732 471189502 524335202 824701531 936451261 610913012 755257477 724141381 732116914 830894314 923527609 748714562 484094251 223404297 740387495 742355080 513866627 363838369 38025269 278681750 231815746 776245519 699183989 646672551 310615050 102820769 716840525 677471264 455055441 173108121 330504510 782877198 988266139 870061809 286893915 801233482 943051874 298184234 204854408 308330152 639680224 718459403 65507975 432116090 286010429 654476554 550530751 126299370 398086598 587925744 958501670 15595050 330642254 824923821 776059409 803421741 409403694 799334505 107685360 400665301 583684035 759239405 413338102 625893107 251893031 16020023 37763320 755667072 238407489 855023702 330588942 402541344 338478630 853989064 71242390 592305215 197127216 820445925 129595342 519149614 533964020 15462851 397833757 569174417 55702443 590557813 868844832 288545063 832520898 782057600 408752416 557140735 373292382 541714573 227801901 684016206 149618453 948090547 533827713 912170657 143702438 714344210 860518850 684859333 87230889 816698200 42935502 549565516 288755117 754994588 68687456 507547560 586470675 702192223 879008184 606661333 591907254 762653598 970999780 439929083 858176559 879782132 291998168 689563781 169210955 671897288 560845913 44793489 260106720 386631716 50441203 259014849 737662524 240659436 944004797 270975911 868401438 423108792 426252306 91122401 926777877 873712420 765428593 505644443 119862621 960782196 303868211 660705344 937146159 661498228 907921686 831972658 469905543 986325436 260067063 327615976 174382282 587335996 516992678 391464034 267549991 483436987 926969124 722825594 373293097 73642811 516156623 433959119 306998661 960267148 224776803 564840575 424067032 212895269 947414064 410678606 146901888 726635508 545574276 354706544 217156708 725706899 338162719 381608089 520175275 629790477 23072785 599236380 343483958 490020019 876502000 864606692 540500731 463466634 108149627 950088162 217354147 153841209 854453427 281989628 616270378 861001645 403230432 401978478 929727313 864770853 162318831 827386954 173130859 231155099 703788507 864756258 962086285 246500714 534396758 528452251 509777557 343037578 711197528 627797208 924120872 737059231 811581517 592738721 695678391 927788139 195452717 940079078 186760006 815179120 956419319 96878632 500950247 241417402 795300796 223693807 966466630 675804155 194181889 528668202 623733622 904682118 42181834 791815678 199264160 349126074 722392290 848304546 355689832 981141781 820673801 702072445 510365158 863545618 945888214 202630218 370537052 250524765 131020251 937632434 610924054 962000049 764346143 278223435 611352501 316112163 555566895 588416916 320583879 357628127 645404408 373683770 30809822 390473328 547687076 731852341 242930159 228040621 313620866 854306926 254256841 428861418 312434466 898510937 246444611 226410073 68233188 330915199 50947526 923378501 120564844 340634595 733332304 12862363 742138383 315661026 675570126 642845366 243555752 52602040 479787435 279117289 897037998 715956833 556115202 337286374 219768504 621079610 401236815 142091220 172976691 234631632 860663555 460770608 900266829 172573597 830918414 831448891 943684539 33432650 333354492 848555439 352866555 925484778 492847682 446123872 247672594 325367174 798405582 231148690 338995773 844291513 973346322 911354004 452662755 850417710 488688801 188683796 74458290 313141465 381936136 11203396 437216212 561060047 38096401 826654185 190416352 469840017 990816113 469080214 301482636 733499370 383211059 165923981 855516864 748729453 925519352 389979221 523602196 192775046 175182776 225035839 834356924 946735082 730388606 616417989 462705165 42616824 504822610 51909590 128129682 89895669 88652970 210901975 356049121 379036010 399135673 316415852 56755309 377645011 719691771 323098964 471577035 570841862 143216351 45487489 377187663 150551470 210381913 232971458 755014936 673118439 834214133 297527394 969471543 44703169 847787511 209489656 968635221 24501069 603399855 617947878 634191525 553826578 142707269 666211980 780415495 333251014 412091235 231042096 439822283 75083259 105980613 675419945 979433784 657971627 412839791 166217793 549108265 842053717 273259991 319487996 669606843 436450745 533328059 453166723 629001702 955518169 716098192 275145751 130666375 952671937 973318946 404710999 265617808 769620461 268541850 967352371 174797814 803124488 58680330 565086431 704712310 263285466 468438334 921255471 2039601 347220671 722878615 27530539 851587416 186148651 823324948 21419747 679080780 396175611 840393846 252384047 602783385 292174398 672008767 942805291 63667337 330145252 250361127 945998854 355418035 268238378 207790260 954509014 331346120 655002661 993555769 773991209 68183755 755296226 324715641 824754200 286581917 297901290 930378934 723774593 690143928 642526768 522712055 652690514 921321825 85886343 136944800 8564371 512017155 704281861 474741013 768045735 675551843 433268019 433959743 816183074 708346749 283862878 41104439 377141527 120040479 394331460 44718969 215158324 460028679 552696208 347925418 277955776 384001644 664868544 401467645 530227331 96267457 341255404 564566511 531776758 400510751 434760570 837778647 809936611 746749461 285805320 729137335 807549335 765670677 802376287 808819788 743944679 59436026 121901804 994286377 182126349 509902328 456567601 483443231 27126996 667961970 8650523 947153128 144932403 314842656 203942166 1160748 109424989 997527910 956204884 871330832 403582711 215552425 862871789 377558256 384042214 378983117 924901507 166551556 639743701 422246396 358843497 160573542 234074946 640440506 343690408 853325702 611814657 266425900 59751981 941991593 453064584 789274724 218510705 186124280 606479090 385658294 182089792 340636059 103717858 929164351 421833333 605841019 449557846 427275903 95692785 972826979 560881653 355282743 790704727 771426559 897981035 225089463 541692554 418183897 623326778 952255593 249049742 521679638 203339279 858783953 697012588 205416874 570172350 836897800 70016388 560632839 885701928 270713387 985437161 930095512 757949586 919851923 412548526 574664104 581651942 320634017 201416817 111206341 168423808 656930257 724555890 900527344 759516505 350518852 283535706 669366207 409794457 831418848 980010302 440753067 605513374 389399876 144619590 368386346 273532195 873449144 998899489 673609360 793154318 153212929 959423424 100386654 355652931 503625322 244765476 953083847 151372273 603361490 641750376 52594818 177743445 319371307 152503540 444527777 982682129 837298546 203112117 192758755 966291938 884163711 807292841 911247514 194701210 356775330 877479176 329951268 577383820 797197745 523265358 460595919 967798230 278434164 717338917 303801312 604635757 740961067 203833440 886610191 961939024 108854095 125086001 103114265 626931772 142722022 152704719 778196024 722262846 776838149 156821727 493337269 777435903 442701091 666511218 846818389 78455553 745898803 521939549 642275351 748378036 479493922 160852104 159204377 664345588 711933090 906905117 127522292 653588363 859398563 236023669 768983174 722007725 832992718 456164141 428595075 67740014 362734768 51116043 692693454 730695729 722420114 512230256 787643161 701256147 840040223 598575736 368431773 317071842 418630538 164473880 679878994 339772221 264264217 807657116 652504256 64264165 161573608 414570744 668540963 107581615 397126660 306309380 569292971 454463531 796646053 953968113 97839306 320484303 44950416 872397650 790461642 801603811 400616966 729797755 903730826 631889317 107314566 797826055 593858907 875599923 91434042 969609635 247228152 198187405 699433935 310331219 898222296 248642251 358145544 164918578 758901334 423117929 864446737 799800932 721596304 844634726 706385759 699151584 593071145 183839971 381192304 789875455 570487987 78423356 171284527 708758947 145575845 396108993 856708069 511244803 466722592 620406730 112845597 65332453 66381612 395237233 505571988 505491806 235750380 694168770 876487827 644581097 554542902 832899007 779154654 740312877 647036219 151609083 92800957 921473183 626329561 344742415 639150799 709025886 916459620 327223242 760065050 439358030 922152979 974700583 842643574 293317699 480320084 167333162 249636588 91264860 606511056 813363468 264161265 843234496 587985901 803021260 680367685 454467409 345498820 499620305 658139585 283838040 23897548 454328471 3904673 410532071 718792534 111550871 752070214 947948344 225393013 514752208 715987333 721467727 32616130 877624612 241940046 839340524 841098176 788582420 840903532 549729929 209678022 605154218 790116532 941124100 750768909 10033321 678858703 326707490 618818298 258358253 712805697 978410477 166799044 339117915 109946607 914293868 855311941 575602026 75288199 158015692 138357063 174710255 843557804 148798098 423142913 532268060 915097077 889939701 784448743 341970025 608137712 40831908 589475701 631654314 839487910 635802570 771670115 360969138 680520537 701160540 963004481 185809152 99031801 522497679 664531322 64470761 35810606 322774967 401684376 211861829 263897520 361788713 124793070 539274659 164092251 938860605 884059753 631446338 864869088 96681151 95236786 637263591 177893375 101811442 319820369 699872617 494712146 882224303 671171144 81597461 199141471 924024415 702225409 205386217 566816328 722043670 831663552 571839358 875017286 686537366 148062165 499070246 85393933 262875732 569093514 259037410 736898027 478801773 573280115 726975590 265741442 409446616 712801425 785038463 708881200 314639304 68728181 614419514 254179390 464737060 804825424 866210882 321104143 93709580 948562392 935976990 556977663 567454672 524253625 586260335 26661890 608891661 967056984 398133494 747702370 841577902 50699117 811390009 144274557 479883076 688373061 681153384 166614683 634715085 90649973 217718416 725881647 588815550 178380610 672402604 696171630 829955872 118675874 182576405 289586082 764768949 281882628 263213587 151377208 171805108 447538577 938772456 214006098 48972825 850638312 866970787 794018935 500544725 512326819 871214666 285440101 875632314 566285433 71610325 248524238 937282916 55634105 696465738 613614437 373094762 96048690 148741993 605642210 816785647 220223710 814257114 935326713 576741273 845373723 640042922 71480125 966792285 48369566 813084829 140077534 815627375 455609228 473076412 771607932 741378142 433469658 174739866 307487758 268691538 532184815 436918778 456262081 931297172 557264073 990224092 557098146 533133289 159880307 23036546 669620166 452435230 21476988 38103501 800497895 543799354 731141430 109083548 500923030 102843414 339464550 17833252 626123314 202936692 12064656 796733303 310126508 649806448 532399939 896766885 682687442 365894028 800714041 797503150 737063419 942604559 235632261 13765383 449687284 66704214 69269021 495805154 405217227 380507046 634266315 524593512 973795638 737122202 413636064 794160071 135533820 343320821 920757026 266756562 165532958 285887089 507451491 722960954 400773755 366917521 59829074 234005759 502275596 313673913 295398046 755334050 632911875 278569905 759688032 287099553 802274213 927280727 511916849 657590794 383515660 448427756 864837160 249070928 891918122 13010752 290066220 819742521 443041333 525577908 819991928 57801743 983582858 327717877 526108982 124304426 45878481 625512167 10894489 744195142 64426221 745931984 890596645 410224200 469333876 947729215 570350128 387572003 908249654 155068183 954376997 635348435 616599844 606619956 204004040 148698677 499009718 527904399 413884748 538827595 332625055 883269767 333764329 675545450 44584587 409132264 31492268 954523041 95835561 319687588 50994588 662544563 297363211 489359014 116764487 588628651 317608553 278697801 993465870 120164876 273508254 319723056 76046598 336431007 289259101 738776864 259221394 10063321 229107572 246833701 399367330 114270060 604896866 142103642 740692762 59783277 353665222 307376372 352360528 882177619 29901779 529651372 219246056 817151261 271971988 479249961 329491675 697632469 970038023 733244803 240605529 125962775 275103728 578722218 402820996 101988309 484459450 248142249 327983810 222775091 928647529 707854749 182855589 39321565 72600256 418924821 915139773 241775856 168541812 7506274 698723866 333479512 565802040 643275444 157951932 685992255 993498184 63312959 154455412 54718553 25019815 186744311 320948343 167228159 311234071 540471455 325543790 586798855 261287440 44878411 927937961 674583198 479560271 839303982 264238072 938618585 51259159 933926002 621241107 220306295 641850775 969648292 92559473 268999944 709806360 148119249 617320709 502661334 972790294 339589106 796967981 879798550 460682945 128847085 332119769 311887745 743371318 78820895 477121103 403643170 174607751 662567415 995308473 618236584 820013526 211742621 324236344 93606392 384764723 424896642 546748243 213058151 459711563 779364738 10586001 185547495 154004515 800545612 387409350 101751553 535725636 807709103 548227322 845287667 312161665 343825146 989010151 782825701 528537061 889253288 907127119 612837286 224517591 897118269 671703350 365446585 178220002 456102198 11261981 519843830 630856309 300639622 94705408 462320843 982185493 790363100 715052792 998023483 793233695 24324133 762630991 979143631 20684086 284750220 547880777 948678781 227372444 685955819 324542894 105853012 733630054 163451431 296538837 887455083 122899238 566765466 388302041 110997389 183378553 906001857 703068045 567886504 965484397 696004245 79965161 368654157 627741817 120567060 69361001 182109389 858075422 225786908 266301998 745657185 549475994 134163342 691700805 853665833 202581879 382350201 954962626 328955220 222560998 922171016 942169617 383354566 568423223 446989326 545918303 436048861 510320988 440478095 227034502 126291576 871094344 60663026 723717076 571270639 755525427 764065742 88488531 282851051 934780132 909630280 452544424 809690456 918384726 280570327 196223041 772679533 250705976 777038778 731729698 550972602 282909391 337096597 986974505 901430591 317921743 756925203 549095696 432618598 704140292 512309847 836584855 41321806 6605566 387565828 601765906 581354025 287258334 599820885 209771981 454803056 744666385 85848137 947878110 133954057 155199836 633990959 320314865 986545746 158304312 819318670 576255494 942019252 820516626 543175854 91282879 714906866 195802288 643872486 401225782 812208810 916797341 426384296 713436071 499657656 752406340 735061662 37149628 119350421 522008330 57308784 39210171 935413284 91874372 528460167 852847542 259652323 715969241 380792999 690320593 558941837 227567018 125375138 83634608 449270842 876139436 794505787 890638309 833445575 961394411 207514996 145761793 810112055 469808244 820766028 462383228 436555733 985146879 809780056 403375323 654053210 523914712 879141446 609472167 168908875 491127561 951669708 469486218 704444002 81417729 277936679 264220807 624679342 804158005 393912497 255675456 936599443 214522288 66216192 658569975 948220967 911732935 672953198 515331914 391743478 726564096 98646538 993217632 140516126 602794344 113673825 933121399 508548529 762497524 357772734 606948819 632173163 944303515 751945731 81149445 289894888 54557384 854153084 26113904 278281286 871962159 481396104 377678941 348034846 883545318 660191664 249664936 33643033 874966250 869586191 40887841 550106482 362331996 822231889 767780218 953051318 80634473 640822541 635013993 956861551 631409444 839191858 874816917 96143067 768591621 861409733 929963967 5645175 198481049 600010326 412289274 155029384 949340297 929583166 186573316 256460240 599052535 477896298 14092802 568887955 481601448 1301814 114177564 80949018 318264952 955812664 473468442 648238719 535368480 395860818 613725387 653624962 35185717 977103970 642011413 70573809 953888382 656375393 825358349 349687233 162385042 803353120 684066164 279865863 696142213 12679521 149412294 584897050 243300152 7208087 648617027 15178033 177590786 191025653 39837406 700797038 326968568 519014920 231669131 602469228 238487202 489786489 156384236 361937680 683152200 753378868 111712632 594661383 402422154 290375181 637758654 463442281 467786457 658748547 597467264 908088139 994052666 370575352 23400371 24983521 225090993 570571334 151506182 337603690 611435575 70977958 101593468 874122965 492666749 671951583 417259886 68853438 481742872 369280672 178104985 370954664 168788674 35590893 61498700 443571806 701248140 892730543 703908614 372919324 324560578 569608905 993239853 731506867 766441728 634860100 579154328 368952994 274764888 273663544 226026207 189676467 152818019 503569760 179994483 92903435 847517863 843023002 41510684 48592246 890245677 192986583 142049685 879033942 424543145 526114954 546761251 623877970 239850464 254000117 162481995 20843882 311366727 619794101 896251146 756003090 671979345 41310967 859860253 989336157 530865260 28645268 542153026 824723666 613819286 253895124 826594997 666347561 403614290 34915925 708398145 758817962 112072485 497641141 858648893 699234722 441110187 331296002 344526882 989981144 856731543 587637105 536244668 146485072 686692725 326324518 353905981 355413623 947367133 875596942 359681138 88341594 882469474 968845834 953444459 343681591 590672969 673584648 513566690 588715447 15313019 354228623 150260096 175704136 120792284 232430009 578094368 229036809 852731856 161968113 486490760 671699352 291909277 505092491 716826223 631926479 314649342 530864490 79189457 161658521 771417093 771957055 60450516 715891145 296872610 418508539 863273182 795936008 556483532 725160504 699091316 890351829 669869558 827745017 717296154 699412535 493716134 437212836 574799326 451144054 626877116 127374033 515709284 178257409 157955109 242223749 355492741 690957620 915666225 719785205 316937590 163831872 145707894 695947369 490894840 381031924 813648817 166479591 861821778 483710360 896879594 806520036 574336912 131689098 370985936 189838895 594416029 284711996 468826501 303311215 978859109 645384428 415807552 68436335 407133341 475121435 823640333 6181918 949972210 842505037 566588501 984355623 839632683 505463613 113384971 715786738 692500780 186372547 387904984 368824054 605505835 159421153 380381010 625452783 628700536 102425495 27857649 373378862 416532438 27235755 491251900 835551514 648244876 802042287 647725821 131242338 620556819 585107110 589677564 643404631 673750963 729145220 74122158 923433690 271494575 890058123 942322495 852692643 993186576 362998065 401901372 962929649 323114329 274667698 453366230 153254555 721057319 539983304 732193859 605700758 869540536 602278582 505540209 602805638 855297771 639555432 968124779 767724119 262120010 59865237 755075245 346721798 557058187 328492127 39668732 228031075 167507151 128815758 716943691 886157486 998240936 91367296 472506931 632652507 98290571 336285647 714287548 821823252 77437193 504519265 384083785 204357842 857346039 264071778 254021246 380973733 627296459 659140279 633976342 463066770 171556442 871008958 679377763 16477223 147076672 516893628 970835240 716124794 782811503 886854182 523980225 845935619 207635204 959953333 336439335 491288599 598036266 169038891 942381755 462433874 169355173 941050488 725510375 235852523 262716850 870181832 580891310 296097577 429530471 795755129 567782342 124377383 881854745 567314346 954818402 30343474 112501712 590715588 634118453 174982914 98139271 421788665 941300465 800419426 758779281 455704744 715849449 198889649 945701838 587380656 999746769 566645430 606127541 556523574 125774766 511073152 496777907 632254123 3891221 274921082 253489666 505563328 13489418 869646714 291729012 82588109 305234077 705180547 510769417 323416621 227025409 659068075 124526494 389369394 992921518 757336263 828568755 742128075 64615823 736567323 131529945 638788311 426097260 634118153 429055187 774480000 616458804 554382927 127854438 489001585 566773925 750845625 899598390 961619997 733385948 977929103 105580205 826388653 766577421 481336833 174281147 128836953 416038460 745079297 210595072 214187101 610007332 329110320 501354086 390662803 365524420 975732083 954737455 466731218 566000481 771404914 750396795 344613970 81384398 792349857 63933475 261563316 516364161 485229625 676961244 190543360 740253816 433116565 162562117 768981386 327837531 499170028 71715684 198678933 530403922 370998003 615811576 473499140 712045681 746296663 647924868 303277202 850002353 97378289 430033678 850064383 474630984 260090984 565373658 843958815 445158397 194924206 299891713 473782845 83376862 614451923 112746452 369576779 209568854 90418621 18209204 74416677 355454180 120567571 836459423 334977670 815646384 997438679 451925125 225847478 796899548 78609000 266754210 448551953 833705766 500355342 806129595 358974996 187834645 963432319 436093883 809256949 513024248 357048336 814722122 841591356 103355648 748554353 385787449 504575259 567115616 443763472 101024021 685576102 15337109 210057201 706941270 346070945 106749895 611750825 599857007 120209883 440275931 957171787 484669604 566630238 146912041 815904479 694167519 628874247 584931902 350866995 914669096 946234248 276688258 379899112 59876025 637919042 266890283 392642387 309954183 770595195 703200193 594932493 918544889 146184927 732386616 701404782 504551553 477104644 978425019 467474814 928970402 588313449 389917764 190141074 769053133 475910266 391450088 505380695 36436710 128900014 569865305 71328672 814560888 593808753 940864535 239364176 923391285 681235791 366423456 227078370 308974605 686863261 860736188 895688219 52825512 791838664 939670570 268646039 534213937 831590158 955959518 156403824 260436929 502998951 843380275 24499462 817339581 499731472 803798232 450521277 400433225 512330391 342556713 545941805 181340000 915432555 851677066 158442253 29403714 195923748 372923931 536260591 339087354 732680889 439966381 966755744 746129475 126948967 885226060 31606139 135628635 960405276 739287294 47775554 655797978 846260954 490884118 136127015 877250257 612702791 305889208 31881029 117527383 263031947 150697043 883342165 436710219 780250484 871340049 284804205 327607136 138100897 945615258 843077504 210337868 308676740 759887148 637684610 635237920 504505824 70601713 436178955 820663778 858007394 404413399 412164725 842924236 379341208 948602781 183449430 441844535 475320430 131877942 219775932 911341028 466581748 546105458 868792215 713526481 488055670 459569315 241746534 260080615 204915692 708800585 731236064 210332302 119746682 808301502 246831150 834083450 524699873 794385046 67921313 125592336 370697771 922291614 807444009 82791881 42504795 632111488 117171443 563705250 65738754 548145393 620255473 386765355 453369936 729322002 309125136 652677823 380350837 275804179 46414662 53206068 202432958 351980527 156025124 791422057 779687136 957230358 943048187 338592032 513369582 263929840 980117257 972195412 219205181 661853180 3935183 75921672 329838931 735079733 307154214 939627389 637666262 83650236 755363058 688669703 288084784 126481361 266288444 606160940 70490789 962779290 57805022 943542328 809316061 13058838 357522040 707681719 862266568 557173980 603307789 183698986 590020088 281339916 50431583 846182367 314056175 684961959 60823134 561678632 201779134 141225115 519138210 483209303 544988089 332057388 168247082 314375147 538302279 132902673 281952094 472256561 757380477 984582251 648737054 609354793 712981218 161026097 835132079 958654933 253558733 6572659 178846395 815033324 75344663 502773080 743843190 166350138 671409028 563275744 784295463 985366554 719802706 652952707 131514133 314753025 174353091 460433962 347616477 48346277 964507982 240277133 978805081 985656212 896695592 546615178 562169465 410048481 781655164 911304186 616661772 397667181 432469348 225473469 105882701 141057655 164466163 331529923 71730244 1096746 3170483 956158784 815776652 922278086 164910592 512877401 456570251 775547502 845518206 879201357 893018016 475275210 764932940 380868483 798945750 562634601 860479874 767177428 270876181 435528126 135178633 683329878 69893330 300288332 292178134 948095545 27729888 876441932 293266464 311881380 698542590 924707613 308831811 45296629 883779975 863188729 857984417 126703804 658341470 965122362 4498144 198961304 59799091 924601799 518451552 663200513 792053700 722289686 790014754 848508244 182191167 563433938 325186573 807983081 154847534 589948911 312482064 285265150 532513812 606573856 780175765 207100515 329004148 110560539 712566229 823702817 324431976 797929073 330128390 223453170 731655542 795850921 953405603 329746040 959898782 739511347 925229539 97997413 594436488 896209657 731048488 522122201 640912193 185618252 424453023 191495985 728165016 718046581 531185312 780715281 596536025 270224948 424439539 499103818 247453674 696246052 103750062 959345411 349733971 844914644 13885603 461240857 223867969 221732745 411417863 100836968 199632973 905009705 249716148 939615339 453780614 601843850 599873410 623242027 49541340 709578975 139879980 361175725 819912456 356840410 429181256 273659308 600876910 519018575 974043201 505254692 947414068 696996025 502172788 277168599 866938429 830712776 675766721 558583678 754228620 466140640 505482279 250163266 727181576 825886062 226605416 863543917 335049595 309577633 811805875 435600159 67476786 285077620 614144220 254707004 757429684 957912050 107679587 44130094 695211786 288375712 529554857 346787000 447790747 97087639 198483502 172524775 62628699 998980475 167968166 869360793 171314386 88295850 704713718 458576260 387738822 302978645 99529291 613841035 747619783 757844449 579782471 324210016 352205367 578379273 163617892 488799710 113633691 590725150 292064095 486448258 274093896 862844750 713342995 915990834 518349638 224952994 263369190 769803011 129499542 400901379 345612772 168993832 356087907 201405678 75466499 351583533 847954811 404984668 372881504 158354610 959218878 856702923 433996155 30056471 247441944 103177180 817973979 337336399 732227710 493534868 867959085 652185866 541183379 928474131 249566068 894728164 40268525 844950680 608785582 974084305 668413776 184240573 931388785 464591122 515045897 670903715 417373183 798885582 704709141 870515798 287335362 100719646 587615842 504288855 822593781 466426237 51161272 443416365 312150921 75857876 262119562 540263344 348044892 131113596 661488601 294158197 505147428 83102110 254836251 102724378 938482420 186306990 136893004 262243558 750446159 67720126 351735190 935808301 189847077 487528684 412383787 413465182 555492200 802740217 7835870 850897991 21740082 485220212 275304004 865684593 811141331 577576705 771703041 129646784 789522061 920041421 357594164 35064964 434881222 773359684 821966865 324404066 343776341 667909074 871821361 7295858 783527751 325423443 188610064 412573060 479075671 192885541 509703822 394239078 155210524 565808163 668085704 182492932 155630809 702957982 629135822 251001451 983832409 456058131 151980174 455852449 877836311 779327611 88430191 235888322 850990920 178411776 810571071 483522924 33684656 417379689 253797440 893229925 276985791 395308592 241217533 585631867 39997246 950146131 565219482 639706207 637853118 83853104 601494115 246426065 989520945 578462472 350992362 188703156 292718626 443356814 890071057 823880379 889556602 392742133 653386255 374697608 344378684 215857449 520782865 666780560 973177846 736141679 571559668 453704786 773856193 521327238 625329798 453623022 532375581 681063607 572982638 570957829 587337703 956880384 607687656 679739495 702566645 160037076 798245331 423413139 88556339 65670629 525184593 485796694 828372344 798387641 23396902 143377029 528542888 682766334 483597099 796002298 492355835 706744018 574104330 384394388 815012003 37595832 905624715 164022585 258918483 853079472 445400100 919933420 86715405 872884538 722556967 948359334 17356645 784100494 713266684 742759188 154904527 963337954 344614239 664309188 558681102 673685974 726348885 750810984 491139362 11117681 11999037 329829048 631871437 863131580 8605377 840633187 451503389 530241869 954043992 718002393 206124294 339553145 963693531 442355688 663607988 312411204 152792310 167922861 68087065 327513777 162556742 64499437 681963394 99471990 414437693 787042201 512936125 306034598 392132390 217894136 108822651 722474558 723162178 258841576 154606523 755304746 24623965 818314774 664396423 893571760 89903962 717363341 192488906 396056890 108347704 322965794 727620747 652803660 181619658 852329763 718920958 780835107 176156620 851190593 346435283 204489286 341574573 416567372 209020108 392872237 925456700 292789133 849856597 29834517 322660403 713735950 185658885 56394081 907399971 849351984 882384098 953276895 244333929 908430798 410912775 590264905 816929929 326669980 152765531 619111297 267388498 806316605 400180035 935190530 133747799 851251275 109891047 241939728 748024548 877766286 662245062 753588254 619451704 737930003 29616873 199960132 306043236 434255008 217245976 155031429 247728389 5129058 803569694 198120601 693283362 719665536 445712704 937371056 122290614 971637532 531217787 892812508 252389175 73580917 916167795 557931348 964301263 408586335 889197546 958674630 119614591 798205036 213873405 747781349 936058191 222934321 95439739 281558490 810961423 840733123 262768405 563311022 101274627 285822504 208070393 830055241 775635432 939438339 242674252 123135370 698945461 168076059 724528751 588026231 350047418 13984152 635408552 596258221 733938609 5980983 851281232 631599905 261122537 342071237 408703068 689542640 931753622 1764817 466769017 1767620 340935677 649804094 329611221 418895836 974714206 922223204 867235618 579201670 143575073 269593723 667358544 512217355 441250997 790021319 567363432 662749551 608814288 711509283 98102869 13073750 92774312 378046659 834482418 814835850 312525679 755571814 843239457 938269624 621812823 589496378 817657020 149152147 104166503 945248810 574597627 113215551 429009324 559068202 173263161 783360788 761520095 343261239 133514446 375084054 291771675 276578671 449958032 61618812 934303543 620047290 959152282 324438058 508191076 220675207 67434602 876956566 924190092 29023165 192551468 138252796 286575259 442498493 163125022 870806429 516298016 385875072 570269080 10614078 910087934 838910301 831496319 317113917 23804057 236006696 71310853 857131632 363746324 264634839 138106018 781304232 303430933 487624043 433694153 735646564 865795698 611325235 475008119 616802247 493151354 987074110 332873687 692416924 493812523 127865776 377681500 999022270 659365253 174949730 622026961 992027749 981447591 674314015 961242000 484079467 934914884 37587126 48018158 808125006 644689829 510528682 203306958 663975313 266229568 945146773 672271698 53229567 211319562 71056948 446968436 921056844 29599432 135950033 266386721 279552025 276173697 191701965 63584510 984172806 962532609 238206625 748840986 147463886 782712797 459444954 426807196 693383827 706882850 929295155 13376389 831464017 376651678 395426233 786177643 130305434 91722429 636249807 245729841 336451559 838307154 202757162 288908158 186746093 45317787 752481615 539184779 376944107 896521670 225830847 653780070 465464467 348334755 654692805 254211306 641324503 782456103 329282503 635257767 981409497 493708808 441291554 46861949 870189777 957816345 443713423 79135168 803607214 664083776 979089069 582358479 940084177 248422984 972938907 546759701 546385428 391285986 782075156 275966203 815040730 257778383 581841525 430414863 714647750 209432742 939021342 569156205 165564686 146869110 590079218 204469330 49712331 960480586 524885215 894594940 50389486 177776614 207867802 580212135 238688022 580974815 316973500 89199471 771906865 951794180 830529941 973299167 734591054 680426956 399757939 881103114 882569895 719944922 158241834 653523145 961848275 984211829 354467482 690698516 5915010 865010274 72077610 443752926 889837198 323588267 498942946 495548195 837270727 488768803 256771969 718876819 589074695 502818207 992854910 747617994 89473119 763727742 321334494 847611252 987846234 514546392 855536995 714775363 945555324 740663295 14839062 817901823 46439323 113700856 865548328 435517125 218253277 720232667 837740832 654210687 321148557 824814007 643366559 319077135 64258900 532740651 144740133 907246562 382799134 378714190 887028849 598436802 417249364 224979299 410815113 170459403 572302142 507553017 573683434 467213147 259926611 91968849 855076957 280594321 810192843 272203849 611486220 893113116 222200019 990273772 298975019 348159902 705629154 823341900 156521966 556693926 275537455 553835839 642991440 847090576 462772250 604096229 233497524 495245402 58751729 69687043 844455165 642018719 390044615 334929136 540151815 788993439 857759916 851239469 987145497 26511847 271323471 852802729 751838674 708443080 674016118 18069937 904816075 81299779 986453819 59826484 800453846 99417874 382062816 676958952 509751327 399943721 587938198 86431733 557916577 71174979 623458190 488573273 732507454 236961689 611000086 487828528 532489600 937308402 956285261 537476976 230732923 675196409 760232680 469239083 621347943 961015120 8759612 980413944 717679025 705087427 84655017 842284938 494606273 656790057 442513010 508167901 22560687 126146153 21946204 288036078 881314215 815462347 336958480 165759427 891036729 781843997 821107061 212854974 377415993 825806932 881815927 589062459 895116330 31745909 914507700 419110834 616131297 271253856 585806004 499948336 848247618 402489687 638791959 238409567 63938359 915849219 528434520 303298909 729886212 43677936 744767179 576624681 544936694 353488281 166866889 84919830 681115760 589553732 713672727 254747731 318646993 615625204 793545119 2308762 147859993 836692595 432654364 528105337 474816076 411601522 513691971 50745887 361220271 152725357 258010254 523885885 408419874 379730116 96252497 831113783 952549465 405384226 455395638 64240349 264487038 925004174 3558148 355020386 635240345 224646429 281422611 636462347 796634996 898947390 144671349 198823273 312785503 173440114 231052226 764744477 302867442 949591265 927315347 154669636 454040250 475777853 969061876 558201410 802212297 322869502 231172233 776549204 420377708 704879099 468742394 337035570 779355450 117037038 943587538 338935371 627282049 353642256 835568405 836833177 984984513 427580170 324994035 122390944 686662713 253359716 811192306 214971428 485400825 927762844 362576170 375269429 567797407 279768030 92051541 207117248 137067109 454736716 786020689 181726527 303815921 177923250 402923833 975910412 477175969 38084917 367347368 23777955 874645017 256082779 140199099 575849852 325739172 850331070 194035782 282569390 648728795 848718419 70556163 964152908 430662598 278729665 673933658 502065804 816368054 453036445 493523475 680202972 699312380 707793330 491829429 422312712 459857410 118455360 982661588 614781177 309279095 324782985 949112532 739264101 541265664 446728695 943264990 164781275 23271368 542971290 523171680 279542745 339659678 58605310 491903063 515563518 359554279 570666600 179265879 118339622 286454243 342774285 367742482 905682949 603903586 793553266 708356906 142235340 868796842 126070212 627555501 38286197 151759616 52770939 633484980 932569365 138665903 756445958 686509275 477993403 107200952 709453608 230315886 733509378 903547439 452193121 457935841 468097859 66067850 134032566 739381176 43886298 889610300 369082075 418438375 392538290 107213955 212159458 500922688 83087235 175110942 427873911 479023713 755727009 994469885 607936155 785049033 619882815 629867586 346240671 256853361 2278995 504255866 154150538 805977076 115264138 572824106 987152920 193355256 573795603 654743821 9609938 454136310 45629643 993191904 142984202 673620394 897334988 143469557 445281421 63471622 117222173 723852566 334446798 527114161 949748995 205051487 513226396 12069619 707045893 990416664 106450015 253610678 727729158 376387996 448863974 212914308 886068910 351783192 769536424 326516827 253105701 479539569 961636216 993995491 562372949 522174601 821260343 45970651 608321042 924019143 522832737 705496825 67535644 608063324 200632047 647591660 253049961 646275429 924089696 228142672 486314252 292064016 431273700 543699891 182117589 926957263 685784478 336190523 55524221 403926 49866549 214247826 57321841 199532229 51853113 594140249 32462458 996188288 829758585 319788536 336616124 17575096 111893674 49699297 942061105 19989760 97591868 849091003 862761466 76989227 736198592 255360190 974020508 927046146 112474496 612752074 462965189 389452235 503753221 578885385 373350370 254719116 706679145 87981946 421399791 727177804 232692198 741633980 730033609 411975885 998127671 761343434 509468954 63147458 532651967 271821620 480778173 59950526 107425166 622321704 444771266 5305205 414386506 614193180 592973738 333645948 42998735 854329893 898968262 667255734 581176202 428717310 881723283 712570387 318977296 852724597 718566230 82531458 418387937 933651738 726493727 558479750 562076490 164681419 835730588 93117062 170503541 925268313 160619920 285986852 745106948 92899273 785902015 684128390 926310291 577492080 617734050 742809260 733830727 915831220 38910398 808562354 521648875 513594002 110112841 396001907 378634504 827329005 463949971 506218800 165240391 493174285 498014718 37819307 901021661 202209876 256900656 891423691 276794304 959509942 800646423 691446122 892708392 459835973 101478356 199354531 220566004 939141193 165606135 366784744 765780449 380492031 93455352 567114868 599155091 833438706 639521718 742539653 621616439 630074605 681151307 515941349 412639443 873059471 313350629 207157992 359317760 604493571 247567533 714832846 339149131 213432014 161701787 786303601 552630817 596549297 631288035 180652061 949145189 290651687 155581649 115494982 311723663 285213539 919649226 909976926 667288409 349346146 446222079 499675126 873150451 986107902 963517484 694571857 431398224 172704645 634661969 453867364 387996603 208109203 415711128 674341463 418082532 648494752 425144267 913163226 64657341 594619340 313015454 424724550 130206216 965839743 935248619 445217377 201547157 405230606 289978297 305475401 684594686 731874875 624530169 864454064 855779160 780193303 147013391 37777300 265765080 536450847 107303232 120390936 3996458 19858318 384146698 160371578 400777514 891934493 178121234 271257846 651073375 364229595 188114313 236987944 63803819 169768260 556849884 93125213 220253103 556814859 841414266 354382418 249404617 80878586 904377128 154919164 770403952 682487348 299333053 885282254 869972188 361655062 518172531 641431989 261170040 776170316 775919236 863745897 67217116 223584049 23017159 778218843 85380267 238590073 848322832 77152136 662476751 779685567 905341755 763166918 553007544 750767513 114584516 231651478 646838075 613911250 235870003 293747844 249935564 207506057 727266278 896433130 878970357 236227799 671400988 476264527 508511477 424978007 633476359 147510601 414424944 191746086 370167734 484327240 871046031 502138433 221473253 282932374 530413856 493351273 445533611 748923122 772578591 237958388 104342997 891816234 419266092 862073730 307923450 315596570 487472820 694620448 759462180 896289271 945965782 987626994 779025995 750108236 223111354 40038297 890111874 937797756 560392788 398513883 335294186 266926838 421201957 731666492 135193182 483861996 846458963 521796341 158163601 807790034 366219505 422688661 645501887 913204265 486061539 402275881 28910591 924266537 610506032 928588566 42592539 120872151 903287737 278023502 392182801 65205303 537076175 115884189 184263 923644421 993879451 852073780 647207259 251235929 799294837 155985798 125667016 963762774 442707357 407781973 623751118 717632395 228757126 255940357 536757670 25103087 184086991 534490580 406224807 738228685 403581022 200857028 923801559 20970132 90580937 716233660 186215718 810433225 303700655 130159878 131807127 364182855 384272309 79695034 682666695 788589718 228788508 594873720 181307779 604181121 31288385 855339791 519360350 2823829 305870797 509922958 73178768 830048089 397668748 870680331 514909381 86206043 943850137 280324509 386031517 409468937 667671327 397226094 415717009 414241140 151574770 551558764 598609227 919734000 748959110 388275675 794205108 432317440 850729414 480726766 885104759 893555543 320006801 59936920 810476948 421662154 457154988 843948892 45030866 888538991 917055100 693253272 577478925 805505454 390864330 332382398 176085490 677384118 725022640 111700046 151989540 758711286 329720495 476382482 545037754 298603334 24912870 505840448 566429456 889705063 663190074 234197352 357359680 339468167 781219494 314519808 126938305 164183298 151186998 842473823 59594950 944303842 269109174 206855115 329792529 18740131 423755259 608748671 928200523 905508887 352475243 434326315 735736349 653001775 871601470 782362312 952585286 410790072 745573087 214039350 670016624 271654067 181978306 424187528 335634174 491071764 599562773 893955246 273639837 951994430 485084490 603381001 463470798 161214277 303804204 420359354 403332632 943736814 334243655 80207591 894486478 110059465 501546548 108101060 705282074 287709649 659318101 337506594 900952700 837110797 827250557 286407313 45455026 405952225 56487981 959152850 145134776 448562504 190093536 663175792 466454947 762515558 962317178 575208048 75792151 665380162 520368993 597742592 203213399 467118441 361490885 484386496 619780509 280105847 69791368 556229905 452777262 813527180 514398654 263540021 555147357 497309830 785943086 798567770 858958283 648464833 208013806 594509542 887602454 919749882 615730126 251359694 419850809 884928798 96312771 835712256 814956727 363084286 513502569 281136108 863408021 149996919 519103997 277921769 459395629 816723439 931975689 402918622 22376803 57579313 317459942 249068770 322947745 929840809 582552857 950693740 732567166 326818209 883708076 795119633 764609143 750387877 496657843 828704665 182565740 305466214 317267342 382829949 574577767 663926946 407685448 917697745 734925785 657107448 786284107 579718919 690740843 154296436 842267328 282333049 620501607 306135667 684071065 282743125 780570131 622306070 612036930 342931651 150712030 560544986 968350496 962219898 769427335 486087966 715540917 856703233 482999356 221487733 166301822 196820850 635513694 754545542 363605483 757228901 964580730 259739629 767692699 540833636 957306701 573206334 205771407 337104889 310343998 284030534 260435361 396061051 900533601 646253965 816909031 719547459 503629346 891486658 421984153 736610441 539073900 650971132 992272268 212851985 758302635 706458384 489829309 165265058 501251424 126254473 975292005 198197897 343030696 569797426 610866544 343076098 998234538 985343234 995082268 526360244 67587634 101907117 362000134 888326610 784004476 279729413 609771998 813503674 735473658 591353274 32635276 138063422 733054498 451628648 995280412 575287717 687616941 627014232 331192339 82666632 551538652 339413532 881522276 802038035 518697964 591104763 257867899 218703048 731192968 231845983 81576 461767239 523821159 145396363 940659973 500406260 785591783 803233938 655198717 734206074 52323989 420276783 594129232 962919873 475055558 193557149 734664183 698197368 902752084 510757467 649983664 51076182 334125927 277857313 918877711 464840106 462126933 353895880 296910206 980396556 84353374 964613505 534557538 941677640 148291276 584975412 309448902 490030857 604181149 39314691 870654181 125413836 643555299 714078118 379637321 699130461 291071667 454459677 440250995 926379127 819468672 4608023 429065599 18217995 418789092 850104897 109588323 376041787 724886375 631065675 987701447 227439532 15859300 913358057 584900431 586148175 846310757 310926652 642830060 581875110 490341768 716847102 831874099 514151858 628211019 695943897 936452424 946195109 267598436 211415830 158110264 296648618 788356938 539507941 965760307 264285261 45296857 779884799 203175943 775499374 511537822 718294773 870128061 475450204 621795563 858824656 643764111 226101805 943672902 935762225 775639112 179211987 789796859 630497584 836982925 54527981 610500298 979890619 273667126 4234405 93458499 792128518 2441248 170689534 96659684 302341708 340620741 72893175 747508221 117305712 916659407 351686198 407231801 75499844 576586375 542265448 625932624 550640011 650578201 921810606 271243319 434873794 553665214 573717443 108680182 930303475 932046725 137186326 2443445 517341085 673935557 75985928 323814947 825409547 123834768 916421667 432023316 630454240 561177764 513928406 791025676 171837664 111088059 497435064 173314215 456124792 637227742 949244239 947453571 853584282 315541033 703628301 844540446 891644063 289248526 486607267 613905083 253947240 154884118 39757856 790262619 36834062 552702311 890222755 545841236 522975992 933094851 689032105 750099246 292880532 209778552 159291746 444713681 731008850 104740797 300712915 284787010 266094713 396991583 697351618 683811685 233526974 150299606 866379977 226891238 497058670 515417731 423859909 224746314 231492551 431038638 475290270 108503986 58603509 471974455 86545167 533737077 507631173 437365795 569370375 249036800 879739134 336375600 479997537 504545839 679930834 352587857 170233199 374882585 160115734 117447725 199238834 391710755 300870340 561712314 135299910 719876681 439384725 702822981 32861142 175451878 412968952 228827805 692226360 233942804 848726273 721914552 351013804 478300459 284826764 876472594 933853322 223522107 949848071 33605795 394385909 547233626 303918599 733866792 575792609 915909280 803082690 271992189 464385755 95514490 537585258 643752107 222509197 686824987 502905356 586302173 353027371 294259347 212607227 130596690 164810629 548361490 922458277 561349717 791255389 222467739 336715988 320735092 440839071 126940127 371229988 109258802 811039424 669593975 932262624 858202188 600558795 789221875 131867679 531052940 768361151 971176648 275502477 107744659 820879765 828398137 102634126 410467207 661637853 896184886 679340073 609484227 824623997 304358694 282992365 902692501 762015438 553438738 674888435 970160086 669188757 720301040 444970987 648851634 519858037 246202325 422148254 592296745 740541946 71141207 329675267 18501623 780144220 809934272 503910441 585699771 193568084 597208671 153990385 274458228 164156147 826728885 15970606 11304923 360295756 149831265 969546535 92070641 502887394 35761479 653922073 603347529 834149568 445007849 665753190 872791322 216925080 864364397 225096093 525672481 957463869 814930211 365967738 272085340 137679543 399858866 300063327 580397177 728033733 30348514 972159728 438731937 779137040 626987461 38442555 12565691 501142858 942979756 611073780 41243945 758090778 64991073 905126236 63492937 576193 731928599 513674026 704303779 381938833 981066537 553246594 112380967 690087512 378643588 727858324 279629524 128787767 784510811 373507837 20582126 344169098 258544717 999262650 231934483 939889414 277113564 579861692 769909162 251864591 507218178 599592844 846916940 498613877 294446882 701057866 275493396 795941677 876472821 158445626 335615338 385646303 289953758 581288543 662174148 450886547 219146660 886256728 964889869 540823428 329575280 574623545 750122169 132510537 977413731 669880767 98677261 114470259 148780317 799384929 691923852 630641673 159206748 82418472 336036593 502229702 771938704 546164305 678673742 495353114 460734627 170585030 489001672 311890240 175650593 993429663 315749622 234023846 975377117 920342419 190910757 986456304 885180058 862893638 148285206 574906402 956228893 750187545 540236389 837171858 657976883 326610242 149176238 403124786 17272538 991778641 689387709 811338945 283728605 973810356 805465776 25013249 726779769 684468641 843410020 910682746 367374766 262853643 733792263 162081413 369414406 517482770 220904476 841139873 972344764 5430220 378532096 105641288 395958944 931680249 821560266 178588177 983196067 520674941 613766299 466570800 209581121 918172701 844443622 486048271 101259102 517691002 734063248 107482807 398032737 199422990 298967972 303980434 385741264 284895720 317031461 521154406 549200454 326894410 447426733 851093276 287600290 109276877 971981458 518216624 14020901 201318993 667904738 546940661 892910806 583266553 278221226 693216126 60240435 173838147 672911004 721385271 615265245 952203249 852121384 11897374 214005138 390496280 126725323 647847109 693779373 305543054 427430490 351447922 177881253 453647016 622548100 722464603 810178203 404701088 223054059 54218716 526147767 691711647 660064103 593649364 362042301 769517704 980785124 629746802 426422371 348221014 127869461 976697853 820439599 501212030 182027487 795202775 590823591 321460035 262726040 718459850 999092890 645844911 723319826 787472422 202450621 511342843 724774816 202390495 970193234 56827054 472000441 851346024 591726060 916760280 27937448 460081469 664489730 702783205 424426014 58415556 389968939 779282366 680275727 29963867 375284351 787789149 878811698 24827178 76991840 5719335 692766226 228677700 706810143 257016773 19919874 770588282 787698163 76061125 280649463 446514996 384536096 549391312 874247639 304773728 674811104 180784167 63501691 656782266 383765634 424809605 720122461 463257576 679480952 356257812 504047811 465181297 83326946 828606617 509544322 584779768 85272063 98341442 185124555 439465146 429501233 920797675 17724274 510827053 238297388 352228029 767527958 648461801 44125626 357154014 131355423 551968605 938258962 347194812 249787325 191058014 576763928 317999599 122564122 884660421 602976208 233205891 682553285 511311866 572570034 891797384 142556680 19921420 668478683 377938167 954900735 273615852 514433008 517044670 148276683 284366915 167962760 146835934 780924398 265945958 467879126 482347644 802755865 331346804 405992779 588017944 773798548 268135896 919153163 730244781 262368798 225041332 77616707 324801403 75920571 744330952 12057941 721203564 174873512 789833707 910471695 777929 770418853 482889869 290085217 119579432 415951098 170111173 543300011 235538429 398008463 806074066 796054539 965820240 745731057 562877463 334396561 214142545 287013144 594198890 624298545 723794130 153279745 345241129 683798638 24849281 194363495 998731798 992933297 368108070 159652796 209747505 677808092 742598458 824786463 539018932 550878527 887595197 543537610 597499486 279098216 207452762 255402885 347050282 285841073 842327226 50132373 137965602 829284626 945370215 677771750 772293368 796021528 354856074 682081738 656509979 111530561 815809928 164407908 378023361 763959061 488384605 207840800 316833089 738113992 154129670 15503909 522003467 984759274 626564942 790247691 351455656 366390247 193079450 294592644 409913345 937955946 988630518 475122881 783091795 810250376 773067624 252216140 209226664 288834373 556505489 267001768 973631788 962312955 131836103 872655388 727498498 314952700 3705555 635458204 220937941 482742940 513151251 313976083 869890086 778874286 798286539 841502776 58354024 736954608 383768264 340293525 940984716 433544904 913353671 978067992 891478322 496719831 667439385 206879179 743749165 603748933 428276232 671214912 360907654 779888075 378556329 670108711 698574546 162967284 791823906 973790979 434706330 527198379 310033159 638185744 829069391 347080667 768265867 319755032 477043098 694496391 969650789 264439447 866377654 211161835 885095471 940219109 644590067 68792558 929906938 887780935 559318223 782670387 411005877 781276405 658077284 124700415 170210340 795225349 366405520 683476008 660298311 188230773 922407458 59841343 399782221 721528457 45788489 789339780 987012278 921635084 350951195 189723866 374922779 994597616 529536085 552822817 393455103 823199802 268016676 256785402 58827121 353629135 111716406 728783160 928721454 894746834 936368803 127023704 909734545 202254995 443969479 916863584 575637912 776869372 185997387 551206572 792104428 323058058 20665576 833494955 25686322 859754921 503868822 741248753 472399607 449056594 99073820 603704257 377975897 780186573 661747919 121898401 562025933 795492371 469467811 553268763 969847002 426982890 7448251 937581917 318744459 582161738 475551904 935156535 35616268 483411196 159661659 492832034 806385450 415049916 131757959 643300632 254589823 956986359 254362196 860051433 348177845 621642513 241976863 355463504 496804739 120830112 712243686 371605107 607956595 681970791 388387548 744194887 713661234 794874993 881867402 468075281 342216385 170695776 296452836 667203891 785119546 984828996 740640862 808530805 366660487 629014905 389717367 837335233 351932889 561694000 912759572 236603170 490574553 346576518 598252976 612684452 3806583 993760064 858799380 817573163 231599575 80432080 462117760 709459971 688460463 369039651 180491629 147179961 220585329 868519897 992332624 517224327 722608691 878891162 661674951 973122671 270948016 401050733 500745713 361862480 14641690 764966005 2844400 734485565 229667634 377992712 780005633 10570542 649678609 105755078 69365716 483932898 527725144 157723927 505588069 891374345 937889061 802710174 835142475 230163237 490813179 166085603 402314512 111966589 936532623 14878079 593440127 612188100 941582867 739366676 1725029 787292652 67031605 959194124 138438013 362408000 181773535 875435506 878454769 843958265 723681176 377036002 968123688 82586589 15471453 87123738 978136545 538281948 626419946 861830418 833816386 920804375 557682378 183929049 171257026 237447876 434106775 375455900 32277514 875435873 89712877 335518318 553135305 876986853 71446558 826969724 599325187 147666020 27669596 100095378 895014121 814491520 65643982 226877672 999420511 232395809 531134281 475476743 390919015 255255654 490979674 904289177 599164465 63551277 126599760 79816644 895669085 673836494 217364977 700343431 324107996 780175333 78900998 651104255 36895333 740501068 268564567 520428811 788446797 143156502 301269350 862953959 705457409 592842125 145968862 618391175 672587622 180015517 856309277 695837845 2667160 457768549 327666558 430456135 505861268 598314683 104864576 310430338 942815408 885123934 398356505 870129294 395122336 90060510 644327654 363583604 312761440 922828251 886654050 296664403 538348197 405774768 705890880 564924397 16256985 464736876 178371112 325534475 807387475 461891207 101914083 179085989 858095275 537056307 999320063 931144507 347466744 166189063 374320412 730257394 956810442 325876917 554583882 431177366 899741335 567146785 913346617 362004490 211618309 543440297 372370591 391780586 734936073 30486936 286990354 187472595 851151939 435665431 532180040 660139798 740203693 429901215 703922905 427989793 392246684 723493460 864269694 724893848 653567327 214521483 946000382 55261666 201309479 36604978 881322535 382763443 975182373 91204434 389329262 596559647 51042311 550708509 100245883 624333480 981533452 391381802 929965057 293376662 60791025 677323973 165557794 699586270 642006142 12468117 305994976 763865715 905106914 479071025 912821797 274890955 397472427 574175904 785201607 192282138 496368961 375246376 204292704 65141561 375824273 685466507 834980991 995964877 742714108 898216032 310680104 354891492 926695922 348162252 728089936 847129904 128533369 897274358 756956192 987597772 392202766 391295047 761827740 483902268 662328669 283931960 211227944 525159858 957364971 478173114 249173070 885045977 695242159 925256736 739914332 885097125 300667390 474492955 769218450 74223270 826133516 272904350 755523112 536100179 127131743 313466017 712142317 242029349 991958745 852009601 169763027 971681797 308173522 348061906 247008293 961793541 420016169 455518778 395585967 984234690 637113792 813395432 685787490 722405720 607732114 439976091 539552812 164303655 991228758 910513586 569886695 733715338 496801799 470008896 17047872 983066043 854582543 788165833 445097041 993180308 878745391 832426875 159703600 185571258 781713241 984240112 34325866 163126202 148645173 628224754 324628381 358935047 716912794 257997780 304152126 570405093 115451677 489942642 326896833 359208913 527043334 368770891 447139120 334954057 275261011 762550571 863695593 548233159 918267973 619685813 556651759 205558699 574681555 880645000 870280899 392351314 919678780 936789199 130077408 435966794 196786442 647683545 886020510 744294980 323080845 639237700 144600568 737065967 656722379 785341217 410369488 242589458 460118225 488349731 800278337 43258461 325293097 535259267 646452810 527491726 980642847 973661430 108091459 362364612 159757910 138828372 583541339 414486307 375458986 105726828 490128848 264935926 652997645 103684588 132970015 552640421 503147448 455089481 393041303 25378056 6079762 200292890 521433566 806108357 316084207 225809336 841205099 329740707 796951779 84301176 178257696 487411444 471923463 786405247 154789267 262390484 890959785 827404156 44037132 243601212 125332490 418264031 91887618 206300658 974437499 999449581 175729415 317264506 805513944 17882056 801768851 88507304 889528130 703728767 970590530 982577924 875796842 668498291 234547235 631178483 230028608 890187696 828442918 496922864 586974373 81450218 100207165 649476975 422205844 215508948 626724250 386549418 383539636 386476665 231308641 66880745 83607797 729661950 783420258 772815491 327660588 942263079 468389625 479644416 472636738 293873601 260238959 753800285 636964588 356545556 679652406 238342941 510432164 195617605 311450210 690120310 410256882 349662710 768867377 165406727 14894606 810145371 582563162 971860267 752221826 752789943 735210303 502324206 825400830 485554962 428782957 771910671 886444028 870942084 541232602 846899875 394172961 370678755 81057349 17740114 726057404 806250278 996464460 792146156 330520061 468198539 481780085 158390588 21228899 340596688 223613590 264283141 448314261 524411179 982532087 867662308 702258436 982145308 596528231 698145046 378410759 348019582 872921419 175967480 795940122 456537364 560933071 513481128 638715755 837813558 915195349 180435952 402769624 453480512 957486999 989958256 941128085 518412491 640101572 130521967 704751121 895839747 595465273 979294519 446909750 986569666 844164628 287313340 77846626 908999245 662987239 410722406 949703553 987425978 692945590 298304630 209308797 45515542 961798376 281453664 353501783 420733125 522225828 678634033 700998180 652999176 97230065 456259227 876766924 282088725 905440811 332022886 64316563 885675535 709426215 646865604 15611323 183046302 359732411 645481069 390148991 209265035 509282348 93626742 346456343 888784778 744488972 504558346 574956635 574234403 644321133 757702844 280722970 970964396 809005736 790003918 305208918 725141581 709119091 339969764 717977509 712387885 684857988 755172246 962840943 315262445 600968630 681344952 754800611 196072843 420711093 530524093 241995634 211788160 550658051 359666806 767758779 25892043 301940558 140084900 269223895 198404087 27508121 816350153 469904385 760480812 873759493 454697099 631215119 116540479 157892493 840381010 182498192 529070487 160952117 232461928 647565376 42789990 429928228 873688453 724608811 426397920 704084297 698992246 48507572 151982375 68739084 426231150 224051461 821931877 773698180 159274254 5651029 861078410 232808528 535707051 591866000 46183254 892139848 699826925 525674353 56324215 429600928 687511456 920875665 277761602 230195909 415370270 161810373 555938246 886456074 23278508 740717346 689852749 601469605 821112456 562933678 745813100 679353365 495421072 472195197 821080353 512450707 993756771 64503732 480806453 442090315 521605752 234798205 325931888 727341238 412401199 199094796 696119954 48018189 823144929 46437632 487144249 533860497 979049124 869801031 389798153 933444385 756671156 350302622 221179201 992380486 629962885 345395423 71660468 352974386 58910006 878214106 218712137 506919922 593867012 981750908 143996479 378160538 946149997 496481036 820384524 815185821 534150226 664625338 718668171 78707169 70289252 256816956 735292111 862191958 840677745 591485676 891206323 619651411 817713965 874605106 956900357 750124359 377016039 769507667 680407131 511219872 782262165 385336042 72862428 95621091 955025077 885814949 972353388 859913691 772208018 951433333 602439939 448908146 715914939 386748876 656517751 857791323 382198429 555764450 118916866 259300805 749172215 926989279 730623476 638559129 730386023 418515506 609142280 476631420 561939338 156741759 357976077 267410188 608547519 247932178 887696172 43473879 817894918 954887176 717926693 678985246 408721993 561448735 535874198 570481756 710834769 528597062 41194433 160284072 393132002 500345180 61014467 754783433 485498177 639977147 375581696 2632499 985022846 547057576 465291747 131415911 579116811 56252822 233263825 255227320 544626683 507481818 720483343 386916116 852832402 808428325 584028946 55411033 985772587 185687662 276590800 555485978 698256073 679122467 748294733 501072961 24655523 199172399 235582973 387871405 710360926 827116411 144854979 958935225 581314680 546346427 982670513 696128043 343757688 813111748 432482116 836646036 553811608 183539284 135487530 929345889 384767518 490504060 69859166 638291389 68170857 955226142 436957896 395835876 645150326 536334526 637228240 577352716 783767672 464194306 216334075 107928184 624776959 857769255 800694110 92498303 563782672 425440548 559311547 463223031 273674091 310058092 117695927 528527876 210678618 350011965 963566641 349116380 627870898 226902293 764740167 680762941 412258807 430638627 40699183 526617378 699416082 54324932 181743352 865648834 814393715 200683858 550766660 135870625 428020598 82042093 755557353 592784506 947056055 737142645 885697133 669594296 440987957 766270321 340702493 695776843 204778507 244990056 406963082 945773123 358748653 895665633 608387581 232674098 121240325 295984410 119478684 769144477 247051685 743153683 405407309 955047345 876058552 569169032 843545466 589112443 500566756 477908319 330318626 493882538 968769309 105861146 709385104 209665126 932426688 590330940 638124689 74883223 611312498 971547895 240989944 697674107 261892822 179413173 312024598 435437244 410447486 98840476 129298058 485497184 72248035 517621171 962401171 507011966 571701038 48466344 968349811 268666408 829081475 928187352 804987006 147092570 752215348 871945157 622930863 604481551 986181033 216742666 112131545 598336970 241797259 291650688 718763038 683017118 720004663 600684229 720929773 28804669 399059899 139083134 409109125 703722983 325813166 447482030 269856811 789612927 874169121 149870250 943691059 167636334 100354183 760956509 96144326 556050009 851397248 151040309 30080974 876503215 469741348 130147620 722818253 766860015 539235767 434919715 416941778 873361372 302085448 202292924 459998932 371865880 986469767 367693289 767597457 274259367 553057536 362949386 544966125 772112778 774646320 827933644 510358490 788790229 170610476 729196424 836247447 41044755 225085982 568080418 842496286 811902395 152090303 24368875 447740279 892936778 23190805 117920512 588411757 667235630 835675788 693751836 25826214 488733931 829068916 318230091 487700838 598495025 722062510 204138590 691131151 511046988 384570572 918922668 183527350 592932501 510743610 17944793 837148839 851224474 73611275 752411477 203778627 72455283 999885806 474453172 744646115 816951759 490977649 480692609 83741371 306184897 913231100 352518708 30577110 264893164 634685887 202608243 701716212 860621657 691397554 783362751 877329682 213831897 704853464 636061985 50727627 200797743 199069447 475191209 718251209 35328232 897973251 163045151 26686059 317035957 757456625 218326588 227415382 326561019 373613825 659412376 141974302 983505233 50699541 107556406 236405610 447763971 612698525 302382614 902710676 648703864 84319437 47238239 997084690 217800799 119960510 732987074 56124216 198183964 223379283 687655766 6878280 360645478 717314473 698037899 946608358 229251398 121833589 11246223 228736212 677226447 687339758 90869467 184598948 321389284 858130330 484464632 205812895 819669736 471376494 524571437 79180716 952731005 178470940 416441429 169911400 773294772 892208823 444884003 802822637 524763713 728175056 193906004 396727087 59260544 949060615 691836510 338494409 411092529 49154362 499457088 950586673 323115326 10158902 905355282 582078517 187121726 966347430 792780049 123350852 36383911 41405198 678585827 915643190 83222307 223530436 232009054 9058948 970845198 944223278 117255069 672768153 369935422 532131675 651006658 732527672 972295947 484561118 786946982 527377376 309035300 583590362 973265288 901014739 392770802 299281997 590787933 359633114 746996221 553994056 435025310 556089773 794419081 779455630 391959337 315388124 521191491 695034240 792689350 123050946 433215014 94977561 152633769 812422738 659881299 382520711 744965132 639778277 390171887 424551033 323727717 562220344 654917261 536096270 425594075 847868818 721773695 633559676 101746567 955763849 487021760 845671468 456078858 841995193 960378318 766082593 550864668 848025177 151853106 164068954 699841835 104205111 265198529 366811045 455989356 131734167 755990272 206704473 920780242 67569986 239981335 981448278 279967470 543406808 661810168 37018450 809867226 981087558 300380753 96491677 138549724 934683053 563998188 95953853 383840588 194663171 93319892 832806187 463624203 303978319 986461473 613731219 935390001 210946770 705057657 530736730 500345893 829905558 754103512 941193606 405517562 744646464 338237045 964265953 318082353 416864540 208230315 271684515 275159276 842790871 720832951 552365802 120786148 622648693 697803124 324737127 225199031 36995283 438326024 161037911 421266105 85828805 138043345 834006626 783665388 687335123 805301453 453843910 358203755 121334659 293337894 768345386 194908276 497791006 364764407 153474500 546730625 661067934 478028355 81412831 66705366 430670174 970602886 16748041 562285043 524689617 732828107 323851630 686616501 387664867 386908036 612386155 124320312 647448427 12158218 26872456 208979473 156257217 366737706 999116835 42877397 736197570 260373068 9266443 698014465 245088790 646909023 62083458 888772646 356974309 644146309 602745996 613363139 105780740 532738327 436214868 597604902 867683062 608321624 168987263 592306223 489335766 905125349 498670898 442144982 10858094 419563015 40147026 76747625 171048044 226658911 662412921 611442469 332745719 599174093 403775935 668923617 175385373 514536489 653224628 597728546 357684689 86681710 315264463 532630704 96182536 754371217 664014605 646458588 565356020 934062075 809731156 777211331 597728836 932892225 534854174 823397335 413677848 210727472 911330736 573567597 131045303 848545687 600399998 630499828 285739326 951385939 898240273 593048267 835905396 975283597 668681694 475938023 893515961 633945772 428694306 45634565 62860844 576985026 694878250 171654918 67435372 807911871 693845065 264634265 60360369 599400230 326800314 959540247 938467878 436157196 765732650 226331315 37819778 546793131 346817908 143668477 220285085 607300648 825491547 422107013 84523308 549553220 708360382 987246313 994644008 37302167 407158345 521702626 503820357 740928964 437992129 995435226 548177076 60787014 100665044 609218618 49085207 49768711 54922568 104662088 601438315 920278131 544269180 819459806 647344811 787611684 583198979 270277488 811703089 407721468 393912079 555680272 704595241 470580293 769098395 241833236 244012602 383891271 497661640 282625238 453163218 970921502 305188260 276505239 418129326 845535442 588659451 460335425 560860671 152572576 438048881 288202269 269352223 873367668 931802175 866679691 856536383 233757152 476570902 501666967 591001811 141336494 190008855 413703705 856910003 431902529 508710998 32677717 443619174 853095583 609676307 459022144 689842891 819443164 273652663 927268965 308416689 206888921 698054221 793759140 170538870 428417006 200676681 225365720 434469887 806014124 307794980 948368565 102295358 643330186 654301632 196696241 198526729 790474517 387107672 413976459 516895746 770813264 95145813 536556895 929099744 372334536 496063063 765856649 331041330 906822069 328603522 300050827 805033168 417740412 772121322 234226128 588565335 186315090 40153075 874117893 1908007 30536110 572915304 410260966 650898699 589158930 98035450 207233784 1137585 345625952 412735437 317789468 667618362 141119784 440989260 567959557 487791098 457313018 797244119 732168590 595143251 133791092 949736245 223184498 239148523 437479564 359098942 455514703 319347756 140455895 621757476 187402212 555128099 577772323 285891945 964544469 394043145 324648274 116178739 270895025 595580058 189062892 285930583 740347979 438477900 491549394 727159733 885011680 142769784 599701737 51910621 271329643 844442140 984742519 589104178 961614859 362827216 76468927 789833509 718921103 798182930 925984420 835461570 999042802 734606740 768480208 427938804 933985389 260242535 295642664 865331914 103243713 999081149 970421641 467013850 109524358 139709284 938336484 953598351 71939732 652800718 385476280 116000532 74634211 742536333 138045832 321554272 25442442 53997493 846308683 511512657 643139909 769490917 189161157 516693155 355281781 690668401 320672600 680064286 309365059 280573167 547165002 488694248 114837620 999591114 227254170 216798981 658191338 373752292 820628879 727554072 822175664 490296664 7004251 38718831 520165300 227489461 256752305 705919204 20804293 591679600 38941994 256905923 597827155 392325434 172223072 58339973 864367401 107790637 201449692 732850180 161025427 364261048 691181246 975323989 346123640 527432851 757927971 266461535 163208241 360714843 734205461 893738654 683349861 991875303 365658593 575592302 995151074 167590931 272927867 954989506 167296880 826159686 767951322 733155504 548864317 431321864 247532122 505253171 333571147 710136083 465570702 111180471 370274131 721914643 498798069 234512265 406137812 669666702 854642262 244429916 180085522 131751256 723168975 922707995 163011212 654046412 532652247 48612420 403891455 628430177 670625791 726688082 788346095 514100682 977728272 190964755 174156409 964515477 543102965 11048635 367712700 603372218 285189074 670899747 596132559 160023452 872287963 458308345 112654682 980594758 125347743 30070734 807169440 17013682 777030798 480668517 748635161 342862339 483895427 839870456 499738792 482981906 305494346 70815236 60741114 846151479 242076462 350727311 118355693 99766091 474380646 224566672 224678774 300571532 327540803 697772288 606234031 905835450 550838981 124861178 54107314 329012356 727386894 942824626 853725546 942398088 384382426 135059828 2685475 912895840 51294142 476468240 572311346 645757741 595183700 149248834 976152426 861901048 453489300 865152344 572203271 996423884 974609277 81012364 358411875 843885458 606202256 490685218 765618514 133362183 603279057 561599490 287613062 724356180 138592437 860854926 492188962 69380459 398925835 724989911 82139433 565997309 135047026 447737850 991260979 779677209 490951125 936125664 77808412 777777069 631022700 586364942 283432275 541337811 440544557 259524669 326113823 591047591 234173713 698300560 954017324 564013023 137268281 823461435 463048204 650274048 350595704 813011167 2819108 503772121 574298449 133587235 267592074 574707305 457787692 727442718 919173293 210527489 580587228 288452055 112413670 322102114 661898008 871868434 765674783 655906926 645680681 453077038 359180048 198488610 842830838 972140712 786430458 459709021 672067168 991167041 146675576 816420874 515063864 458922498 844974681 817916797 76030725 2286726 441856780 373137768 461376293 422044490 814926929 531198508 737525137 294492659 646130190 82185639 509456673 924493164 174311900 58871910 930731374 173349947 697778179 659869520 469966066 201200233 786908111 99288517 836531761 508358842 697377978 837426318 121340581 486220909 918965232 871592670 421198726 954595645 141844745 838261374 578188404 991769024 968130827 351767387 908648903 984355516 434029609 39124255 137369477 423646205 336120039 262903307 307937197 948178569 803476586 557173124 672654944 638986433 718235973 816352468 227215652 81147125 338894972 981096352 409909259 580016624 123158240 640937442 778909834 4292112 688623883 809088774 761793895 63044543 508726127 342875239 967465975 683270315 3052268 384420079 363394361 193994458 93265582 74239772 621219012 310512433 152784439 318575782 684349613 818572458 809061095 508810216 737994468 652258574 997102469 362564787 813746315 784606582 306356817 130771004 958262571 334010157 755227671 746126051 803199903 368194113 417083150 649021933 96668629 690435855 989136769 26392045 256409001 784974641 712873657 663864480 382917500 21792801 274580157 772155543 659814654 522305894 193411406 469635995 986819787 573987089 219025978 641391116 131604341 731294687 849188021 513159919 430606023 860401672 119663359 161772029 952961736 533775643 538293283 380774004 558453725 136609986 242847279 73971200 491113345 679799224 151593031 173440070 733858315 319419696 936468503 512210803 65662220 714546245 840972915 665357591 763815930 955052061 599720173 214804231 541334115 546796563 780047490 310715172 966687441 662485606 770577266 395275940 123692467 131981934 497501650 938692277 880668947 454772966 704902958 630801408 847689250 425083364 193343728 506127037 835053667 347476043 668852058 333190169 162929953 799873128 241626729 858426827 944247984 832113178 621213682 651025554 209491571 847209295 932681456 37065740 977885018 896948273 249539312 766267418 371172603 408345762 850069548 87499044 317990060 657994094 354079775 640646562 511340383 199752978 599536389 996197183 279375290 447659619 888235650 588064936 495039981 996260202 415176104 960007883 590993812 334145461 749947307 86653425 598815870 273326831 140195637 972667118 259023685 283676423 7183368 467444540 574499120 614979602 804712042 516506205 664593600 195579390 978948432 433114592 419627841 266221797 588216940 933713516 768029627 404205651 25224035 399779359 291784555 241630233 619524751 330154094 833313605 943341221 216415095 258945162 377546345 576436509 349334390 34621444 721183743 985869548 345744697 411184946 397575331 599018166 812666639 427459899 820123468 568647504 933503815 619148367 373319434 313178055 657110533 155316719 408468428 339454199 51459354 209837379 109023761 410817800 257916372 30462841 208944813 118724171 420372787 54805653 353564235 273325555 715610388 580944208 460924112 690781959 353651766 710519780 361754885 518664990 892696538 532941517 882765138 599536365 431785984 608546653 352715676 906603517 816783819 296906105 191614976 194597387 231388149 220342654 209265340 795131963 191712542 680925001 382909087 327969477 382807934 374006017 214930931 116633979 104998003 603120060 700737436 195926001 632006282 529268432 99998912 553754777 34307926 732774619 357705736 819667346 195300768 209608725 546616088 540612145 468045806 665937132 486323033 409225812 57928917 795023901 150027955 781369024 112959366 963578554 91974329 84390099 688221147 885555154 430635399 463327660 942655519 577828625 541202734 863104513 250086280 582601268 429340786 856604057 120540656 977639200 378737508 527998051 79935840 186973236 842570103 545621411 303654970 45676094 620715378 250030072 930226421 530155189 539198337 645156313 967774873 882230750 211699295 445950739 493041799 444807733 737930155 990205301 987510001 433052282 405746918 83989691 776542100 335508846 87799380 699798740 301824536 418444624 730480108 58177848 489176703 930905432 129658038 833634946 450218962 515787500 874620911 407691751 15339343 216755212 396656934 455418172 361499386 161877483 683187654 276786864 83090831 489484094 856944786 182469829 281035375 852849848 494978130 23697716 734618112 684901301 717925315 481899046 855300952 410440594 481840360 421618710 592223806 213740692 211562556 896628610 591932471 859311428 228887735 948135370 820710017 92670097 518331585 244553547 926695065 494205473 852642795 408702314 437653424 347390396 155735965 512869632 85319631 832408234 182695454 463178320 41062142 680150118 206267221 108635905 412511570 675103527 416749157 788322131 866452857 898075001 188364922 743137810 540028354 4864982 888074277 482711811 436641013 158529554 478312180 904173558 611161315 13830129 920555258 789782237 732641750 633910855 498954941 461706961 675316761 342517208 488609616 437574173 104301312 442965302 120221768 436694639 796937693 69962554 533769620 919384008 535964272 963341780 782012972 707461287 918247591 55659964 96334777 84172099 865661204 879518613 45076514 285129402 415384642 398400021 193801793 843606775 683245632 125458978 975884218 319945887 920104908 84687538 691464749 997260219 875251658 796581490 884680554 374651437 189768334 674723380 205469988 608858276 470277421 526472735 106496610 847499462 534783304 598611194 202513659 338018071 123671004 354404325 18711402 517536213 98381553 823007080 388782505 1009294 489550861 94666503 246444505 606373509 112211555 723718393 897709701 694766715 85388423 115613884 424613995 243820959 604405123 945968466 367579478 996636321 931120460 109393263 847814890 880818078 617015397 446007394 433881282 698065548 829929928 268344999 874103204 438873258 227053015 894050230 107409844 711721900 311972191 310588855 194201195 111334881 30987979 139329641 915545210 335225951 526969372 130409487 683652092 329564353 182096245 903309342 546650517 716771985 425234663 768242267 178505398 553218338 525594244 101105300 100393940 907353184 86646944 756602279 730671877 802371940 877172557 975740552 381633283 563837170 968901578 73150125 429229757 527878382 74845827 827883242 126981765 924916422 746138852 930249290 101542258 778503210 339261195 675897800 761828175 682392739 320601977 90604873 165454797 539631273 195557790 525835958 405309315 259125545 42085209 520917726 298788307 967446442 309790211 248459822 778802949 24075959 719943374 956455737 122164326 611269485 768393085 44924019 947343427 603012904 485743284 207726448 34606025 97755409 583663097 715016952 198296956 132600897 752521585 870050339 709778334 796270058 826238571 246090898 33254229 396464699 605604697 855233733 649150129 388274883 898129747 329804722 361931668 398194373 902231467 469241828 917892087 457112397 44637684 959058654 432219974 788488492 602175575 778397161 989343175 874648559 532739061 202352797 954315289 94582536 180979560 799650682 790963584 725872891 627188451 709148418 348383155 850068240 553503332 798311906 671108467 513982777 91702412 164621900 63913294 77757613 768774406 936471626 499961348 726392347 929221909 910453386 378965704 584087100 394815432 844384011 701400330 268264757 679276936 73009751 964978283 394181140 68477164 983776702 696399008 301005723 265379690 251929673 193782143 463501412 183776107 46112513 525324189 259982273 517062915 690477338 222985772 198713626 602509494 235453827 108231550 389549785 984954564 769432318 783437403 991299136 286358722 979729072 114894307 91716475 216179931 784417517 175729965 727844533 286578745 219117090 538451043 618799620 655809135 823375509 184750934 421997284 605387120 518740063 256796461 470137441 760071006 499855953 713801693 215178114 674319472 295328444 147065602 354179575 373356563 454147487 580061015 203914741 805792542 187317125 528913194 619432428 678964287 210466123 691211975 32228941 995465573 846392682 44995529 131278801 252462453 146665268 958392552 734012967 365300735 325943680 948539719 207586233 349713157 914285634 769883991 664205378 428117907 544632323 720873990 128936206 54942831 205179453 623664837 592334466 724669049 957413537 401883363 973219306 827454140 459125250 41113090 575362037 450039957 564333450 172444701 756163519 452703163 853126568 647159193 904788192 945922507 73928958 439202191 985073844 624381733 30501436 832459159 650633484 902605722 42553284 739404585 588609980 511988439 703281887 814302077 437037242 199505731 110208205 985195842 28300250 342763884 674621145 168561101 374440672 977385246 553928390 96205611 745787735 14529311 738151953 221647370 326122837 965731084 653411774 838530293 723287087 483104097 356369269 800606467 256365707 293909165 629472886 187203629 684651530 20194060 157129136 808460805 538942616 208510845 334849152 348868667 253865950 85574669 138900971 529255683 565293393 582193219 162591199 219249085 26676921 262314277 390251956 623086992 97864782 76457892 923653555 38886894 932920459 151928341 636120958 89932305 29446826 953629842 622653416 42432763 437235564 328341591 502526353 35380861 735491925 461443978 799479502 129876875 761985709 447512242 737734858 787269571 189016628 815035875 934077235 492508956 832677964 277999611 80974427 16545450 548141001 999951206 687805800 176475062 46350405 69741933 982757863 319556119 693887165 474190057 448808782 942772765 860950799 21473927 526625873 339996172 97627599 246003299 594726819 271457100 860698348 782227939 447250610 976666181 298658359 849726364 983274009 735777250 752128985 596957157 964138580 75799721 259062630 4743741 157983094 312469041 259406988 684195316 383095039 283997332 691276714 896226216 203683198 263462923 353929230 673827556 307515437 859789152 181359323 871641104 208599004 202686188 157389428 715768026 385709323 912771384 444428953 337640457 379247778 734819274 930117822 113509550 313637190 633227569 136678055 323514351 259939495 328947374 4021413 875245039 95463409 625564701 997973241 982288250 391824269 179139981 419839851 784888062 550363305 722698469 317304983 326983711 830068750 580959740 869846644 338453207 963599560 792259179 96113703 576757819 564608315 574992455 781832944 456982037 219077902 878840111 948115000 862852413 920209833 652080706 524947155 465398240 540962296 5924925 768545013 876768594 373892649 543662213 327304690 972795563 24602178 672279326 61416782 632351937 730858860 753012308 189777663 192449779 748901155 725876538 128701851 387033903 243766496 429407932 239077472 908057061 52686033 132586150 274116402 426011293 357441123 123008862 578663732 475916021 994423230 296918255 96513402 898745315 877388286 298048706 615689328 730019935 425310451 997738857 897504130 626827288 503099805 603947235 27647019 282855314 884794881 875483998 244955154 90677219 629227179 299224566 475708652 74578034 808460359 660151988 820895127 960446023 950395737 708256854 294915653 627945055 595567200 874939611 302454472 129050432 894406707 811555211 431061777 828221277 589013478 160680402 442738852 946030774 185404458 183311997 240496493 367305143 668192379 561992980 172380407 85385675 842573925 819823709 642931564 216975872 74179001 570173980 722522128 169104357 946472692 779146725 456459018 627388564 655173090 563859393 23573013 469666991 157941946 309776364 630711051 855764810 643895255 524034492 772375933 177128801 998300871 851549114 45126627 524969701 475869529 857835156 946066597 223826073 728530431 287374738 909085508 606017090 278238979 101727588 130300979 908326327 199265135 92922175 419120580 775266333 962233983 322776433 578528781 470403572 146134175 230744283 370130814 251255446 852772058 629936124 709255445 844436303 877413222 807272784 134770160 410373434 529655085 739977710 278025621 879358043 555544336 566934098 102089006 784098120 284978094 584694654 482267657 352372063 428964062 240898401 859470560 481534910 410928618 396714875 158177838 323882135 328322026 170880221 361519661 456219235 566280238 833931970 841529615 706442773 840574903 246141420 891017834 672826888 260576816 709436226 506386749 366894019 549240142 450184386 754909909 546302237 104306822 499539816 352193915 653602082 468822045 951988227 648756472 202506215 267325515 44722550 760594795 780996569 808979694 280301305 895770357 647502054 555489141 750700362 833603971 65648956 204065062 434752188 206294131 741461884 234197657 867545571 176817139 778369651 313997565 739388370 620514707 758302674 63389149 408676728 310806913 24073323 363868946 465343083 43606289 415648362 205502769 794184871 592119539 903112436 801082689 510216973 165868017 381643947 909311806 780602454 970800076 716382644 907755457 61426749 798550485 685024576 747150496 812268908 951971574 318222424 715859755 368432764 630063751 669990387 931168165 796314797 858605026 190874919 883774427 753617285 890626556 47840838 629135684 377766775 423118904 345913748 288452297 655380059 775002611 626484436 13946253 884913591 548175131 844355375 812910652 707958637 619584180 854556629 920903370 467879546 284430601 932621626 105597774 344749960 562585286 976584493 255652647 21561951 182127880 506240069 855716256 380178100 562917263 117097622 744445464 529006690 185760053 326179224 593954883 143357808 464885023 408978478 805592552 852864792 765697440 768402804 64856832 948317221 563890183 201068325 649672144 392531356 220944902 312000246 972228686 853162698 449459239 239079159 651103481 764835270 394459174 733238061 423980819 387452460 234080559 235827765 230515650 489961463 90455510 847763112 228372476 375302078 34133423 748676970 615727055 809044138 453305694 970723871 618407581 105825407 642511141 440733790 155557069 496963384 909424118 954801007 109111780 932204980 968282878 613184475 871937072 856149600 967950726 642925511 913553211 941873225 598340287 798948221 711350199 789316184 884412833 886883705 108343107 241508339 671026942 206211080 770128125 422049553 162080469 568422872 938862982 289831755 83445403 447811064 393584099 696065514 654921456 463236356 101849645 635536709 141908119 679639093 297966729 12845289 387353020 750428707 916602570 559767627 654587871 844656361 353295570 443911473 541003216 533219490 42563426 441735330 504597175 637781446 24618886 196069102 860028805 11783587 911156698 106699310 173695415 366237646 744205604 634372586 616653326 501251318 513534919 984067783 475583594 697609007 115014554 685942981 766939958 110102906 45090170 120075037 390335272 693150967 863659846 169465702 829864280 953947310 354103473 868471299 101962504 475771494 26368464 827760152 6267829 647085763 97175716 467200545 902227106 295510610 920539281 74859684 452407257 247086604 473347738 686647283 886424015 999035475 262483165 288672790 702414515 38354541 330430115 374562489 290782779 371978989 500601198 225764704 452069303 727070777 993757168 629456928 621606472 616188134 411236979 848133979 679542001 101542606 956232967 240273738 113079634 692953790 331203760 738243274 85127591 500253160 334454213 952822959 556130742 414969237 973425168 468066535 382647561 49839275 329030558 391960348 88515406 697764393 676134312 710211366 894547276 682743288 48587021 215657299 602782480 161252271 399250548 141921260 680719599 303081597 229753954 784337919 935762844 342438456 69191117 309982069 655624085 55557538 6077569 847096776 49680607 362938138 844512299 106302990 960419594 959195390 565956745 866234722 434104458 804612023 819960018 480586199 69424341 284893658 325092706 622194558 163976657 30881127 471012840 636928914 208457373 719211948 917050289 847916071 677823810 486325196 224440192 471505590 258850037 278094679 445609531 414549237 655138820 223602959 354254098 557718981 901137452 834857515 398314064 778919256 81748901 159524026 532096988 740752195 908408187 386540092 850417864 256100105 459026617 674545664 940454691 265323189 686726891 635301296 266292348 760695522 114529000 254276350 527902603 447727094 455792153 379688412 498875820 950332011 291386561 767868523 924599583 586648725 635377554 665428767 349257457 712672324 515700603 310040737 460583964 942248026 500407019 787184486 255767690 81498408 485150422 277701051 588642218 606890878 513418266 618730391 644337475 688618274 661093416 983079624 739922058 544230519 438179804 5945032 912829910 186519059 438634639 636116747 700084291 323123399 492007465 465626149 55957105 283499085 863712557 767020034 329822940 304767194 795456355 996866088 92303119 622310434 922845016 751262188 287134657 791054593 669502734 230624146 172594556 218897180 638773232 451559240 117555678 479528994 260823594 133630389 31495053 690515580 482645750 712868137 708203677 528376764 736972212 304694667 481061175 812012334 404577714 638601948 901181812 144526338 399060978 382664469 209710344 924907258 505059564 347583990 483283705 123525087 589872218 759444718 735522781 461129810 587983576 862478421 866012952 804171113 678292153 6223773 991843562 990907642 209688418 239063382 536587423 90946907 967183657 161974097 280585690 425836600 746186524 289748181 415684713 171730884 205867650 874412266 534273882 69450793