17639
555318271 50373939 961696104 894597330 903043277 67836209 217663382 782092458 118346179 149029149 862606342 110254407 291445943 810438378 362838876 958780103 345361893 584944405 79881732 871214417 742802978 737714858 284901609 345555900 638863322 989955833 971379322 46516351 994231256 384041669 175506343 728565036 492237986 377299488 983536580 148941242 544696811 432249882 135945817 889023936 255900357 927483348 859278325 324775707 248321179 351799808 668501031 925901514 556867860 495626007 876937547 611498376 23101022 717301767 976540345 577353385 231403550 360230674 636037701 328676595 222678356 871913555 871485055 175980594 159685645 946144086 119005468 262543858 110174637 402362606 42583750 78859075 256204228 693000801 979427746 491445563 910093408 270768881 120477914 716174550 695425131 643056818 999622836 753567829 356199889 952123071 736155904 390288130 755357353 32774340 831258824 713115789 376702957 971906839 437247614 353359595 265684001 780726209 373851508 962281635 346422490 511518012 907982106 138434014 763352879 826886109 852359388 406457569 467482530 426462780 195933494 811871980 858660925 911279989 87815735 324147675 970460231 451437372 780452660 435722165 593564441 110575280 976367159 556101943 970989866 247598925 128344404 556717043 170414847 223419891 359359360 287483519 541065429 101396580 763472839 750422088 334260974 44746822 453496796 694652675 440719455 420294320 64162171 475979078 933661241 865095619 649532371 531992946 658366578 103449791 147944103 591262594 522932235 635712544 747447553 869775718 237042098 593906365 45463745 418052853 524919206 898619087 614659750 454393908 519694367 719098333 169998189 447470629 979469658 224615766 324527748 821232654 299057368 194433878 116995731 235360483 914223825 230930514 924244692 858883020 724529989 148210427 101305484 408291508 112342455 417330811 331858258 410979002 183398684 717575600 853082151 604079755 956487796 148143755 329500235 720682862 621867260 519763806 931806256 525898305 789951054 663219317 641145526 132389620 234563257 102578510 997953225 422177118 879606518 175309325 652916077 431900784 996977083 136244393 205939188 247302480 845719 570775247 640936041 563757776 694357390 676372943 76699395 681033850 121538245 314804148 535137231 985561752 258487926 520686777 290527773 860007992 581393301 842090849 802458355 197810204 291657396 979948113 378122297 458495183 493441405 492189488 518321203 928423993 599340767 786736144 408148634 778109499 595146078 583523689 858950343 504408275 569176116 950058917 611911761 9976027 961714564 492077273 609593254 673634290 899329589 594506774 484774671 188711141 969049159 459530970 930403401 585384555 650811125 245470192 880386010 754759977 142217210 315228272 530662627 45078470 629089548 187892646 123389253 369973400 50030073 825467988 396690418 542907809 935509522 91417222 620437891 371210183 27252501 18448553 821942077 459733087 284589514 10903499 972215880 579879759 416785590 946643553 660017695 118330392 869472575 900347417 505100128 624186619 808600381 472853579 506781004 720597151 910971491 427485317 102311719 259171015 16427607 998450169 841161885 939996010 454941695 800238863 125712001 714148337 604486836 562447855 167261981 165385893 940176024 894167840 814435830 357564216 788542107 566119528 955646970 219323081 344734922 86959182 590833055 11437112 702253233 631934561 157172424 12222305 717389219 176966607 165033873 401575013 908096988 88834819 727992415 617946165 717453131 252814116 310852743 787539660 905476799 624504505 764738735 203392464 530652432 300041836 880398794 209091074 780477550 91451344 374442162 507929336 776520792 665747096 282753082 555649185 357302149 71520541 370857424 622214175 118668012 351979357 256436756 824680411 957657591 106989617 221160539 70533737 11151760 797408273 855690295 846802582 592247540 212192836 533415569 994040303 610533655 496372567 841588554 737291844 833394407 345478593 137982889 130537178 124885343 317794569 231950317 347782626 554067010 139542592 120974782 299575163 777998420 31363607 504665706 995282183 779077023 257330648 204312855 517917131 833609543 959678091 755334791 203748812 229881909 348654586 280950185 493541757 382866190 634641529 549842170 638165549 774284292 549983354 584960872 949656629 329583128 18036299 331702936 877236010 877595571 939257474 406025856 496426327 695809259 182592495 741168990 97018377 54737238 380598969 245574278 135141862 758290244 187768387 909876493 573208115 908864294 159991794 966590055 360983683 658109043 849607449 903175590 691216095 279926776 658184513 986556267 27650237 347232753 261366348 562041902 668711061 640071550 727993980 423415875 571378372 488861090 329016913 437589802 995677186 757058166 433485172 467428023 290677261 551636585 487067280 999567687 973762481 965318672 266110401 244802569 58392433 344368074 376506119 733307229 18310820 584384026 620620181 848989576 71857072 63969487 356838137 407826794 585323091 514385016 314156638 136440559 607695526 227142483 301164794 654921390 46347964 83410588 37227865 335424139 531403835 223506781 458454555 187344140 587014815 277816174 193931445 504776975 341062025 637722391 136987320 851259228 648864020 184097474 685094791 815291400 811880414 998763232 661400696 380081116 877331758 261734223 820567788 978611233 660989713 702277779 518882575 690320685 143021230 67524497 746207038 328712662 633423055 609085338 573307459 260966386 866835355 152976316 370257183 805652115 565455744 420372039 780064151 1074997 687014565 181839150 105948605 457663584 61816519 400649575 839208575 916518865 383542032 870595599 245206338 268719251 149555236 679330279 838289795 787666064 718310017 525962867 15830052 840750796 411127603 427069030 449046183 992612792 902768822 617396637 232652075 96766539 932851632 118495098 21759580 533772807 341795387 844718967 142120127 471912342 661164551 845320211 643265044 171564987 26354093 582212206 536330966 327869557 927028052 245056651 876646471 957222683 510879712 697006905 544126395 265156538 972872091 630656014 96677353 123568487 282383349 56405885 583825174 673428842 659355802 873855523 694231951 360075641 246447213 340028907 894844545 428100338 858870481 244701052 132933314 400142228 610763480 973999328 644578404 114529134 57289583 753719623 31924314 3436683 715111461 473947048 864696764 809102534 701972065 687263152 114161957 543163750 610112316 165618267 234600822 937520152 745806950 257885425 808365144 175411307 270168832 622302794 296001541 586372527 811357686 335260898 19995377 550771536 937925929 768731015 372377626 356234719 772674853 3897004 170158080 683433999 168289420 301795946 126524484 875502783 345306503 227565775 743564365 740943258 335588252 838389406 174159471 736915636 983110887 225874348 236874746 526507034 253937094 159993611 297040687 220295614 809371897 636238048 244102232 645257643 175083246 435932574 17622582 982043583 531985697 821060445 418967404 335801242 173369651 15970883 220764060 365914700 842856331 449065381 560606252 590802682 201441641 362425781 576063963 941172361 175917622 858601665 188775192 28370693 466430643 717471102 759173635 432230058 451092442 414782969 825794826 943872972 245617308 850683378 388461651 71634371 537186347 498291997 957830690 531041828 98091667 317944969 210966012 669807367 599503758 593841156 515985976 779364991 982999660 297283924 324054981 706561461 884171207 311594241 468441813 248957666 807263207 220141143 753534307 676096555 347924294 15324152 466696181 425568513 796743997 685604566 93075417 916420959 683276568 174812152 914204899 789525757 360857193 598494664 853683430 591033668 126083178 187374195 667753819 659654900 831348601 302981899 428622256 668362070 541998292 226248800 336643049 698396788 484267644 72651008 88870811 849719080 609788905 254612251 504256691 375408831 989405945 740864152 30707334 803930146 801164254 525608307 431328461 353574947 839915804 495434995 786743870 765735112 747079515 226195415 436741626 9958534 123942139 844839666 522291061 384068620 770901040 872577504 957038398 994100274 805536124 414757163 664285314 47832741 575843658 752122597 813034806 719885397 919850706 358165761 372889352 531423324 27103060 515868959 862758849 347041419 682541659 555057385 800300765 343170657 709467967 362552784 309419271 670112497 713988901 181881545 417269940 715958798 581708613 143864106 671211644 962331590 288404611 437846203 329268606 815841767 319440542 524598376 297393499 808280212 218561518 902446372 209984550 99564877 92589094 347229400 948493017 747887917 424096486 16134385 547944133 218464931 419436583 831576847 276010013 972136550 422629601 392380357 833563942 852402929 473187439 201832868 361048718 767779137 497824932 508969172 356726683 62263995 617920548 434337546 814964275 406254403 514571231 742945482 891632696 194324300 986458418 748548140 362389171 56265774 310733404 849353536 275501840 290590615 253252117 779734051 153484788 243364716 708294873 4917023 877510935 780848736 743540410 659728411 966052876 476598922 13812039 688100461 828758582 147284240 237484488 241375790 250377081 568861423 448853360 258847249 918303463 824199178 563572873 688753533 328313103 946837144 138005617 377879945 393829447 480237700 339951995 144270892 729383160 683099844 691498475 712800924 927822804 645848648 743492590 305912084 996359051 555684975 410934056 956642358 916733914 463599768 618041401 85743674 7863846 76342205 961626106 949010419 655078713 314719771 882909096 237228637 416638621 455811616 652893000 897948741 955679957 615961095 179067218 33229851 522523292 962248538 540879603 220157479 540365792 61939693 785361364 399657116 694011020 908899532 29132274 819065975 11188516 218321977 35910744 29049224 312524149 537890611 991214082 47833274 944010564 230136597 654134612 206787491 731935983 868612498 544070236 120689879 67810227 425556330 192850295 74123694 990961735 746702499 706888537 68014022 278880881 525630305 132500397 814578355 592340886 937682504 689295043 6717180 155844730 538748338 264094613 584451374 673225641 590138899 37246809 290548168 516845764 914422460 963370065 762525873 338837148 875902561 722458675 633140012 412868768 783991833 639107499 588611505 660570573 800909434 325108753 606298931 495048249 836315996 544780694 295282315 647196502 421881729 704270039 587397221 155440806 35993441 467992535 647535325 838255660 92956621 772317495 367280017 236515963 521195001 631900860 26786833 546080082 285532559 138162204 90671864 946966072 14603724 360150986 825073844 973006924 443023327 930439125 714291066 139613925 135556889 889242075 959592785 116232790 570747800 800637839 548835792 601928882 418325728 161732190 544382407 882082853 124900525 874527218 423373075 77588267 455292098 617285304 862171716 193340518 921974258 289775787 662042348 663628097 542026091 781214902 713051543 344271192 926900243 599770170 104818182 330178092 677311355 829069359 914487243 52817600 740675668 19169307 599870435 991345663 551129963 879504958 656117105 615675409 596330605 801447852 113055784 233314007 142472398 952020627 139996516 120846233 651230721 823766858 870374498 935788738 254620206 234310700 291412661 328454465 770550142 859138443 64626979 242916925 237149914 159813520 915215756 903591875 252403066 302317441 126072054 990016031 750082895 632433958 828139177 716949109 584218022 653570014 807676815 747289235 185636207 107350265 975028652 338551564 346247460 411601818 195766850 687030201 993858758 640597360 809643916 850200993 952405022 15995998 840137761 97011112 95889467 173222376 489285881 757754931 607271739 497406738 445183406 328480188 266331104 591774937 70880667 286324383 699614554 778704794 709825158 137121295 116614928 287029168 890291098 17837782 747200632 426849193 279712750 152668950 606289 358550891 548538765 694649446 866866371 685538922 59300949 204794782 823359519 781710447 19677173 290866810 538431482 746829101 283514096 91983706 803236381 376839582 286073507 74063838 977583166 261477614 946009207 628724858 112297907 330887569 206634073 158553861 373291554 260355759 617526983 616461434 666079534 817793719 462300966 182273994 363333949 600560194 883857475 180801304 584264876 993804639 693905836 446863005 283585049 134803128 888387527 425242263 565974007 123416927 278733684 936792230 994601756 862347495 807831590 242081776 704936035 187997050 941877580 495871356 131945689 601346226 237128162 913481625 162223275 242078104 223992593 888850052 309152116 474119355 980592027 857064938 113038554 549489084 198701295 149707666 725584150 116190636 53093829 307156731 681816785 636411888 93677208 637575090 284480467 161709468 290073222 158212426 415545892 718647205 243613048 890190525 68438897 374400529 491957639 994937733 943829716 277556910 358832732 378281692 843211848 888714109 455395746 604711545 557824737 27056642 409058243 859385119 807999738 906949475 305835044 362102026 813625328 548597456 689220523 718635088 444923387 20373048 276870430 606394677 818701387 274424412 315946534 187090711 868670726 515381078 378866935 757565458 24436450 880778212 888497732 364257463 11821134 392206962 820909473 190736653 41488344 43408825 77244354 133428416 344521728 742679535 118446595 191753255 327795743 478901161 730792102 423137217 81842288 58831163 531105571 293672780 271894237 764172598 327289122 115504128 494888535 597093731 248350742 959114294 342593508 551981858 584919113 594967628 512344224 628152971 579706273 383959847 414734721 450001765 229948634 696595750 452956551 705720382 709199771 437306215 173509603 531824093 888940643 15456482 988403862 466725465 623137543 316622886 22233264 955272796 655618258 347537950 623485401 535750786 491386820 601876896 986285863 584054837 622604420 632377553 265811737 770515613 304149741 72474579 846557749 327214509 682791690 360011595 626283729 257142956 506165042 804540426 994942783 298237665 524126271 704693199 412137246 806698552 851427397 29256176 392873457 502108259 45359290 324535275 609895415 777448558 836139335 298441978 46233801 126340862 645590751 69634356 997828612 395178017 752597421 722550417 538837168 988441984 348498744 768733849 253880293 411923266 293217231 283527912 644184252 348953313 123119948 275295087 113142426 81075305 266782333 594736930 869903631 248242159 49437217 820614958 890136770 870995795 37156789 806760580 599501503 916217640 668766456 43140322 354438519 326109765 142115083 179154597 434410298 907688373 193961853 312461609 963582143 773922059 114215865 74341578 153299865 333744843 627841196 722726536 908403123 942995267 878226455 928799319 832797660 453441926 222739627 210449993 188671986 373124166 304930534 670510992 246413191 143651603 120954864 945380638 298002032 475078075 630835695 377845273 534502614 280530355 547610062 969550114 127286772 458360663 44110124 721499098 13302237 250215280 506568824 114647050 14131257 623683639 975002038 435388124 439828136 563879878 381826921 814332681 775246033 63297784 577750111 275522012 741575973 436225965 787369743 32821073 746467777 184877261 119593207 293074262 560769734 610881618 494360065 478463727 65878249 14750387 426199679 107949916 543631495 174212501 965045567 73916352 91034272 282480405 90973047 855501339 792088876 44546245 634012641 118778360 635944510 628803799 445738740 195273534 886377188 86344670 832606189 295233455 8879764 552400767 882414301 505706346 47262961 126948765 669387659 253979970 692561607 299503430 798385303 5359182 947660187 255736388 465342944 13420741 836389894 639251472 800878262 94673843 592547097 341386302 17549198 923208452 950506551 127393198 614949971 374602160 464127894 651938570 408936702 331407527 359323523 324048128 277001008 430271727 214996089 947977944 358297520 88854482 107770613 288116907 361523725 627196462 501636348 374324937 902017780 470110496 919566153 827088148 609896538 415133623 17605098 301701426 777228197 956741112 192664421 319932581 819701304 341274306 455489717 242782225 863793425 9990874 104704304 576183891 427931760 446020946 258499540 255345580 366142880 643708722 897764032 248760408 62342584 45273127 96467282 363157519 545106423 495960114 513247502 123610163 684088743 803591200 541934984 238709071 785268654 479046124 267381118 743983146 141225768 276803419 508489436 713399973 208717720 647163931 224960740 834440532 939240969 593758831 701879959 980811779 602246907 932851986 538790102 71960117 21866101 197079965 865576556 575993855 948527277 962656502 438540473 865469613 873870300 820108409 994962511 722236413 989631511 715964012 286496105 394640929 124399744 922657670 885880635 168096476 868021410 912986787 14818791 563255610 272908452 105971615 939408716 492051166 31755425 380022300 562884051 729439036 349599896 669469275 288146048 244533788 224113892 23134006 56971223 685105099 128461332 489852906 175365419 452638670 424562201 177571166 318530215 809765531 163732202 371608895 801752474 999390501 679620010 695228132 887087956 13871670 110110442 88295160 824509842 686534432 633669162 287301824 894402698 899843361 951052511 91929416 264498588 862598900 731266654 554655580 420134409 437198591 804515927 511087809 721654026 321477511 128696922 270185376 742740696 246580437 422990929 497365088 81962419 55087977 775546252 399184442 154249779 192687537 842094691 715903158 866057070 566078682 372308944 938702707 534793227 101402084 51643875 723818535 678609339 656874186 302190163 386301850 273693258 868217794 620201953 857794879 546962604 892593441 945634794 364652803 188872177 768605258 941968893 25719170 981431086 809998123 151875067 978561924 781368491 33205613 440948048 848063601 968509882 795537105 683206748 293062740 473136639 430733479 931711226 592695438 415862675 353585513 987103404 771289828 566301309 679115863 846367245 963311868 907988636 875510052 998172126 676096475 212306983 561839232 331457314 738915892 48263733 516812526 923496871 734830046 521094278 191111940 850751058 736772623 663947412 773855203 76341887 474308817 288069355 384095132 949596542 673608407 687577077 572067659 591147163 766614353 164433591 609989016 141681206 185829684 92022227 819750549 409714270 741034882 471301989 525018658 995452258 693851554 2744156 915159349 374896045 729147656 918198183 967484991 719915486 719419695 866399669 603784444 495075876 606914750 246967276 921369516 171410049 352368652 271960153 100991066 2103322 847184761 440928673 472664486 14865707 929723165 146741554 580785985 131164218 358587002 447717779 368228870 276629756 842255889 474598320 419052820 142200497 19305518 288844586 779536099 835346566 928055060 698495941 645699418 399336951 670964626 437547639 196807104 426211608 480078147 925325246 39913961 542543243 562480854 70698622 980349933 623366334 639828192 952756627 659831204 715622490 706021117 635522497 117651240 87182355 215107746 403418977 154626072 43534314 968736201 933258740 242605876 176004818 445149514 142515955 882065190 743554805 465611347 652970402 937445344 158201280 10517872 316991639 591209356 125891465 451758237 922352764 587851807 118859812 891325653 654591979 116320480 830980089 845569099 128655044 421653006 793764441 480880058 525520510 522670721 930950779 219704689 588107977 564297773 587213971 598056486 871146672 955545052 782676587 676128272 324661493 194095340 901136779 831818212 208717374 180992232 227123625 681707958 846321971 520115280 829336764 365739375 897143752 983081793 632062275 359921510 536958940 999604374 11689798 578288433 486013347 329450371 837399282 520695791 158693648 549093249 247396924 3487352 575458249 945108411 624842144 242035793 172434149 288135653 225219957 953335213 200716405 136442075 94411322 949758561 108364788 284249196 267992005 361629183 195494155 476426663 524302876 614551429 715503936 802957908 21530136 991154125 534417068 922761553 358064096 852227826 146866188 136471721 850204311 128604620 757631433 772986734 146941584 96432560 933854322 464271042 407348948 66522122 881746575 651612538 512451659 471262698 255608448 713496279 691063882 21964649 854590004 835714136 458537674 965153626 975846500 176233127 23467453 55193664 213815637 311958824 211150537 543830124 211318014 316521266 422877017 476959640 84113144 87254945 707303086 913293221 472927141 791398028 338996084 57291933 325964046 81039287 119837807 649790543 879841169 787638095 476296146 656129762 248220722 887170623 125775457 141457799 827020002 325111899 340570435 406983627 41572475 940210233 654671059 771846331 370754881 88841244 29631771 879721237 539362338 459173549 265308153 247768119 140841885 872281415 422918163 892651778 623479962 414509005 871083924 68075824 451842353 776567060 73201303 893781307 241862984 213693025 221746780 770150147 509016232 798132170 810754800 59905104 812825420 923160306 103255578 104161820 711966882 11703215 635333552 531230653 712776149 146047867 476155206 50064913 523482278 937992493 3188255 355222877 157094125 814820415 701233497 536032963 835614174 332944394 496299288 595588543 192345661 543566846 344468577 623803254 268461854 21742278 360547237 474560592 916162343 848472006 208738673 304916526 293836823 799380692 968265342 642825025 115698638 878867852 698260061 357315664 596264847 117908261 887859963 641899793 907489420 373945466 990211122 663953277 814306952 259926673 114348933 656841880 965708833 834133244 29322016 121911637 844337764 617795179 65162906 861556466 658225711 292521499 353844110 794390620 538169693 670183503 508517642 686719048 918065667 85661585 924155784 778651258 65393397 380705679 428139485 776090202 83572872 395019851 108539524 954463346 589288559 730852776 979392043 230008007 988363923 805434043 228032230 391538568 873981001 920021237 703252000 251026556 606175522 641795632 402350293 996089466 331256643 111019632 809214872 503090342 545430541 165088055 715214737 316955316 687751805 156595993 662002613 31846198 123023902 941421536 344943681 419864537 79897301 949313419 626571213 11662430 259357951 782530325 629499023 851521632 830848379 713149848 384854515 618725679 457787899 208158737 269292012 553336742 389402337 880178101 550726629 638805354 743173335 624734777 215843399 412160078 76260702 141516848 395915129 600877133 125051336 313898760 242652714 587416429 557841086 179056101 343433343 763224063 632597515 379448462 499822608 45838873 989378577 523272212 687387005 892759994 431246201 316445825 890984709 630668785 264095423 245313287 667860103 362567374 78748018 809009587 350737211 87082700 191201491 658160148 53801173 52986388 776442524 841798343 622938532 461690131 150772023 147040766 548049113 318447085 372044854 883187904 635193735 202933208 552759008 644913277 674576485 833945127 686822328 880328945 930325710 30035389 498007667 525096611 758723388 310953717 979457493 796476636 53648863 733441321 251533985 955866000 15696948 5351905 532000476 476226832 471945214 355910098 461858531 140402071 618580131 15484454 467182163 421259128 554738131 77756541 315314909 461554448 513984127 745527379 228366903 835258630 498656355 441815293 229306251 189998643 269426109 66699234 162365953 270633901 473055808 905589563 640399825 832053377 737973517 949481005 950105237 167328828 79339181 623994960 107889494 848897571 210301987 729693393 513136552 829063477 182291529 146276591 66394426 276236596 991027814 90608593 67173650 196476761 777923216 611964771 593886913 802296640 404814474 71042683 672861440 712906703 650388402 835944818 740577689 923502826 977446299 599276655 925773622 410443538 50004378 774947076 313889704 86585959 613251227 660038492 783501836 89539800 76969702 859643576 176869528 604757836 641862033 479364308 442972491 522444353 319729227 136304706 990537020 225950977 565845953 126614887 274136819 56874711 330596741 213941094 907872808 168414906 314865642 717821754 413495909 466107211 637174172 15699205 256350986 730224107 915838507 322296724 673118017 614320061 860029820 573647447 804947649 911293757 960202463 194258533 980288474 249269784 622099623 510458712 54739297 605837576 538861582 547171321 331991210 487069421 607907461 930552851 429579474 591249271 735726187 775090479 793163502 907995471 617660808 412532635 401366250 750295827 241142484 330346167 224825120 734210747 420020537 478202106 538962791 641300874 654039363 652741776 852996168 537579468 184350982 627838948 55605220 903939718 514136421 433591841 599128514 837051706 302860806 394053250 275988925 385225066 381779559 860363686 537347007 806913193 713129781 841908445 787802530 975965828 77033745 526453003 972508765 976345631 1468760 402430493 456035542 182833550 786921864 433945277 690267754 78816401 889785255 314948203 366885288 663891717 472686837 977410090 118640645 791549099 559742006 417440416 965985742 982917083 226134501 921657832 843038643 927363247 715933983 74530907 7167437 208787191 209986661 224445544 510596118 980994445 237556459 601099476 342785567 191822766 137894196 457181827 694348526 551368641 944096007 716431785 873464581 762562121 895564361 409447887 715849213 822401765 320570586 778311205 61149877 400782888 8948354 184098666 17660102 83434429 387734474 187658895 732951448 982625688 590467966 554318723 712370933 412714732 616545294 955700274 625996379 858039559 548785341 227079926 73648313 324680688 781009981 451318807 554707961 598796744 689312410 792808456 286193415 190784049 644154497 191606412 742363884 948925087 264740648 991078679 791006024 777843648 969630171 907701137 851932735 782690704 295677260 4991399 137800898 13754974 219052291 774490911 596221498 94791497 758911587 69669081 312131622 851349034 804567238 510847417 163638891 75401572 326224506 773992317 435686665 274049006 777252423 125793777 269508440 215671505 788732309 473778749 458422883 988350298 422842955 165724394 992213433 516060755 660049076 325589374 547942639 258760026 670125954 28575834 842632116 353637427 119200798 696825366 914939320 559555379 188059154 986982150 358405483 241898945 103423496 822429801 10150644 421698007 694909072 757612930 467043783 327532177 652407710 566867113 452383996 837069730 427296508 129440385 687061376 93930767 33599826 475120372 532818932 362108742 827226013 503452417 976355053 940514437 303823713 349502971 339966711 707218483 429164773 563566048 925934810 461832922 679617350 675780448 148148054 150486876 772386515 322782069 659372618 294549767 71871005 938357487 533632080 421031783 460994466 302677710 248510711 679626528 352170230 967407937 321063762 886875117 710201471 852674850 455390046 813179836 317149273 878049321 834030561 515126909 858640318 83933736 689757832 413897004 514690731 615447666 942298157 335058369 908027437 80482875 50994648 424801161 734145339 469847070 858180793 638184309 229891322 231223634 9094212 347010507 70082298 346055243 296287737 541730624 352315974 699732177 197271054 848221435 137737096 977044953 164277040 517015791 276400935 870913479 160127349 486933834 236850938 699964404 204800960 214475037 24525918 759960236 382852393 871611819 160878547 615464872 501061365 282806824 393436746 357905915 294794976 489378574 492986090 538372878 255225365 804378880 741259494 593637592 676068672 640079029 804252938 921664631 675176656 997435274 783259456 368841370 331293800 53810219 256212702 403047424 529666228 315602072 479069252 441298784 580259230 929563825 675780177 681213972 733294055 999853235 363719325 593861969 479408576 870037691 801948306 496446035 311752080 672601480 152620248 520584070 536485216 957100719 852107964 117508773 6197384 583628544 68649484 294116885 745788864 72484271 839149058 251673385 56149422 366576950 280997697 660844393 58759579 502871217 424985510 433553795 821471652 107369711 909867439 985718101 352776935 560459472 454592073 706881435 228654802 434329141 287955060 977560376 748942912 92846155 568144044 827604523 463747499 569956701 854086575 964461245 81945415 41996599 210662056 108718325 864689967 344393971 510149508 555779334 535088539 506986569 948670949 756247389 498897438 105533082 82003487 85424698 381223746 791087177 238241186 799847100 680504400 679641473 934395383 50844428 894198454 538979311 108880052 565280311 416393546 699522260 82255881 894667581 270142567 669131976 391314101 828177732 174064817 797702608 658785308 63447248 848952435 313551727 720924155 446046708 753391544 577652009 74615457 361088743 755172996 762840639 887833912 271438564 813220158 15870853 775930175 543186246 812617070 12414543 693869218 126349302 502929091 973946230 317453067 170758574 443869674 501502562 925515245 834821945 995791599 527473244 678102429 52177614 547668415 389288335 468227432 473491806 839839184 121120770 312728104 940313440 89222589 433051651 415634848 155379787 634881768 919742030 182112845 356590787 648388347 55615566 377252821 256874580 725437834 477832297 457453934 871762824 717632032 848456459 978706091 789070017 270585908 856897277 443770224 123185812 623921726 409483026 187897551 46211311 481129465 26255502 932389704 762289473 401573619 766146797 532013496 583365690 704132680 944916594 611034072 864620948 10879189 700408398 653141539 236487063 18603531 744577457 907393085 210173332 6604688 175469229 505842423 359767454 857641447 312750269 326947485 771224592 537519423 837681358 477669025 660651913 919706896 373559648 714844984 678451242 73949794 431788580 605290811 185912161 278799751 619429922 169367501 931221382 78951657 520494388 119492489 600405217 546240002 546228231 316406223 332612840 850268159 944833857 997638763 891193182 150771095 445619260 386650522 969652046 396429921 959164838 822188048 46419251 241561695 610442074 25807846 292613961 715384502 404529671 435658213 142169805 61823910 85450575 69880456 275607911 228114769 520395120 429660662 966474403 72002899 839686208 88024290 916386544 879720916 904210008 663602024 956557893 857376393 672325996 862571101 870862596 70740625 332772420 926439014 679434914 947826703 736141991 590523497 329585484 437626111 705415329 117008747 659288293 777880057 242704804 903985902 980901834 830060020 946766318 906377585 660333174 320737073 195991346 923679249 962112568 452908860 662748423 1821309 536192719 273133253 688675190 185026600 711428214 492855274 573328959 349405549 594851023 282603691 282346979 839691267 598618220 133865254 614964267 138421316 976106006 818479619 803549908 528722994 541998365 221320674 281460265 417031453 534167331 973396683 527517470 750965185 578356494 870228393 974562500 685066346 853071879 608221746 542355252 778434903 618172922 55767495 17433527 427216878 298565460 645054463 594782529 990305948 783050935 101155680 617177078 328939896 517971502 620020921 898011698 206968409 595961610 905646222 301499303 593306454 770428415 288485322 751928675 85960689 640881095 85284885 462094071 449513043 204262986 903503578 538498780 210892260 216528528 395767319 702768072 459315406 997078023 720216551 263229389 629001386 902389506 612693171 240957536 941505251 913194444 771516414 132439765 908984 835436841 181170584 581418676 357253500 610208498 76873082 835851359 754311073 756810530 849833217 100175401 163222830 300377603 660808118 437021390 749273049 497631924 472678049 239102515 633935753 837150939 371080044 810678264 994842324 560059522 469086887 750366860 888309808 659675276 41500323 631404890 663494576 264943089 280983834 635988090 85765342 643482325 955294926 308009965 242309811 50620077 559789163 767446431 782124504 973717453 515869133 261970323 744201694 433359661 893902939 126844088 890971859 484846269 468987179 298171832 370671471 373257862 928753679 640632013 823285920 758992173 451099215 701150960 622381597 913467861 763030964 71275516 835717162 561214724 707294378 53094111 507018175 217106475 293505861 320105631 487562302 381049821 573731589 707411002 168504076 50238812 178155066 709246357 539198660 952636803 890205112 88587156 781027341 757179762 205900096 367918386 658491730 739349171 262488984 214672559 419846241 329706661 460927452 850672665 89553056 164015471 309466635 498836456 785081670 896461642 537003830 165890424 973143047 381982055 53772939 470487068 914341509 720743629 642792609 13254029 631440680 398629666 909207190 858981911 153408295 468101021 274479530 481333327 630877126 51381183 204538094 693571748 551366344 381325918 330042753 511985543 962432814 363454522 23783185 656937980 175948507 986009921 959882045 209037661 509365817 134853104 941975053 40365423 309269251 349631687 557413337 309182090 276661256 872526742 938181650 780288106 195483827 177964011 125409785 186935478 77366957 621704771 928725885 142640308 233345081 180104461 558630876 639746775 78172204 107521412 859064673 878226138 81140808 866998048 661912949 176770523 103327912 690898626 859681281 659018309 179210008 123729861 191260780 851643312 258787538 588400841 522584225 418796914 3786207 230666103 145662654 940342978 291810989 294622444 492252789 563917052 98790944 412399962 384073689 794582002 733048369 709694628 490949060 647369891 433214252 321804696 954057341 766157612 858870784 716279711 674279667 299378479 375154526 86266239 825359323 496957223 69325498 180369348 71282520 273222207 746983837 375821723 318252041 25922305 402892658 809817390 38982442 327840837 726374905 362162492 643157175 929390529 802395102 10989876 789847784 331421998 145238288 86061001 816891791 402339664 363773627 659169207 889327655 293068343 836532936 348795370 866386465 562956421 954155171 784018280 189996415 315703045 332405911 555198789 951091325 660908351 980564294 469551327 882867100 827318726 380745955 56909856 663811892 760276669 533049840 385046757 637581271 825761010 166915433 96420448 826492948 498471038 323101753 757392453 602657246 875621574 979108095 193438218 527831129 201921497 635512090 778345912 453439254 636828979 729785731 590215802 629782742 396414436 908346169 637076534 693333938 517875993 647741430 769566891 18307043 529262010 672690828 785284870 758003227 797561672 723973017 102198884 768129683 35025857 400108662 606509477 845916945 172931525 66488687 181936194 521757333 763527313 135108629 132833407 731443018 695495944 275795014 502241756 930711463 22216750 476593507 782596435 250584384 243231548 491913881 360650137 912499158 481477510 277165519 108375913 70745121 525014102 546785083 153306693 243429266 413031828 934035079 195429039 876170759 268152728 397836467 89277866 388582253 887745884 891883920 393931182 589514665 408117681 905384203 279141841 676792829 550511001 775933814 921413484 689973150 353052533 922820307 337026411 592111338 174742158 406140627 751489547 189634614 389661882 869340532 178904592 760703364 600254718 546829622 525626865 223936393 848530574 869280100 953636509 913621919 818424710 77862340 147447770 457914739 223043335 860948349 449492823 274334699 982620949 911412950 550897133 774214041 949546458 408935918 405175026 568204996 627780914 588666740 879869514 596778005 871976207 731662437 587768364 401734177 939836803 341326089 986419959 560669233 118117632 609497205 17916771 754829186 653622346 156110589 932048677 728801735 786920277 714630145 32938154 879503995 818055857 8967880 62368401 572837995 122791635 341693380 671292126 889049014 450739810 657292138 256106517 242470777 108703731 797576992 775615531 275179061 450272903 925973850 815905081 637503824 498045143 296857942 82289340 840794992 805307738 757427075 843442490 453817901 616756224 985977723 445619835 17104919 690481376 735945459 615117441 264505311 268889181 216844531 610357282 433272549 13796548 3053366 20966701 588134046 331647786 159912873 637396201 333137714 433376520 513308267 551869041 445126979 844431641 139094893 954131428 224935982 7583449 448149325 204404639 931309328 802168728 741430808 734765599 294566666 239690353 539961021 204263137 833287219 596792484 169201318 275732128 817600030 890857186 826768762 793144532 967841294 700973725 378032247 980527612 354571106 926668342 312666106 972366023 396529431 699393440 677468461 268721969 177716505 507242589 901805607 281807678 310441609 667011131 747631289 720203366 371054497 74152904 45314281 858976972 138215903 309281718 821437480 622849688 753243740 230327429 480597896 58386566 146285475 319640984 436336003 304872563 69933699 562764537 965929834 957978345 521326146 222175091 597332433 207459251 506069694 158229784 200546731 593512219 578705557 40033961 508577858 644648779 198001009 27161898 120036881 468825646 619826408 688682132 94216647 853450119 179969479 995888579 940078087 4280089 626459580 259094971 391661357 340429094 436684143 436244107 204533606 21966351 916452692 644707372 167357214 978944715 450505294 291727475 449421730 280108460 470759218 474053088 914484146 314922419 591549950 877199076 56580707 565257636 583444853 870221870 772368811 660519130 194587313 840840215 948895342 201514433 975915012 347531953 369633042 175468243 821233779 195337413 587360672 327484271 897594374 430625783 473304632 203297909 362782777 961824333 442499442 931817195 643619400 322804284 674370301 294519038 872232804 285886721 789950454 299610392 750770339 733788124 81530214 867497399 514502161 454418044 471178236 479105413 166023152 572916977 596489293 78363178 234123934 560278082 939728633 801502250 584096299 191469204 257602452 632146128 418829355 753912574 378387066 728485024 193294908 502559027 711255176 413754435 488132163 10744102 191823916 929315206 727046741 20864667 506878298 576910546 673663195 129299937 586935395 626341672 607105928 8422664 916794597 602654776 511164000 583145572 745672749 870439681 148178167 606651944 200016071 382741597 32477613 163206367 698410048 326404862 244245912 329723567 512578689 29835233 456558940 774026255 297839059 174107490 918874770 292511425 121133546 465606938 98319458 647506688 446610470 44288075 386207590 27498780 593566109 343892421 387540051 643012797 302899014 98798864 405982319 338783233 788883960 665507960 388083510 735999519 755283382 991591316 927602470 870951576 422445110 135994499 290279193 114865025 312147002 293010428 87984227 988598400 128710021 712462007 640059406 701255706 737471991 826199987 23871146 94529693 302591346 488203902 511509071 623693436 859213968 569818149 58224512 571524819 631148201 433814149 751648100 882897373 664666767 93006994 353597338 276966030 764784863 213263430 504867650 774970812 546116456 723844900 378139400 521044736 452401197 74698676 182122973 853443411 692582460 441582714 393189465 38024238 560249397 37861796 955815391 441141799 475104222 390031727 274210464 711261718 496796958 226491304 606807887 931637420 728060619 304185456 891258802 474073811 384083242 880278008 516263574 313354381 8620984 237155856 902156591 670207233 230893895 594106240 563652388 866854243 663135301 451941934 159848955 173614644 209245137 491236619 78571087 994207193 410575530 872065293 544226383 285675880 989369811 880203709 224374434 497274325 994336214 364086522 316974588 29174927 297197546 954577666 470936909 768162723 478837010 913912478 839546356 324253901 259879585 586636722 177059867 294047728 353614422 7796303 796131447 320623381 504989238 880174261 903866509 593197918 707232850 83893773 844924502 259253636 778349585 20284303 123824080 804323798 397764368 110730437 408050534 995661192 990548015 197347083 777091482 284467449 703620024 841311023 184203423 632440899 528178931 118994558 329107282 756083016 767988146 228772021 721417199 295565108 117991984 454284747 846372583 422495758 226380394 77834250 119172199 491744224 513931655 132156577 869612270 507014138 333903856 104040591 733470371 830901463 164117758 81430214 113640674 756386973 87614884 309795302 444450493 305149302 581142001 719571600 489634700 462168472 336496480 378727436 96022867 495141553 814437852 252155515 936225935 681286437 637869198 335813867 905879501 212359447 401251488 321275347 629526419 875537010 360994369 750268497 768784026 848766790 342981558 469933082 311110333 272932154 279798926 21257534 247504647 138682409 584391852 762584080 488963873 416115871 306778910 426795844 907367554 638752278 868057045 947504104 204403087 932353461 132791316 950903464 531323727 149980354 353839329 954436277 116222661 456336813 952651263 401759871 954711916 236599459 705678297 353313523 408163871 857231959 602764035 715737907 497847956 682483297 463889902 23906903 458242353 988213675 177475075 908706240 222310887 670418081 184948601 256081069 691874679 885136254 567448702 826400032 73883442 28046901 194398585 763963650 317986911 667284546 926677858 959115959 729003029 544348297 667134870 895496698 446261740 912101660 668214452 787285699 263696682 917276726 943701782 703352212 579114610 293545319 926778946 992004991 469938480 57772065 753306876 507622324 933874439 245725623 568568712 644180255 295674296 237361413 288240417 554694646 434691494 529009675 114712168 225196060 136148083 252092053 540472228 842611735 528925 664127124 726708818 348917411 367001439 721740819 950561539 133553964 650188555 470736845 680552082 885090382 190787482 493536638 342419617 309390954 914086005 511111110 976619322 878332016 600012132 733974427 445218699 704799619 818127816 602313198 393460732 472512935 839622398 320916638 93580442 227870025 134176012 224451007 433303099 727550019 653873693 231469522 430995729 222864491 24082943 213204859 94211517 30449158 43024448 991210075 854327099 976173795 406316477 995594996 416510121 372453753 626580785 472031051 895631626 165410369 227354848 9737376 503206514 623450035 720578397 46823101 587134845 483336108 287409432 896040958 506117365 376081387 427136940 351613833 914080212 364928040 271532181 412985202 355606089 616459244 242653646 154274612 220564120 9783818 60735699 516441138 23342771 271846086 696636818 9781128 383264890 407085545 339127815 662732303 923083763 793625922 41461563 707292129 968996434 835222534 949515106 235405062 215737314 951454496 212134359 246178782 264364866 941044240 507525076 572953131 27978802 529137996 433766686 297308469 537117888 147200849 242072386 754775237 279628584 209603013 608800196 193435685 35769 339875444 187814155 136364149 812731140 818895555 309714268 113113991 183121310 515943521 56587008 214728875 877416599 450963271 619275233 341804607 933185463 599535761 948866675 918657778 595960189 437175249 538066274 696889651 430750782 493994331 220957585 979795150 646453296 584893444 797493897 574546291 456616609 449100065 494072884 375363578 378030835 969313283 209509762 151406523 88899846 961799742 643468928 259394011 382610006 807296046 662155666 848287989 498496422 855486487 193070131 195715581 443710933 886255318 978105200 893766646 437499776 349001499 746832306 150291122 433599063 486788242 924453824 383571160 342640968 693512024 195141658 47324190 564641896 219668001 607134250 479937304 731727409 159023982 226550910 928238439 100408990 304719775 678034672 272679511 974532337 695253468 859870299 920604620 753067797 937260750 721437210 652598442 689406465 260304756 944082557 659251328 834574662 813402338 157903948 500725006 479928548 817403004 116397362 311582946 281971485 341201681 237454652 960827802 637059523 501321375 398760104 687661154 730335063 186591368 837229053 582142286 567348559 466244973 538909932 812991595 162013868 318077891 475513944 899631106 520541488 791043818 651339664 381010309 967456959 405394772 952718337 916927032 424150704 272017954 364389823 206974948 257965830 654280054 220750807 6878473 739718007 274883668 352895021 386967037 497290410 658424272 88460183 518164171 370423716 656163807 694548329 206120886 902633405 263852765 259344935 531208927 65371019 127317384 148399432 531580371 108269432 455764642 282782529 761819583 500104954 697189707 201833850 723620326 680186886 361793868 829628175 657782551 911172836 904103569 435049391 942896960 496122291 5878018 750923468 611783569 488779982 968135832 657515188 150070012 491486725 116632315 840163903 885912268 241326786 359745485 34253402 53683851 746229576 494472283 820125413 643472388 149002293 960384740 25226159 254151778 227298889 58964760 800092580 127923389 257697189 801428477 87191753 889751435 624997126 846624219 848142142 753725599 236087505 666040554 325062936 655360846 393241981 909590088 31670355 275110896 891849381 726832524 966857686 246482670 696799750 638806114 41266793 696838970 358451141 802547358 90905409 789595256 330141466 19414562 579143793 16138106 683522501 708881254 975466945 756575816 597698531 87820538 561226331 244234602 972520546 297336552 531935199 320385938 427633391 358451461 345879122 112523620 659111807 58952652 138460618 924109051 20919668 872207990 153151269 258551862 975396729 268718894 10218734 992558754 211821969 678405217 173342665 15529422 565007699 702120148 203665086 518927934 214264411 54802522 4957417 391101564 759011120 820758216 876278572 160952467 940835219 930168431 610321941 908874323 238755155 855357291 540667353 903002654 215048803 309332758 103510457 753243172 105362803 243033466 338773164 294903725 800656162 696382020 75363695 98787245 263232936 211622531 83250123 973016453 759066221 944749245 742324870 547426224 598522666 380451843 357176309 675614776 103191116 953161281 679305852 169177414 243355048 268121774 243040009 38731275 183860923 747112818 701157530 897365118 623026514 21149321 327971398 911867688 668336263 834460587 317356240 188146113 773708291 489874925 191368668 809465134 838589488 578552793 90288105 516400606 491901821 963506260 56761101 639115921 828572647 655141875 313211023 368784426 881831418 409648695 96901819 98619660 985376625 156576470 37331161 354675416 724043766 837750752 334436379 967925031 738661497 584114469 234539748 885658587 687426430 935904584 995167190 870667791 430380399 836925932 579261124 574503078 807538354 836790908 107266552 262504438 146942677 601060296 787647852 156170391 241921798 100369401 949587492 874583470 994584570 189959621 431223518 864025699 937313627 850636552 894980551 883185302 666006799 55254264 142262687 513671425 13378081 993300694 809886630 641985019 272699869 618297723 69134019 469609240 42746036 546953397 567670882 171062999 627063413 645573836 421611252 316926714 939777263 338905963 566086655 277003736 838732467 680398035 121737037 779548494 853364933 310382180 501620307 706860496 554741585 264573365 374983291 868222271 663849513 782490669 737796048 133161716 60775151 195423654 440282689 548115167 126307292 611246937 623524714 644338580 607009472 143941369 442160013 590147117 390864293 82472546 739479989 127747830 983879454 608609916 640580260 447327604 864093661 714850931 517443877 811153766 691194576 348722889 340118197 845434467 53561694 207646091 446766414 708180700 223490885 532032131 79560906 545656974 554320107 727039508 420173552 293328819 282571303 896918012 655532780 537620572 829747535 793538948 295124655 585642183 493097679 933875692 526990587 432865632 878008503 896519454 32421845 349825443 705858600 631057579 626259763 879098301 883619481 816621510 662353831 261598597 803011895 468887768 123215260 974959900 82025764 526072065 702060299 57971753 224396375 557299429 214831595 116206905 29193599 299229858 338923256 328629511 639310923 809398928 872414276 812492040 683081036 183776653 477819143 135995189 571432323 210581925 928579365 261556012 758174373 191707866 416987199 873932965 165981062 256287467 962921300 810308178 566995230 399597687 121620184 322514761 926407479 731011145 789516266 549016190 477565910 452325732 174749023 279983154 216404986 992855869 501180313 508533522 536184010 344328123 481719583 814638129 765345588 813693135 536187940 893239862 437231639 196489659 594475129 969688485 269535411 613083543 694504367 811066403 679576111 163717530 928326979 753199543 247023723 670712162 839227869 552673788 487723721 307862968 785318110 281976089 24347988 168977158 912923685 634581225 220867905 306112302 398957187 640438345 595197593 173662082 696824664 7811008 319541687 678932315 114130129 6884641 633005802 417555473 558335142 518947395 787527775 797616710 610384228 903987783 47279554 92914449 733304657 916779857 200710972 29887855 385729280 967137050 414412927 980249075 868461121 600834664 309672686 238097466 971667886 217363924 114185715 317317114 544480686 47596512 455635374 469546720 845441594 556183966 283035121 635443138 805479113 23619743 219725901 358134543 981710864 929656448 438310161 810054662 610287722 942564498 23505582 603383548 382713896 863837461 666517419 174773570 916663977 125487811 904685526 383671308 994467471 868199485 887352314 96979042 275163488 527920666 184386354 899643316 239153266 588559472 915058852 856259919 21051290 427440916 727553793 868315371 900857398 869787721 97507977 583816547 419048457 360875517 18954348 836825973 939573503 19125479 402386295 891776579 100590343 702986188 468813889 284245282 339331047 347694036 68729150 7316534 512883914 434181795 614633824 283422844 182145721 864830043 696504260 34278158 893414439 18699312 309335347 79986291 718690683 614957799 144970076 415393406 906129530 295117464 514427444 375225772 237421107 670703905 335614736 766642895 598974449 994553033 807596435 689332110 510402013 622998579 271611325 321513081 664328564 903017436 510650731 571342356 313629032 911917721 441562932 769148744 612634657 428924036 421208183 598217833 900200470 417947092 828940800 915538016 720142978 842297012 175859742 672245830 212054466 89412751 485243993 968453981 558090430 968702809 911598966 913630017 16513579 961981316 104269458 626185158 143622281 281178692 525273740 494763232 109139561 360736418 677406782 128558262 735458104 451470390 971842169 82505411 165100824 405393114 65853191 104184568 468515048 404272605 57027587 130947377 383661453 740772995 490393082 350118891 138432094 489776810 25644654 121321327 42643363 456480102 528511512 374615591 714132597 456310237 847609901 698126589 294101199 8517300 38507845 20577469 720951878 75684328 148918892 213694069 774490225 109451228 560717854 574502394 913647270 687859299 868480083 733337174 333127609 680986018 982268622 929558684 899028112 748938886 132072723 864941791 577410457 403407047 391227646 170064631 826573886 305129091 432258830 547142070 212641906 473431167 906988788 70474746 200561239 778119626 481516115 230136788 911295842 304177333 724654658 451684877 853874260 450411139 773245484 936974228 762628853 983654462 513725584 689295928 522814651 433653769 272121246 380236168 734938287 444935539 799695123 420530497 904587237 726357518 835231657 864302528 970914195 775760095 608372416 916193997 755695392 264632034 850460079 380054568 332500002 234646730 240369327 875956059 740478663 223227601 528949040 22447691 844233149 761977878 20575788 579143683 975900533 380437317 550330620 743318160 145940512 381247426 769964292 960309853 420576200 571316811 447171769 890718316 269890203 499238088 646220419 3314294 395575948 528695234 62258442 237819047 577984645 449691102 315671120 454734315 457855666 529796858 130903627 904213572 236193988 45125462 194265137 547689562 190596736 190900033 483669703 178246853 863170888 999142621 34857241 967817389 488812930 422579564 392502700 553098282 116904149 126186976 389530023 831187821 714909754 555499776 61849175 854591680 475483612 332706090 188977378 930176287 151264793 785899993 846872916 820220120 20633095 576731238 740411846 998987386 493647832 864646767 930252974 142796991 870781527 603411889 134086932 300316030 101029800 392171470 87872531 174709182 457382815 458136605 176534603 534680101 228245941 41412856 779415490 908695569 923982321 115650456 674050456 886810246 665808751 343495406 70910779 208264998 788372137 193672040 40774406 686670186 670469592 437472613 591852703 988304306 316264588 642180787 850680442 63173083 601032336 518081215 608964609 709954854 320942806 911378864 641193899 775211887 985545454 745915844 573278640 327805582 984615120 932728628 188656380 254973748 820493163 460021679 279665075 94470117 113868841 711462171 942010076 332339946 185905279 428386220 579161379 991234099 847688301 760937721 97456089 44863532 123051980 236029310 947787381 87490801 528661826 417360728 725007942 988365888 285771605 399461230 766934198 173490695 205625959 810259254 34157142 463190905 886610083 131898592 80803567 641547642 942711044 54514153 684065254 728038125 630366080 434386316 279982827 357185431 965840727 655961600 64792871 54406583 453877093 232436730 323369482 315017256 792609090 228568312 586951045 144313623 476446837 416256816 919146415 116664655 832361032 425001022 232369720 933365223 719174083 598231274 25631527 730576086 717207452 181732638 309195260 414254847 92655298 554925600 297662597 409573251 823187450 630845184 878834132 287573097 392281314 230846688 147713701 542276761 426402319 440623406 682123722 628154444 657801478 866897325 294769772 25862214 827975104 359829992 270641876 766425454 463054648 547556784 298538071 94495405 665598659 9898068 194211948 757295912 457861312 554130901 962896847 60979977 661248853 295553817 625597051 651310139 227044674 113416309 295879390 363777469 817516528 235626158 861376038 254518152 103054396 352688817 737725503 221051216 68292404 500649826 490300957 278234908 531480281 333909221 43508041 283315343 287995397 25987142 700518346 674712288 14298041 209096713 903745372 621995796 415586525 337479834 246498054 352354484 186337908 763171910 188175670 172079314 888882399 832450600 794396932 21882803 572588117 423771175 334247740 639459574 408745140 744193005 10376131 36265716 612668236 793362603 275796322 250335978 247414105 302299844 54508389 615963089 903124557 174247394 969242744 126995956 938175560 272655807 829451084 339780315 317536161 253834488 417547025 736956672 765998779 244604681 917058846 495354296 658651838 720939732 577945090 471976164 846494794 65108864 689011016 303481909 851171119 245479838 905351033 483156440 426597862 704015992 441507996 530738604 912990481 926995034 911950776 9531821 617813410 589029400 602752143 966317861 28307555 664733081 944783548 726444810 585013617 31107859 571568337 740094981 588889284 302119876 437340303 383913044 339143983 423528222 700304805 801801482 416557468 133295347 595350868 728073457 567451379 191954588 362243142 522534240 646794754 484935809 515022017 312498123 986158754 991561715 914056183 203006268 521395624 800962359 561857992 56216596 109428486 886010036 780051809 101233148 695889465 936023145 569372951 938887098 496804648 123237456 176977878 218657809 65959914 717219173 878079076 967876108 26388575 540721706 278484920 889551836 856385360 473407850 324263313 127212273 776343499 34795086 507814594 17393819 902296954 326346016 10022154 808594079 668611718 578104497 680218889 612483905 88566979 265975552 678404735 923759839 931355544 70904001 316721184 373654695 734110819 600488272 621452078 860605949 920055242 752347466 255689208 50312056 312073946 837216825 725934384 30738712 370529008 707283867 942248949 621829447 807554066 290949534 521062577 476438484 854665444 443857720 980723948 45385332 449455993 31334603 44437961 671301535 111122352 78311639 220727168 89331746 184750965 826133342 648011893 857119372 523905366 539404952 645116280 897397944 340090883 582343106 845864500 501500336 480038577 812298670 115550251 805074869 68932463 217269822 561207936 140324577 46394247 858177942 835510201 188643358 845816306 39619439 209714550 887258202 511198213 840068403 136773571 536559522 826859088 539959562 732094086 194184560 325735831 780716888 706544627 877477424 51820623 591046371 858155455 590017159 702160824 318936000 948888932 536559637 146150334 408073319 363978527 98124819 265677362 526428307 51522132 94275993 268693954 198239592 628839946 43911293 179127353 930887857 275698646 995510792 642524340 743504140 739766544 879537352 192290587 760506528 857287092 976660620 346920792 445562195 803667732 705389391 97755545 923522314 555707733 882391210 259631765 127036064 669231537 201423182 133527386 991184701 284280029 403005857 617001736 591780332 751575923 727099944 869933509 465581572 631776473 50249304 580317352 437491547 922666711 28382162 150819827 541675901 238973416 192750248 637162834 693023523 573200498 594278956 222091530 982764666 389858685 432135973 900277696 31929125 414165815 284252790 41033618 764679040 143056588 132195787 451778672 25198424 292510924 242861103 635619777 10033892 812542503 931647065 282825802 426279501 532297249 605545166 459201031 619896690 107450714 623500263 947568345 464528144 153288794 794946275 524063811 733939337 338690097 910959246 21044508 87135521 459886433 82746464 929535227 885452616 201797217 152382994 624979341 870820666 251060687 267010779 45108915 557034406 37692639 224147903 244571274 801342475 429031758 172816237 794453073 808556348 4292191 772047623 598688050 634383340 170786525 949261123 724140023 87818407 852742302 866588903 991894562 31866048 906193690 252694461 719015840 929941590 48403788 176915363 654217667 268357807 808588207 503047954 854061816 959229514 858517301 576354047 107991070 828721806 658531222 398328265 778081204 930582417 825386538 504522545 496888299 225295242 124775071 707974207 906103341 132406515 838369337 7916709 724894099 500736388 821005661 564281265 602356379 175503475 541990587 354843407 472324909 426019682 64231373 39837755 598181147 222302023 221888461 17910928 516800112 258322809 135388459 380940306 323960343 969466438 915992162 567487088 883196702 383895252 891023543 389141629 215201569 643265298 826281500 333639698 586422716 191590976 139904548 627307693 28733073 422710048 916673854 341671900 307718371 864127457 944984959 732556846 127630330 985116389 304858794 383947633 50293697 964727877 927103634 587686273 177226959 843072728 881353964 571084891 222415902 314590766 94284908 166257146 468301227 636712814 324663887 938323668 788619637 543207790 672997548 152993473 875982560 377308361 214212167 125912830 838550330 732420384 106170751 505492024 170259299 80844239 949750124 959303806 610554054 442105355 542349602 571082069 739820506 372628508 32927901 318608470 138339933 524701954 269076511 532679358 218316750 518025399 701052704 167004033 920353127 929183217 192737222 354174364 234444408 598293602 180979617 189178613 696770615 868280984 31856969 546678971 126459392 816140368 63685365 943722759 779941327 405364709 971838545 833673991 265805705 220053343 928129072 980424375 928848168 403749552 981347861 181286359 883318854 476559316 262443838 505494455 273282168 35846893 631633639 228333439 960797611 785723026 308181695 555424858 553546360 202361761 145854657 64834704 792976317 151041768 831225020 299045276 850154231 617966811 220271848 251228924 999081015 103160449 209397571 452590298 408097555 659309187 881140948 235234058 158808208 680044823 434971320 332450542 679963218 199781147 108042863 723661840 232634438 432270465 489390910 668043481 185461572 60929163 727791424 931675425 105786395 351655015 279201103 896769277 227801130 328593012 546270191 101924508 568606194 155944209 593664271 862991767 235485520 128842782 716934933 687920813 951925158 709451627 356918329 411351691 198624477 886380576 358154938 833941712 854754418 340008765 692398680 651892710 296463650 354708096 703984218 627081668 999800763 47786846 539677673 135414811 461545626 686133878 332078747 231040515 410525905 608373160 448436720 455920875 324556869 492759421 365940324 359098271 176971496 396246910 737853946 754151658 13316643 933889688 834199892 828052146 723003477 960174947 601744154 186178352 330470233 476016452 493607939 580986057 37052001 461711252 656523926 537849650 234927180 301829468 674952110 919655739 915216334 216299404 62359811 799415526 901017953 778066046 363756255 893332704 834222965 273265769 462835844 75747135 397529215 905492742 14105647 966673926 99368334 781329772 969461718 39391194 766279562 167272971 227721180 115228626 797619226 283702762 448075437 884200518 613140562 389840298 980842665 836504539 926360864 103849007 455055695 863457007 736826192 428288506 87854145 292349388 55295962 575866469 411633299 445453229 500277212 169196195 750249719 775076687 317385007 40350037 6986325 121796787 883104599 164950024 325591727 316311741 420389194 723239877 744066295 196448768 204747143 284262845 167364019 195525428 835126292 825947853 991742940 878625180 833619542 860384595 164937255 349563252 84823814 869246155 876256461 651807543 771478598 672677519 442166265 448951442 642884320 687828963 63109773 671333656 146563241 722520827 726917665 133901087 786460901 252778072 269993344 663719654 427837697 94860895 172509348 524327519 835024753 43377026 379221836 257107903 431942505 492665716 887707360 169259835 241487516 960407389 360368511 145701403 204031860 288970107 299791926 64682527 601864810 996207792 984734663 600826483 556984000 959072054 7729229 130827154 97654311 262976940 593330597 148262622 758574920 135200377 854151918 445571140 668623850 81709275 755823066 62332805 798116913 495936755 206675756 797851074 102514742 866243737 173205521 155417798 228895648 508159364 709999334 911769708 225517159 926189363 320378723 326963914 778716978 855490829 414989112 905618333 512483751 522912091 506084870 748565206 281191343 7281752 967453954 922587487 317399376 384132251 910575136 422733217 142305128 724089737 838192364 904731126 960117993 552566918 368979699 453928777 340136853 854947108 730322 495508980 398890199 125682366 700048169 816868797 289162595 566160642 958723443 73561743 321128609 303962459 632248890 338584778 796295513 449023700 750403750 538192914 581567297 746469368 396633192 307758216 867528820 102505460 958862308 581380673 587558730 958277569 192588699 442912154 3383258 865823765 484477915 629278334 917020427 481291757 22847039 471163402 865689952 648883321 532839119 406267003 747171714 719302989 560370502 929478487 89096078 869658516 606553762 362263456 711474840 129076717 917068881 175137706 31029158 831513439 513753559 48705633 618487785 104772683 801894556 937885805 825652791 902498051 901830268 545873398 384229265 344432776 394146367 937502724 100633933 857751431 188667866 496258751 530515105 380532545 110784324 669867535 554240004 326119752 520378126 902234499 937863933 628159946 10297161 270723491 498822033 731429883 770435720 990233691 403101704 994478665 722524493 806561744 621430883 308419729 717021193 826196512 193174792 416964461 160562019 358419988 848818768 835070639 139803209 995413505 888231866 390774334 242903582 12553505 741387116 555849644 253258193 434201515 17962658 475841821 65184659 401092689 717839409 717411022 91219661 706004623 468529547 402660352 615915652 60772655 514936186 898520077 39526641 543359419 175945135 9574111 470584875 265191436 44355978 222841879 654342984 145415705 859762352 71903137 996659883 2586923 682314831 139819203 744175826 193346755 841126814 190359597 135810725 651941335 924668444 484458035 25986771 350040152 42689134 499851853 523736793 23898025 716670229 500930494 358351269 914605209 784289037 797352863 449940412 802455052 520355619 456584663 840350689 380419642 377270545 614033256 145097409 354128130 659701431 430001592 858670139 538810641 328900976 387122159 810921279 271504559 52226578 830357659 199402965 791353188 10976158 368385586 392414211 848967216 805454811 549916584 872511569 431872076 799472520 719025272 35585403 606094338 682396815 442567388 266487473 630144749 113998840 855667078 460827140 576131694 371179685 827281388 976473550 120234178 983077425 143795912 551672424 691930784 867366809 83377811 497151276 796723396 859167420 826120812 587430708 788059146 994659688 64931435 267553853 541890462 284232286 953030630 386760435 197572101 823102001 268788057 392821595 675922533 44018722 13255387 331812353 662444932 305902932 167477812 845605963 922771240 800207786 883643764 290463209 329845834 123835001 705742474 967311696 495524834 710385152 376108338 84270985 323596869 426975509 729322962 332932935 810992114 798598422 712619371 619287190 256894035 303385140 44365388 182653914 285271912 212959795 222270539 153850092 253454702 420391870 235280438 758000850 476275817 548672719 939261244 675354075 113274740 358848499 613112614 316642606 700513721 120814764 692170430 576827732 23075188 366343165 456164383 819696096 604789854 3262380 870923084 756928330 363280148 713253940 347937441 808432465 117860566 309736288 23160392 557526208 761654291 978650009 140322956 672762089 223118529 225927787 565243002 477058946 762529021 48463879 822944903 507316085 263677981 650994321 377267593 955603215 621712789 360133238 388007616 508698870 613618058 648691098 844573475 413755797 845149423 962952295 217040212 569204488 152040387 259895644 884662710 837780990 954162594 604913549 508126510 403999492 36360028 627518330 942758190 350419055 124582059 6469546 250575332 763038171 733002139 3763963 562432044 385184224 2870265 539505425 132045620 730152152 550390885 207075961 436582522 126791104 831940920 199574128 298095627 204746171 611643793 372291332 579913573 793069097 413921487 378709429 360292808 779802870 651839924 308850218 151958306 447137301 297516348 906071729 449851496 196977221 567856760 762002723 127854141 661734909 926169653 509556398 448441704 351661314 699543121 962226292 842438526 933703607 414182229 351509119 173690245 294546980 942618521 42170642 776524125 38214304 549909427 440464422 842410857 770854278 584607358 311567264 301390125 483018211 387845684 314667229 565423979 724545326 256086428 893774471 611541607 826868343 482409599 208503661 765429203 464995604 142444790 325419202 802526284 282531253 163975337 774606628 165757600 734214393 141652053 181913604 14365407 989292589 104659959 161859628 616740407 22398857 78443284 233799505 412950175 754543951 496520016 339713074 444862280 432272362 249506155 122606599 486292303 72193382 386832073 869077534 303236788 980143168 375572961 193610199 808740777 302453106 409287139 25575281 791603374 852322900 532782325 666560557 248448038 996315942 486873829 357858914 878782474 982113492 675036111 945192387 766495415 697754945 598077959 206359936 711836213 89989719 253035608 925047629 344061660 991072423 802092622 494172623 560177383 525496412 413433456 354834068 821390483 60184214 458667235 156330822 821759040 557241900 86514547 355774201 989104196 939356707 849523551 522185051 741161745 865731187 800351880 591499996 407434732 243676949 347085540 605435803 307914019 191325377 872975606 688830178 298621269 273632222 626875764 345990105 912995791 543514376 429176853 96449876 859262260 176152728 864047492 775917083 385336581 315780955 165160351 962514009 315659299 765039563 160052358 549839791 722459915 153936514 121037882 456761172 930128467 251583703 114552156 267350135 327111027 150857162 974168321 112623855 451177785 844024289 508642137 783358830 806221069 868136518 617740507 724989426 467834511 274455470 309301062 875794495 136236482 618932377 962311077 687218184 168275484 610518283 13373928 236928869 526786897 552224518 569751449 131289408 939660243 330354525 219448697 752352081 764633394 880882697 23677200 631444945 435566620 361839700 554708096 439918810 58195706 45319995 360512568 711517850 466641765 804512512 715682580 679078467 784386982 980149386 87829884 993315971 570496335 82979225 752913499 24947642 100870377 406437139 749440103 93679163 237352455 858940771 112183839 606827795 787784966 719604672 124746614 863976727 588509192 556889026 205645766 977178806 735045730 935054727 367316548 629591457 790881103 173716097 137974586 824918053 564856871 596717285 117192863 589379 261828417 222913598 821097902 320393055 908492014 922135323 371820686 392192499 234796926 407606278 655192616 859195356 421795450 371336790 413296719 757789379 35801904 404301117 421849730 219449066 265924144 696070791 225077511 961208894 74554166 828531292 713966034 376053039 672879901 478010609 316500989 301540602 535661732 924602774 92629294 487143913 834389386 285920500 967961161 896191476 320611164 129991279 392206897 680180838 579071543 3765941 449460202 262474623 155298640 638939991 13308996 339864423 58461478 558507147 126108874 416277339 500192816 834752948 920847803 5211370 130313992 461147302 782510550 390633209 158180129 174444096 252662654 399986691 180774633 225759971 302170705 222189718 7586529 794361026 248021385 295156006 583747602 176823194 777161009 130001913 204628152 424660845 87104224 256080618 455829185 13794124 283019967 75759496 70187819 747474283 69119006 902290400 404764949 858058855 867127521 129465318 83482008 532468300 379362585 656286300 680636343 834345548 714050589 598761272 931674096 335592610 846369127 78236477 613613002 215481591 363773259 190269341 667591076 35536487 891097061 861419266 665968040 426865537 743611244 235914153 794406743 642737464 858614503 238050459 430457553 714635123 502794173 122804007 661195883 284215657 114015839 532722682 39664835 476312112 883950106 582264357 973330427 200285045 64534915 745288940 200674132 95765738 317127226 898383404 381318629 48688251 382999041 18248700 977634877 308943766 734107804 976665413 287779311 357337413 672297747 580471077 715545334 219627239 186595334 973034246 961009061 602826394 946927910 162799671 170101827 186676770 225391070 536833999 424787048 147216706 443721746 912850658 141290720 578042067 551302127 210671420 120363712 543535056 826456886 264980461 174989816 955740700 277146015 628758593 305686348 252910916 516046936 885750726 83308101 381339650 744173469 769279546 60364471 995413808 430150652 89889498 184057952 123094693 661120571 98072847 647377881 553460921 930152825 875924527 463504501 373831326 179799066 701503058 904920077 291918081 254831039 948088386 116781883 482835505 758432765 55396384 293443945 287322947 830519108 717201599 457552197 439010750 772542802 186355296 211774546 911507067 761658452 136972578 982508410 318919063 199990034 413893826 496988800 464071581 748298280 741725509 26459787 276117538 624892513 795321852 840971384 845780143 143540837 608001652 583729561 560718409 762594692 955440353 596453443 313588789 744565027 970789983 470859127 721399814 205101420 164319573 439803659 73858338 279619286 737891550 763973364 978324705 342916896 825869060 229883863 844414047 323706664 892841859 461998260 583648801 556941687 778754092 22545847 168628477 690222797 311224193 886618816 545051657 928189078 94808417 540671084 189712040 369462527 737389416 138664183 397240996 138762540 124118062 818166508 132928920 234479626 874300586 952056639 498636432 169078631 780963410 674739834 98794113 607111992 495295338 912351323 537505059 746114451 960788933 886313234 758206000 537612755 82950475 182564238 556530079 885727358 44727260 542051807 904379931 853042156 395112260 75354550 991853747 7397235 158490062 642071231 239640066 286039791 996361872 500380720 105364582 518124445 57575506 990933033 727919589 903586899 692709055 723074116 266396730 105209714 617031614 78601333 303396550 407820742 802901350 253807416 733995719 434043649 641957618 723492291 607603721 201606156 222749903 550922136 327144921 361204380 213973115 573190392 4879984 982297268 134719887 561895206 983385257 552214396 437685418 456485745 647501180 161862266 956882946 578984768 398863112 718413518 653188189 739671731 552561258 436846320 48525628 489833803 470327172 608150803 994376718 516841746 630684187 799271277 558433116 6415922 174957676 508978572 491645712 780994362 22361924 646952697 527534607 181065443 322271693 135409032 411316248 519571504 854238205 7812869 587141114 492603607 21568339 25555477 338899254 367216504 983338852 27927245 182310551 147666308 904744451 833781237 565749713 870741818 343210563 282439271 223492153 695816609 817133825 207357629 673199358 279581884 964382599 518820515 877675074 626025373 531858834 129397220 122655307 950300425 305108135 925296427 184004454 989218361 194700877 508404090 239521453 653627906 364834453 651394097 142026329 553079643 68475472 504257925 886988341 275627418 801436436 670863023 415002238 866879442 911498942 944785662 71693942 853596921 505807885 781789320 250442741 546262997 289689011 248267938 759826161 163490094 11810457 259167502 745216383 95575186 660595941 649820611 921182276 448602226 451354618 339748584 336790917 987279469 122955002 557578678 482475826 219013922 200028125 825674336 652609146 178818885 315895241 208836597 287127834 367651477 449000195 678521569 177518156 468515294 382356793 672935144 758425121 474601014 757946803 802072323 837852618 396340891 567431147 43199590 616187029 548732091 250298735 106957428 180248864 92401203 686586964 694046789 10360059 681950643 279526297 711165691 8557913 30683918 852048623 713283738 892501630 552999340 986532593 150472386 316193050 303711152 579589093 803751709 605565269 156872651 275099146 816560908 716613458 640345333 520835970 100869826 714960673 744564480 985632825 629238701 414361032 89498364 851349405 905325030 804961170 954389825 84082042 52200340 380045323 951185996 913726637 650050474 143726618 648548848 641776559 106144350 976181388 879888708 428521651 252311264 515022353 40114236 505687880 428702818 281682543 747461244 537206959 831046448 312917923 815163524 650244489 848502831 824418655 921667056 681772599 295393319 607651133 373493429 126657190 659245537 194965438 563366476 128861106 926064474 684728950 699560681 874895552 331877136 133564591 738086138 490556297 503481965 895991413 999438576 235036566 311331920 259052785 985790674 624836254 282612019 770711601 233125939 821986533 452609566 600226085 508661532 376246018 883145814 1163540 989169286 119126505 880168950 878349620 731119 665781663 111375342 470690452 712241446 198118181 44667244 435333571 20915065 364850225 303377821 957242129 911528380 387054201 934390817 470146710 993496731 304374411 538166135 623353829 921633587 480717743 615403399 167530128 69458295 201180706 655645569 485588969 944827457 169861812 538785471 701613828 106896874 360127452 305575290 570432268 244295890 400696048 234405513 526820487 77324920 327798999 524472744 660364148 540130988 725572543 772693905 119979499 158002108 401059644 765569791 242017042 3493964 355212486 622105948 869168066 708383310 743848908 787391372 337616504 502161053 274653490 110870348 622142954 756696965 265489374 272463308 10747068 833507854 84584768 627835565 935005058 145608747 199471937 943399260 487541065 612904132 765559015 135725642 920697401 815456604 198039203 609679394 274606689 462948199 563906816 595961577 657316480 112042981 335990143 354380124 350340461 983576167 245795417 763142710 311022636 54979716 197128220 520771640 992053838 527855841 886456341 376053092 315609141 384777862 825833695 643810823 80376686 605107635 152893704 225992407 72791077 987445848 650020951 36286719 945867293 774028041 441369211 62751815 707497708 424372499 416833601 601958951 886312534 424789628 34529905 65036140 12269801 512445249 567576741 996981426 811035953 845171000 886007423 959120089 618553810 755275324 546593611 460507938 872289017 503800643 224124209 141577857 651766423 578621582 245838182 592735283 153573844 956068125 690018510 261238584 643390976 43818850 582949120 443535978 4241753 762187909 653882902 877274046 248982201 15323658 222992851 612786559 549478042 804669275 625974643 700115125 799331830 663743953 841488089 634870531 342350821 112691039 373006395 764265988 57149027 981740053 121863657 585356995 984863963 669357253 821705845 218372358 148248905 406737183 208039304 797490704 45667560 13727148 466951353 769411025 496943547 208714893 919129979 871716907 106653283 136504795 348857257 367049605 678129872 334210151 358212023 607272178 759863341 409887764 346390023 210700013 35130981 548117918 827296759 236699660 338880239 540030166 636042128 448184405 215723278 511418548 150878593 240255820 806556704 568882269 441031073 734980833 873081139 198697558 786403277 945499042 121399349 303597534 939738434 686928691 657632663 638130231 382035571 691108011 417796485 217255493 866680349 597251458 180852970 39752703 487435258 500509835 576471235 757562504 721569398 234125395 371335339 713213570 544941722 156905593 265469691 830574836 14982148 519238518 104746829 400167625 364375693 876012413 917583263 830485204 395052646 442954802 964243731 163711593 486706253 798074248 97892242 111511186 227344816 552809389 835577020 823616589 437690525 509944875 858400005 307751095 18894238 51708724 75494483 766549632 782821614 727391632 57540717 862993635 676679655 435889326 850886099 459621152 379096672 158860444 999737885 125449012 760161816 596609419 679721350 539576369 652094851 624518296 286011328 108039912 63405772 663955097 159964899 653503012 24721729 269459669 910504500 489282610 432635099 448361628 82244975 35201981 925967773 849068883 120651631 389273100 713589043 843416423 649668237 499596753 264209874 207784366 753945981 638694163 18862804 448796689 652254376 317259450 477208421 613471345 760387043 550186045 582912680 45910300 408729438 128419431 26922024 45179996 368271898 933668650 564391229 205681536 468390247 843047294 509575519 791492466 270570953 990799376 196655241 138883376 919018327 426238207 461723552 833205781 10944102 442856007 915437403 462999282 311890487 446928962 803858877 885224441 710436810 103495346 518897423 29441077 303691848 27862392 215285178 783962023 670454006 267227340 750481015 686918847 31876356 135322025 843919769 267505139 787690429 440237283 845615674 151976134 94244904 267278483 494947749 742258937 54100523 734118465 221547613 956568941 235498300 258904936 252633578 955970407 548654298 395140113 457030599 988562847 652737703 13726162 56477092 179644059 538057173 599048013 335484892 512545902 743573941 565830056 166869521 40337323 18271701 198103850 850097575 604308773 639534338 872783400 431393263 352002035 968637994 496828315 78293570 49109399 14923417 17090573 687783591 86010732 174071380 509178206 708504816 347751637 283574983 183628880 596993775 113458032 886698916 923662318 183605331 87364202 871574169 305037700 370021459 277180226 865405534 601566927 954760531 18417278 578602058 997841244 691787046 192873909 286232089 38930247 478196632 440838460 864799478 226905418 245675383 430357696 489166865 225183527 369369060 358979610 12653724 365302745 444514562 645436355 412863409 150460489 619445296 432949373 265505217 858750238 121333830 4857902 86039079 683073929 337417964 223740739 119703387 514624210 629700222 738504036 632873332 927557468 509278601 703858570 81274399 480391751 238359747 192413010 605689112 854963571 15233707 756995312 602185849 578491457 543059293 890520159 903915567 419968403 852789483 850339647 337493648 86751429 20972739 182533190 890600376 24057098 333106709 920420402 901126750 384241044 448291729 856855178 840774091 462699527 216276857 640533552 970579012 440719772 45866355 775291118 384145203 379402366 643327904 292080693 825855993 474206744 396808621 787463461 121583966 950461313 468817852 678963070 120722762 652546136 137825128 448933657 511135472 298997776 266152818 839459510 529566079 969363287 584114358 288691742 205322787 132812741 441445999 513223857 292854736 168257896 76168393 545019763 886456913 24609990 52859608 993168859 927710300 943644452 247162839 629208866 51787889 139985964 856085111 376791316 916752418 861749246 312173638 388736461 258995267 406624566 668395866 437589891 922074947 675790566 559304544 352171257 768819175 867622437 558936186 476714557 321935233 961188245 480950516 238682901 9028007 94252621 151474599 728102604 254786924 496193856 836652218 321472532 119737313 447766866 378016166 478111735 585608869 359727757 551890126 731028853 380893029 664305145 592440994 876912075 701315990 752684312 260047747 450972104 331712158 907556905 92185460 492223444 119427996 684756124 323407244 381591623 960910957 167737812 675222157 72212833 385920648 310404595 94508316 628254902 136996765 717683867 611219225 107926435 434547373 421109911 568239130 948943270 790454826 943098740 493016993 19310593 789437816 661389990 395091981 790909693 84295963 155790538 738577402 448601827 271123372 561982298 141927594 316754916 267852461 451692423 595271456 329106921 444998542 814895608 724547514 35105568 125057491 731373518 406751344 58188943 807565233 376655356 790701865 994360719 496317282 561956473 47444589 372920093 279821066 292712893 529866412 110882197 989800777 519589875 30120971 345046424 167589970 312624707 819197249 22187091 275133784 763276788 5964970 128249794 249028290 288596953 493007930 579159551 876690424 353311774 724265121 853310598 665175253 361766327 314185535 919437534 538446695 624415093 945426890 121073044 837604190 849710475 923612915 487952517 156593274 966768930 759570312 898276428 106584942 62463535 839315718 344729678 63523674 672911064 972182395 32701193 176620616 468837850 963530035 443008728 775423603 766468827 690839867 309716738 97178209 167863269 882547248 861340377 744508363 928264764 165499644 573983133 128787339 825036195 673596398 137361155 426498678 497674256 750904831 760749840 774679178 301861220 156429860 450244136 967191182 136845614 468337195 83505442 600287774 586252396 92501058 148380577 658790283 914977602 920900543 636725784 365026497 85132558 99247365 16869948 522417964 652182973 767527619 926153784 255816630 596125242 469316243 419588442 696536570 78516413 349499071 746122182 892192530 577472297 4978613 864710285 433779279 715789526 107341918 873214892 342139370 557519039 384834747 834766532 612372987 767743765 341123356 561406789 894684661 67946271 207507088 670347045 954704734 727745333 359689934 400754938 989269751 311278188 922990060 932120338 667178613 947916282 161410862 711649191 494456614 322612295 429828205 488496117 495031331 601396514 314509822 344805152 529591749 186217887 746240826 853390181 701086757 127799336 842884867 682673103 101369752 170896118 492855709 535192970 896454041 447957625 121270066 577738797 303610790 116177957 465282562 669780051 493473051 690342086 863501334 439880298 691231459 204422703 973951686 241233478 81342694 146423246 433262266 220584762 426692349 915307927 558749421 45503255 75458906 591748797 641885895 527554835 207145941 486551693 298956278 738278353 146405157 209531805 658509149 167491713 306484316 171265182 509605492 97278535 379194792 224371483 599462405 14435467 756158323 53607793 864603703 922914984 703155477 825098169 280050715 843127015 782553140 855444936 466541649 98746441 664879512 725451933 493710374 270524415 431063817 741920850 831423069 447378373 576094938 767167666 887702545 870792957 943424904 871286710 269830084 52840110 775710223 304081535 943191890 813846405 424828826 486852128 596913974 69942184 11382847 432984217 552041202 105091317 276944203 406670698 89166851 925530483 329477451 843615252 552026955 116722585 53701802 874752830 790739116 154909996 692946395 661791211 893425322 261844568 61680206 23495466 607269174 758457760 332142225 17119208 329046346 207371899 684441038 57535148 201825675 534101009 298949914 18615339 645656512 265859031 302475325 448013815 336825178 260105364 67806529 989502038 655092213 494041640 378074841 458331262 161892380 80094637 258268801 167289515 407486038 228957805 774194040 256361031 715872239 478601068 654851684 773482157 528904924 76325919 637774981 996709318 378526555 492508901 244522968 90213355 316580095 339054494 174310264 679355484 537309211 62043516 959853653 263951206 706017317 578179047 83296971 993341914 2741701 294628850 489240347 53540975 416748138 345212698 677444436 918247402 641022961 306311111 384460077 825547341 287379152 956053526 907238308 937071687 645088077 890928514 440439026 937166442 292004825 454238194 343443291 406381779 524776414 671545961 949967578 572400227 782626544 439979548 853934252 403187032 535705319 69752520 668880982 331649361 820438687 738859802 17740155 505838842 199835190 994246394 866980840 604781341 938820194 731811763 538369712 8228172 645371307 419969288 914220032 98088456 922764503 238768875 421383201 5708038 41631398 675460963 913782192 741485586 664162080 908618717 65580707 772328177 41997577 342514381 20872566 846192172 761687054 228376005 446591601 197316205 179684255 621830416 990234551 170144213 78117088 741345466 316663958 645663682 831795002 533221262 192323307 854019640 490648130 366870258 493906910 372666703 368261930 170557925 127953584 218070677 381534879 793996251 234786803 437669972 856505832 267188083 422135462 973564519 619208083 332905371 956025640 252528014 363098822 147886070 187912611 688089325 473978868 513995019 476600697 892584741 621194722 57443773 13115110 633423687 426587509 647147730 286112850 609584211 11179620 841232424 390070058 506399683 589509257 431369796 528551250 991599593 90744159 947217428 607944988 93381378 100036002 251806546 436526994 131188877 720938796 508459478 724242717 799729220 828112197 870510154 228763305 981054278 469742999 889793448 85997251 627901053 871296942 713316119 250694723 387062237 72366675 40036769 773232814 288755756 651988839 1419009 343271333 278930551 550739334 892987510 965357811 159660323 585028766 56440347 94120850 194238859 92578968 91192886 29097670 924557152 182601894 305109114 367068449 627570966 170773550 732065191 779207974 223937219 348211524 21382586 118805616 72529347 729251732 964403303 77797278 82608294 459907203 446578516 401077224 824902387 645866045 980461338 874310774 749201344 813599291 461946720 391017747 933421125 154196991 669769186 138833647 68737857 185959706 121875086 598632150 718503291 661040501 898744861 322095956 824837370 847186451 883046389 571792774 417811885 936237886 973584179 322285857 384673552 906627114 683025701 982394840 367365433 192374772 632988021 478812914 625971239 777096925 295730841 348280949 467178358 729277541 338032926 139112667 792813096 449498024 57463656 503892466 406471196 729450884 132688814 594977388 2780584 463361013 489037934 568219377 836603872 365082468 261182030 768657871 936634069 721908529 702532868 987639035 588366408 774332214 16392867 283909614 196673127 562885492 77666033 81892779 792589354 174209587 983665976 904655538 106783174 828831230 874439741 650582683 830962382 850733986 7814630 721557292 631581743 294213123 762886700 165132434 877924041 356110984 695666528 119278663 558281098 43110331 67637195 613133331 419531805 681518974 569920254 406512642 186670236 123269869 248537784 936657316 34399048 222266460 900829187 625295234 854829383 318483686 103654296 198500017 891673122 885711093 885140677 169599722 485880728 908583939 802925315 853977830 913303966 30406722 888908274 344913037 152463110 837586002 669089589 516601599 403498544 433410834 389636508 637671688 769888236 638374404 478722546 815154371 288612720 272742690 653009739 723959415 926818664 350553075 904756908 608463200 211185672 848490370 496728385 349444435 85949044 508093005 644797556 916795096 828528361 272183020 465317782 25882005 877922230 905925939 391445565 932437602 666966937 586600016 660544991 330360128 324501696 633305302 157712294 906060543 801697575 775641027 810660504 959809575 645114284 911874570 961517716 35769476 463137611 906117797 505386026 674454663 718914777 34062022 518065496 967423040 288546041 711486698 815557499 390162716 855079477 145554203 710099589 667937178 141617875 145609261 831770625 210084003 978450418 401522132 620453621 893836787 270893002 36456132 67950722 988891446 659923128 669723311 397346560 208577220 276301421 812457019 991788312 723856754 447542085 80568741 740060455 666146256 510846068 921270936 590606679 506232821 682089573 517783410 138677237 128741696 422414585 109627065 69041691 7134936 834146133 686967435 274518874 312629869 27565057 933500261 259593792 55307890 855643158 79336380 943017375 322620361 696561215 11689001 617477117 590592378 971020477 304340826 466747053 889527752 621000273 304624505 290847396 371607231 936615571 389387428 506656891 240633997 65298928 574158490 129469318 338903064 849949015 471129891 405501656 76751845 909512471 932790052 699545112 440251680 135921070 793169315 958822143 819298575 834242821 579461418 487109413 488728997 874472134 193469518 847223474 32970911 985086181 114452861 255976438 669405886 932421239 233478328 116263774 79908978 211031672 217743652 607015036 635037683 57199511 862614566 408521936 332503233 444448654 107127661 315022679 107292509 658217468 260008549 643017293 964890876 383475250 310068036 192047319 517719752 926299053 543377560 244097673 397937220 702803323 616003492 962738266 439431672 153884624 967799316 588732988 837458662 766410232 327619240 87729420 57007216 404054770 487896974 226035112 499926176 849827431 853941056 659422326 430327552 478700962 212137309 28738589 782325275 16393391 725304746 643024300 128301885 113114480 17606769 603293938 875381458 225032349 551111796 397571898 726723252 635506922 752637756 845446658 430802102 378970631 448685540 356889840 407357301 608240963 549160466 578973922 584248222 778755447 811297556 531232023 68087369 284123196 748721920 635669531 290787862 224895578 44208590 921985489 520220609 246800116 705792182 789487946 341412313 391267667 335744393 506784779 438881638 413504317 993215866 101697185 536417359 590057721 867900429 70668317 285335537 659373876 777796581 549511165 596814756 65641024 324073437 777757289 479204615 941031717 268604360 899198057 907507094 390988718 922912018 675226157 17581006 491480613 360111681 78659226 257275379 224468290 636141944 445326076 991478292 973527973 862599820 418757640 904108851 164282621 246153287 979537343 706634191 324157057 481605653 159615241 140382272 58147510 307068102 484406741 512480925 841128926 770255883 597534653 386972402 747811119 800507956 6913236 480905017 36443797 588878200 717595355 17318948 131119132 552776145 364617457 729193753 828182663 37511112 574720841 232862210 127865134 604107385 239808039 61550376 364091208 92602928 481141075 968667367 935287598 91066077 488907297 675914221 120673220 317807507 162270710 48268672 183712225 168423450 325736941 90564322 522614740 692485665 179723020 537724655 918703426 451130124 32493812 735071698 285072509 761427517 124072343 784103137 640103081 181957280 484178368 125257340 867689416 106415622 263463738 306568799 500293451 94371795 96257720 653420687 793517315 528242665 381257341 887236990 92715794 243560222 132675572 530423421 619797485 292551423 142202651 856051217 429739682 218172548 941660942 247498847 304878378 977650749 563015442 257419881 285300814 382824638 867987375 260532785 731762661 156692050 320670869 790629372 384612809 852533156 672598145 288802736 908698935 391527246 967975246 512780190 613337296 606047893 289664199 566048867 755500062 45449387 700576248 879346262 917775855 627494235 876098317 574989911 805632427 104077401 423539987 481975732 944263545 58848091 248274165 746550300 675146299 639235236 548979762 566948960 646747156 546916311 602531762 809893887 591819767 307683362 276422706 342299895 457705927 212615532 893137164 263139560 919325767 434640371 636734245 241189127 751071668 827495952 242464635 605790595 415552112 325019033 695860004 223091792 211482536 395736145 810437161 242845448 92068521 969059375 406938318 914764362 386531721 956552030 809674998 911640382 579026797 759117783 798930927 600668144 615219263 803772375 835112203 302678752 900826824 325088430 954967787 210452376 169537072 62918568 186788481 651838995 489732110 903785940 958799740 223560192 816963297 170684450 342172224 699682510 887519069 273024039 39433249 803479026 524288948 457647329 754383327 134927823 1042651 899394785 659236066 501307343 458321558 272306004 444906916 89542312 842650991 477424550 456456935 993202017 11997249 466301058 140350926 722707799 24754928 98568287 380926207 349792128 999694881 364736114 68452583 711562676 940874607 932556915 854072067 671735054 987077635 210136196 11845159 167101636 360356144 674656529 553981181 194228555 781440794 148000348 544853448 983835839 567028569 300732828 788894781 453064409 849810652 927020538 698306466 537476745 121765506 918848568 313044041 625726584 102524226 572066149 266134221 23926895 307944303 902036627 438981374 901155317 624552705 735915248 73120766 379421100 617846394 242577482 85684498 39168323 843967319 750044139 497364020 333329090 205666559 2651704 388856616 697649289 994481551 172161776 985000125 735115948 13605385 356853457 660899208 533009894 6182935 716027367 821020363 931345983 255147835 433832542 842260578 324646705 323724131 842268948 383686948 618857758 983190726 467917414 632694374 684651001 382505195 84300756 531157948 780325250 876516130 381264711 781688740 746719560 629920424 581001500 906719428 234294260 486078923 254704301 377991047 146273594 236098608 518032876 162245656 915852717 535118067 919629809 611801866 99718704 114169581 543621820 519999459 358174548 746393544 936674128 936191679 757841603 519243469 598838001 305725540 43978700 791539555 942639875 586984904 560394130 742131266 728140564 152245781 471250833 174974820 486001067 208206653 623095772 692481670 701340186 250555598 323169950 857913 130653183 897896184 176359769 639360197 37132795 4118764 624728569 627359433 526945744 189907832 262513367 172032385 14545480 379367313 797809791 561884318 305809110 824741523 463852283 424969027 348281268 737999731 722072473 114677354 798236153 308313080 825983134 576172289 769620317 878071868 678582860 706445378 509020731 237076731 545301678 829148681 763502926 35543398 468165395 609075794 518889030 391725729 180200056 566632144 339872629 385701425 551500633 171671246 999541883 971521523 901864019 554234204 386354852 249194124 903029277 645507206 699048152 97896266 734721634 441714333 120113004 742895165 427240246 351891078 993502355 205516455 319699516 212107987 149248670 949233580 821338907 851875382 364397095 249714905 43362042 357881882 702833632 658331412 368811602 325077715 965344641 629105092 477892089 988746904 513991670 369860790 834448383 356149153 581357543 716845538 536309847 707277746 744483591 484967012 55792468 665647379 159928323 581285371 294995549 739801665 820072247 559747121 76864874 140088693 328064254 646598650 755635430 601425483 354071221 99411784 38882209 285660870 973163293 576832709 965830066 192499350 221237802 70671726 832699300 612748585 165954816 64753923 489235655 877360241 189631476 551839452 940307307 611059783 363282726 729237900 352846893 691517253 798234785 699582429 495437787 958461142 576867986 481862482 621401083 229576386 332725406 785460071 156010518 162162468 252396287 588312861 525331864 170306603 481757241 611690399 482109378 543167229 290540225 93466116 810929944 684147263 119642502 923914487 904806967 121337403 581097925 480164421 224654720 343705613 652614063 807268490 155322716 241595940 789862857 62903789 69777077 286041924 284699688 563380622 821565581 365088146 351533713 905654544 538368419 521534854 373650999 107911076 98077276 740754774 708052181 159923518 781055837 381157210 232005861 481544255 392855254 513628589 614642562 959262104 109898146 460292207 28106864 233791169 947957896 749870611 244363729 89778218 823399235 395567660 648263513 14788989 257169338 424880982 525846229 203844809 248635964 202378449 171463499 903532341 886707628 170142315 629391014 968188213 700581343 660315782 265273981 921671103 325737624 655557164 812968302 516033703 556694452 732478062 124384351 500424364 518121850 459313278 951121671 221773311 786216342 57648119 404076311 307895855 972481403 791270526 467277792 539269874 748702149 889506528 686575394 906873536 689126470 243762294 826842826 594520185 735029080 835156650 237870711 629213624 734848219 120554810 954603582 624224117 35276436 957080793 240454442 350845254 43767953 457973299 330295501 165465349 64453533 820588100 124462585 781625704 531461099 426729044 518406814 575091456 558399756 920317691 822857290 318901310 243407567 410389354 695882117 490181999 269282664 52659210 682416627 788286586 516788795 185681260 848407938 276644540 9168812 488245922 400795573 477105513 872109700 865834380 769548523 733344639 634695848 393021315 55968903 927587282 414572775 515331153 367347956 97389731 193115218 701142685 361166839 554500864 584609637 431849738 387895408 33816464 597798054 638370116 811872861 849019900 864343085 527381455 58297505 968004729 179265773 373837245 354186118 763200233 618283964 765151818 994504272 482277366 83451330 782371836 855594735 859552029 330057873 135060606 847522447 809124204 866967641 149331859 925510261 984185765 614562091 883310738 461856889 199208002 870476603 124864199 433990179 860139856 860990658 637999772 373997359 481014470 411992194 963092521 926647689 559189467 903276453 204039383 211678744 625979918 498379775 764198734 643507371 916343801 550861130 860464725 511989409 655204918 355473752 812148866 704958135 386203691 939396568 809860228 911326773 422231504 167753053 970740879 686424309 360328806 416762010 203744919 546759646 238547489 886764705 747890284 442282482 298729786 354160418 217747383 565286425 734053365 320285909 523437224 112419065 243925273 607383655 305712537 92819603 563613166 870807160 701624064 36509818 794848473 651696667 401973706 927322110 805545797 723756765 387698075 462593374 97250788 342297672 171590306 406325782 781023725 817173760 606095683 581715056 804710490 530973892 246551680 510373071 111093353 892886514 82044344 625137065 387909616 70362825 25664516 656196140 961786452 496759913 759656859 932550902 498629479 704574955 928855967 402930190 704504171 78739999 574841346 102333130 490991385 374036471 423758003 244283677 290746496 386741615 133246514 713544359 784023284 540087965 707003463 920139260 670469952 714718859 978800366 70915257 787615337 576072549 596008252 326209884 133968932 212183284 86770496 854140373 149634706 538941862 39328123 689967554 76819917 953018043 86694843 448593872 495331621 103660269 493007031 318144442 695690786 111827049 519180601 147746322 458189829 715996998 658368095 907976441 711666390 494977818 477685607 299432704 519106940 924692868 227250858 978541857 559856258 95271164 396230673 707534081 106504040 591415387 944175683 841521119 443158066 667119093 830193701 536648012 298580681 708987009 293391170 700365726 393834856 627762767 735635220 23038624 1834135 376468590 274608632 251898234 99701016 664302297 589158331 662495808 402979209 791886021 567143803 509079845 976808089 283034267 678813468 881273495 213319015 336103487 684652790 998005379 603586711 249168773 742204826 360401968 87673765 825226017 83675512 151233074 386284274 571969918 273230096 16957944 810615719 936725986 823645075 528715538 295437745 323559268 618909571 142170011 553900385 208413613 722369860 967212302 344322624 105849913 822267001 152825552 283706295 95307310 194767552 767808998 705651834 841172534 855661520 92797422 606731459 766686905 22957297 287906766 802224680 674605644 562902247 340360126 254523544 504618678 845718104 265909528 792454928 808558025 115643326 947131400 953192029 128590337 601170716 908673878 277701608 812670187 891889051 572017138 830830085 659694240 968757051 669680794 818231754 8647899 267726467 238889534 396719339 439875701 500415640 78298486 410597933 303417978 533674783 64154155 636904168 193830423 936976704 546231263 11599063 866449123 831624543 449263823 807837921 745199307 179101603 787617231 619527246 706226 899117198 542277545 474586553 156575 710529720 339906215 677889602 77029777 271676580 832257631 638981188 131735793 383241330 327895902 966901269 829457121 782098383 15048213 128303601 998249986 200988024 305361674 675290522 653144669 566461342 722239006 638363289 973733221 561010447 486687842 470898094 289661696 502265899 962006959 724111749 104124122 219880075 941565949 542902333 302884406 296120372 109662313 287275424 914733255 85474531 127403141 82441261 910263104 336253084 49006179 40809568 742489 701905092 302337496 543877652 847278602 232223768 975797318 733683753 108892163 374790891 652668733 289400656 325971247 629928729 418243180 861374335 805061047 310390439 694062343 643734891 605592503 620479342 357512312 782945039 354691666 127812312 617635532 345999898 344053625 176754271 927881719 47430200 592870745 82148888 471908457 552771403 826990395 299129550 851814661 665779791 483108294 861669562 17233994 438667976 506132729 459764335 582681259 646454096 785918240 683595162 529764919 524233092 475194078 912227731 286305100 707684865 638770756 495575778 592765502 953004004 303149993 728755844 947905644 621598721 694992824 820178881 445971607 196852028 110032222 130014737 564224693 429977623 739161257 579484620 498317688 571843101 567026141 442764542 161157484 285109604 808061019 548926534 451815279 279705923 566405447 875233669 632595931 336824168 683373125 237217788 8884431 458911206 989971518 213779787 647558414 432947804 3609605 614108310 641625783 416106991 690502127 405249698 608370149 710984127 706568675 338656991 641206301 817612548 221784900 409077239 995943489 175071019 301477165 624371279 326765641 56831632 295900528 597983847 139340324 104272189 742243713 717774609 908525122 338390694 1810312 982256005 630423822 898249630 404546536 673320058 917851078 264893274 913184339 814472364 804698392 37003999 331304520 975932614 201987445 827721637 939809838 294919465 585312163 930662320 173740948 899711160 344346698 253673218 545271428 6110532 151715921 203133795 104046824 600191572 348240979 445695759 511446446 17401759 52239865 489390576 118379794 489027764 203110549 731215398 873711694 283724177 989860970 951598913 798465067 248353740 793421780 912270247 802034841 432703093 235041030 473556842 484390036 937103632 576428905 69301474 127649636 912355604 631744519 598711261 146798604 301806895 495379660 810242648 377597874 474881168 302768456 264617879 297330082 101894658 921944785 927961069 711535340 101565583 253398823 326407227 256331820 446529921 714654341 847415925 85553633 726547153 219674364 446404893 398893961 621683271 701520061 444551403 186343644 948693071 934989453 149917833 291374201 638287222 764552878 539874566 440250848 991564038 512692586 560894683 957978919 873865859 282570370 279650847 881763457 945709060 507438468 200609982 975289683 162252506 792732081 166340874 288214536 269700450 920273628 693176803 987170178 371593481 253198165 894587949 832934880 258471141 276970908 537328969 914200141 500844738 151905661 76094647 113519547 311745391 434220352 32068516 293359839 509260735 681302589 771660834 869050929 308808019 928181444 972494371 483912101 334866924 183261506 848048195 607784790 310831865 314266044 48872276 734750096 33640581 916753710 677495732 149271186 552892496 764095245 558805566 527840616 995500035 20254488 189948445 126766037 481500198 919033641 848909343 34260212 837738233 439840733 321307658 781993662 107157211 476461155 501265637 627516663 65952961 615477024 981811462 387912909 251325338 584269620 739837368 390469493 634298802 338536793 696762645 837099476 214859426 795875095 967046906 374528076 335123746 218919894 358773257 457019732 724825854 370225860 54710857 113324420 76391043 89935316 149715716 800931082 100769230 791168671 572559464 655550709 945824269 908717168 131661231 621018874 20797541 37484199 387790715 150219234 74204149 8777377 607086829 186432065 299741054 64763277 699368891 682855353 240001775 138463586 889970686 991767114 772303150 180899901 751985872 363951726 461700535 88832452 982062370 500151164 330968466 542947421 526336764 807846592 546882086 660618692 920712596 482050933 538846701 275454012 651014550 762557756 56344224 800312875 987732898 263384261 918045923 917638977 418749980 435478251 3418639 719523295 599226531 668920110 845434488 698967720 799527314 942462450 768039723 378788297 796388539 219012134 840010270 594918348 922057676 621466769 692615223 344214949 293295652 338429891 168759142 60363895 30402498 20460673 625977038 37097347 365114666 991674234 491641063 981980450 70201709 322043489 274404243 375248948 348920246 102654657 242789692 604206883 724699227 102025443 176763582 919131906 556355557 486193923 468737627 674728027 306715505 150002982 998942385 974490113 629423161 419172908 865119007 750820212 680553986 800244342 694914297 709598709 471655112 785472674 956826413 552608346 263673544 523492961 969999559 704852550 421196127 706360470 26321895 582824778 591975030 660293160 61261217 623519652 945533760 846487598 704658394 226720221 782724712 458604681 677075468 407214703 501850144 256900482 321741227 23381522 718797273 857832393 551859808 112837382 500330711 126870583 751250192 642682973 120764379 272552456 171450153 389932286 91904905 335726126 539244812 251296340 827833559 265332585 54995383 888911358 395925461 242795739 205454966 166376701 353853745 244228456 25309019 531709490 181039167 392856941 743058440 724884388 126328172 336463717 672479280 962533617 55054546 41062465 745428838 787076736 770709662 414063794 417984260 763193413 200200057 69366329 660404920 270506949 802051053 659794104 136032881 466659648 591274737 108139829 508020379 494780476 558593421 987638650 618078224 638888419 532945932 703758100 436902833 575304742 383339123 991957419 400151639 890012820 241372673 653021090 289825610 510836561 718965334 678444323 277218165 589494435 461489616 221481846 588667524 612510894 560346343 112055587 346282289 752390628 130416788 135923369 88088042 773774828 753589557 105240228 371336200 225223379 824837274 213340436 124781305 160246751 14426306 904296675 627645042 769136170 535135907 558564119 786949418 488225531 235180737 800750228 275058335 407541127 881483450 32293126 862301263 846852633 951271729 502997566 699594441 531210543 674885559 280481004 936682607 167780502 807771095 325969861 631935433 332563975 879615584 375742724 818948632 565547974 732608249 387349981 37298264 36661254 266886717 237527200 569909110 179613538 456146978 112901590 187604793 430224091 829731071 60286282 427842524 447374590 85118887 820877408 374412262 704869519 288199982 146428224 111391563 121461848 389773754 412920474 860643251 976544155 382979684 56023473 790958748 721124951 198150656 86560928 13328335 331220202 857744956 2173655 169750738 792012863 75852284 887463780 347163172 846177624 315367256 980941105 301882720 354817324 779792769 574793224 394949318 540890497 181618209 459613632 985104550 921648898 798136659 873154987 384286753 650896882 836987782 632359175 566744344 332932025 606355263 337627523 228205038 407450364 274882616 50883352 829650661 436743822 988623246 867662022 268315592 554135466 622164282 649464062 107903361 73400861 872072734 711508970 303455398 996899308 784656703 30818825 167107263 357234817 482794680 203394186 362809546 531479814 107940181 270052485 928508385 985419672 730297850 601259717 245162399 614521255 910099759 472508014 660380060 669049192 588983445 594933988 110887039 382571790 657069990 325464307 765345871 349787083 795662854 440308702 829625344 976966786 997863863 385581550 603049247 354033690 630074656 556330784 764556919 461332412 879994073 553440586 573010925 844651510 105789508 486408683 456765553 215014894 777404514 866726776 1251675 61763602 163311283 443736457 631452866 775290907 222925690 153923535 771149421 424905800 422372905 923472774 289900769 6877035 192231708 617909605 820152010 454095570 108291894 708845170 187734770 343787665 628692646 264946073 649083105 663287445 693601985 158440226 449063561 593628893 924508494 682063159 136524167 6424343 418543997 388648136 390344449 238702808 403867368 439561195 390116500 272484809 826218964 174877079 882611462 349570409 279424208 36725088 638280396 81774999 267188921 602961887 974372972 84725332 931855692 991830985 245142766 556858947 613827835 879409451 974531676 413536703 938560840 784124917 834933062 279205379 509522425 299934018 683348389 818215086 606057046 890280064 123544270 147313391 882086149 714436649 975781527 707580112 667055830 136080767 606536200 689137513 519236494 887918323 715151321 640498324 445663266 795604823 192419993 115619974 334324271 958076723 371541185 635461952 133463908 554397123 276344455 627066483 396095261 178082217 255438920 540403273 695046279 321106291 348986211 514669094 5372910 658226364 499910582 728234268 312993521 123185856 884979855 354255600 600842750 761137514 802495287 346889281 406102149 822633752 128239955 270975117 311982976 148414890 34277855 516783210 223461204 45444371 721113254 226546281 262310285 558155548 569129407 232396491 820918007 198038188 577691566 617462299 794973005 936960340 945879307 715340000 141130698 634346377 555518097 393480061 767275562 277656993 541269120 521170670 104659603 49087251 614291124 398769891 560248175 81221832 499629916 442868317 735018619 293735682 883485706 970455854 161031538 911192442 199024894 587986926 250192928 820249696 190356507 488189590 532684738 977978171 726931332 938849471 178344221 583947190 719563242 614885033 902768773 814361518 91843036 471804041 311588526 937400785 26462815 361911513 207250164 939305214 19724370 667895037 502846285 273100761 392385273 282330968 90990999 327245288 437950798 212754875 577857659 961990464 187849676 382688163 983955545 816237969 911274612 496111039 556255634 922373883 19951351 573909198 732244776 280290896 253089284 913158565 435279754 513550429 194722288 30116909 358596769 842775749 802248017 653771209 858619180 139581583 763567554 984432847 492406531 434086686 516586410 212929017 128186249 289436585 499444151 87265514 885375429 16134751 203158565 683563324 993991748 352070699 556225255 304465450 417857166 719676488 922915471 636132196 40583403 43460839 48021525 749754772 199319388 975903317 680984136 866773894 517186294 54405989 21719795 277443357 393411742 851071943 366038770 911670837 17065428 696465071 633068544 852847135 388263763 265134985 487163974 477198129 429035642 803960160 324847318 302835813 724308610 732824469 497631219 188751220 728633994 566532298 582700477 192069301 944350119 495496432 913095464 241164245 434819879 121284161 102557001 314512737 558076630 312979379 433410221 560038563 574678473 263343400 460479299 54454463 690758960 995157268 710568668 922346914 829957615 728139397 546048499 508052309 338088744 657101101 976805956 344120213 46156164 600324036 453741707 122628627 278526104 432553899 926818707 186745902 691941881 147968756 922331461 819658165 845723253 73343930 125723795 316994492 94890580 841082587 471196408 559232693 871029985 970632518 463071535 413006055 588790044 11076260 550607163 911831018 537146024 864023239 290429968 780012680 616276311 351809119 263715415 847482437 523569520 713928195 235635117 141198078 637992450 16825682 821201769 602089078 352752632 381470649 978176460 665450440 824537036 690262755 6300140 149164197 562435178 666844469 58248799 904628277 386390455 524716849 87638014 476438709 843130774 516060214 740862853 899212691 641660861 468106068 50546716 587695189 620915451 286684937 830888238 705934535 251070015 106783158 480615092 959768434 338648848 276884865 525288677 407648750 949174846 671706466 46396115 644850793 484956096 31752979 499503414 33373309 506733980 973850421 750814999 582788347 793319740 91423872 349574519 532558827 856225032 142339739 488183892 458997079 551604638 356299849 712249343 254992531 226855328 707430454 195884914 43894876 546209780 631580961 537889981 945694802 168942493 866015266 947783548 415263332 239082439 55769194 237591714 761668174 850567995 381946565 383453485 739249483 313953033 626214371 952085977 122826367 81833091 391654825 70647404 834249746 965770562 16191803 638286248 886546152 834852609 908096801 239481711 287523055 257448535 495102247 807287849 538768258 140330402 502113354 75633618 941047194 521225059 282197888 958274977 173774239 446492997 966320948 602575041 768699749 661165618 180913811 570494197 479612757 24463343 914470171 875611645 860078702 24610484 776159259 615671536 994275464 483421213 386547015 264466857 640359412 352890486 360914151 860202394 966608986 982485427 127015891 478331215 965111343 378322522 940871627 694338786 503622636 217045373 889926049 473592534 86744664 626905703 911933838 371051568 236277152 996403837 10037685 33657081 27881352 56352083 782119239 630586289 814415035 191459937 346457328 887544264 808234519 105474405 814757978 903122212 120898638 832133454 984944953 489962130 682953334 375787953 318077752 80379162 79459857 964865532 255423716 623598150 829351901 398600327 146830310 512207696 501059127 71069877 259137353 78685178 664356266 20944862 326675209 565424318 899800432 722183160 378001352 715397497 96564589 860725831 267279820 949529586 928127345 858488260 562435113 736638701 929382375 186003731 895808860 359473978 812516644 148370564 299522989 734052763 233256815 361356866 213918222 484203891 75215320 419963350 50003035 982281034 764131308 291795285 376434196 279327167 597341551 434036776 234925097 641380789 319371596 846839661 860002111 943767609 364076802 443623973 465191343 427469837 827945690 119482427 519724406 970880469 872178613 816893796 23457898 850496166 481154934 54940710 930238160 766617152 906669716 361259532 404397996 251168105 233390356 236004935 229165146 275520394 618924990 709385302 985846944 677183442 89653610 346503275 452200154 392982141 236378436 101592307 604883957 174210904 367442584 352524985 74383457 774738769 666095001 903769548 299360198 235551272 875387727 275615578 5647227 370164169 621267158 598750841 484780788 955180453 717111267 483855482 30126526 198432569 476323666 31986975 266647338 714112941 79004777 295915472 515006457 221442211 951176342 368773027 740729307 125536887 7974895 3243376 947144452 59006729 783706950 807327078 489310598 925486139 765265575 281357411 576926261 738533116 310207256 548460948 753079897 524726513 402868474 633941945 453793332 34841971 114104509 49407893 389722510 993071177 87446536 746358900 895345057 840300897 714170571 974559272 737016865 514985199 867436038 14813139 842805003 363122380 533188842 960031627 63579149 740893750 749937979 910255107 895785535 501728929 221846941 828263636 712422884 122134441 29593243 930580887 870952860 782573357 135474121 243808310 553012448 924299463 165498732 911632523 516418105 382490531 959348749 737939193 68932713 243130572 771557357 920909141 493445489 157404974 188491705 135760902 932447528 926326115 768748860 7211798 687428687 378733586 19198419 229107721 146760034 951147491 221112488 715415310 156839644 683333339 316149408 408805037 460952278 643011539 18752795 295296346 257901292 251331297 134756742 267895349 74085642 284287689 352079356 288137848 510037689 863985033 37778044 656932585 352685279 960054843 876044924 792419968 581487060 586902286 820463566 374727014 675985814 808373103 100519657 374454546 51518332 342048749 154365820 290553332 660418885 370919172 991675042 898824471 247078662 663037197 766902506 411962719 208981586 486559047 294650536 49558347 711712963 840832421 258034529 882759608 58013064 779571914 935783830 247496581 251051189 373838999 406959545 386418951 798662686 197409765 727750231 328263943 844050113 148170877 170593372 293868944 551168633 534512661 691148075 263087664 872978524 280172796 180650928 950792131 454975194 375148347 889074356 741073316 359446199 175344288 747935624 363846358 423160161 135740745 411341981 603000259 266566571 778839699 925000327 397892920 201341911 122136520 514090161 685900175 404439145 65803200 648601975 715018759 493222326 462400456 125396299 382929690 889789715 904397125 531339438 415731245 67496069 475409133 338311972 89098946 203860248 996596750 560034951 771068022 485683105 675339142 568932815 427233066 385553461 80461974 602502549 181218019 65545055 814464959 977827919 778457820 469909439 802498636 737475823 367701318 977439513 441812283 152078570 142814146 354646490 284893350 292731540 127698734 935955977 468925871 269492338 354864216 718354916 231606301 978225687 493653081 612305033 377438279 477540955 600724959 955224111 272687309 665241227 324901211 508709612 186519768 501447052 732322220 183037759 925861777 157336829 152259987 496368300 895633362 826512360 335291211 810254292 871556481 679476872 583642623 679391664 313247282 428651288 176083216 570500881 200096081 287856140 221033529 296796883 967912042 223966707 368546085 955257646 665840002 631347335 939507062 698336788 433827866 640793205 43210876 672047386 162378608 783630724 64410394 679010912 424154980 22187771 346231944 317545821 601162606 45253808 350540035 570379443 440802990 824950373 785641908 995528216 89337957 454133591 744411039 518135073 830020982 401873010 647019520 25773462 613026266 118698316 472758022 152895122 908760298 766634842 828141109 713358782 952452205 552070729 149944662 940761309 229613304 174625573 546685180 584209306 812261786 271315484 958856654 517876732 703231454 279349195 362550255 492133057 916372663 198511562 488487040 597044447 48456282 949653247 411084869 653454172 349345213 823545466 835153221 230240076 146728232 387638501 253373783 846981430 986285937 439378109 183363362 839276486 944743614 298001797 848978768 737427090 621674453 784507862 809526483 705770782 596845233 865902784 249143327 978947945 748132775 420756457 953734925 166251642 529755005 174262878 617617509 445669555 260705551 485444951 32074131 6230287 481991943 664471522 274876959 349548413 171686123 161120603 508168402 894851477 824515462 964686050 359109605 769502947 939007668 880136223 448658711 118349960 321481968 578304241 977533414 795765599 981221443 293651655 84428558 48256264 134840516 117030282 55068636 619950830 290688799 197179810 823392805 53117337 207119050 368474485 184819322 877666833 380980659 713403443 829428303 76291907 445977875 662796850 426864736 794913781 590743425 736460290 555343460 842234031 397494519 308491263 649092956 121238185 906344119 77292669 408888711 703686553 802774095 94755612 824740447 626588250 417385658 14848895 369728524 272492917 489463281 850785762 830709236 912728295 867818514 823019011 794226514 869412023 610060473 868444437 775213255 358464657 523853632 589238035 432806879 269164325 779036345 742883560 874697592 618154519 552917087 906972383 217298813 622659129 742200480 241177068 909939279 819712019 606425071 487158014 860839804 600142657 723099784 748803097 658270981 898594548 824849014 737599330 678915262 158589278 348644094 702897339 7248433 955156894 451791171 977444925 338799771 612514606 681191040 396873634 244328327 18410924 923478900 760012401 493675563 98629031 778513971 970625743 126955869 663888049 131389422 174415616 171021369 798568601 908153163 709835915 573498972 734372371 835482319 191736329 211943591 940127230 872027385 921380370 623350800 96841026 61781816 617593416 710328704 746777660 881325868 131263842 674387353 971147118 736184544 455852064 424003366 450768003 920113294 845055080 626700268 346107445 312605169 160981472 197218357 148941752 622831149 290117818 752131348 404576070 250550909 64244450 358671983 686581489 296942075 43884748 678860542 964570497 820406546 188167459 928867383 388813922 632434396 109896106 546557653 38365721 518388783 871850133 106699126 863667966 902979121 532973794 213642391 598203584 234814694 232440519 532631044 252993132 835603646 581997265 175645464 603453575 922177366 164978088 952718225 23061110 881968667 290425194 334507500 650567380 813041304 617986211 218364116 25991540 305191541 270057272 632443521 477524202 148975242 607952296 847580444 986878374 401760200 721193110 494202198 647525498 368746818 554039982 25550158 657740658 101318156 185173012 172146510 538569687 15764357 571896543 874764721 220324272 743533083 214332290 92164683 901439197 500906078 349990265 544534009 10334555 958046143 484868960 173193985 940655477 692515902 759298572 639075608 832918577 969631467 349788776 432952211 959385691 888808596 906249170 138576513 706048512 521084285 513239812 798649938 712232021 648094997 360301464 6295246 306182749 508452095 578898715 502511156 780055434 270218111 540766566 237756184 241139404 489062388 569252694 678407558 17135515 425831620 835719668 996548074 679046576 147577634 715087861 97694371 514986148 11581695 409031532 542804952 128973608 571864489 636530633 597513944 338410361 182078317 664124282 766674960 142331423 273392645 405986853 716053241 159162141 182144853 664925037 345897347 40033370 591325636 78099124 34864684 903916840 532593778 268958550 909207263 302747980 901171966 156854165 816008297 768534514 892140028 701816756 924306915 870246736 895345259 669247786 552816504 801911591 256289298 342233795 646158451 178866440 568843303 515287841 605131326 897124128 272947222 631486856 763497453 314155823 690594235 448575279 672279330 740409102 278195538 519287433 816046363 267567711 210478761 19534487 984809883 900361550 201861107 446419083 278995808 949704264 290764767 485418205 84961207 805620578 602272772 287053282 468931342 687980272 175518728 244410126 160353557 202391677 674910241 843314299 364895261 67887978 866763002 214714774 674157379 698175593 573836236 979195287 962008671 630578515 36524512 398146498 488833743 281168931 246154881 515763667 413152505 758909222 65087568 310596870 609860188 69925423 659793770 44825537 541298942 518955960 200451431 568318005 551088815 852588047 719229212 310459170 215803278 431137131 559633270 732625346 295564006 96479105 55274903 505609597 20792607 121212419 565832454 61272733 457598554 75398096 444570496 289680892 601220768 231489437 679559842 611473063 790711774 769626305 348216815 338200570 443524992 634672290 718425978 379411393 441380529 671081986 683114185 996009476 652138703 219274571 604316463 498541258 506547399 693456006 807055398 947393376 587919005 898305170 339807694 440671055 543813913 781859238 791928144 493834357 194162888 959928890 936561516 385961091 236428447 171639788 929912764 783104623 422712001 343932149 572108797 890778768 656865166 572302251 558079000 687132133 248186115 776271658 245067519 193684065 589451397 986309982 850520020 172523049 407814056 107544691 397065483 372407552 244838230 700591941 93030523 148931 745255443 852687727 415351384 872460247 279182422 351118115 511801535 989737442 140776462 595966846 471767898 603428992 836106540 159798087 426688164 426098180 883198361 396227976 982574272 580961280 239021045 264447513 799774480 854674011 480066771 155731782 817879394 997790154 97748776 191251689 620034254 743648046 97800373 733608343 283804354 980424807 719361659 305553912 715175642 61837306 391951693 978230943 453804175 641509150 305412079 798784768 462940152 341769394 806605364 474588103 692463310 335934661 788987849 363910420 82502304 312722553 700235435 184918116 524423485 732732641 350621595 621976310 83317562 711789597 556032213 526345646 25048216 11670346 39557301 920165308 885829786 410363546 891545100 907240829 46979544 457269007 728159069 667962771 152862492 659152885 845153146 761862952 153821032 200097508 416842883 833143405 908285240 706126957 722182937 898862488 812362766 808815773 163186676 141996829 75513355 906948938 529515672 496898353 268935210 689924168 438779924 938871674 230614740 807038406 371220849 775718844 240928833 62705154 649292119 133894784 123092851 979630118 670551664 557910286 895681302 177004391 991277253 933391054 854697781 256941711 808981303 682491136 565164274 288729696 924224036 676360565 942411445 526514037 167012694 79661099 175549617 382427164 264248878 434670847 870285719 135648522 112077872 988931273 483368730 22495527 77378890 986241039 248427570 206411913 515973701 990906117 26985123 140107639 322878267 96622527 532663720 241569488 606394731 258547312 14537145 494283523 199867052 621595469 794295599 776109953 442844849 105098935 277987583 79911637 446030543 953479777 185907558 986503610 460218601 389933953 964286809 24226628 425285935 474924329 673676311 325256542 329629532 41635962 139783978 907440960 719859769 420591487 469368957 643110838 192690469 924095433 993025821 404810425 115236948 809878766 292981355 381401189 847033896 480277070 656820070 80276843 949244714 472092512 497356596 352798756 527143764 832661631 758283695 429044662 694204108 839388106 749614303 705856542 473510923 596971765 984053125 681237872 61804372 686014489 364558439 285144779 354135276 411323052 287000089 408304649 37174744 325673386 881095138 271187119 716590138 424279977 96467771 748650324 755658100 73018994 708651020 190263099 597346801 965356307 407266414 559184554 569967104 166759487 766061115 693377976 879881220 297719827 834462531 233210899 416341679 893206909 349306921 204258141 895833666 236642480 287151044 973518796 343959721 709807675 399946960 553201229 46480453 113123172 129097293 781624591 917339595 796762076 791546212 613481227 58033384 5634308 693881471 654739769 805601194 883273319 820693461 320346338 656706359 743269967 163444763 996635249 912960734 928911818 717350384 197100566 682013029 284065257 750341299 432098054 580501615 129815240 131786689 651898101 526610308 719559682 143223361 619908616 997130828 458802287 742017811 456959980 643148464 853868161 295977081 854356502 863934799 861723422 31474413 177118672 297426709 283429649 109229937 421186055 774192114 209905837 586691547 684456604 810706569 353221565 795936035 804738861 157161805 807428565 75314679 994123686 291768485 34191118 697698441 308374749 658866119 415757638 226042108 327684080 901947147 939288308 981624140 286742816 188914956 524859915 192941116 57050488 435092342 761971308 363159375 640182073 879809491 348092705 204437385 523246964 375152048 791144460 616444669 739900433 322080231 487197689 342828939 145682737 69482437 64508755 634160391 65591859 396338052 417872489 603127784 253375835 396064022 970984777 683868019 181880628 340580739 368335834 432902161 287527726 237416631 615134967 837308544 658420853 809414648 672042637 482003751 78414763 445803277 273210325 949283975 668999645 826691715 270704742 265076795 335205170 135170560 259065366 905026085 413382011 399906765 923935765 499031581 551118977 915254589 151718548 863889057 951850416 103142202 50076398 74227227 950616441 142820808 471623505 135796218 275016509 512396829 713837862 446749005 911992664 865724002 664196693 494547730 381989210 24844518 502700840 783726848 516570468 797147495 159855248 954422463 181517132 745126382 792076730 497896654 107328261 503580175 914435625 348926217 10994705 274896833 628676760 373527715 982930098 888725331 817963633 124777542 892988554 894846660 901597461 934227429 830182342 331558744 720937903 513633325 627073559 989960642 228926565 559739951 159046332 599621728 450638537 33768311 878057262 827618382 682145369 649207446 976211546 889217623 934146016 410390567 172558877 95784035 645810400 23210020 877454665 799260390 584270600 860790949 671470265 405697771 963669111 229444806 923534084 963462965 204620130 606650644 690585695 477302820 401305909 692656871 754531507 302142794 456092543 782770267 825439733 975590466 515620016 267007827 818594815 768580963 463485619 642139837 429977792 498144126 863967911 913306188 722122147 395226305 822916754 57903381 833227303 372384597 323762255 209603330 227029529 676872042 237984530 935126214 770285762 11852653 479228887 904326325 23478790 688215827 989471904 945293504 510469561 421921521 555218771 15506084 29940541 600469659 533024614 708199607 960299371 753165854 108754259 243029738 546509539 597713638 758348881 360003319 190950884 606786233 637390729 851791918 9021822 125335752 749294807 336975934 573411300 724631555 839075772 553863246 896271944 560516194 686921360 219810213 150558089 871775699 296750542 557324430 337209874 571626199 373892937 833804023 687671806 75842154 491418199 102325365 145931765 843811521 363695328 518819223 323009225 629407210 779783120 746345544 674336955 970775529 384626624 255025000 601478307 892256021 280180190 680206789 672309872 889676468 878419914 946549560 399028906 79528624 242829744 951253398 272820405 614579524 501287714 939485922 773591021 191523347 144321161 185209551 652784986 72572777 912583790 526840592 148460830 624172436 31574673 388553241 820323811 151592079 720988550 557287000 53907204 628502649 803733092 135759863 242713857 207029161 519620319 191127831 181711481 767369346 290194834 660050133 626583037 205166530 263067087 967183296 706188696 282999226 146941714 244900751 323232783 384062431 386396996 820285117 198429803 419759511 205073032 841794124 208279870 684379165 874223514 81180652 951690219 971224111 341370403 425039354 142478101 527937437 269471858 699473584 579665632 296486907 730048577 519085018 708839308 680173210 337522418 197961340 23590659 137873679 651313390 909788397 752570866 45892333 931173150 338015347 807366783 87131982 82383148 651573728 90856446 531552202 450953594 372085353 816850860 945181471 661354939 537194566 634756655 458827845 956746783 98697682 685987557 560242500 121688422 570924749 441539078 380564684 169083499 957256206 725284554 497085078 941831100 435999622 478926199 493802230 458146241 532906496 494122825 827011265 407003997 864709476 474605440 940624088 526287297 160544272 244859638 641232176 207463924 874876727 743771724 582702003 179866847 985449503 947851796 828644856 948686662 959885241 689715879 937916818 995281262 524267466 12555632 502507549 228209017 600023828 260219756 672743835 539205742 140896362 711708141 968139326 616249012 203826613 679100899 580946878 851438369 773091755 777374919 562408675 508783851 936904727 147180526 83654429 582939317 280952324 923997940 891440388 93956643 560086280 819250147 736730286 974842561 324743301 748470714 284724576 21089595 808384475 601349024 46822835 585012328 94452309 753330032 801884074 335358214 949493554 254898443 600204060 370852557 268396902 128088769 503961660 115771351 555919413 602466957 187835576 404674580 350824808 675814185 881671445 497691486 489596819 114294421 852668564 644067050 655415205 864537277 462262284 114513469 110342510 187584548 193586924 190937940 311671332 123793225 638326567 610455794 31536604 223247446 32588276 180450103 511212300 895605298 505966435 718389612 964868103 585653941 35669 536363281 286585514 785672000 453181215 380546576 909501067 687649566 467410612 398210473 740889010 595121213 63763783 22704591 437049691 93913118 613314525 437709708 752825304 991756026 21747580 10037567 512013169 369038247 94005436 16914628 839433170 700690322 537872152 104035826 216814992 301184889 501209150 957274148 352142533 230713169 984540266 276918253 62779394 182225461 629992993 182504254 728816820 439980233 537220332 663832189 895000845 322546029 902523244 761426869 857768714 276392542 873236480 47245893 393663333 978824564 320824356 549192716 178668464 188447862 461202544 417917432 107592458 104025049 451524602 317894901 564837065 874568116 22649784 415498873 336465693 927863464 920843248 819295993 373860166 125158803 493745873 904163308 763014576 407925492 468272440 513446586 145330372 153856306 927560524 446048536 80374015 642296040 682089251 940711322 349828170 343348670 916939776 3197573 757712762 123599953 824244539 370375613 371342836 538210617 637966035 708377339 360852653 416782184 492851585 502418083 793616475 618978622 793066844 813705687 218106592 159769923 538708734 239740421 732968324 472396324 455290911 157940559 192341233 893397908 986304125 663915022 509143133 203945129 440792289 532430170 406130290 30910562 164627927 916433242 267144537 162415554 576709361 954199663 674132113 761543528 569824218 395882180 276243777 234739420 44160198 637149215 523119833 987886362 125270434 127205669 186456967 80997267 314784113 336592077 291081752 369282300 904226700 715873382 598438391 930793748 609559963 206277845 742684969 134369728 180295538 785342499 550391614 979920849 126102021 565093413 128211646 1769623 838649407 558867897 57482132 639806363 154537117 863432742 462021315 14221705 15977756 400082510 736374547 598906168 11044517 819074751 116554663 824700541 923301242 955958587 180807805 277209608 608476982 102761961 841430847 761514201 75405232 746851034 913888306 549046389 54196955 552947684 413690033 279366462 534263108 808114881 187509949 150543008 494969147 880165661 474067361 315715996 780355521 345666494 393877474 17804039 159625685 639571296 217682366 28468223 716762792 339181850 837887192 879604980 195827019 696627976 611561083 358835067 189592910 649900953 635310995 143598097 605751149 909089291 120954410 929380222 684419586 593492205 351097612 255487965 20994974 770497788 64832375 759750234 527193202 15259456 335945335 800190856 180192553 908773542 785615404 915052376 479885327 205527101 139836284 596917722 61710970 915985567 665911916 801216978 163154188 102528942 856023370 938005359 295351829 568774311 303510428 502127729 330029696 436842113 599913723 102574555 190622886 473723233 999791633 593634471 182110267 135892884 62107699 863180556 887131186 467118322 758415304 469630805 291461348 983790268 471039318 368725999 784175385 209966037 378267891 338461008 438063333 661548422 600346030 668543816 137414154 394010411 108337751 846642775 446393317 453447046 592813924 931916217 848107561 287682841 355887387 694939817 891478248 635947508 608255235 352177658 672839676 833403367 565619638 104525324 783706674 970824961 901757340 611957271 662994023 619005118 974553064 466304858 791143667 430348513 895670577 49854062 505529512 128405988 545518429 826182214 937958859 788196615 970530722 31550277 730829070 986978529 417071708 408595037 637127259 634016938 530748728 634706330 58776338 451600613 751320115 87623819 199404567 842812845 827528513 725849877 118769955 512038557 385572788 195493694 889504389 178753377 729846250 752660631 536530227 364965044 732662273 330701059 600305232 804958333 367095763 399921234 562322496 717969867 500570611 587031128 788951882 905861260 10565285 550094371 309664732 46558654 781346604 981825452 696646037 322697989 853490198 144649280 180200373 751507423 534024269 668782864 300050826 898596842 482789698 870240805 216211484 257247826 218960434 443070616 251475770 304764024 938521629 654218591 319143024 338836919 132113969 112139597 727160040 2419715 68677050 430767102 529244413 607428980 69691598 727504991 641273060 719068254 146775798 485576717 362285642 667590556 368327749 595910847 264282514 932222415 410743628 78382268 371621717 932366126 789426620 819841700 926304398 718342433 671465298 548804408 577913600 971392287 966676535 849921178 234004070 869317196 106725069 700912258 769344535 730199591 986554293 958586209 567315383 484098150 123667931 858820817 66494882 385622622 519899266 33644020 999247552 28309245 595958454 396350831 153592985 311293099 649012647 633481904 865622328 201044314 807435486 719856277 522100741 290955753 382847730 418298910 563037550 853579218 247780188 582237489 856414823 179960316 644351713 762884260 887823066 876533749 873827113 286685449 184659073 877439895 382151869 877857476 41406876 218028774 191251403 945979421 819710664 960752175 174982217 591614054 806570304 317804843 19822914 558305229 633989228 86916540 327966083 439326421 50446216 68613544 146807777 269407556 904336465 154755489 861798801 36056179 394453727 34335119 809503945 670373872 715999674 760461798 347632906 555388640 737962699 758930860 810369284 572078867 600394054 986382470 813277719 904540189 736698187 550929986 310712500 468098179 980230165 987902678 171029467 581839463 122892425 695964903 249661609 172006415 768908347 829249316 104131564 563394145 761865849 199634630 917706972 171072141 853364236 340682788 722053120 357434486 902366951 462399724 102629086 557057219 768129657 160040489 967923594 679912042 651654036 967050347 518474263 274775652 783100368 682837308 499173178 897890119 641398779 348717819 100983408 439514369 943656317 186886470 204101615 387809560 706568317 220672561 847233361 919205916 49404536 20393315 376589991 715614671 570930058 828419823 713219608 374040219 510033388 143332048 562300539 413275828 949754779 276433452 908796650 380199133 304299043 435451242 441332053 462312975 964304415 16557862 264354266 912680720 375034111 238766668 176456803 82823289 374545077 983059991 21916569 569019052 346098586 23428691 705515541 351573454 412256630 97819738 174503968 417962367 518690914 862104089 6634803 590619521 437007482 490348479 993730941 534581240 925753170 391349719 329101492 651374655 10841890 938713572 161422272 229490227 51106750 114778071 769549211 175703707 299406910 650647930 907658630 97244564 156860940 699821361 679651607 514278059 121320649 637466871 989406215 471443146 728813963 275176953 18373450 410711769 270201401 876729450 745692543 296757146 948977488 175142937 86575791 713798526 730364540 406190498 259852916 585528308 229469950 908081770 147768499 849662184 449967632 397676790 20840310 185136398 63674605 756719679 443113789 204396037 302881330 850639066 881338652 72450173 453574682 864962026 559006349 669661306 755909322 523107939 845933865 476403940 340804276 955896107 424942615 79405728 892339278 311606194 243423592 698607297 559054111 178646113 454511937 993765455 551817861 485546194 395162093 413746383 956019798 186301109 52614872 437570826 479743425 506305848 924746097 574480346 540997146 219754039 873479622 500783320 831934705 533486120 158850990 850659549 80894944 578010546 111655512 54417496 280849874 934497128 936122444 27143321 851090312 182861182 11717542 176592140 744903195 926448512 721304896 24809596 120174370 742515641 774320255 487746381 564407979 879441806 669081394 795008339 905150892 484981269 412607720 498835751 114743872 644200315 641225143 16384927 636644404 839702565 726905348 421874658 405076138 625095920 168289995 595554224 692578653 332040023 772545727 782679925 358700811 123571507 125276326 657856982 695621226 734908938 560547700 348228304 943557173 423949433 312212163 369741149 546872124 113692144 491255598 216715307 117424744 335030798 150498193 44067690 934539546 549694724 11915168 354310129 709180328 821883614 477232744 119457320 356259310 943281745 871810595 938893325 657530548 451078780 767347373 464644566 674912929 81347991 425666172 709772812 391458400 714337223 915512315 731511176 719144683 200552275 668039505 917761060 121180098 827918437 670955754 530205289 76262996 103913950 537108676 456182892 473529543 794870759 620570941 398187397 213816202 729310672 939303754 945431691 7348989 729879470 383293860 121383259 832338516 637032761 394306770 262584518 940902230 962250799 667333636 132589420 382510995 580314600 601427362 347709347 284606350 42836753 912771733 574845629 86904235 89797913 687130105 674234828 225795614 383583081 359088831 869962417 210714558 817205281 813648220 654602734 423175655 422365519 979300356 792157340 960700993 251483638 204226357 604280331 357661172 482683355 237851386 365288867 889077759 256909579 362259974 720422350 640136558 810206612 750517252 143678511 511964009 116043884 634841078 530143198 442901258 329053561 248138407 247572675 512180436 791251604 841419757 115864916 327887615 157021242 911937501 414361781 542782244 561706280 652766297 945942394 509911855 158711805 180452563 449958193 240416832 487040676 757309335 894530963 230027003 672807304 793435962 462108329 975666018 455440459 48220316 557103122 788704140 63497128 920551598 245510818 529574012 400477080 203966174 768239781 858282296 73443303 303704146 110039533 720549283 207801693 463453064 398667957 841073649 462107254 89006230 446875115 141067585 391900250 196905899 8881854 685919534 770629507 341290614 310397150 624950792 761963552 649092029 839117158 155794051 790379538 665960904 766702221 248351371 213299017 24833092 671612566 868122625 303292562 926939738 65867566 601503973 615107588 622821891 908994693 439794601 86162912 265177044 375957037 373531767 627545159 159031976 327380264 857174051 759675809 738322182 836566754 935593555 926035196 89059809 753635189 520341672 902510370 802437829 65089760 537510702 734750140 432144553 89807380 866809227 960433796 7502911 164687018 976018615 329015709 975570007 814013357 541137526 23648562 640705032 601492537 90929302 317132463 93117238 890334555 609281004 846843607 801991177 150559126 411973903 50818246 840331209 946035085 978987152 886446503 549092378 213014737 39152352 717879381 556833461 617385532 800938596 382930782 824282782 442338343 655290603 470946763 175377668 460522693 277252730 565508488 510012283 822785949 54975145 895967179 878704534 313138550 882940643 250669507 612751514 762786098 389485664 132797058 858200562 838691984 167767015 618808400 331794323 142681486 490130238 887523386 21861024 55259141 965550001 265791624 578561728 985845154 60265479 750924386 806202612 375882226 524448179 859300548 378812628 510430435 922660430 925564971 162570367 326732702 217461245 715285690 486074381 210149325 326920605 143865740 589703335 555424725 432003713 644039365 981342752 354275856 736024121 249150955 225918707 976552575 340064970 916512318 989739415 106177815 324457510 393691746 614776954 943283842 859982395 31607500 463101655 658830327 710756258 183272213 417967362 993656627 646178526 851859055 662030148 504561777 644452470 21944915 435864609 133365950 373769717 771972579 554187413 803292106 402981088 830093545 659585606 990288108 916384818 229978218 90182504 555307070 976001086 357766677 88092891 720613012 160166301 246854340 336919474 312251757 665121002 371267596 872108660 636371812 710381649 103446708 682479409 928665351 802663187 516904142 839661404 307305592 649593846 359079316 930673030 773666678 882698459 440009463 945618033 71921956 269101476 219197956 536462874 442874103 55643281 554376012 950078862 432969443 531786664 981798417 725191647 862697773 582714100 4532482 297191462 365192400 716746687 753432109 344985080 875370744 958572904 157818611 558111155 702565524 967039942 83927685 139862021 583965058 850869742 736975223 300093999 450688930 773508847 486238096 599947168 7467899 606607332 870239303 426122006 443196533 221304980 111966333 618542293 704027789 661193041 354763963 697566562 898850965 21260486 383387624 363341241 516464890 263816358 889931793 288014874 928671109 532341888 295741820 902538831 398253345 111800881 586962497 580112210 479987340 375631266 887487662 862338405 946818477 49437273 978865568 104795696 917898329 16161407 98313662 368465223 309257134 410056400 660636593 820797419 79828764 411124849 825473694 708569068 924563547 38879861 440629933 43878300 701676614 630660780 401050887 894238435 699380416 446903282 756990822 407829742 321790134 639077644 653249372 892410567 845172625 863971551 204614371 9861806 342081298 563323586 652174595 163627544 839701368 346846899 336855544 339932697 443118802 771617864 581579625 143648834 525159230 719551022 509893366 217684143 166502323 838537564 288075026 823114231 341938682 259819388 807988286 529766678 727901691 299913850 289963862 188018172 981315833 970160263 176304240 55029645 666336647 603868342 298987445 984931592 51467390 330135549 503759083 346944119 593131272 250935576 238912253 409711645 636434716 958177405 267742848 27710776 56449024 129478803 251822979 931154122 408682624 975375243 235265890 535640522 64782952 84357028 936003921 752824558 782092790 960019912 734665466 468437880 700746391 45153894 683121360 723498411 707970863 171822154 443672880 830623576 955561243 18229286 16036603 429361119 469548388 344917473 661846823 564801873 385363823 195887885 227685856 314998721 915374848 823317758 209573545 252580628 852470806 375525930 515833328 133568227 479574441 355797157 579309200 941121198 171926729 557005682 412153602 358039174 991955167 126965912 478638667 497359759 914125702 134857064 627514268 878260018 752630208 921550937 920686002 73268497 663032511 187832564 534685878 35635876 340857817 172614501 239514667 594670794 47429544 834744058 835979781 357232030 42029894 331055030 196721137 618954844 857311524 50076224 293951998 214101094 156105615 211390023 550118411 40555032 537165858 847065088 428465349 52435486 725641909 15487336 977136309 114189162 496955530 268152182 162750759 619167345 346384246 878582977 166306857 908692057 416463020 431520117 891882087 925698539 807344666 788513639 52840339 888549479 138820941 749805937 394513116 37758568 816490123 600184167 111000887 967760210 429837189 756282015 479885824 754108553 359475396 108473477 646129110 75473193 64667168 854424498 746044414 130626417 32296550 636465033 764837915 257671519 905705887 187637080 760716452 7135060 72560072 105462631 18365067 97297543 885475696 92704407 419482491 451268904 612959615 880566545 181332337 904331413 14317259 25519573 894305972 782824513 902228990 346203715 950694280 196282471 591284751 973368989 603112122 994719612 998730641 822264400 705731928 117159744 218561145 190481179 878765671 808752382 917391578 714097682 807436199 132722898 997829764 60126209 551477 445829096 388863589 767656118 529548135 698249958 814930346 47289973 105863834 168118501 681054203 979958067 473947926 768813722 273848869 339322046 126206016 753312465 386132742 603423982 336424595 77022088 783733723 344420133 806979352 730804781 396649521 722852209 594716930 181887411 211652457 871458093 601126534 817986713 737080403 178438204 908687020 169341403 181074312 152426768 770409815 260857521 378612100 617839740 44960865 657482692 710863334 632481388 561093407 331694720 138649131 9428981 44777566 867453291 153470545 116218451 30732226 196012237 279147868 671820260 175948053 478258724 530438397 160049397 489136104 164576388 781253652 59624649 635398163 525690090 780534432 178195802 26266062 87991732 666989908 670972084 486037149 918660679 840037814 811729677 130294260 876152878 313441927 914030646 859921819 360696334 135729644 277718905 54399886 907543330 305614866 523698558 249635744 880912956 354382534 286603560 768408006 85421650 712988891 13885790 408028152 195139507 859655298 481705990 743741092 360602692 510091537 72086416 540095597 148966917 539386766 413902102 689685899 924707617 620588148 769154162 45084713 320226642 190021377 911965559 269943531 434477656 810378124 147070279 696518594 570393227 629868766 528508093 242781003 584000722 60332152 591304988 240617127 624217667 759361121 8082324 996338684 674241924 958600817 115756474 343558395 246002302 341797745 126500945 386898630 785253576 359883508 310183917 414556447 979247070 320388278 601772308 990106590 271817759 806479222 787155594 745534848 59324239 619085193 264054996 923073163 607343091 638417498 449354285 452056974 173292390 612692747 165870977 361103653 808846067 396400415 603995710 855409509 950963376 417571262 913256546 991605799 398688485 636417553 286118407 226980849 376261347 223139675 925638919 662968365 114484416 524188808 774800444 981813311 355698431 841103199 704831740 573186559 448663427 733893588 971737530 35987281 285815447 500040302 993209164 77508929 329191259 279844827 524814565 181708524 35134139 31348469 950259490 913712809 472607119 622181476 40995314 323135267 152631123 321558193 792854669 645310720 932597339 211166422 38776139 879906711 64662837 215261087 12760080 233036875 46976650 900657116 923574196 476949220 820442031 136310977 553057986 776667451 8016219 289102037 729087859 230682546 936985089 782255737 817270190 273278285 476358345 466849403 234629167 469533773 801385946 275544439 599929719 701951559 511751948 481577417 233122138 38608809 92575803 75227522 409092607 284420060 390659958 740398159 112337959 328452383 552481147 530483722 395886501 338731973 173349604 727365189 992517688 573794038 589771286 377904718 149701485 66922542 856086618 288138181 999302441 667252137 335565684 678417883 377297103 125402430 802529951 872704853 286966513 138806678 594857241 241292441 877530142 228144736 461119938 926947945 364315656 83243718 768939804 178695743 677346328 186229805 63370130 285583534 285208174 19910830 642743165 371163975 429735706 636850430 875351299 335406399 648527981 628040946 598346117 719934261 871525353 428976658 511783830 515715870 952238582 157682699 266962141 720693032 780854720 161962771 187597219 30319903 451973879 40061965 77477260 206814264 712640985 630100547 806528716 539938018 751022188 33189361 820565342 720265265 939854711 988769864 67262884 27065349 541801371 722843940 37319730 113044348 899045613 177991817 493114351 406037161 597868392 48603872 317627332 990296272 946369064 563606694 170851092 252085373 864613659 348150912 797291483 661365124 992469928 510671720 277245749 22222112 772775262 77176768 783511529 622359993 721505051 318360041 170981141 168367066 994025030 726048735 569104003 917292923 372887789 62517560 69883564 209734848 168453789 929717670 26394272 667139508 923202487 765286352 740106213 282275125 547742818 416196473 999469893 652256901 399990836 338537126 501609045 726130990 418730414 681746353 265737410 440132057 59859411 446657400 322683957 523909848 351302956 954223994 87948142 488221022 681904380 198008196 52786407 951064823 940231443 46970874 604892414 223771753 625100198 280576123 352844110 570874029 125976704 270184945 236990886 901274847 486881853 880484784 580675309 43479147 63340737 250965965 599942034 770995157 611198476 374065956 14067872 662680646 270022495 227010452 867179349 739042730 711280679 967720219 687682791 732313364 890389047 294881027 495403866 26276510 732120029 548381381 696214882 216286235 834091829 354473253 169860826 415069771 825554648 842338456 322968030 220931731 184747740 502743618 182279448 191235318 870015981 826420758 375624521 656659132 600762075 560029684 887276593 342199233 250340776 120636817 315683200 194244839 538947197 261493887 15600444 132367725 82445444 857448009 117144648 187511020 730855547 838847823 918139778 240053224 960631453 401509194 840657914 909645312 34355697 27067420 601948225 484796316 358903167 934430126 373449112 663191255 763224774 189792166 504163403 844662604 369827544 434710441 371591590 522879740 801779644 530319954 308887039 185133946 831263684 892046358 204341490 206438416 590520158 828229119 207567604 940250821 268946788 889696906 369322688 43540397 628424128 527309136 421912614 215709292 170229919 383823919 361349664 588289184 826976706 452180975 519848847 618092359 415648480 838749176 929166086 648875368 873607735 72613357 954909785 447588031 105262053 313059634 774078303 569723411 966679069 600662728 489788176 458660357 210361435 683843938 985702122 848552805 614404032 21802692 879646880 588920166 762256768 223330992 909549578 853335294 625996372 439590368 743937961 983445746 437032792 315995974 890640453 482829476 295040612 644057013 602192138 64361457 848722282 313368957 536312245 927355066 955771195 57749554 586400599 830489529 633820858 278074096 476891937 305654316 289481069 399270937 436938983 491284962 295350272 486376487 834505925 388833364 925804028 842538093 466103262 119880525 655648174 658854962 156559891 325569347 937602384 392774927 976291032 518002447 859381818 683763729 310358963 606396590 197698736 390034928 5653162 731499398 760467359 224405002 147501245 572546656 32330799 840523875 325278084 834965729 721130884 790748026 104136353 972451860 492537480 636157248 244037693 784536322 972344352 867162143 377469159 344355309 725907624 39256926 489512554 145614596 226123019 255290357 37370863 37935762 63726518 457459111 202121365 810695441 437935201 64613696 822168938 489286025 567902999 382503058 501531282 211447044 101027657 344300749 908775577 557057727 644010239 280588792 570277316 656235102 338457127 776257992 958064898 434381187 893949679 668935447 313708384 243188644 745603851 833662356 196541446 744217524 564561565 879793557 658716934 533604717 534578564 590567591 201757039 777153672 628912626 140699917 463586739 652158165 270399145 475698134 907537511 851653714 245384051 211139698 983290022 231903493 896291496 261194776 649721151 355191678 705134514 611091213 56942344 130455640 104242375 954910209 532814925 294382821 113447744 161407637 706686143 671475494 378565343 65582294 267556099 957696469 613897594 613701056 470653084 981951696 909162798 936332484 868749909 999397491 676404092 907146116 577278280 883531041 647555842 102757823 734716033 921478766 281002102 13169181 63601499 850127559 375736251 939828849 531933200 312922098 485627507 317730739 207177594 638720759 804036582 884770568 419929714 884005674 351457010 79880717 396472888 144297725 49354908 312939835 671811337 482644089 656467416 487208657 448178748 287623807 534778745 659017376 849467673 394881754 628474239 144377141 176785883 423157055 266123566 896612281 337727586 735576336 442760428 232138731 830060602 797327951 377896064 637400960 31899920 610195130 340412431 991253023 734934792 432270411 683547671 354080556 66671849 931346293 227234199 342303360 242791580 614317860 286791066 189141993 225955912 703733955 282667041 884768817 354011464 452827661 548363031 602008761 499957690 49377260 33298880 815039451 27453729 773915590 41099722 975305637 969167090 465179615 173608319 432943139 52400710 751798832 367495724 506182618 541937567 725013618 44816216 181224362 322863854 816993185 89554090 500573201 434281495 398979311 574127867 150659673 349815300 727036442 772969099 121895677 204954774 957791499 725174876 317234311 99554815 679087490 782621955 335266101 558007900 92339493 397869027 64066099 889507029 614307724 332837582 942626 943653632 24009175 808525022 143637102 178879539 513623625 160208923 859802391 805993523 614235267 165914309 409119262 198382672 727835591 638313186 553303418 219957381 753635890 196254045 634292208 626190058 130875338 400908300 576699133 771877095 212056999 577208326 145838129 228323624 711529889 954314399 336677247 440342969 810012436 494328622 710026423 760171967 353398803 148089023 175766507 435601373 165257602 340417016 715632911 31954277 308408729 185659538 986967730 22210985 715175234 143519043 711686100 86867728 86196598 109878551 959833426 663122050 402129068 796361240 711267827 90023187 5202510 753098415 236605707 154642007 837693879 614920828 537767726 280161443 632999710 38571300 965344894 43033159 279287351 186254480 186904617 67800291 205426563 566161082 530019994 414856482 948977385 313028833 56649917 851943260 102033271 738792191 963781418 260446653 254158630 92709820 975790563 557065855 309015710 675408550 274019051 580156954 481990652 483604682 990811060 528578942 736570885 206444825 758431396 312929731 921789477 854388626 899201509 386830993 383763820 464087148 266295082 130886465 474383239 640549215 407445134 913990993 484163034 339480898 500170770 846619456 731532976 936685637 377520464 371986802 416690423 546080970 729178310 589419929 827261721 287997531 964806353 527412934 223052808 832448972 242965104 91972757 972633152 956647122 356461247 845574966 178055418 940585852 465129039 336008909 544931925 359233691 654505757 423458981 541432144 837748132 60093132 93137748 642697558 22887668 617017915 645029414 995443773 391732670 866684715 3238849 71131021 583407465 819783843 65659163 152490936 592529846 242625030 866745140 462660428 795741206 898938746 612812667 425103759 319710517 662717714 145267660 236177355 763808821 600851237 68731819 753374255 870954638 438567095 798431664 688517971 735571422 356921986 982788377 851899092 997991031 462746849 569711276 948821206 60372850 935931096 847171569 786834225 84459961 776828914 236377629 340230065 293570501 216623071 399292697 336491304 258789201 335901343 777679822 484824051 975798491 198326553 885785861 613713309 612913481 490339513 150280299 680074166 517957364 997048780 901389571 27588481 471920280 872666215 244083049 951611125 603604805 213249854 509249621 777535379 843363319 271744736 610047138 199407196 185406651 830530782 303864908 325223488 849534931 425670856 516836211 694032619 233087067 880728205 299406051 572208789 971582412 150592540 838799997 891393614 58735388 956220895 399327659 307835651 682180247 743117913 2029196 890447394 911268902 129668551 669039765 151051745 748263016 329970780 372798748 156212048 787563488 944217615 234541531 577961681 927981705 21486841 728457325 564970308 879174381 467176505 746726903 846658176 761812908 231724335 853869737 601518413 11814067 846635272 470808530 586518482 10015578 528707170 193594927 48551710 91442637 416875830 297873919 345758469 610128592 465165765 446536251 600806611 183740748 780724109 744450447 570154837 132453465 625035784 844496919 549706343 866812066 567034044 152573973 585397211 148658130 568090158 80314793 386023335 400475771 768046997 298127213 49513284 931129487 960309570 557356795 504610997 687996023 420226507 772912636 577887236 484172497 231715690 325269509 759210463 941939070 881899130 636740411 443135585 163098873 910696569 493175897 807861728 857798752 679790168 802385526 888211297 867290455 961483957 248357365 759926288 851805776 173843372 960455054 308015578 312897443 576258435 158498025 174538472 873308098 470189962 14017242 307475413 299858520 566420192 796278425 214309134 28287879 631886847 942961890 931187481 185431113 545903747 35983955 237171569 506758613 363377182 326647198 834973644 284012921 245432461 762099161 429331109 855139240 816620197 643306317 453565979 341073030 558255268 619964459 707223463 18133305 612262784 443605520 830260040 751014239 63772776 953206199 895147459 547372809 92646051 550916348 690595053 829160872 873341508 486689255 347164129 362973674 629413933 37086912 462502504 926581316 507909319 523707806 28986777 999458952 342811425 429914 667334801 915418749 649647777 785862524 316295841 865243814 306347350 228437374 952075550 568456759 518467688 639661930 71405124 81639692 902128192 881388651 32559546 364022623 145187396 982415444 975787315 718366815 696790891 395397384 91560876 533077060 631756389 807825900 506593212 714107309 613148956 552983032 971545221 780837190 50644556 821570339 524163447 115584838 839919426 905093903 987227053 877537326 967566071 648990996 12250733 254844738 640191302 29554330 771936813 655349908 217667500 827457384 753818034 393163569 599231318 208097114 351478080 427420963 842564932 801047573 926369348 643011851 549299810 893291850 496930760 127981390 160428303 33649835 2449769 804885203 693334998 496821289 83325941 468485911 36629838 35682040 111897788 702058457 505379436 911498197 164239961 744215385 602443669 568985571 300618836 134210463 865491192 753716679 159085619 47590159 866498245 569954442 794638679 683765397 636656421 34067821 448683798 462443784 530413502 910839168 491462101 443146877 862590653 775313705 941561610 573434161 599659426 340689868 691807496 634958949 557393075 834857529 890320052 235072568 727821222 936786630 504113269 379744719 842722800 974286954 244726762 512961080 210852766 855633530 418231582 367713698 237109362 740220538 540487702 282380541 421812030 699610527 161383169 470611472 604056375 375698535 312537236 177420924 652823751 522685935 950568184 426880102 462762356 596273267 56216169 888871572 438328547 775289507 810672251 70471771 613248842 41211275 56328976 622881769 711317252 759627555 517469434 210544514 832156964 837178004 880384876 661935320 761857358 42760301 370183847 711636360 373128843 811113189 411589793 571569998 509537125 933871341 152633990 762851231 981319332 903942058 589693143 109402541 752037164 680402060 938315633 802712742 266028228 558425456 580512517 477106988 654048440 482368852 953728838 185831542 884042890 210851882 135881786 521291167 327433727 684563107 646677704 396225601 362419869 694087228 736397403 706457272 568883136 483308466 309304435 936153479 349643299 411287959 59448163 524054165 491076539 925080429 352106561 110883660 75249664 262621845 881395970 753861874 109183767 363574250 972390864 807245594 651896455 485018777 677428106 431723344 800292519 591698416 390480034 299281239 512040230 71518416 545435638 141490146 88481961 511692180 968484036 499192143 356156990 915719028 321082390 457727913 257713078 117391455 822276649 63943360 162169604 41515767 970102685 569263320 302802360 220790418 348972447 871991847 58782534 710412884 396209771 384856815 472082729 448412307 705915406 561969240 423575548 597754259 117900281 566330791 473021560 900918956 836798174 399217521 696796802 824916359 50329509 544387656 789126993 364380974 810450727 859272540 43751761 379293395 567077729 739968080 945409572 187859205 138104074 41239578 565009300 599059245 33515320 532366720 316749528 746885001 790664917 855885367 357667646 236055860 495088286 328740263 774376926 106046571 908801449 805380178 527768936 765944455 200828974 519052241 980584865 641847720 456919779 850459165 919522764 983232036 770970432 658220959 219194816 772081719 756446412 694633142 68655810 469124273 986672175 254623898 875499845 332473372 877040582 473725609 452576454 254016969 699260958 873682812 546772656 793332033 243496904 213704436 627661501 825908495 114621085 238799885 175354610 309876820 298298638 307659291 781260655 181966386 710498985 420260669 966656844 379945901 81922287 759194418 345731171 947299456 262735202 486898933 9551060 637579931 268473462 900301711 745938180 558384491 129439164 553881380 97099839 527116267 185053604 182676966 126639863 487096066 260889235 377780446 916012210 507076330 257832673 385242259 151798533 105405817 610929606 515567573 402383301 35401329 748654262 940758936 734107016 128388839 664085197 522070812 423203127 626433268 289568416 899575896 773482362 661180222 816871607 812915876 777062148 801644121 986327173 571739754 711737841 883930394 489130141 756476845 103642080 138740657 162585649 122799130 191413426 748878634 526917260 832175950 913843498 275926125 310611193 118157068 722445819 387169059 243212275 134272971 836666216 432148850 90225055 525858252 84478528 646121504 445385647 303228315 228316650 799239310 7168868 928212487 569960293 280365291 602854525 375941731 704234291 274778385 25453805 652984676 353603760 5506726 946885316 415648227 997284844 102468700 557713275 261293822 175595034 384258190 45668122 204313422 954160000 54686669 406743099 504950040 129143183 84661967 152229890 217430834 292129099 310437580 53561914 181913005 250440154 165318897 849748395 399960168 995096768 286857541 671206358 68676042 27116446 241204571 246202477 35770345 378008068 462862853 618724306 651999662 376168120 945587354 503991104 501437126 742809161 677357882 545908109 992882277 174091146 164211853 622401785 372215940 810801354 202716702 145302782 61774403 626250691 437720809 181618410 146978332 284809095 718052424 866317816 723579698 35801771 349442598 443291667 864923954 693395946 413998303 27506212 739582119 689701620 398688995 756299174 813242370 112464768 110505239 541757372 686498295 330716075 857918984 527527620 717996972 505972813 996604276 271861215 651567212 738410255 160357572 90134738 319882717 888089717 119815624 693968047 346310045 431541151 959497536 770705359 652269794 507532240 724267955 636208234 532898500 750718285 567649264 919971819 135767092 808766077 753721153 230473796 111077096 680774367 635356677 598866395 132078307 516542580 20812850 666215245 821809754 255210499 506426117 666032094 206905406 189799677 170451240 800119274 17648555 985311629 704194444 238336542 227847779 111990234 259514534 915024819 903013841 112780473 931101114 239534647 246287906 394755478 288027621 91960859 564166042 754499580 46717877 707926423 902192221 364166687 520112950 715383481 983860760 375839560 656252862 403625112 650953312 673423305 815248642 782661451 957023267 420168992 198190584 190337091 832214503 396875308 593217239 66793229 722866124 47375186 621134836 558863512 779135657 420260532 857262335 814612312 537556596 293777661 986470798 840263691 892984596 544083533 252187318 436614662 45631370 621144997 114768259 157571999 190192527 747813276 914153210 478052345 649113761 444076987 90622640 525947391 100024824 679428319 242453467 601280217 420917829 657165436 282839970 453725144 316680926 547536267 219453138 436806955 205760237 170660948 801473471 862287319 766476363 630479673 103281546 998764794 312680576 484830472 891034480 795221675 649853261 826998999 606085819 293984644 560349321 704437964 468303747 593577870 439498567 588384813 677970931 906273756 433550577 169929760 988183235 969098845 548807438 352516093 654319060 521754552 933585902 224984395 217182116 250452639 19085609 853223279 525272005 672825165 667460952 658776848 535020544 692541284 595697092 141600369 784591973 451425936 886818406 804076685 793220148 627604502 918633596 419534118 579763397 931790433 322564518 846689714 981729685 776408985 646437067 872564107 48943490 325943407 788416832 852840614 878925893 280654756 799486784 535989954 920277611 43127423 688902350 451773194 120194549 491747347 149473062 645570088 950256029 87913977 323003161 893121196 837509029 464521980 43695376 619999907 526747148 268333821 866931223 26136237 968928156 319930598 78486913 672276577 947188777 203287993 488139130 309075224 165237733 819750445 226845184 476025589 479681713 68868816 417302526 158954323 532187557 538308427 237321123 860796094 902842793 922219438 456444810 76165809 969583541 472394983 924598719 840858062 260554562 61189806 845554404 349848926 527485552 612654955 121023462 515737422 486790467 704751068 301707445 250314747 53001178 566348457 308461697 954677309 338683643 323508319 300699509 705595451 192442944 511498558 914395130 499110687 207041794 644609185 558116862 427685196 344194051 872809831 818767055 726470204 770986444 7038392 592138600 918114092 308260696 856974854 457495481 705324690 991892879 312911303 773780338 669338094 401500054 201983888 329763087 733133921 944301897 648481646 133765497 510840196 225264643 826274031 170255105 711110239 350007698 576464092 89402092 294004052 64563284 433023692 71918503 419252798 192733573 135375998 507094604 346106370 675336529 5848601 887177301 533856500 807945460 990113200 487966671 530728277 3467880 306180832 471350412 646498714 924452400 938083403 583656674 456468023 911770248 42208884 890456854 160985791 469214198 503562538 173687876 292410154 191949754 166279196 228711310 235813400 891474830 978842003 534521364 693736078 115248691 257003516 786873670 114871129 616799178 338057048 430348600 466247210 669014094 270802901 791666462 900812458 925098618 374678551 730043402 431082957 63002758 982362222 2200485 341836764 615954905 552177378 589924994 346179489 700375349 888657443 813082218 819127830 484922829 382182194 479968076 587493283 783995160 843003969 302244386 281644877 248198644 665660104 240364303 277730691 312155020 999890419 151240647 929060918 348325712 420588290 782679376 338650730 931026114 401399897 309820779 421023674 892915594 90851286 156977599 458596739 672058078 670702412 824033453 585419295 556678477 785359039 60674166 220268918 517263256 438728869 56210308 93424285 982087583 744770475 279464226 882068257 835864657 96415444 125577753 25681705 946208073 598064517 557828095 184363839 965162096 856417743 382233354 526709247 78934027 342354306 355101747 696023009 947219102 73421667 359612299 534920280 371617486 899329524 813463316 657604029 116928962 942876869 596341429 607125935 858166317 333250964 203684198 576134512 628010241 453218114 981496993 169181769 180673865 192298208 394209555 166413062 206414977 282059669 128986729 605715063 248988632 288239176 720363797 819773675 526737761 222898139 565278169 170563946 107419891 4109785 881983999 258911307 510839655 589081969 101361638 168641363 464383017 514556320 170754495 50144040 250134614 895663548 630322250 615215710 636323497 976028149 843745274 663311280 981598703 67388611 740587453 774312501 419855260 743188025 984267059 68084774 122849573 157403461 262320126 388003117 938593779 653712872 641440162 97642920 958822028 718150102 870825626 734798832 112852110 849994673 396475975 110846369 192379251 372393033 848717089 232569050 203399996 755756054 577739755 879328206 655983891 292283185 771390398 175996492 812256268 693566255 130258955 859580972 722638660 607429967 318343073 958837219 848988637 933313027 493399551 402998895 195261487 543513757 371732574 235873533 624333884 450859706 750762046 126384374 239770176 283801125 958812532 33550704 148477104 520449147 779393313 325101100 627114442 306060714 505700868 860210724 786922568 963814346 989082416 204265970 92841428 654212041 534644242 926639354 357242033 14256411 331897230 311981376 958098585 593128374 695445010 320400818 937225306 576313449 855036000 945027242 189288077 911466831 443587287 91270550 299745297 910360812 26889727 625611433 263139280 557032837 722466417 264556575 830846141 88203708 453817183 678548314 223655935 156801762 562583518 295063289 193429684 886049534 41904215 678101094 223168640 880178822 920156218 113477169 805216946 610422224 147505620 700829252 492567684 301496909 174630343 40559302 387973392 766921508 594316908 597501906 182210977 39764153 480137001 62844554 801648707 969994858 333322443 6060841 29905663 123801625 96352106 206915791 250132901 680092120 16043446 805111171 876610193 656462310 576907702 280730295 964345368 322113221 297690468 599244325 482561807 898522379 796595250 118739580 949855542 400867577 705325041 260212545 868072699 830052986 815470106 980193569 857015541 561825071 457841659 634798791 210667433 735675309 552858295 325884508 254851867 404383098 148043838 568962486 288000708 538569257 741355477 114832801 873577414 276861185 223437209 588605042 167878992 683815291 727253932 551089534 534293889 732376610 419723404 804650168 669397394 495894066 341866379 497777328 249592692 669842950 132388130 545140895 573363672 356245088 134045983 544308394 801546770 228492226 522153659 605331913 772601049 95839789 632172626 197161812 617997225 222309599 938008184 486960662 506068551 604698712 270616358 848755485 673399587 434995436 187566698 843248401 499813870 65886704 128525437 833040480 476682412 571279185 809509843 668666870 989220775 239886725 926950555 493871236 578870801 993752338 193595485 235022305 867192331 892385355 771482117 935877365 778540499 664903555 792504421 575823200 674694409 435393238 685181497 919091807 925643292 588959708 929732646 639885917 412212618 512461208 95878309 264719618 365064558 937159146 395848494 876698870 640755876 413882890 160780445 403512854 782811833 903794519 579780231 586752835 539063671 445503934 202162954 596709019 278531647 195178068 27620261 487462235 111503230 955746250 682888964 635260924 856805480 988056853 38868482 771949001 108265441 193237160 282474774 64292849 549253218 957704353 284326973 922401065 928837779 957794818 328157196 23485723 13161659 600984590 916067109 244992789 348198784 217191001 456577416 125466217 726597878 561496587 972028771 610026914 794835517 893181828 775143943 669630327 630894941 691174463 791874429 102393986 197588367 451996690 70503214 709538064 501778100 332522469 199485064 927826554 315701503 407624508 758956938 668139813 492802110 180199725 83366641 826333178 462001537 14364966 631631687 638613020 898517424 752905836 187976835 637362137 518617201 320931518 382188684 85641580 174349122 794701462 933178665 737354813 745340396 797204982 377642086 193404750 887342820 317500095 879520278 853132754 919816924 865751089 995180224 704401521 421814251 231277526 879606622 459747654 438469104 120173300 369703315 396320479 756294494 109125598 936994667 899360008 92562553 16585890 272563577 624178728 791937556 664151522 676848430 742385531 448479911 289738640 244940858 60846122 496159352 81913885 579203919 730881789 648791416 420728638 948588996 169979985 371151119 339341496 490320192 772577998 483346041 832163604 528603774 57241574 438562023 275344592 844779392 284731230 100508316 428399483 192083529 10536228 199392718 495382288 673442050 145223110 888024818 600354313 924367888 18382046 710016648 384439619 196285989 981976849 660316940 793394583 1241373 406645602 192897626 304443257 255166841 355781400 272091817 812954481 833002950 352315724 824004505 301570864 42575841 19412711 204720849 797752903 20588530 944750566 583838907 255408409 405496266 937264655 777847548 566678995 350680931 537389764 142789006 607362546 289199333 310357453 725481763 65569335 700271655 267992993 665238500 945103112 230853513 92421159 546019325 778397027 222058230 311350107 279438321 997072425 993026386 664481214 115022731 196937346 228914395 782849407 559458217 19369195 856772969 498581710 657451204 813415489 222405795 513207206 725069828 420074739 583678474 613105935 657355717 775486020 104104515 975415173 458790941 141638012 287609669 6882071 504421048 74767455 936185615 759307044 777766087 615813346 174585097 378104740 680541699 495269097 916667203 372199256 149010175 593505366 327950398 34435154 624786316 104575304 21661129 931625975 136496037 401032256 938701332 28681595 708244485 262742904 103874084 872308617 254884190 97224649 982017071 795563796 614826171 467077271 962790802 290507159 922944086 298073321 609591996 445306953 456240043 914938275 117965147 740951419 763207079 964824306 98629618 787609684 723840373 543728597 603426498 102512449 764660213 252513525 233922573 813971140 183231595 806452415 477175649 777036265 947733041 502828152 203960846 169989078 454327080 834183185 399875873 888706260 530660302 423636101 979705969 246099747 288688532 34283545 813042550 281846537 420952318 695528685 258475024 684316909 654841427 360826468 302086381 446355358 258131661 898593169 719221019 666358978 727577552 992481724 635774874 330291062 36437674 389200425 820576558 461224004 350698254 582935754 955933846 416868448 861443516 668427490 124954139 221299644 686053137 125486609 714014275 566984215 879759961 848089123 843368490 175871583 324942284 438080304 479643264 668595861 881686365 878376535 967228348 184445620 145920009 273030336 360566349 76053958 911410584 373350828 737904269 457126289 586677749 485271389 658691609 603277364 827545773 569467248 277406223 90930901 441585141 603862882 911798659 612965097 78899173 308720487 97597408 298583890 991638929 52906233 39455259 319596680 921550066 223402388 875569250 179680146 228606293 620595774 743713682 677271212 870116621 800420014 506734363 888952362 59337014 236066330 261340729 774742873 223077111 441170655 477470950 242126148 652151248 938548238 634831062 313523720 662639355 897885958 291482176 735370792 428910546 823440604 21302573 775619084 373917561 667692180 932509511 672534824 640680944 238026021 683903241 338738603 601048591 183394855 941964502 186517878 818005083 874746048 410187523 555324738 171591455 739441337 150618846 967697764 480347791 160553670 111736436 448454632 854968468 996619971 961158202 275890017 272034332 746729477 141713242 7963284 862099412 181897872 908016036 320245850 393751201 716383338 842778128 426135851 576712620 828887109 832316626 817891510 160427178 577075898 789200226 998331586 615379111 742976892 15993813 135590526 502810508 472636728 250365881 956235294 995675988 2369898 375866292 442086946 472103923 241188205 123327872 379839138 461787997 178664608 100583288 343910719 128520192 404810827 424080796 751815538 595582037 588428491 40762943 773924547 623217152 954432971 691214667 777567762 317582904 798462215 265752746 128901432 870081215 600853750 810891142 273175291 692343088 135247453 408196867 74442473 660616545 158710895 310387790 764440422 487440325 135070217 200694072 941860095 757641278 886542859 452122084 499171581 801250841 308510266 347287604 862178176 263446211 340630879 444939331 267092548 869850348 90297852 596214921 147099979 37753206 974691465 307600919 79692289 922653967 308239052 10117549 765812327 394468474 219680821 71003276 389589905 48508881 845063882 789655717 122108102 935175507 404782361 321465472 264229855 183900677 14279466 419320378 432240073 560498161 241106097 40875773 41615519 256552131 604382748 17454548 107830997 733494580 292651822 178643815 913868470 211204228 682872140 551779694 694016089 962462420 761380864 733652524 43466800 931269136 667800085 212391609 982805248 623452214 901620295 583364242 699123900 807878447 262158519 451337273 489783263 24941020 488663212 467873005 275213969 534473701 619298440 85797341 714805070 961675142 17552142 643024765 137210955 178709401 828976369 489308981 207259249 150476593 913943515 496655003 103525260 131142889 539984811 537687473 384854100 267731165 966962447 106772752 187450722 284864128 952616273 100185069 584482167 7384926 366095540 354272108 252860009 773030505 159651307 899083497 346490956 499303988 176674449 710852736 589147914 626206829 538509132 170556405 69162837 439346534 853590907 488204274 838498039 439504472 720450517 954940348 503327874