4000
27100233 984768047 407506454 734905638 238677718 719303235 620899250 4761280 873208719 693076067 110545268 652205710 144440692 805093624 217710976 799018323 525185317 933417549 436084643 549827199 848778180 656458803 695746076 603728364 328500840 390666453 65228694 331543502 259590483 785585241 552941561 504649075 219516605 427715894 519921033 355385100 454949303 70138713 680290693 283330128 656618682 500108520 391039312 355358079 983368451 821835833 45845788 201499643 744408086 854348500 688491658 751739128 956368322 26317739 662439253 185547198 463526949 930494732 30189398 376753474 577574620 501556906 955398607 392502597 82392752 539656154 707258355 205740875 517873633 492602502 824096344 439503574 72415993 459026349 890297328 258567114 474603531 780912442 404990853 249202402 468159113 195999450 443876659 470687303 704486066 496329438 55017542 684338377 922615602 750065355 807714841 649294382 943523848 946323737 858584255 856890174 960685601 324557900 330045476 281147417 204927848 692128458 258479370 89402460 248824760 193681896 275704367 260677957 745647312 91180305 755877470 604031144 631741139 216293023 799555444 873262270 520298399 968794082 1864266 14771284 602706808 539741735 179933136 812489610 182120454 473304605 757607301 373965164 723124838 369167876 349846828 353241011 903190083 813300858 806918708 265693981 489496510 171459433 18498474 119337239 479414732 248239711 69523879 878644319 487052121 388033892 927299394 526372529 883926755 288065923 587032596 29971879 887347987 911490662 435620741 759797800 332231557 565376927 877353291 923578640 462191656 7731026 177986710 943850584 180561139 86989266 592996928 71491161 813181089 332168594 738301729 644396389 481107953 737047900 501142753 413958414 486308116 381453922 495548908 79192046 654647235 100168733 385996690 2745409 696441898 733985121 577453167 970299248 240520587 55275969 33416282 234107318 267188918 888936518 427562792 650619844 910519736 726842765 928269239 435424588 943245597 290890322 653044139 112432150 599954507 978363904 997389175 787218532 976986880 151954832 289144893 787720425 11865256 630961373 164261691 842163306 428185497 306760015 620489041 176630144 344774405 859384581 938259612 612542531 352783905 498297677 330207835 128406542 485274241 418626141 163998253 301742430 158768294 354057814 988933323 317624592 811691601 910652956 983668848 907382180 195471663 436859424 942161455 996678797 378774267 513768848 436373884 801677630 282172848 187395857 719561078 219308931 883651387 308868779 851184999 689465469 884987341 365372925 288968508 873393246 563936817 202888996 346059403 608509097 156196031 565893791 933808680 152359843 583330319 783921961 976607091 579655214 445460274 21377808 984133328 948086757 143139941 245326103 137074081 354362521 785119454 918988636 159445524 888718238 332034285 713560824 454995903 210620823 121372581 692001475 427938350 111127628 589038189 367518166 30643814 931349109 191253584 396610065 795998337 538112832 272911007 939511314 103342343 875804042 767877140 727697367 657264424 55458290 956631640 204861701 233058560 994845703 720197783 607991913 467132253 458064035 606672780 454010714 334364619 992612278 292879258 153656079 624915883 387271076 282781327 104200909 315691155 815025552 281797178 698764153 737942664 951875774 327104397 28588415 89770833 16924980 53785296 805474332 845759055 46251723 680748552 799321080 29918681 225194895 444305690 751754757 42740815 980908329 244211166 766556859 767741130 819488023 942961537 203623635 947979860 732596068 640425770 888361050 287758810 428054417 401450306 986708175 950351462 98174951 776400156 950319123 419993896 957662907 274914303 901420128 197118916 577386748 119324234 722689062 641368940 555062516 469565138 476375577 752426803 702906525 893675880 505355087 261932568 440761093 58465059 147643961 581984219 334602992 94021892 928710913 141883299 515898148 543910121 376468028 765679511 475352498 282654672 724290402 940183454 310052816 398533270 523843388 809072761 865507979 467618171 1634922 514118466 519435386 752119324 896618256 264396987 797601705 954450958 971327500 609983013 164387557 923989433 258964012 424845103 26764461 200092547 38480376 969315435 519696427 359632804 910259855 235216818 939673401 170196774 503577967 530883019 275472626 768100958 589131547 737713639 228333193 312377412 505280990 868756029 101899446 537982865 491925083 717918099 172651907 786898607 662344972 17028400 409584613 707749322 573687689 320428802 288259760 592779730 506162523 978059233 108329452 471693670 895602116 736019089 683180291 915385894 732699747 996562029 533266848 950329344 853608399 184681613 530278621 961870702 975290431 909329126 283773088 158961044 408656051 992261015 387343002 829004984 716728180 384332713 742133229 574785569 684266246 89008958 39641098 845229301 977133232 896808196 241042481 681386460 211214873 78257455 143532908 791570154 264575106 148566784 771361174 673612197 430730441 404546808 712453433 368976485 109422734 456312050 141025924 649722493 696254651 110569472 708988806 967285257 687945458 83320256 138691069 165806410 101704641 316025667 420511818 858784343 786351812 100052947 480929261 265834813 468891128 363206198 540328917 539744345 223721181 668448591 850947916 755604663 680795246 1185013 336232485 170345902 35473363 643751154 186200109 259759987 523300513 282365811 124721873 701709384 41453604 794724997 303247482 419174472 906485253 563262699 977138972 429712643 956409339 564365586 40010269 226942959 997213590 478450750 731054087 575967194 878191413 477786043 199759052 485139082 393990721 484667224 574440185 588158033 708324058 839411393 538225617 579983437 203787897 736215705 400869501 413727070 983412675 881602476 993583744 359583378 725420866 247842659 175817 634994963 356883885 900804523 658193033 738146326 2780717 942120842 830483845 944200874 49445002 917886013 533360955 483149190 333112188 211889308 798265636 608364238 901817334 417095718 390039402 526427687 229969173 777126957 972602550 204760451 994557476 483068974 173681291 835365627 342875834 417087876 812952335 211966693 551696747 826895839 731682929 259693968 685797283 286498821 254286231 454951123 508294217 942588354 845698013 593972091 770250495 797638371 465882243 772618823 89085579 482335343 834656523 622445489 884699464 240739488 229798125 521217256 495959357 996046878 838069083 134622678 17814119 276152661 434140325 668604406 847437915 887627672 375883750 460216285 323638749 530541436 677629067 282701253 66428927 582438721 970065525 988013443 968480111 425861281 867135701 42959814 773054605 76266792 690178550 537118907 113855697 689665489 251045101 705412324 500108523 16434855 23082825 311580963 498204535 337914723 389503339 90668673 214612862 737306688 658120214 421683350 140504561 34910420 254313171 151698060 398552862 227531332 731583864 406136596 383246372 346023455 922199931 805575301 227790057 701143384 911294987 606710615 118317801 992688571 524712407 62901563 900681718 780472678 401274083 217889048 952373024 69787229 701091318 204580184 217851533 474170263 339447346 739202963 350951098 193336019 719741817 444887908 149310536 415339011 966613713 346007128 66819166 132392313 91614209 103345696 681746407 417183703 627612072 938937424 344463063 902015869 460887769 83846438 11583583 879626198 134709639 794177240 337142008 684573860 695445329 668945471 674458848 49666293 727272724 675810487 236386056 423686546 504300519 864016481 965305383 1543115 743870367 983854549 754351116 5558745 917047558 518535813 5782099 885116835 285426253 446321533 833276129 319762497 846588998 983551136 78868924 464100321 988246365 385238277 659796063 535328720 810075980 204914058 544238955 483986935 199246581 942728010 274229207 916771105 798066007 683319228 550722934 523278001 705174251 932531975 518926945 63596307 866230033 528605853 938027697 109144 665278268 433209191 915167074 283713622 263207504 196320690 717805466 52755058 962616556 940839113 788531425 664166200 343042440 262470570 83923780 146575229 237167449 53480546 91754323 359755407 27536701 135159791 479175167 285507887 534577151 739434718 147863351 714443330 587497947 894853676 516778198 404802438 767443691 483081859 153301401 467163707 2110333 346318811 922417292 350594415 536793305 321353148 942380627 958895866 107679633 641262265 10363170 326997652 107763654 389307320 698003442 18471787 540244557 565423459 168995992 194553944 188933060 905666461 134645153 983092350 314763712 175662455 896072669 836916367 733725385 409207711 32350431 566022627 885169699 460845428 454636287 469756842 264118479 563989601 850763944 230953387 240431643 324327603 834134063 887927464 843789016 234950934 535351745 804965724 428142965 688235881 187531793 707363118 871638927 682556439 23724302 7413582 54229948 967967670 42020025 579779071 331239485 253183944 895997292 982402599 448772446 849706520 552358951 146791562 82309276 13167042 420696233 347317714 650109338 637782276 192871497 681936096 914366008 919478631 381034114 905676665 408865074 433941750 188146654 394981726 510655198 510827403 133614585 138254151 397158081 192878670 858161589 440078942 342892340 219258927 418272281 922837443 195645890 924695831 870551466 409473355 217413803 201863493 884877013 343824515 765302525 544518182 291685873 569346211 905246775 391192275 656516067 244832144 651932095 197031892 992821589 462398006 249395668 450042331 595940587 759252677 962164452 277710615 512168591 9108563 568399434 226437637 629449984 371995460 757835455 303708793 102121926 376614094 737315142 634037994 262033942 704285016 364530309 158462528 74216249 443467718 965505456 115978660 996175910 964785119 490599019 468308578 542393282 500631551 381118408 970193554 703963033 722888379 511539287 506812628 68320834 521432597 896450468 445688760 202910505 716298807 235373500 622916351 819553628 576456247 828200340 761859712 356988450 384151442 107826208 472965184 117062644 800944353 112639180 566685152 101739409 208203814 537622710 319280890 819180869 153595609 109282835 700211122 633931550 227492952 134742130 495632549 903017232 10577840 865558802 279419710 341408694 815305991 118185537 863451482 883590504 929365665 233558222 610037597 98015188 569131637 456391426 505388283 190794075 600523639 93359570 297368099 989996987 957510220 857276635 472595681 11574315 439536997 336402343 430394663 360045248 665801778 24594453 143570683 328989396 733847920 803634220 842201448 432999543 153706807 568554774 133824153 743934365 746273227 473098783 838848154 958614124 597068093 807091929 930414059 50334553 487089929 71512120 99363408 558646558 219147803 74889281 785126621 818809955 792793723 22220879 292910550 682010928 154989753 945393595 137482535 51509714 446503900 897738136 966220464 486207859 67958670 364465631 555981363 694531908 410101346 89815880 370136863 934311379 279406069 840764897 214603997 259334949 229942579 620352490 161018914 653589226 884327242 118805133 746714134 630585099 371469502 287925660 398155215 17274328 740946343 586686084 810460084 274809967 663227675 728897251 718430649 142337910 89265111 373733791 971205240 734041640 423498109 340752448 509588343 168434224 870025450 829990337 98677747 125056316 192794378 319744482 755686819 786479893 64356678 576322526 103023410 746723972 334961615 592602257 896165530 153357576 926827834 798308310 524959861 62009043 14088662 679650090 35674610 630196644 165387182 234005742 466186368 579083266 834250371 362804529 863540380 402399507 341065207 355934644 585971376 254510125 847903597 712325015 695977764 22052503 38627675 360392027 708861380 321540113 175605644 502239276 327890025 411984793 485775873 404383082 706575352 766077117 926157120 101167647 573114265 768355772 797216748 558245320 931088052 583164525 828982076 250166816 343254078 851159252 293908467 178303249 407795726 984857816 314783824 921915733 357897806 476475930 987672860 627917959 277929240 671954589 195027631 314473087 159506203 674560790 703262431 837290886 368823599 673149390 956644767 882889326 426263681 278616355 410306180 942404119 579889264 439035440 70798502 41468853 363284617 95022947 602315390 349985041 386590753 441167351 344529970 10054574 805789278 441163994 798459673 864619038 720168289 677050689 788498864 116445750 970702931 620271085 81138945 147840476 735012551 529191686 547114543 112678378 530704358 465007191 546742748 335506818 481922566 73825938 331609309 155460585 387289817 422013086 700513132 982805443 145502312 793936712 441757395 889946128 513943127 312202044 631128856 187766323 907588088 197310804 46017359 785272158 226861344 725123839 959715939 851433031 295947567 904763592 418708318 177943343 994879717 820857869 610473399 568254357 625379576 160657022 150139850 333382764 490629606 965309482 443401629 579391079 420349883 3555977 849911171 821264892 654171110 501916558 602865019 843079083 383048740 142961398 830255633 666181438 64157115 468519307 329838763 707789015 418172297 600862015 503034245 983447534 161299152 119412183 336769442 558600712 692804477 975318983 457312248 108296502 545794178 751265636 978231806 176893701 219553800 183003470 496011358 255071330 679804373 131624302 100796067 453588553 937380099 56409883 994269104 307105702 227669249 727777016 474945583 954974577 839623529 573469204 242140230 864135874 552798541 69387939 155892668 981746224 469552260 842674417 372614144 965024482 672873102 714942815 143738327 596131578 249292398 80313400 113229956 662607446 814402864 982757154 459361143 816492713 348030362 129172145 672671142 287121559 880608292 317166431 856061111 314170220 198222302 745145801 240862415 891629325 867493256 285979946 457531880 747619596 360653591 744552833 682167918 7337515 350191420 388450624 971965414 616578020 717998034 137967216 679829859 529579770 86964641 349436732 404542959 741278913 820455711 736091180 228520795 910498474 226680617 185106413 641449794 50920184 946254223 551937877 513238928 800065514 157340719 256156925 681766516 608544624 315345418 981518088 209042455 170580963 439125380 936895337 133383814 922081038 882722513 210425466 928444052 721956699 219619790 876487911 920109122 130542258 659083399 166812233 728245145 476245802 647639109 759775897 578363918 613726294 94747627 41526097 795898319 190853127 758701865 268597365 567667189 701124191 830041568 517657383 828241977 95146410 894869006 524473194 909973043 133358570 734843310 274869542 410838430 333378441 498874001 467107843 581678071 937589101 44727453 966479321 454117734 972550686 507002796 976426164 739844081 323475342 664892313 254476015 561801515 764529505 665934092 264903695 682164336 807593895 481904017 866493880 329890007 497800221 205992356 373190434 295899349 648521362 236356888 820048492 207700984 612753066 944289592 527060456 98363745 904829976 784018619 196799753 814361134 71602605 984081414 409710628 708060886 230536060 417489978 309786174 437621238 564511623 146754722 679033053 189127828 231574430 421554921 511458660 991888431 675514366 181423508 28503928 12256545 532283462 853591016 797024505 907941667 260135863 923012955 416287177 834983061 812943817 439418222 455671132 764903170 754464581 720262700 783948642 596581848 987565909 323451892 950837557 756828117 213904246 615229099 520354686 954454181 73833311 284882993 534198229 294122824 598322222 47120848 457494713 177509220 475634978 426305017 795859612 726393068 950854358 520909109 379355907 911549534 64420632 356134526 571920225 957503203 616976904 659465179 656205119 391805304 586980444 828931779 752783359 336382784 286589717 502927241 766548928 314237542 461157446 613743956 322271915 3663242 963187593 218273418 25979230 747693638 329843426 689036046 394025153 565489142 172852631 209338621 867000557 558612225 740152608 81826598 943839276 465897066 43923097 183037883 701985595 816670033 46810362 990144057 840652112 716575622 5617912 516110927 761379821 243311982 315708372 151517140 870339104 103727016 799940531 174862680 44610053 630526458 248238125 892899727 159402170 785891726 962690688 147017028 515949235 260323634 621118398 596142788 530656729 144764275 29543774 813819032 405961844 364736975 158730198 621465618 701781008 729383837 692275575 68817038 181996325 110423246 428624208 261664768 133268888 715481126 465175998 166585273 830474301 234803284 310759400 390975269 8967324 284816914 244497193 433931614 874113363 408050353 843740902 773032525 868884091 825868183 415337786 900019027 416998589 315581542 766235036 421605612 764482048 206804379 856768349 849650392 646094749 753101302 504348757 902928017 230232959 602792588 365850556 127656999 860911941 680723581 399718640 211030194 724116566 744926583 539395194 458037601 471459778 442290705 962160038 804318208 207916405 565223457 178128686 645829066 985092760 984850098 862236850 692156773 953647337 27298477 59011526 853196260 51009728 524885748 212040265 245347764 471919454 324733310 458989438 48119606 6378604 201340086 997088927 406780861 703946225 179103750 259212091 34572562 769031848 554493877 812230748 853995391 594489324 239199593 894970990 178979128 347030600 600993084 920050261 636236003 832082784 145179625 964956008 735713801 237816079 493375217 116747929 792038379 955995954 605626536 273029567 991513802 195243656 393763241 158162707 464710436 595750963 883002457 826277408 326436473 408602916 997755234 77875573 628169759 29524383 527137111 548195391 362264764 910482203 581549610 570487170 889595284 914116758 216664277 887699161 205024168 142850696 832988213 686399452 193241026 442181528 528951275 789820626 983544904 142094312 767974965 177747022 960376498 297257439 502014771 239549679 957994518 755003598 954829311 148572956 608592182 462069561 968440880 958325378 270565529 229139046 114038279 240328453 382685391 380404906 399869271 976666817 380268608 564825794 925850953 192986417 475197105 211708780 298857338 606421257 89294165 329571301 412723315 907450950 94065142 539905249 512619264 61794479 117019596 722240835 681431439 693113226 952543729 45447311 105430175 996766486 810417255 152498535 144409739 569888233 113069919 528468464 301998354 460172528 774802886 646227805 839420307 244634862 779200809 492419949 765790766 988344701 162622109 775100505 561451729 727290582 105947281 625576107 590008676 101882338 793421499 862037221 27143998 371351612 432626696 864977687 440878796 269780348 607490855 119742014 697515040 700198055 219489327 418296370 469463969 133558758 774139442 272039103 351613755 479805560 363569296 120029040 759347257 33748294 82984184 979472820 100867578 278900207 725666195 305412253 149913939 386867354 763724731 822305601 264807299 282090295 957970307 734141339 921632253 729416272 673761443 205964130 167034923 640041944 37414606 816993250 856996215 183361912 645579566 596707031 965566741 708510322 767718471 698222445 718231651 145129555 990143159 78183548 717348955 680207987 206506725 15786203 481587305 449991459 332623037 531901482 170280345 576032159 226878337 212787552 261026381 950859101 22027095 318821620 6038585 348548889 236171304 209201019 228560599 529785747 662597801 431081361 72529382 404778250 367572764 573370205 849760810 792285935 949560490 292241512 292315076 4599879 402517781 406858721 322611811 492723632 394474715 402893733 277662659 362015580 823158889 575007118 442473152 321663229 700496415 644908624 126574959 557059582 106902224 819556334 270284232 381842474 410836094 889719551 222144954 352207281 821064817 57998556 190691122 730547314 93240219 716274404 536287442 451814455 290606244 416412886 207142 201162886 739386157 528800107 287399612 595045519 32768627 415835394 623070582 159962577 936631821 33894014 705810388 703788975 229464010 414242307 896381297 603491727 513434777 425837345 626285953 696159444 397162168 343928625 135397690 76997480 943112753 301358678 414578989 244311754 23705383 445519459 965628283 397148794 881259798 762501948 122519374 652504894 227703863 704723634 686531900 109401237 207557855 909618742 187488196 63341329 866607255 654528505 155169869 678142706 745704420 779232891 404758785 660420346 878184628 31183947 735549825 957775597 185970758 295001017 857126748 297199854 987461630 654794342 143997403 663563586 870327525 492738102 410024711 880843194 901944678 756319215 484456698 817321322 210685059 751769369 709447914 512497487 184436821 157972614 751200494 204843175 258844553 385718113 717325484 250394790 475049922 575894399 64689297 799526226 941032393 75475336 198726487 521718805 926225919 38796437 695313021 788893282 44381142 605999611 190894243 106546705 731894410 266014409 261290315 491284452 717590723 408065152 678926739 601916317 643134277 318374878 266052320 794246772 145197710 807177346 431261549 73682550 191501007 757872293 104485870 8189316 644819929 452050806 802181392 660214184 695294837 236584314 428865943 797272922 401963544 598475094 208972532 326170381 309284768 951589696 744573312 510642522 529281146 815798091 483002904 272604097 348930683 603673475 34600942 238144302 973027544 783113522 584653544 274121245 772279852 457739560 231925113 898381566 856345713 297497032 493591028 746262696 211980292 302345538 725308553 292446466 990758210 648843906 933127910 844010961 964011158 908274479 19851504 78134158 49703259 167826492 895522081 594387423 514961109 986654723 943826839 305257744 24334489 365364372 943099768 540365411 699756571 866473589 390643138 690516229 974194953 990415457 469656935 154520581 601851607 291097256 437764540 780721268 509727486 803021163 677665963 121609721 188709063 314922262 687630603 371782214 791861062 915170598 762096383 199812328 492340759 634418100 174414004 225799912 159622304 237835802 243401250 948817044 241827408 531780603 581293268 746615296 47081739 838243541 511442664 544522434 157801112 116648049 893978525 508141262 756537425 45644652 395686202 189406145 236085234 832893226 491509295 887020107 213236036 582653669 556347551 396665582 129924721 886184584 878570815 931262092 768656197 297223261 523078771 225667372 686227852 169536789 961510890 495333084 258054456 796002383 548920947 105756675 941449153 691326701 17356853 70519599 661618482 73513293 341887829 600768239 565688119 88594472 702629594 677503451 104130649 663559756 691960242 164554409 36212582 501327818 124028519 206360488 264932154 482940034 330866091 158322128 928659498 890548808 774380834 604271674 332696349 152604255 428246127 431162837 566580658 982375339 583156873 802530235 354371252 330386170 823838225 790686167 439435344 417153083 528599339 628052501 597621232 171949303 22752984 703873928 535319614 446991180 225938566 316230315 288718589 333340656 56342924 461596618 227940431 564568049 13328236 853096350 874862662 31491156 904925704 255778285 503884477 659169454 151201408 539731412 615727796 468824586 115392292 666684270 487195181 26255766 19773624 661120812 440414315 100569636 648793530 198404405 694801333 742837925 312694837 631947616 76258029 850533873 359103589 635088197 778909947 506330330 112694401 70524212 600125505 269116198 317097546 504544556 356071762 311666001 664428604 50370694 956400678 618676877 817407892 554126001 708825822 401916426 396561668 619437220 75241445 357960577 33058761 713166617 119081545 765192822 565693294 366842325 142424498 348244636 475694566 227605440 875598000 585434095 734407555 180700964 182996397 71441823 476639431 714375444 584227525 22953117 567712374 2017117 433368465 501378816 811041364 383317982 501142894 354971909 496270741 526830393 365659753 381925181 787446202 246014613 1363236 612407745 313435241 254613618 274387296 107498126 241464190 935367646 679470974 734700226 164275863 867491420 588399026 469835368 933167287 770492931 307967030 573111245 360267088 956277352 975302040 336967390 246667637 492791830 429270585 977676484 573393966 975165010 789735444 698291882 854938179 241184840 656623510 602581548 285671123 268003918 710784529 61292817 373569342 76690899 637481763 471538608 412064448 928650320 697382016 991725716 271104438 636612763 395233013 997956683 996234898 23429129 114279206 171519906 907204382 918954677 915708507 700730250 499442094 105460617 226284844 891197382 541986171 365815772 239134280 794439127 217550015 103411485 490177702 755557332 9692436 455362254 322093350 836837263 832099188 73708999 106542833 968817815 979722268 711114579 476526227 699064720 3177043 660062798 993545827 675684647 39667998 757635717 786380974 239047216 776046459 381992324 508469822 179722766 346598691 507016997 309491594 422742336 394986706 387230106 26128721 49558297 99247928 404162492 518391874 783004798 292296742 491891693 884915330 713091623 421814084 151983447 481138455 409586353 63829475 734014177 255297572 629168244 520212945 82049534 468761227 937610000 790839013 202604299 162110983 625854470 286028962 27304291 689821846 417271799 22581693 668309128 605568098 282981062 947908613 985671584 271244615 480568800 724278131 206486219 185437276 904627051 697193856 370845654 797974021 573286643 517550264 701723256 715900185 943790156 604088909 193986450 171070916 904680674 514317499 422432464 751468849 348193115 841762051 75144510 346887672 852804743 520690078 24657609 76993352 718469875 201491805 483207846 797876160 165825571 135927734 181824100 233069757 851630787 138578199 451154872 784673333 40052076 898756322 394873797 708333155 308623234 145421616 401429403 647304660 41618441 197856871 346388535 641408514 293232780 94955140 993057920 199428257 776385658 232950775 331409498 742007364 617976694 897174045 294876258 766134023 922792949 719327302 73575121 535479087 914462514 504934435 347951558 126484418 884109267 886773308 393674437 743381344 651523912 204382462 852663842 936441494 803762464 405923659 820895655 138601615 939936427 208292831 649502644 960135279 217463626 625836880 701004316 207003957 503820083 897048885 300215742 514767105 109715435 722552163 520432445 621433089 255129066 283088825 167580491 66031763 510126051 321657738 243013231 255224045 73101594 524182519 191740089 724066609 83902948 970661745 615597247 133367279 756194910 468035750 756455989 538230971 146658536 245266531 401599853 516251668 828145979 793352311 575459790 514704008 504505521 533414020 624205582 946319034 67920998 535041269 94943244 456093161 401042081 843951559 722164249 566965862 912348232 834369385 237738146 57294580 935546178 583840112 129641691 789723589 601570978 633443775 159296052 808739547 287827444 49583115 48747214 888316611 280157285 912305516 502550662 330628600 619235937 164099343 880212152 852227412 58496489 188626222 43631462 181166845 595330738 455645298 340275403 135813718 866125056 229471968 852744107 241750345 126475561 967981085 666484086 620947984 143729794 895560100 352899032 966051516 961353813 434038437 449270403 785327721 963293550 829574704 214701099 514996097 908785349 81255044 496364500 101858619 374855325 361699407 420616045 615769909 804329723 138091982 269246218 887815344 351717054 390576496 348108242 799007359 188965653 830082295 888706839 14319497 867895031 67824542 474559869 2238599 755811695 43348476 570174142 956077638 220484294 607062269 588729160 862559798 12534493 818571466 426316869 771189447 29912848 813696582 548322282 957247091 811772914 355318830 305695236 799633122 413765782 899184157 369990946 261229745 17007689 845039211 989357230 305413847 735800570 948089542 203708379 1278909 498567326 656381223 202592995 733621856 801931896 581754389 480689670 814530597 625248041 869740373 422417007 960575589 446653991 397835577 694412051 361056412 105850855 325965061 522488594 534589186 715001112 912379153 712432030 105850563 613129955 113717418 40775917 669509378 245508550 407782148 578691157 587345570 790873534 648440526 529506602 465118442 359301225 523535058 889929781 681049958 699318441 362713628 603176511 187234633 495543729 742557894 899613690 275605848 300952860 614821245 338467866 553832215 660168157 153296544 113148094 320049613 152005846 252148185 267667853 514724664 621393463 304931350 217051278 205948775 159586575 154545356 90699858 857950968 912577886 272121938 289496127 987150570 884344120 289140265 418713060 464874185 817688482 840563078 324163381 800766835 582511240 207478409 496659408 372964158 991813815 317509298 656993409 973004714 371562374 803446341 338002828 520902993 388386578 744160802 419701503 93851251 747292308 638245918 978195914 912588435 686221020 471474882 375815465 384787750 256894297 577745705 440459550 810462044 339823142 135451641 834540159 54582950 737079018 874023462 615710528 810376980 474848549 292377391 98266843 482752424 120071629 940580188 200096182 890645175 900541036 19115500 619614726 280112554 745064851 784753054 850542153 184805270 900185453 572181609 189638912 420455842 428519503 873097839 786127696 965806507 236182311 494532082 195082413 609814636 781475871 402319765 585167194 268468466 118485213 966578206 13865792 929623059 841225969 470093057 749204518 548737478 98386424 688430762 598046047 637312057 855618450 251330973 522433657 892758239 275579593 939072956 210569416 89826211 559270960 729146856 157175977 803963318 408935576 651037038 786136820 820234204 572646891 755848440 914632219 794951009 553021040 988925512 390122009 818895601 471897020 517229781 637566918 728187919 215108795 111178112 157933928 311212606 120841756 322424489 755933045 946010671 620224466 835426017 727299341 294506225 385612434 178550015 965795654 141129031 631030456 611080621 428387592 400888554 47571713 97744532 259590901 346319998 757561965 981532277 740107051 697685196 472247810 274211303 356228960 919921261 989000929 383419505 432817725 64320651 596178738 512802423 196882420 737706120 10511760 426900181 981100611 37568660 947435586 429846115 192002442 705223234 889502824 3891535 23599865 888302053 380137040 237544307 521622405 152740053 598884355 730502326 176922700 829846924 989957628 499626528 438390010 646946913 483435031 481618216 989066793 165331744 225935092 162207924 860968042 242616231 653970835 258947363 245034323 490598533 106424847 795682684 487696050 739460100 851190898 856391951 663796778 485110560 984732067 791399736 763021712 137970651 18598245 753790135 688179941 637586406 331141355 267859107 779527645 670079706 352721470 763358601 761972315 13847634 1144 339680320 299404116 438775840 586740705 930749434 714351409 295000282 539199908 850004231 958696226 47938311 16088645 160272240 846382780 954143114 904637110 485891137 53582533 441983494 8817238 723885032 735013283 109319833 189541433 675677829 175907921 894360364 169768515 734066365 359453603 457641255 865627367 381871890 564198268 523357608 63927162 510505375 763808963 201720961 285514491 374871488 272154557 293046780 233153169 449839925 875947810 489200921 449952695 381280277 384606879 276333417 8251388 205340464 628429798 793648695 302043083 180612274 390478897 621074754 465879840 583925816 140088609 443231295 698667757 391602924 722779495 525413470 643596423 20229059 164046478 833572091 853260007 308375189 79475724 609119273 562169723 953863652 326073615 181432634 70421258 288220022 830536953 191446631 707184191 693428642 510957669 8652431 919236766 294561591 930023951 470271461 130513659 592241556 968684721 851345200 189715937 155288075 201658075 270880556 269493018 653926391 444384573 834391912 698395230 320854633 661635188 881400721 609403150 778799690 223057040 906025695 570202046 420240481 139801556 506317882 184791351 780733959 99223888 606644391 773330158 51394447 966816403 374704411 445184805 226759709 391839887 207850111 618327499 864404672 412177371 835189119 110804168 357565532 823161479 786136795 592627036 589092227 499654061 671395753 977949551 386011816 116394588 308490324 571166693 890440165 853952849 259978080 881823004 14249313 491188779 817750591 603785136 975793142 983358687 395865674 80073988 114404834 677158993 611621511 251013017 422345900 915247564 44499708 939765837 549148503 203234152 384013456 90365800 141631537 494601218 359243558 516708222 397892365 364506944 309782296 235857435 202459212 688706362 561630746 921168322 714052533 813125285 191174318 720304818 840197939 530861081 878398116 785284584 550491297 784643159 272697305 318235047 337482030 441944548 238513256 174374983 102850767 220643290 884201023 826357470 853911936 285139747 836542092 459813028 563565513 634284993 400530333 759934257 34088970 46810804 904486772 688666072 418718986 600725605 665038808 271412811 267100434 907941504 883162309 894420508 20387920 531456169 30254215 769493159 582059470 3580447 652859251 720985333 384208883 336556304 396528251 433924309 66063897 859253945 665457778 491546106 121497752 43683609 445585417 464122245 711376360 156542456 534239021 236972447 371655320 982168205 247493500 380162315 742842449 63802465 244348057 960365471 820701918 444923582 265366601 339007677 500090754 401578281 315959270 436707561 822850128 92701622 260916831 326830741 211508362 301686756 787663389 559969916 907371811 10839710 255860110 378710530 244110110 486316560 32097606 356197171 475862453 803942756 815258691 770278555 3836572 57518336 676589905 222689270 255735867 657417272 402301965 633328544 79923478 567222017 620029654 339234376 164748763 404904036 815290296 772532672 601943453 835352332 624951894 430861640 444151681 464760832 565202608 259023476 176021268 333103295 984421245 289240596 78692229 829943904 516408703 977929126 153916463 258678642 201275617 424717244 642412275 397726998 342277987 954067178 406908306 58477859 288202955 219526222 138154060 474297046 629581687 823568165 488171024 967663792 511160532 911227769 19897548 54074721 329125861 17500857 931146694 217240456 173416644 880936097 906790852 692092196 35320848 376277719 508976887 575644045 283137404 289176129 364146530 719520691 695084772 241054194 231036412 210441454 841848010 890798872 380021137 900673824 413411890 33996536 553616926 255131955 966158810 6700057 914358102 673079429 737445343 768004480 803810545 367233553 788384772 830320562 742998292 767347497 118055953 933298393 653919670 852183950 245567622 510293470 754422681 105355865 400853692 57004840 47455044 594245505 854839788 570581760 94177532 112467537 782474612 123118187 882155767 474469295 972872500 27237889 985908050 376342161 298400675 609632751 77134755 30678989 169597259 158308183 414715060 528300168 34517683 778079395 237166658 173386447 737678867 169855806 767961521 458764461 19823719 256102505 609797940 398156353 599162437 871966944 556268572 506322 702468736 51001270 807657573 931041830 741471596 556867021 973699908 766695302 40286210 857799624 285407335 787270306 721177253 672807903 594081305 426519348 723213960 60757264 372254174 837938309 66974409 891702356 914251393 557791663 413467793 388540158 639659090 239211809 907490378 148642947 475628767 53319209 901626497 613649818 450273921 616633524 864305237 30071573 53121421 319122442 386183165 691246807 527803038 910583132 268365973 989193358 316520180 930224184 763062904 456882031 445182070 702309966 996891951 261681072 686546240 778773886 949776709 873267832 908681780 444041978 90237216 921428184 382339849 693688668 838260649 685292105 275781929 519673180 38310218 636453680 250739245 171651983 84165536 938874020 997937054 587283406 553421572 69943561 527741782 660587515 890996436 141311938 878653180 285890252 800546233 238117959 15688957 668369557 7488575 608288382 315216642 268942760 627425709 815847012 468011141 789455895 478116241 235624226 604758429 281881043 987764524 635904776 742676032 427800330 413809370 803583006 866270403 536583084 104323844 948066628 948921044 5303181 811527523 821698960 161173822 895314808 342282479 132500421 752053318 627816250 838213184 797569586 133918755 340946793 229600116 474995314 338134940 361882025 149365418 74208359 888885849 973215497 933614382 803272271 995179171 862213579 374792040 926316153 796633313 423606636 95993124 511929074 855025960 138653765 342257857 760291605 366339989 650301595 233336434 425107532 683476855 472026587 638235031 198099811 819762000 75524932 750357347 617741487 904880122 414196074 266122388 396525427 501738718 108503923 467774918 801303241 180088852 729381516 606828376 258343098 569926556 125123314 810050421 537229382 303997789 666981379 930471673 860000323 617018981 322045671 356515019 81931368 255061234 229645098 808730909 598165323 207722962 939119980 154018790 635488536 30484962 934448264 863383629 107188035 874124494 480228968 97286007 380189567 27064631 414708985 211392321 748278260 579265033 749281382 395737077 860342694 369441077 211108502 851050515 332444354 11514524 648942214 739538848 461921146 739285548 451308060 144755790 725449568 961447582 183718819 150095891 669456666 465704323 269826891 582201138 141485761 259970531 964899707 330316730 730489185 426443677 449721453 80051229 392442660 576314453 15756983 426451295 977477869 65074310 343873561 74143056 290154872 368864810 334465330 56195475 526664556 246607399 736722353 21333271 106620114 686727104 430850184 511096793 420946122 940381375 963983058 731231864 892511814 629915512 406062634 756277162 23220362 864229395 913512308 778153198 341025400 612655533 125595875 313346240 28062537 874326207 488773457 280095658 6406343 222121830 457184071 15131887 929430995 9854661 834208806 830556940 714343354 267630715 512415017 443838678 232090510 137432546 547758207 844635059 11127927 853358766 359029002 872367474 55193231 788429566 81637004 633595555 610122382 66104837 12456619 331078582 928271383 425453346 116540188 60611441 399944743 208075614 749507649 592900355 539893196 360003936 458727563 923861349 581933270 482812229 401822479 648577967 952263468 842078376 821184024 326167825 223258685 260432527 803033900 868493973 221065110 136327942 819166155 18602590 416800635 208962939 371465954 943999925 94244010 922961797 98078688 428248126 575345778 662991727 204460801 394020236 69853862 451792085 162483396 75531508 558489266 510389859 108148738 24474012 269428348 246281416 114243327 726723715 533420546 649014962 568305329 496825901 472680816 237468021 516367144 309076759 818193324 524722512 643453843 241504441 490535608 874699073 42471427 615729338 401136405 505280920 305849102 673762520 568693712 251644219 867413631 935462425 743972670 557037631 924627268 831045721 244447565 87689569 888565408 819667964 694912880 918903501 822320298 613216806 358952937 229236120 700771665 822201357 443653780 438829653 704391155 1131328 846317057 853794810 230390846 487810983 263218119 731666936 957301146 876052524 206171349 527907010 192368647 595839530 552256365 551735441 406371993 758525787 827243260 238546861 798203489 108418930 136587820 546956882 499083680 888756016 413626647 804331621 153840458 954773013 716582864 325549040 678117971 583041997 687717272 679081575 60856500 977330914 32859338 135835958 689285905 673775629 590720579 956133905 983645455 582837662 973326788 43049991 429254192 438711531 630621916 247411146 140922757 507424983 728866345 734103365 633235101 598304988 583772941 972558024 660067778 715596741 57441284 253606734 619063649 403725189 595084210 397154707 735153512 294241250 296989576 530342315 951501947 88191168 827429741 620124712 290867213 637258392 553122303 17670339 779048256 762752609 173396471 553902793 257919182 30406768 696338693 703946328 235397917 147317004 927611941 712074913 627974012 14125812 735091357 317596827 94425113 836269900 70228821 817900429 276677676 895444886 767690248 692770625 787013096 381132975 925277035 80712006 390912695 949318165 365505806 515660847 709698401 47102320 693773972 115233200 357375915 108718449 110263310 496782448 680699745 200235260 585192881 395142210 538161860 573301416 832734255 189253228 773091452 501606244 84245959 408310069 398200965 487723353 87995651 575267289 105156432 721885908 704049412 245941219 921461263 928248604 869723817 934706704 337128207 430402037 439329099 55320152 977874026 179837334 215934902 514191576 580498231 476274808