2539
834142791 939367383 903489279 859019913 564549440 289065743 183841189 407874079 913574065 802923563 937804498 671935784 87016750 794871621 184848449 669123230 629298257 756327499 249258223 970148549 422750178 454041798 90112167 622443253 912590602 404687839 487799641 749275879 908014616 262171673 899301703 258848097 323479874 447987986 249773975 451972810 529181129 181706483 297475973 860931245 12644559 914612528 458535957 401534940 978639564 755101188 343064373 462427345 941556716 840499708 683197777 780045411 445831435 9403524 115346381 238064635 406422020 182755933 682096718 88690997 736914893 760759097 752988240 324023951 139396331 364733443 743966552 695805393 425284155 985325017 112834349 596627021 918779196 996428273 61445288 290020728 620717822 109140228 876573728 694700379 521548182 822710612 619444482 886167215 955872060 96049413 823398783 511146021 909665803 670083819 89750717 410665875 459113864 572634993 213049636 501198314 399002157 688367553 826344666 239211854 427654572 677380062 501672924 804867354 751151459 943297185 280866832 451851614 207036223 197252441 799400633 547738406 911446475 863946847 863169401 532445717 443410056 189016489 384928217 574980952 609457439 272369819 707288673 589853671 741643086 37977670 661485861 36104517 12915739 862385241 907506422 366150927 771238019 430826202 435804465 5534709 820767284 745161306 117077242 616159560 76872791 200019088 731673629 646250692 333060135 204307988 919031982 139876291 853061984 592173609 826710871 677076851 904917764 166504242 365232591 418849687 690911527 36678355 544567220 339655531 70930818 919213142 518840900 946751398 716636189 721961761 594513431 523520312 151137355 334225133 793299434 213837274 285096289 571680022 912337539 685827271 817647521 698205385 747717714 312139931 167053713 789916904 730282378 986573821 957544449 778361348 697974999 725696068 357033470 936297329 990660966 395462281 918055207 342060453 613075188 264844818 844859557 550005664 970271536 261903012 35660516 305699189 832485221 883166005 129825990 992072208 355405294 258783177 430900583 229298370 444156514 615400821 361472434 582016730 359616486 845967777 380391002 721473604 398224296 863458363 586948157 50056786 337611028 763320278 888378536 626080763 577922325 579610155 259341520 268325967 245859210 812145995 725010042 849236222 504345462 220905637 895594599 847794653 459406082 495768290 435019438 310021436 906980173 409517859 771164079 640362303 874694332 81601683 513891860 499741361 75172491 483091225 736989563 283747585 96591443 11833622 789040815 205449579 747221349 421274643 953694961 484937564 645530449 222659930 35567739 846808437 399920389 251526397 471939313 513232598 588285599 375451409 389355071 987683694 66210145 936910338 432160596 378432051 625610894 253635676 195585654 98117675 268196662 728467366 491471265 75719274 510223591 476527972 261962365 982871617 221530951 355841974 187539127 108164751 736043002 131745957 424228065 622078908 7373957 432020228 943402763 488976982 688388797 755276272 496765428 858828134 774367194 412589438 473827710 546151606 841516025 349103144 400874995 787077975 174881514 379538725 570021435 833524281 979188787 120546121 198575632 387881396 818706227 162546876 103549300 712324206 844274182 129259240 106492028 397043895 859156700 317755374 139561668 207604975 365493759 325731898 538946516 635187892 351874413 290757514 758142804 280218201 615711181 832823270 650886903 664149002 474206287 303450389 854742693 708423709 309798836 378350103 344349726 772839016 306263496 69781447 117546451 242240292 969786338 681137385 794198676 171238220 878514621 733468029 189873412 763324025 535449246 152649212 559406673 333142195 615070587 773641820 347793571 963433455 628444933 197182889 108156142 746397972 240380296 467391276 776733611 651420926 835557406 559161087 584257205 44393820 70402296 157938678 361262472 650806442 694286638 853024789 731742051 73291085 101807730 718957151 951948411 181719848 483670315 185828970 529278467 393972051 58785160 805938038 598104856 700255634 13042439 902390774 614622060 962127760 778250879 512810154 93471997 83578406 491839062 975899242 728229360 643627655 947861186 879326334 912902086 22700221 947217756 634909101 602489729 44933993 516096877 665596207 989849242 744337385 382881007 703342195 575136916 492743224 806643992 558440412 52674238 539744743 482364327 249017388 845912418 704744169 564463891 362101859 459502385 663702539 74753230 589548512 137095793 231262504 176545006 499520262 640295883 217238376 637222660 627674910 471636772 556383651 313408916 760145719 445832861 771266388 265889248 264035 688322535 902853037 856659628 817614337 483723403 604249092 490233020 870008252 171121754 816660935 600400815 7402684 242111473 503286929 913351755 352243224 712496869 97915778 108498549 460091349 349842118 941718110 502170874 582398100 341305701 555578280 552712638 678516963 374078611 553320569 996577960 655082239 327274369 848155714 870360151 914137098 229653821 767360290 514246658 349185153 170670791 26133139 666360488 930806123 362919591 140373427 18450662 646529801 71743660 693293140 552827930 48753123 491786610 357676948 212099779 594456964 761851117 684395996 441459922 204928361 841688278 793574695 748053667 200849435 481408000 476853690 912288119 972655112 552057099 963230375 128540862 134388324 447343710 503684881 629830987 597980420 306897160 327763352 577535469 221588022 721843241 249770426 850751518 422596620 692158125 584165464 614575402 484753539 490728251 47096914 391179860 50314114 131012160 335653925 786419478 165337661 575812289 619993869 926646166 711607253 905142321 400905803 809496354 745730995 233371469 23668148 639711892 22862374 992674009 29128761 452929844 744532789 158538424 315288437 711925847 136884670 449916471 705151596 101617213 335162369 615038652 476770988 285341667 943679421 260147526 538884063 523605389 555677018 498299228 828604783 422380658 166537247 193354050 606674257 81072684 288184700 954887679 134074847 445751470 343153159 712673762 419023770 742525425 543671678 980393808 290688579 723382485 291496053 274105497 525875326 735720833 91913130 677144857 699613824 560873915 717983758 195643413 655378670 98684256 974410273 620325393 220025920 453987055 721242616 102374963 680256689 508116816 419434251 564393404 465517341 585933384 973240624 397261968 986760646 56970633 375215045 560480547 89132646 516787063 743920037 934002775 399476696 675229448 378318481 346587258 326481475 788952269 64173727 832267743 192888819 132557856 723608681 374385114 627628153 369090367 318684697 145364911 33180120 76554566 59823716 724304655 65702902 450859906 316509207 215149118 390424127 400312518 198834318 61018669 877010867 92537580 3085329 883577646 121230442 403299021 109890499 762696085 894165822 909312066 664033407 994368024 637844452 1079212 675695978 493189310 244216400 759831009 83235929 306679503 859601998 305545766 842101076 39457115 877120572 876037596 919012698 852967520 689280523 596503212 961212912 652131093 537224155 187507615 885119116 646131004 653097179 944955601 868061321 375902987 658161157 998000497 297035169 682493623 904994094 460520911 210598837 907050476 481275909 343300227 767272851 273501020 462448724 948252252 552253641 715179743 383910435 155485899 170789957 644219493 613378179 31039195 269852349 649756461 290188281 189439866 44126813 545705323 675144717 61271940 802398689 268986161 504408518 744093329 286341570 384245154 928872494 85507700 316641203 312119539 81922730 276906929 723183559 446426258 104400804 586535201 389030494 594361561 665925295 712524986 594868630 13755176 859957469 101648650 290036775 521104848 928019706 40575816 188402008 305651694 87278311 684177657 247240071 794051217 203827936 583164341 509382817 841681074 244983719 904703913 711019541 876874109 159324922 803281772 563109804 234027359 825243099 293259595 543999911 684861904 574368976 899004138 901899315 899406801 85004169 466419563 9206236 677076184 16592998 497136633 740230047 536844998 661846387 721109294 555253005 234367687 657158909 568670844 394599616 935980840 183741025 636088939 456745122 490028761 690275538 839619227 631778557 387782968 920567323 737953250 814830368 388436565 406702935 578803547 622880955 444489625 711961830 719851157 604209717 834840461 822019994 832377345 207845525 607281530 211509693 584055967 515067619 957323603 43539101 352084062 664893877 503402384 457814874 982944736 262036225 913594172 167954543 185996295 575475716 873162747 388904649 958657344 532864978 745286569 620458739 145415913 945846957 250179817 428571310 4548719 257138420 774344233 199366380 787825433 346107570 686580306 234687962 135461352 507667099 482856540 385219360 15628538 552324364 894019644 344716280 757110150 356755004 493082838 360666481 367525163 740101915 78991245 211257189 664907174 743402062 142933965 419388089 51886472 263722260 924866151 942386068 297411941 542404282 474487859 648921644 132737911 2676290 992686766 29206564 822206342 163516726 66315659 585355382 805941235 668028549 136143716 977828781 789258972 771338811 348203565 253680081 461843191 551050995 905493600 660544580 927186236 916910031 424692483 457163554 951108693 439683756 256785949 100861373 641058852 549112242 352387576 26308092 34332019 899481400 295051174 442167046 761565760 761747567 736414390 388213941 34369333 849851661 621693183 955058476 384288673 586390413 709765087 915859720 950213708 789887408 114841813 147910468 777767740 468712231 586029244 700911918 381793292 443420581 292829779 427250283 369585281 866366919 974384480 499467357 14471917 420314302 496379895 854470374 668992011 305658684 649654147 640927685 220292874 159297931 787396217 440029312 963325273 56224977 65003214 325225393 87506729 242855344 958176924 189537053 755803102 758384508 83272947 440393690 582427584 648080082 789479915 159909542 818669428 6621845 806881938 67945639 310999164 873718805 259025835 496173473 161267578 93001560 544689676 720950266 886886513 764573378 646512147 384560502 980479434 399963569 514013341 531596804 570319498 682210636 100414962 671769324 49187191 401447347 760063867 546470409 746835873 871210494 241835922 585419849 169997838 972794163 570116589 555618740 253385179 635668330 737457308 951013268 23758058 726728722 268067256 249354259 891034159 101815687 292608343 598487709 425315342 856988046 298564646 289698892 847994492 360017903 447956167 735996373 35476108 734970865 211143292 890566085 285917379 245433553 902264505 22268023 945761264 383436639 664873313 385338706 526727121 769319946 43779011 912854233 15838825 586096750 536231946 415824576 792562564 309031895 587420375 74104549 21598977 443728758 141957813 593961154 211515196 338609392 402135670 261809420 661919650 856842417 392997835 830662736 888570222 408243949 705075004 402851224 757161986 788440436 415256241 246472811 771724413 902943980 194814694 652591686 385451680 167176586 483204958 292839917 654190086 708732242 145810030 484974160 354896604 218578200 803399210 555533456 320140318 510801378 828992115 613049120 847728669 433017550 722708994 72024963 740481801 413627096 522593235 453426256 820920670 727252889 541788500 490982573 465148558 938259769 800705467 538954975 496574159 330274290 513863352 11498210 970129589 592341408 495370726 650089675 895950337 35200761 560182797 135947245 525083629 716216916 6598727 657017720 321067499 289020983 10329292 745766056 930192561 395725557 333304274 991840179 634506467 877326638 147468687 851043262 495562966 678673777 703052328 916817502 43854461 50770441 831086990 567206824 78484368 332345726 191298729 102020347 160034718 63189471 522130404 188815047 520077266 195922501 194784708 527726492 378539303 257991791 154655936 56325892 176162278 688236863 905218359 376148567 436468608 337919821 831257769 225520774 105881554 728583243 525720320 134532907 337959086 136651714 213533940 920115354 392409696 409033917 16060881 217418862 738698172 608834097 248831470 498644998 940086924 663221961 986440927 237570958 919029794 591107393 112618292 567450588 953339719 33343857 249572507 898504010 604968351 111328905 394126015 350145035 26362509 814459323 909408500 907976010 103946819 449137925 277769914 56752946 770757299 270133188 684295109 713402155 991362279 753204000 907487827 957005884 833375837 735335970 809607716 600765477 216796950 481063733 618486096 907310939 559579040 88626869 915989583 3118071 589942221 576447444 612672408 645095770 565282931 334770428 290257548 73863310 298018406 955214698 539956302 966832590 666274726 606222319 818428735 669157024 315722933 860309801 605693668 639172458 690254897 38916289 631360795 165791244 187668249 930473967 403472074 918143242 67032074 435501363 962780165 400892219 117015725 593758258 457116027 245668666 434229273 877191485 927505031 157253409 164673402 741505076 505019798 323073790 421435957 539702334 399647760 397641345 707817743 868561393 59438742 958012589 338277810 448696836 410637531 158719118 296758214 466298509 573238293 345296062 458486808 333897291 283830410 79277141 920630696 82644620 820783594 101731494 494818778 485140776 384091029 337109341 558934523 882416476 491345322 651327331 826724826 671874621 248706921 395848525 972705173 904391804 25623594 638027900 127821693 732343784 217737570 701850054 261836137 962870995 509328420 505669577 401682479 195804623 801592865 132245730 586164466 295430958 517705412 977714905 903926542 494499610 819481799 70237018 463365758 592219016 10291441 455040186 284754805 18506253 639861350 277166320 938511973 933279794 468530861 93562006 220469676 176896950 818698517 73007185 540165671 541406651 745316294 956528432 490023297 280488141 889974463 570546951 991019320 719052587 431902631 229947203 240247714 639747075 637913120 375795477 110596506 18704858 962245676 899410406 472889451 8999550 6073705 526046688 497400884 857868108 68038965 369362125 295245344 563605141 512367583 395650762 863030141 660700910 886675663 213517170 784742479 761228394 565282738 85089788 853137469 771453275 592099810 756086163 890536104 164509639 486505444 785440287 663593013 827293322 186200161 929456312 597434396 434352638 189413154 561578185 102376571 274635052 273913999 110615205 516220295 837639389 534785098 477819294 799801411 218448960 621564647 590940663 470475073 976480303 815239980 908186915 941842225 108111240 680806547 632757177 215883939 210383590 978725000 493204840 493062135 272923455 263066583 318615408 751527709 88104389 213628765 124039396 349821102 538922113 221092599 689756005 193798827 607635381 980500889 884046783 344626238 408474024 271320891 821754958 45790906 133045815 414343966 143348666 745258526 94677984 25688126 551725234 861931862 671691330 362815846 724276952 954533935 443091170 855142650 766239714 420004609 596121012 278203574 886868460 457892073 451405971 99090485 590644266 303896209 295889021 109200545 50857979 332285235 343787520 719579786 516861113 255022496 545615343 786785680 610645588 74959043 690789449 155512550 9481806 188294381 605619932 449427179 562660510 434796121 750993494 761509061 797058085 585732483 922183438 585002126 191367261 16855015 39598224 199999980 890514521 278887687 60697150 276575145 644199918 308714021 101140301 861006304 108571698 435814630 486951650 853501053 811416449 533733383 647530613 153529599 529899593 769143387 33368303 577117062 571218879 50791306 356292692 312511805 450577124 288099096 455972847 37616629 609169510 215627362 49850254 15311589 639461766 840286540 362179972 70272644 893480666 371635451 970431818 711688186 834599784 901985491 351746362 339018145 763535989 514025759 393123606 71664634 300583062 345373448 110396892 655850346 300068727 328900990 370925731 170061991 729755248 624315274 228645209 704955428 274873562 3939274 27422344 236317599 548212805 186575255 285888901 643733129 748788529 931765598 709316277 615126091 950099631 338081229 883495476 847770034 932614000 379195164 768821938 939155001 592919226 804884485 435334371 666796443 460321438 533315427 626775890 683227346 636644916 477560121 675293406 572898539 417204323 407562751 339483127 901529998 700346019 108954656 591181847 88703468 225935990 398822319 581415924 923222215 6119236 730145044 916811716 439565886 745044112 260908639 831041076 255765846 57992098 403326136 23525510 854281550 42875678 434478661 917089711 309385136 140906752 533042854 429395247 406263911 902717260 455185911 682135117 532179128 439804861 739755774 533891424 706032493 172755258 969565575 456941838 8765735 757163549 168020993 429667517 946424559 617336609 848031807 913025172 61638718 709218163 484817607 178940818 777978820 793268540 818854928 62691883 472089881 754643933 542776365 996164766 449722464 56651818 43858722 394321654 101511370 974029003 832265801 310519140 26223867 706165328 483496796 517344783 4015733 544026907 58698838 323031001 51731996 692414353 138777177 41397947 707949091 714369698 843039555 285100013 671326620 804421254 167739003 383768861 738989183 125969742 823872988 577042375 359145188 736237918 116094605 364366128 509898330 236601189 881525875 929565303 362971595 422093060 759051885 55103589 590323206 24532957 785947515 995344496 152976901 353420326 530074292 287256915 495600608 644938542 463632867 930285614 663482003 750761804 564505965 458106348 16609297 987950115 797146779 77883710 884653596 245874060 683094562 160549905 79993140 994017644 4328303 124934965 960335823 270583238 820507727 140042227 326752911 415110302 749059614 704158569 283892709 314549523 840504049 821133081 717026486 418622498 27598327 106574473 234151083 836030169 548458803 146980579 189817385 743626459 234067269 57344304 352634853 94252927 170959946 678080774 568889569 441363201 758573142 132604948 71044284 426055178 175007715 664294419 120150015 613963577 361162886 171906946 449018167 384894674 834185651 676929570 765368796 299370763 880618211 884117268 916849971 855636522 262850467 796925596 829236052 241584817 26821311 118246772 995353082 721607644 419115956 471020901 349748813 418832671 222572447 37808497 884751970 380012748 931816534 791354631 503061266 252379806 589632793 466005668 561770814 936374774 165286123 550996543 112881252 950097207 757068610 854580679 13095743 582542087 462195861 306428021 903030263 670614749 728725536 939558114 773886941 160528985 289425925 690069342 246684260 109694997 429327932 422955383 451577829 322870304 546850476 698539244 112624810 626634120 737429964 493717792 844676507 300420177 93800890 606169261 274144944 200560380 780339787 9151551 955519970 529681946 206786545 10860195 571577546 500324998 431945716 868446485 670429996 872890654 558234558 309053399 328680624 360894825 801464724 13275806 22046378 567265830 333313050 415717349 386933439 903439081 873495280 687326513 258355890 136137369 826548822 656272843 251369008 736741726 979170309 482103462 76251361 28142999 78610833 30089902 720635156 300671048 11471319 272881134 26470243 713714209 290738318 419856521 591859030 984271294 416151664 36227650 339949783 985235999 943468080 489228540 225697177 883020521 701378616 782211641 382923624 708128918 711461556 903260911 91300240 641633771 146327520 380711843 357116678 780105610 878471925 658615083 682844438 323210083 486822809 663914819 56410739 764971548 486063469 189043713 983713420 189738055 217440000 173764799 484093372 38559851 236756996 166430966 776463776 853841374 963097811 80485807 6058507 990609250 690155569 586159384 653884165 942992911 148013268 795697787 131775205 275577391 746201227 205414781 531874030 845884313 877885004 8407659 291805706 435729909 788243536 554614212 184665317 618137903 716120109 259268356 669295454 679814527 545873152 17250315 417155609 954498674 34182006 824556926 482188813 918247362 632000549 337784252 115717557 71989029 949025474 909201686 822336579 648905377 630299000 510897673 271286553 324134270 775031097 630674105 933027790 357171749 330693730 913590389 909677469 760652172 713504154 704664381 570704017 99939548 174844018 439720040 151034373 525790915 579099208 854177512 401729626 468694497 181549357 102903005 766464506 698961012 230662743 714127823 261021272 228142301 770363177 587276855 623273164 32225791 800264659 153877652 825938864 336905269 236467880 112031563 346362557 915880093 82755361 767462119 384491927 977240969 834953758 536081825 677330229 754960345 103354943 149210035 148577565 839628451 558220691 165301147 129068090 172455380 18493169 688508716 273123894 950115861 246232120 478119947 930633741 984432273 938324566 645536921 69918376 872631850 45245434 978388990 480837440 895970134 948377881 660441192 98870862 705373707 764064235 190804546 766779998 647811800 951835911 76910524 542024454 562944265 911861283 4482351 570133412 776294432 531600226 243860198 117383969 649188638 667837371 849754453 26986515 373935852 911526263 34372461 821435268 208591080 371929034 206006154 646904512 118312741 665313788 13141704 825659470 657670155 242527963 980174024 180433152 966042744 774475030 416843005 963243982 99895520 868707674 332985827 520618331 490806597 177348198 258892910 408011007 572658337 317581323 515630211 328179565 729153130 345400542 681103327 658840642 418203212 859917554 801242676 854986644 166392021 874242902 516220282 236473226 575531053 605085369 861057065 575620267 263680070 393027952 39217098 563288930 134116103 354487583 358804558 890838208 434274630 313573006 926484148 801830552 594476707 812515527 832245058 860939224 715251603 202418652 612889576 462071755 128447415 357060492 645809526 307979856 905343659 187745346 575210673 691084134 547572671 338103699 39493836 716001659 633339062 394653717 462589746 804908883 758880723 195667949 183271954 643572164 680488504 110314919 304901952 778211228 191047741 607495983 99338673 568799942 874747621 504828970 602688872 283045536 228502042 244429777 192056123 750536396 770494217 753985946 897256554 846673613 808818961 869711923 487350872 299717296 643654280 258736099 914736275 301385687 72700998 605414898 437580769 613808002 865058509 451087443 891204790 15450718 845713182 332772386 312547531 743368935 82693526 761299886 467021022 236171206 705878057 82202969 988352305 953851845 358616935 661552465 104501343 292525926 587852622 249555687 438134946 576522771 921934323 916431194 518350224 130228236 399064699 256419206 752061392 463769567 396244469 56657586 399812766 576269715 933115606 847067105 111385761 65098034 724471166 529111715 30756988 911560934 311342550 740010515 638674181 872306277 993988339 400082451 474158912 309559317 417356220 106528542 754446740 714071119 227289761 405092195 695904022 973588674 232154393 181267792 926762586 772847010 160537091 109833703 146026801 438966469 561990332 633095019 595673251 65578619 37217270 179489589 613415834 864876005 941032265 650610481 10131071 633099702 564030056 792128067 428781775 250757981 123130467 24387905 364156105 631939282 520556154 316288465 896027805 646083266 491333855 469225256 2792635 994481017 547267803 696416630 978219348 172371080 610673795 684967728 933280620 276214516 628202807 769823628 193231404 799716762 889728779 580123791 889884796 804080620 782503311 724202104 509979052 282978504 942660385 195474532 951034181 799637697 828986514 370589471 613509331 671793652 786320131 737431720 550136952 60835393 629176776 822842623 964786317 833903213 347489255 448551907 456581736 85784940 557294746 394744587 482791888 553218838 542679617 641655974 920147253 428192839 766802238 839666303 344704310 977508007 659857058 650317262 57134056 763756212 208199540 513932706 651828326 333141762 496405630 630896028 864769345 140477026 432433729 700312463 815020458 15620201 827285303 925577801 111004528 359667795 72720662 248389814 49292833 10033851 932674270 469797913 206029348 963210626 158436996 291988315 518766182 708309579 995413716 693677611 620469183 264236173 416364574 561718141 564020142 986279500 990991920 514825274 285822746 956194421 683084802 820388133 365917623 756487121 995747027 881583826 159553101 144124332 225588202 924509595 196400298 451804791 30653863 957879347 986409938 200848763 440589797 780940643 347343519 16533015 694055037 877455195 283613970 772742620 833588690 274391233 686043036 261168066 612292542 934434849 99628260 703279331 199663035 24218168 68147542 261403019 38116333 746925452 529370263 26017598 281724973 89269802 292922813 72139355 269761143 850273572 529396911 421160926 791456732 383507554 84559360 449699863 401441635 10073658 954385948 340298023 184277901 201656707 739381896 412830729 652256246 354984115 716162184 250534707 656957911 613128271 139855073 124654087 780075771 652231363 9608906 266890208 875498723 939504478 547118854 181521010 839077067 131582358 719474858 556839757 85221642 617488473 991360116 45433838 470691879 815041109 935973370 850836895 291359766 11581085 744601566 378817308 257456589 95363074 195768211 748971870 214212442 889421618 496170354 708467827 688740833 63510966 589564303 376808355 963732135 122095913 792818508 811112276 511020716 267588959 915608931 252139187 334040535 170556214 861917478 497526129 579880666 283908831 819896019 762775268 289532159 559193644 949604351 953346627 722958099 628144475 259994427 576766590 753501723 496409486 445615579 574848032 625709241 942352224 400762322 513720083 967238090 971902610
157412323 394845285 669868604 679570100 283962326 233642466 295563563 742618621 1449881 375471999 970376300 546177066 117677842 542289813 339121415 154216464 771465048 614491887 722796949 699781420 142618683 874536125 134442531 56292481 942149489 612247539 689005684 229962644 222727859 439689593 351962489 524804648 756757110 181162560 294617111 265602450 197657865 826283730 277871644 972906877 772990878 107964275 961170304 209907429 235217867 188878812 792990293 776883138 205309872 809331235 593010196 931871870 412791068 71814912 649919654 209072725 939264961 136855088 51080980 728868410 925290476 989819044 953066003 864024084 680079318 638602865 693672448 325955501 417898959 780893614 572245833 840332562 628141737 736853669 883441127 856914452 25919588 54203549 373373512 166926677 22790670 394857938 11337608 936431523 927009512 803804525 132749825 112418715 255691765 423632190 853064321 430035654 354457768 406199721 689022308 239534594 994502753 153632956 929705562 164368878 245741671 132013401 29929559 713459415 243326269 583117503 438904141 30319464 627475355 423858271 401736051 747190022 499913661 951685688 434142579 963585861 126340646 446494161 975736378 55746289 625932316 417444269 503014682 544933638 572118698 458395888 909469773 499147143 301937168 883191379 434891038 401207913 115915467 503211410 468215380 383746175 683764613 4875551 47144185 290987777 860929425 216860789 274467152 143902295 716068613 19939760 565080458 738276020 188287084 905762847 678809355 92801192 295980457 115855113 827670625 71417498 218145004 129270233 792932877 237401065 486178161 496741297 121128536 18115470 505474596 798293499 24213313 291878196 43335134 728892031 320125118 820046774 262520701 620865951 41938683 487412902 967018137 611574130 426641143 311712192 2358954 304758295 146984034 885282940 969566647 498210117 947768041 78600660 511006955 136963759 653628786 158489154 669521140 314748857 659605270 113073503 235075058 482028541 600137136 94383376 117161432 951849000 968073516 253766258 191006655 755789466 542773214 464300212 31287458 924730048 780021943 858607782 98836050 102729643 425635940 108666985 908110798 65142314 368434078 867268785 446168043 78675379 221674313 590362712 653930772 280830080 102410241 312780022 975948489 272944811 256736324 904864408 641955415 228334443 618440914 730740639 345526476 309337760 309413263 178769229 274255349 107117959 645865074 736703589 769706981 475756782 890556996 654043264 390790018 167923613 615023520 467701106 899957424 243057448 104647546 219929563 665481287 633390900 414854991 215064380 888404621 225998965 722822426 170158969 770664851 303308303 110458517 369180863 158550275 589643702 545521571 782166989 970175339 819221865 90445671 332083938 486021864 162003204 630095692 397298072 927821923 355088768 537398205 159664941 339109976 673664413 112193413 182624059 219209194 131628906 488964852 433704509 590361161 961178456 996424530 869952919 381148001 254850775 732058088 407347263 572475191 323102303 23106107 122256801 77224937 910309168 912562769 775814534 35455279 193991159 280953434 330192937 856864556 522965230 176643059 832277728 27614206 838824181 257137260 568336056 28864165 101590267 415738286 61806525 21466991 918073720 301490569 603127278 665361491 459502747 186836856 181266049 55206366 121939502 740578961 631804342 87523984 97320586 186799622 168971537 202029432 829013876 566730742 136439308 845530737 105342484 942082251 68852514 672739038 581055205 624307124 18874898 584309982 102280727 535543231 69512824 440324710 729286032 70034629 842483882 690518967 574219889 178847697 902988313 581318007 586173609 51299767 371080706 667814384 96779349 651233112 835521692 617275952 656707908 548814820 243269230 329725936 991820338 805487049 82467818 693224741 670071691 226194950 678999561 133756687 649522796 688918111 660582678 229144234 768117360 214107961 371055208 711137023 589953818 430924909 809171645 942707974 89024179 897842858 661419842 973922453 968150264 368750934 445391906 515276421 70534900 25542132 367301335 631198234 835881784 945026173 374336416 409751484 827363946 454304082 731593835 848299352 308111603 504240257 519633578 830974541 214733215 504669112 628572168 78458585 452467342 607961121 361540184 428796674 682172903 685984891 367271546 16839276 887952960 26243630 905356663 377510871 910640570 955441412 610554068 809583629 274867634 134880033 531651030 933368079 801997514 808478936 234930693 729390507 783430623 85284800 965652554 638582724 747142649 253349858 86480103 990672901 957322707 916477202 489890722 745582872 522436834 647568209 488439757 493116284 944297447 100664618 992422998 123615544 358482573 792329696 661360763 518827387 836067096 598921384 866849974 38444306 25443140 971789599 605323795 494788368 504323980 642684008 803483459 293386244 148843797 667255183 603681491 621249579 419670473 601608622 642039089 879865795 352729802 402578975 696020813 457550294 660242912 599008004 797950182 645187220 546997007 665989008 898865183 135615599 551782736 303440634 997096377 487494915 472408523 832928229 270276894 351827427 193563700 114836876 620737785 579478371 238334485 326396553 231124005 611124321 496499595 48697519 237404248 392249035 934907835 455535930 579551326 157783764 492897666 69185113 181808585 324310216 773220138 276548273 716999692 397586972 744131374 111218028 883013906 376827413 548892808 55680032 361658642 109048430 817379485 86678946 158608502 51295617 802842700 812875220 777439648 669984170 292637631 527895186 282632334 224776307 738382739 701785017 56387045 941624394 502481813 937207322 286409036 586462606 808869527 945016616 628247263 748570073 850446276 331116046 727364820 682839522 51309793 659158716 754458643 212525177 808217486 251119888 979055774 765760867 580598404 331176581 90533174 930100681 481417145 944920961 937359340 633990818 928064293 426076531 453208125 896439253 540037821 884430533 7981278 912625412 316719802 280526180 724722433 642501062 767684728 996388927 237327555 529694193 997135126 266816519 126924988 423075139 502317231 172284639 363825866 733062687 783164121 622573233 753259165 834177636 936191531 30727074 615645181 873503531 207620989 61432721 960442028 884556820 791605310 280998830 951708522 352682883 697706225 502504864 202192193 945267427 171366996 791252244 776394158 995230009 669823794 508571375 422805483 217707778 850266228 901706552 497217325 140918872 569971570 766659002 933335444 739446943 2391683 364408983 788341120 496448657 945787773 911370752 687408611 892644993 73090428 934241603 37835385 131210278 69427066 75905927 413814519 729066982 309720265 475481208 594813936 246015980 445142869 588930557 905883946 856625524 641221830 844927274 718896151 15319120 812665079 537789376 88154176 69256110 978813268 53597812 447801699 936039627 882028261 59366862 548484416 859900784 567822490 417208506 367636430 354287467 217207535 459621831 25547760 790804825 593420989 703086418 840027721 190052473 109394524 647673227 865627460 803202096 721970063 990292531 599097863 669382275 816171071 673554782 709143868 462785210 230419938 622505080 295880667 524539451 848701364 187863063 538013429 458070021 179356811 389705976 668707207 216974887 462257286 617859786 940904107 528654620 671666594 515509651 596684428 706344426 436385384 10403533 441963291 364705225 436421000 138873909 421721674 410285471 902608870 765703798 145770292 768765486 560827070 591148996 231665378 671824092 310537059 756088011 210038105 29475856 677799042 200930054 661310005 769992425 450463613 355511566 737739656 418065602 810332095 41160386 379285887 769105064 663802433 973082680 648539864 685354212 276985990 428476233 342849479 925517375 266189717 679458409 995414012 375344021 927386517 938486563 213140735 614909222 959404801 692857575 572964914 835978351 423208522 218594963 802095912 300485170 133384036 905689261 141737816 872071330 127301308 330566396 161411235 995950511 832865391 184517116 93932895 875986207 342210779 265852610 478988196 790072701 829410292 727026913 404502193 682511512 824088794 183795336 236360130 414649463 377083796 498545466 472531545 544637145 100374588 833351746 483303992 413774107 214379963 334388822 178527864 620449664 420233743 964873018 651769101 244334833 375325083 676212435 181974336 260118704 176651121 263831776 223070400 875972083 250833188 585684680 476645628 260683952 847106145 413438194 74873135 636696092 916074592 959554890 584008493 603873308 462909690 122868610 182789199 496811215 250360982 105310634 721954669 521516896 107264388 738623189 450846384 941301669 507461409 309005126 12534529 540612335 772715548 121146055 883950589 392584604 574159988 285699026 203971063 210812838 509561036 619672706 236114522 582156982 952224315 285668140 618881296 552940890 984429650 466767718 184236255 903258923 102905558 160133274 201714680 405983797 656522794 521398531 220586116 747937739 19520479 327632833 150929962 249621600 453523790 983659365 766103287 322288954 419574522 415260228 131127656 380407283 65420823 764031951 226442985 712187517 793614320 749399167 501565073 608315153 918251233 817747289 137868484 635805245 995254105 436911791 927419723 185768032 964239372 355726086 168708959 56290219 159909736 430500604 605946355 582965603 718656359 660663893 379511857 327054763 346487160 229087495 426290600 427150932 301802433 473049881 783325280 119667325 587154598 236608179 599939190 711703941 465425411 245221239 823930669 321435604 970509124 214307364 468282505 690997897 896957366 804596472 975296784 505144142 262220656 68384584 360089044 122697233 582615428 841664776 505497017 543718441 441732381 172430235 880591307 952203480 540653077 959832490 505705632 325340486 646560757 799066081 587570216 315677042 968948753 403224876 945625736 642114223 830202271 391478838 489149017 237690315 907551023 881123150 710790704 114310586 827471067 760241953 443791013 658441621 878350651 456112870 372135006 41893529 131384413 928204268 594600407 637100303 639905372 102167636 907296574 268039363 726300687 623745132 253756900 413581775 14130702 628523342 798006227 86726989 744321603 228358228 487070210 255243938 300716344 785816115 969162956 982055153 253087004 524966099 396435561 839439153 877397122 893540237 316693998 941963446 767659643 206866056 509479498 529263375 560410992 933693033 492260010 295927003 553844471 942185850 298633584 26856180 81041545 181505737 600186413 251577503 207867597 421712795 399119668 120798042 116674622 864951880 331310548 299786281 195345178 688641028 768398123 441510905 725632652 25569558 583552893 381399935 237767289 314504567 994673303 470347053 738215313 26499359 104409181 725420517 152765729 901376347 968773742 104310878 387808459 953999812 260543739 575406984 593370643 309694438 338099999 982110698 903851571 890985097 501956800 365817110 42496860 631290582 199226535 368942092 187386118 612211821 112437498 385510883 490796272 521749405 986669314 688330075 321716310 341658120 253588090 195879506 184911213 356132266 700175553 868692739 760539946 494563861 244292686 489753346 928899377 697055943 758396788 786105509 714774287 418026495 361448968 302395392 791653801 369305269 942066470 112524466 26262594 842387622 854113794 487163082 614016662 794200945 499258770 129048162 275979677 838583058 46499511 131995290 182607953 263292392 262444362 459042980 643650885 52319979 491147590 521849928 770880317 732547628 811343880 427094733 701569011 464908475 202129248 344732618 214832345 226134429 660353736 174915458 134847168 721548723 27483184 302392657 250016111 502943227 736575871 790776271 409721493 161760573 703061549 705111959 157846269 491796750 327326461 705161181 832849134 534660882 968776320 826251114 455248286 667080788 657813041 531105825 847106273 37063167 910377105 380833672 728131743 228049924 913666291 678996898 641172767 481517983 780177864 991013189 188151871 236806705 109870651 241904731 272781053 743770565 517527815 177449132 635382853 281083422 312535276 95521360 581720695 621551959 584968053 838714211 749423508 691037555 931167367 334031186 636553780 221893046 627312146 420023108 726487411 816672356 129206006 278960110 982831641 283963396 162078585 421683070 662001934 910844514 180492612 957271005 664773831 437528207 519605746 814204805 83356323 622544756 531882179 849112174 223333379 320383360 518206946 713269213 292247601 281251589 442326153 842180501 267420825 176022076 915939953 982788551 221770901 855474109 274266267 228932874 909609588 707491883 891023619 649725469 332005436 799757741 80937905 615715313 837099951 877912725 916940573 544248779 130859797 26484334 750071082 166542865 958260474 729106305 294774403 966163052 601711778 166802469 949400137 431653166 48773665 835892158 694310447 64304488 143312787 139548486 788728 949037424 609323439 567807406 520163636 541675360 34944725 382359223 579786333 997012546 587429530 578496579 525865331 54805939 725554887 752464096 68034162 535335413 306959672 131887371 987338734 422477942 839296010 482820228 315773458 283842820 686001221 609776246 28246400 148987442 470491920 608389880 764312951 885247120 693370824 201798190 739186581 550163175 41655700 470512080 715527695 412036230 261697521 329814129 115286817 242831401 43889475 351852098 551160322 780025525 193420410 669650356 857611621 886336552 961080791 439738959 263895409 804556505 411035983 676580724 689043476 109257683 369717838 958951814 959012014 452198889 16065219 444684029 348513304 159907544 946727903 731672606 831410790 781099380 400865019 835330995 938500906 266944015 774178049 585211948 412700262 368599878 119337968 988722613 823002978 419307956 650754252 310343963 738558930 316530194 95825452 679506568 90111453 527209356 725942704 888856833 244472415 76178247 901297097 196153263 310869154 850138868 435560665 86753813 894193285 392301558 130615200 28163477 721015541 709721611 621072539 647308122 711508875 297129076 230622247 474114108 993580157 205429509 570413420 289569025 429696098 718200251 202037862 468710650 98804910 855011806 935319976 479685812 857154711 651264999 99234565 95554151 509990516 478211388 162917273 129297062 705052514 594890480 410449981 618892337 716892577 725315711 869350497 936644675 432300612 761806223 542530020 253181125 456530565 263574488 452090026 703730655 13173518 532717786 990192229 423583149 444298196 764222269 862640319 689130322 772763428 906335715 751296748 854943616 427363040 289320974 310508128 353953146 818498054 249367936 69702358 105882482 275279348 829523737 549446492 571254917 306262323 310003599 272731960 735101157 223032684 259797000 560468463 554740049 54435480 876388538 13839301 436861192 95449889 125961408 4628206 709290721 69107619 623497804 116545611 869597359 158291923 550194489 572433594 371122773 328175735 396347435 484052920 792091970 521377392 246059803 308793938 8510241 869423110 50602282 750990975 270032206 189641651 511759076 367146726 491489887 899534249 148050115 673067994 280226149 288105351 217959287 278603314 447565640 64650873 429164806 245745439 847676533 139372963 583475530 974912944 757277163 274092234 204816693 971050722 908530981 672141549 772196412 653089068 547127185 510282878 695830504 461606909 809136442 809497611 150909333 936800670 165777400 968460772 605013314 480773938 816278131 608009893 979713197 699317718 930094861 631812539 540654137 979720374 718466308 861451558 91975230 770796025 268175291 940985704 763970580 485844296 745649405 500715965 683052343 298835682 91573479 271421085 39832114 880804690 939167342 813196592 313904164 493215813 417333240 257656564 476212130 133053918 997645663 127739699 782088311 82336033 203092759 448851524 878737759 974159556 63463379 445221464 527608507 237920404 327380751 347611970 369495604 243420510 528298227 975115025 723734993 145083237 542904448 881445948 853963141 406808037 591503614 216459865 826214502 375868788 26539294 970444645 367464551 284815057 784470560 160913731 896309608 465323418 880302725 370667682 364392097 310512377 624570572 612424812 684798029 461806100 231672875 416758756 435262252 805910047 196216362 847801268 333844922 803047363 594214807 132140337 84337382 504423370 192608562 688256877 735575081 127032327 885399267 984429321 231259950 770595829 623187832 810637761 207615755 553453063 972280012 743991868 204301395 626968870 250611968 846208674 875706080 662039270 888806150 473918375 663874478 112623964 467139133 269951194 155251753 624774200 503975779 269148905 202022839 765757266 322729945 490628513 623706244 466126992 480376342 631337159 402426469 778847003 413482020 768580264 208524877 189731321 723559596 14408679 204257654 134325171 854217079 776024457 336775474 55604174 665591105 215147465 218305427 49806847 686518934 315730586 129572995 561791408 327079813 929178258 782119092 464197823 510062946 334942793 471726779 949998471 928446175 468892178 930942789 25837763 448852041 826089236 816052560 48994025 570892966 514419517 763363900 353227828 228847902 573900627 685653320 13397999 74225424 879709449 874849073 935628621 545561456 825444313 682868781 986164494 932351087 522808064 198808053 69863261 916696932 473151941 237274202 248015759 848509350 66769686 536754499 114035811 560094709 476554263 569891896 669413542 798026522 271506932 953810595 962774871 161141015 911972627 799750576 605948891 638055089 511704807 722066842 36288618 372748992 863903543 690914191 123510045 460861888 25994837 873838215 671191525 494641477 371615412 633209448 894955853 229930131 244685336 297708469 120546557 932562944 83999408 889134584 748494682 600728379 155452010 10542299 515916035 134436250 285456042 749563796 801838158 417760621 945548885 134857730 995787895 934328689 806942520 891299163 883559352 28803151 510975146 541765360 36264819 865681077 796454775 524990523 975126901 938963795 843198260 293217299 433940489 963803422 99329901 210543686 262417854 612400817 67852577 658821280 268103003 555062777 191857785 110271239 605538307 363654351 966566153 249757193 33303725 475982260 343216820 506285992 557471049 476971055 467400900 432715370 352900795 420196537 897242201 238874980 254796255 653436559 959088524 711980066 935499999 622187272 682164993 293064437 155686152 278190092 963772628 16762689 156736654 546209086 356570732 85409359 645363638 912658821 207399451 804778697 610366896 532097982 659848757 219379327 457280290 665390022 519014474 225565041 271592899 83369095 551192465 328427889 95889942 759197554 583041272 263029569 874643980 861293244 940408124 791355140 296172410 312099694 17517165 258381256 886503570 777713294 97636274 451819753 990551425 134626748 856159292 179771607 289495988 381093066 981852134 980241928 359928369 915772419 223947922 225345168 334206328 902831243 980432632 45242206 768277789 777137767 728498893 772153288 581488805 405329016 104877450 27421590 703991901 282307322 803855529 634484501 887852412 327737938 105118770 439254503 372858315 872615437 726982699 931760785 192178898 360100303 64927530 847174524 484679875 774171777 985508269 762812368 813865709 892233754 986206782 878187470 109818521 160558351 921629584 543191460 83307397 499749854 372745266 559988101 966849514 800041944 309672064 232233499 295737311 349475077 527255266 569970750 232262892 325627101 783620844 162054689 391534951 671152284 324334041 476739212 415110680 150647484 49948151 754649285 267822105 98563056 29318275 642406860 273635994 268104065 361308050 97607859 202640415 26050037 744313828 677785028 358558484 231126431 964951897 885101433 190664362 266997311 779260491 69068626 58138436 857457238 717375749 46620519 963368723 874724179 154391711 336546403 482872644 208353717 556248504 667015576 852334505 428358618 502266506 31340495 521929935 838952695 745883706 19079668 603918387 372830944 595412726 170085799 141471359 542648124 636627898 534653219 202360664 330970498 980854080 151431093 38358517 474106168 878147790 989399986 482951890 510905157 341061678 564149241 137837601 89216685 806549045 924359538 202248779 685480867 804357216 419893121 685624011 636750826 355863176 300504047 815066036 426253431 973760442 968222403 879475998 178122114 794269669 267548834 863650001 758668642 136242089 739476358 70453498 585313511 135817428 952276292 83637914 659111206 970570688 104117105 71746916 169443601 553538286 996081380 819950896 189621726 952393800 233196766 998097453 609475601 159266731 501867415 891176974 209123409 594667393 764096497 970525139 927867204 398314502 489431910 368428693 888266609 409818494 438489887 431122931 686414784 603118669 63225536 378468412 984106707 389795473 749197587 962510558 342672913 188734965 645448729 143491701 544771119 239924355 674449874 110575230 771916756 444309290 615864338 465620180 298533182 654379847 257201063 564437190 661829495 363733823 923571903 926215631 962621207 798049691 620425729 739479940 764065115 522960670 982847942 11149466 847669809 933866590 302397971 398623293 797284300 65046112 575185664 432537881 942609990 209116638 625532200 793211013 712278596 827934520 281842687 845997933 684778443 733342689 520717409 78803281 413656453 542401704 286184000 959970773 480770141 822470914 994366435 604827589 88798623 335996934 982806620 780419536 25071821 354401946 105342623 698024564 370240791 103889995 887287212 891962588 678697003 419287996 948156485 637952243 448447488 733394967 144940104 186350738 108903441 991091512 63521369 749925600 469610590 218649525 928628748 438433666 248154514 800826398 874207431 258583936 324938495 323858523 343322964 187104589 342802884 954199732 545916833 114233163 854865066 467187773 685871425 30893025 981601974 867109354 629899347 154710405 467369159 340857868 932739123 581455716 683430727 437221804 765955741 887263949 577731690 634406489 478532918 463397896 34071578 240443233 559771242 734496303 227078127 423236035 398039267 10736561 700778015 34048613 861122342 236399769 189513911 213881438 931130925 738261632 660942774 760113644 631464027 181054051 829616548 27663435 834051674 807770568 296886780 731221602 911301614 39196684 863512211 637254393 169847958 479514394 228186842 840213564 565668335 895469323 488574944 745157844 655792723 93437347 996035522 286449501 419231223 361265615 720415149 379446025 29769413 640352518 829879251 443786964 120774794 944922964 228585461 509589310 723397390 659153291 944347509 402164201 947973202 422948903 154076473 554340677 674228098 144406763 452693840 489141059 303493928 918976168 437795643 872254670 382067343 793245079 645763589 72436204 186473357 588764219 791906395 254419264 469681164 41488508 304282619 662792536 627585373 279645475 96199735 137005642 384997897 438308477 338845232 76539164 584638782 143692890 671505325 359463907 209681507 710583264 202974189 647848223 66040402 39712496 743050191 328756879 168298315 770759527 502847618 369818944 917417825 855945922 640521674 785996797 258585289 250004573 326237579 803724562 844589451 92269826 436356500 17582179 287531383 99292439 115138396 161954793 976162723 541834042 281073784 276437061 724273063 523347605 13510455 968220384 61408474 554231704 435294909 103114684 172742247 821889430 578708551 196748596 965472470 988781036 3418340 879018649 268224981 567525233 516472220 807062344 894199453 687889092 452175494 686660826 158402729 623754480 220703639 750129679 246886541 159403750 790039838 538285280 228352542 502635215 256757186 407674501 433541380 642105390 453766180 743526749 34076898 793222876 187432416 177444844 691120804 884065816 645327 870514764 336593042 57980442 614753408 106958509 927839893 148210490 684885858 690791232 235458556 881106463 534953398 531888813 305154265 870569964 589499080 990275235 557677385 37865971 215418962 324592422 888463405 726355561 920321920 790065790 66770332 798472316 913677461 507077412 814567963 829339412 552189084 149517673 980605439 25173724 976785365 945705492 668925692 131293358 842749582 604011909 593173203 954797274 69126428 416096294 504622868 307819260 833135788 991411578 851535860 552423519 498494207 544259031 780372285 569112579 221487738 608214062 783780767 390704381 290754898 593858403 888105385 91476519 75841030 575088788 615682878 609231299 282919587 21284750 433686467 105697768 879473827 767787520 716040896 687644737 715289784 375353754 624371159 554344945 505732143 100684972 627184674 886067457 722423246 367689218 465047330 909157421 919984273 800596939 170579709 621783680 977388770 278200127 726831735 381432751 170849307 596343072 114480254 959900981 559761159 402776134 43965660 524875793 593508817 592250456 279767848 252261552 168868175 241166621 890192215 442197722 591203291 564799860 233958649 71947878 496473048 137368105 281314449 907271885 32402906 487524950 22199593 325902537 434071278 699790596 474685923 544040569 513180353 786941295 162506292 342685752 206322466 841466404 50695323 104963822 730919924 111742622 462832460 878948238 530559184 320774052 993650457 257636040 735131822 233561347 174735081 313610749 916935080 379310443 120414267 507613914 221429240 635046152 734373404 302733887 296623421 379605461 178954653 680486597 307316768 63124331 124776086 612200595 715739297 701892988 668672846 492451800 970933081 740212006 843504170 20643979 161162178 434496485 702961409 900655601 65088890 851120041 289615163 211806216 396275134 893368025 364193319 318811464 726967996 940194864 607262070 500781900 8147932