6726
573883851 728838843 993139238 638184203 717331195 9869512 840599262 933874745 961267407 684709912 8587109 971041035 267741248 154361457 51380709 823313414 395707045 494562294 833823496 270124143 974023142 683124829 376015667 258246880 422646440 346391950 454011557 423296354 65027972 847853092 866503080 491428174 576691934 712158669 129612376 146539480 722028180 822727989 80414224 535811938 359954253 941517684 359369324 627695500 95879140 410750032 303525266 344102536 905312326 137348761 466743031 731851819 672989941 842758697 990098699 95636381 41666999 296626607 371449086 106694970 144479698 90468517 598123143 573687983 802627185 580251870 720227462 377171717 402979859 653158037 765500006 762934111 447192072 124869330 243145962 395587563 388135713 546671227 739690098 145964390 536536340 58949480 730332561 209526280 901708177 572947611 157679012 943375175 869574217 529128098 50070144 14053914 619596614 500709638 440258248 274740151 80961507 13002061 651911867 336457717 666160097 269928224 951908179 113352168 247313905 47570493 361456082 635449618 594241719 101146179 633930359 130778058 12612011 364262919 192820690 914320187 937210529 350499701 857695361 659301097 879627798 760281856 525871362 351740764 113507845 966129609 626480914 46985703 979131669 130909132 235959772 497808117 400837355 187867950 463676636 648151260 235438442 825132717 136117229 682196513 778795248 770047587 665490922 791407258 134310506 858311611 705727444 924037386 61327664 415939156 435854835 793471813 28737363 961726196 145212576 142245207 927855805 771693489 41747261 759503825 902602620 277707032 257311942 155956327 318091334 720988577 804107586 553529775 398637646 940224814 88242639 177432893 710272400 753733561 968840150 697099257 464561523 527083945 473652995 525889186 795539452 909507829 171877351 824276814 723750376 317089926 819038372 504122532 941299767 713301984 263626357 696418738 991009016 373454650 852375064 161616701 94443226 656482649 715146475 345597223 449223814 803389114 523030115 12012566 409639026 344386616 709111822 874200548 723986912 35281168 252606086 519526363 797305348 424483436 196319528 521055724 741573361 867874251 25178255 535389479 581176235 141320963 231808217 424701602 514775612 84183280 586318302 461735190 593182281 153981128 807332412 42406094 809886593 182878879 54418659 219525618 379781846 616046833 93726166 103768758 503844352 198848603 475811472 301149700 623332038 672131000 674721775 217421750 392521602 552416381 752811229 973697836 693737344 984619445 250915789 61029307 921319076 689750442 375280848 367017708 843731570 35129612 261940154 506134514 218008490 168875164 725660132 597790335 637438348 671902649 554075444 141282700 870751251 29886916 294948751 346599640 554534267 969670525 564021389 947055868 522086905 316832617 773270056 68340600 153968413 24185844 129369907 927803841 566452638 357167106 147337900 262700559 392296717 409278053 768835072 610305206 430669569 347011555 60611893 68107916 18914203 614687336 61906967 742181805 497090603 356855717 88781444 51624869 326526241 505319185 998680737 701129498 822151801 624467144 769470097 828636566 501169339 751356355 756440406 67621976 108523461 903778305 330322534 353336529 165572710 99157606 963641735 596242278 298685512 876769979 516866545 170116067 343973666 578773512 912297871 841064269 935629228 853595667 892689137 114671821 211431203 743886225 815801318 33583003 220869720 437787766 714735920 722039059 41660473 323692677 789661034 2700285 79987334 972499920 356036813 245560043 924173877 172194899 694318672 222859388 48964877 211185216 392975454 392938543 789958727 157789677 86519163 578104307 863901695 979208299 692776127 75332897 575610876 508577444 961432251 796480595 946365209 676168171 371036005 988025681 999860847 13213391 990725965 79848180 985713310 199279130 177924574 909887186 371474028 872243245 985262925 420438905 935944813 230754731 665893799 578419891 388544407 752412961 156524197 104962453 584137611 849300323 180295349 12264838 210394118 141727599 808745433 9275679 670412121 32297789 849817711 522789320 45511179 693060028 455153851 31224488 892339157 485594777 793628025 263813184 210354373 778890950 536768440 146299185 9645680 202662238 724719076 250706438 955075198 733759624 355668890 391729161 435576299 388480590 403993998 645970416 382724540 65255782 507762446 53136661 97553571 357580157 428442332 143064749 50640184 736112534 174289237 795495692 221707310 967917261 59308875 432061683 599324562 448593667 430877219 461486593 651255904 8112646 564709382 458847454 741872270 920378271 850576614 177448568 161375212 107086963 675935335 544099752 172342745 183697781 449752764 269896315 393794289 878195095 412961063 296950824 466823980 587250299 92446515 688531290 407683912 4271741 973109324 859524825 452865407 403986542 173527770 956637663 412099188 738237151 268001468 6487809 511131774 118578081 183936376 672506985 78181395 859871710 216606736 250524139 896085842 666359499 520420453 289880130 397070945 933381516 586830953 863894925 373148166 531793819 404942566 780832077 536065560 230568241 492873254 841447318 634554782 666401023 798084980 899170321 404638173 66086447 905658129 915769946 37180879 89594504 440793283 115362274 801982566 657400018 218402764 550584759 176275869 738823217 840464889 425863165 672204732 279812193 142274441 45352897 811606012 547217006 678701326 200187923 777785246 24090931 41635240 264856380 690491953 692236572 16543052 95130125 610839370 922201181 863416423 500536601 864312036 156726057 468415226 518810953 814126074 686817989 69395712 842918294 278157557 762376952 268781459 950362288 42189144 411055899 848231537 706311507 810789257 379449214 759015781 441090854 403540144 653167373 705947233 94032096 197920296 722490285 41678572 808759665 497207817 757611346 161812617 361519852 914337402 482744194 880330805 580979828 22078535 802242868 276414473 300236091 564619819 545195931 103114731 459325314 808768182 951346267 18153173 619557438 183311832 777168953 60648291 439368327 282852677 619111876 385916774 480772972 194118512 280111697 142048989 691326328 37723043 303861605 905362531 804576796 786605799 638209687 238072975 808684333 440452554 514487448 108920423 857588724 912199730 64551505 169430390 720967911 15897771 187583562 193041700 51725954 817268866 106206343 491094280 100121543 577834570 877011053 580894514 771953081 9639102 722943502 315795760 47362144 879321459 73674642 704455291 518443609 711884329 795044618 179644293 4853234 162048417 141081067 862441958 74248146 205632572 31872347 647732409 74046694 71972260 840774108 125772648 889241125 799496802 469383279 989362667 377331371 198910684 422773533 1800803 208549785 998233386 170112914 108428280 877554844 243787556 812883570 248514804 955671884 460444539 428159096 960525117 622492955 569240163 822967074 696741101 774872734 707355772 196989861 848919427 779328031 37763968 974692074 668569156 689777122 296591705 510448174 67108492 495502388 785738058 921425647 704052172 783971444 91538560 812480451 514042639 335326115 477880372 762557443 143514350 938324911 43232890 104039467 560817865 612473052 779522892 110075317 387345785 486878664 307065177 88781564 118723046 197345497 63473637 787292201 887122618 212581693 150256727 806747461 708084080 935994784 580689459 412136251 572482579 672228019 77133053 939041570 860070485 555013425 554115364 3584835 493338335 597348253 107624301 906672551 209821305 739663544 16747868 449683441 79058559 176329396 538465004 197781605 226191244 454454993 985073805 113313861 667036685 987846883 772577674 375120765 776358019 205783484 639773367 201356949 878011502 716906420 140398518 590598339 271919844 694513881 594183173 617774530 144378486 554323825 524447080 354199790 146503720 393711299 803883230 225562279 422557047 194864586 423343883 648748290 649319578 260934039 614578503 316356262 248780922 239672528 543993378 25138940 445456011 183766745 79012240 175983865 900673164 219410758 766582203 25109359 766440990 213281727 642883888 910819475 767605551 19847319 117535616 914109270 266074970 921418846 139671548 688632016 116283431 415531782 337380305 618119360 676465821 951958807 934475621 925246742 44147686 330985351 802902033 489603697 514752095 881914272 665587561 267941610 953841381 432169763 145567320 720282371 645451489 788451207 483618197 265573391 660814877 601153813 32199012 926889846 375089010 24386912 615521861 343888792 439918693 805418518 962008151 116384513 609893676 749000123 894147606 654041362 79985473 549565990 143645058 447253919 283996614 809232618 715195528 90354346 93918732 860762847 810636716 591886572 501730405 146771265 857459962 15061634 747925077 742175325 941951479 123014086 766562236 409989692 466902877 58997281 215408209 281427379 27898145 825301884 30427501 774562103 331859597 110412974 176644444 475504654 410183244 460641057 137253623 125378772 550995403 83688706 838657970 214148470 675575277 192904727 360919734 385551590 207966360 108844810 127726915 2434190 84375247 746805502 412423881 403794475 805802782 627832089 685221853 686217279 305650325 715649354 460779381 637509921 678578679 637423824 965530927 88761922 950581233 102784549 66657045 354092987 38989607 757831367 568241456 714564883 803252445 781677542 100116473 11218804 743038703 80359739 13652993 827413950 827165240 278593226 83724776 485484374 906425314 768946629 171701652 64591990 337112334 484997384 554618263 15691012 122421207 520149189 956969285 925518791 475450089 876142682 279611777 514439695 486490400 700369585 81520930 142259196 482047126 181637402 5994351 77602180 261997140 19647343 905016129 89162379 150756920 988740905 427163104 57182234 610203885 598864755 974290575 947316218 83862138 528908837 815523581 58799697 901574377 625009217 836834839 229540818 353668250 116446616 743980512 840158649 669332552 825501441 982417844 3896029 859655194 988412194 81498208 121652333 860575889 986514337 63331064 11332808 827771593 343010519 921031393 290491829 941875274 747838320 237808046 878253763 129263508 53331626 789569811 30837885 530857194 478921002 260378702 884525444 447883969 856875565 577200444 117216520 534893358 412134640 121112548 394548551 253063185 202610755 368717236 113639073 41641443 284564651 977488233 721929387 627575169 751035977 12421215 421966794 351390648 102745612 152736909 480654156 8593589 794823071 511492040 539450783 273744072 624387093 423976226 721628040 481262657 1176669 691360911 16156014 265827660 812473458 263220917 518890845 867600565 484454504 485046269 909242007 769019154 315050853 483687746 249110674 66086830 496108960 523593820 269993829 598854572 676330728 750647984 607448160 323670150 114656375 146898942 597414222 739043467 423391519 171558613 72822476 277084540 862919524 88978489 542912199 527909333 204715757 61803043 248026249 689170260 399365664 9784608 310705765 714416516 493472353 412332791 633019697 989581312 935926610 903013526 440952235 464773689 653661509 900916747 788443838 768317884 900332040 238374411 359877702 176239911 409933024 432700177 453324450 125368899 374195018 848753000 505794583 578910774 763072395 753820832 120597386 162438058 763605439 283819502 876854573 257077791 696152292 362390622 99175454 632078901 265404147 392644041 96852589 771582007 293560787 737812779 392416242 46409178 976187189 752293944 222649088 238636564 184994120 675973537 364005462 559189137 377242889 869800045 990616263 140315283 476137228 111213648 155269692 239742666 247549501 32124264 349336808 943701793 247031237 448512261 428297045 512435383 841156301 377665986 136533742 987233439 115478764 528949983 33642617 91665952 281243926 256291704 182818868 318754398 784781593 546824329 877943534 162024481 269140725 721076148 154856115 745277952 684806147 310125806 837536969 932355648 194766421 186873776 876057440 441797658 487902389 156870836 954233040 181575041 534536821 90766781 168808480 650015584 472233116 54967448 594197888 753477041 311259151 777016755 72231438 96040743 176357435 802691324 110581575 298014512 376283823 265437689 43292463 61089970 575563494 733345784 993445617 770329915 920219559 722019408 64643924 260638299 878890243 18876963 442213340 265943416 962160096 611021819 915958999 286909563 665989266 362673238 40386603 829764768 992206344 965134393 778321863 21080131 620342068 888903437 319094642 996625890 6857478 214903456 910232211 434937323 948249239 756194179 57783589 720985150 330729938 122427512 981623448 62136533 141304475 423836787 328079948 955980922 887374957 96555298 95406836 405880574 459228536 135793438 235645342 303951231 953444182 13967204 325031361 426302601 755386992 644126002 275444843 614760821 859029458 38193405 49698144 807278696 794387584 107481732 380780197 125117521 229909244 362403645 187254053 223730070 638756783 515334000 32227343 526131740 611889298 127634178 932012313 923634185 115943967 20174006 227585415 921904501 886657561 552616776 200723453 494560905 49259129 476168295 109321725 908288586 514361700 11536220 568083634 161265635 119017952 948863830 286383155 201443547 163783826 326153560 425173616 802540609 841487559 309917310 181188700 305893208 437551487 113201012 82043744 406011805 985891370 309629159 327916305 872548930 714762286 528639758 219626186 764021414 857324404 328947911 672310000 224202455 340484130 92909985 385468089 312018433 41773814 671851244 513461979 205557640 998004803 938635594 8098248 692008713 101069255 41803299 850418273 538620741 7520662 932462016 944632546 993412031 94607526 125065202 718477313 809369811 506221311 938103498 573391225 363545715 119567760 98217576 587748169 460051890 191127560 973216258 772070322 85417725 497583853 138048653 290975364 348105007 76684246 151589963 892630071 30269853 193393261 743048343 568890593 200913923 528026711 366039490 46842305 622634236 343621044 765319617 432004047 849842354 703423115 857911623 65904420 822990874 956129198 653652589 135559115 999773109 479385198 760145789 85190833 829485402 898194441 228682549 30106760 827395038 380272511 922736830 857664890 426182124 518301525 279071835 627096046 46328235 645111324 673938350 668962470 988732367 291774319 953482868 691091073 995197433 811394490 756995492 670704658 620040039 263164432 658780125 472329499 742549629 418925913 557520332 424551382 169636705 786202880 454658141 997031742 18991742 377394971 854696632 445173865 895696495 133768466 924786262 794541081 631396141 451240964 316019902 472644860 743015282 269502770 16252284 590729066 933413611 773247775 113950075 405970002 36412207 772730199 878299500 631478187 44172463 288336183 56029569 213809167 74539062 510687709 210840909 946047156 740599031 918053892 243737372 488811877 904338709 168523634 283352957 388251201 619764597 599372859 860896060 215296230 721391980 877148343 806025295 654805590 502912470 919975369 60775591 539324676 692705568 791591443 23319214 736878030 79927625 79348782 950687197 6983039 442552843 14044457 953030194 183151873 932098348 49283917 671963750 688953408 217807550 807833058 77204608 690088498 259722268 790617020 905384727 981114247 520281714 711410021 488436189 23194183 483901742 401728131 415035210 29123661 193319573 438354424 766001690 125763550 517703205 569205238 132746588 960256047 435766046 938293133 995924272 220380745 987577049 520404373 909334152 57900951 328237430 986538760 747989448 587959698 629672131 653374175 421590296 149953844 217300547 910026484 25664379 701202288 311754615 440699588 730325948 357590539 879054011 348843990 483354088 249273568 770565579 616100675 62045966 206331625 406910159 57970237 426712369 394487208 578374609 188562873 452388158 759128391 27617984 52893957 199604440 657290114 706268131 621194735 807243957 776085030 531221219 832908335 329803669 695492185 126124275 60129617 53082723 5178285 261489958 536436811 254451852 32055536 5053837 316497818 90903512 411963996 226984406 370132233 658967555 805359015 558695105 111355712 417003757 586313088 16766020 616608196 243603201 723034151 237802930 903363509 351635532 621540500 588788196 681439200 317032684 714912470 594085168 222631759 720090754 855575125 759068569 827058958 740147013 616638757 143556775 683566876 28602752 223057532 53699108 540086658 28416546 612394212 503958721 297936654 51223651 520724741 914544849 294826851 96275243 4864131 50706712 447910774 626404630 639494907 129349973 943437314 354407376 723435141 18585424 927014481 431526617 777653992 754073438 24189981 246809100 750146564 707756857 127928204 973204096 613972316 668014861 854136993 78882880 171973582 4589999 130106530 692698322 919134847 424933381 788973564 923998977 475640092 89400689 550403607 115134998 218750661 346357272 322058725 794702153 364942695 101589557 78745122 995113038 855662995 102935102 241922137 458325910 663208310 369850340 284046357 277180626 37865201 990699702 356063505 62355134 995289700 486170034 607569807 914424546 763619766 249059722 690939875 91776209 338460410 93859833 59427558 557211070 440217104 381486282 204429575 657676150 483075839 283174696 652789187 191255185 386109797 747227675 502097446 49318107 117078015 786143803 179015084 7459567 629359856 387594940 922331052 624649555 873764973 529900858 391590452 489901091 778960579 82530326 581677299 117420988 28906510 641104857 527148409 469123613 22591138 731577983 126799762 358183328 14752678 632105300 401954864 253378827 231849327 904052310 155213285 201443693 542712464 186744720 61419611 172072319 574339659 983750662 649238225 300620983 366167871 40828676 790522073 145128449 975875354 372199372 115065788 4781863 13304228 494730548 326421828 888411717 78824883 305737941 99111397 946093912 790359593 501066260 51989090 22208919 257634921 207202374 223652611 800347384 393947093 285072221 972419702 968286751 121339234 474174278 121424086 487507104 367519306 911946158 485151904 195911011 136661881 452734043 53209225 2482460 947464590 379631052 890894177 878805824 537885345 842521925 824899736 328244937 196104536 876888825 202970207 453739457 936607551 426622817 254086840 183070995 564211389 79022894 3874098 685550622 553197171 125298183 173057725 920716476 37244340 658209628 116627486 173906221 110943670 22353063 176388680 910924611 401984114 919799208 642246787 939869458 762321132 319662874 120630746 958425668 49068050 323600952 264681476 985675600 602740120 518768315 168746595 166951508 450307560 172620692 852502129 3504731 297918874 878076205 776737558 187679565 388802184 745881396 361585785 352262205 768234458 390490817 115703168 22734923 310290024 757949954 815120733 925127508 77612827 935751478 736069527 126680876 111868782 751002 112356476 714608901 372035668 133619422 734076761 822343228 158756465 439095241 678364310 456675338 317171446 307618219 644354902 705973629 53499614 858457039 58235834 674250423 248947855 26455353 549501698 411754230 784405306 364622430 336881737 862018132 152890259 72951263 841215359 117275392 926218616 806088186 831884293 298254284 939707607 418477405 120597511 98464071 857572645 651478172 407655760 27260442 959096390 904527014 733234071 865112356 762984052 643986256 391879130 864448258 670441608 941380827 276202487 307363265 158519608 465600576 21897748 311409867 391068190 863113106 428685258 317286806 669201292 113085902 468057441 461425250 531563306 441171303 412405673 241652303 92649474 672577784 268912744 51745863 577104797 2146814 769374570 192605200 498649421 161253700 57053457 21607380 102634526 185772296 328970644 113670486 651372871 350868391 425080352 42441060 66497849 706281961 212244217 735699140 819367863 680301657 49640741 203447520 121472959 314562765 445099822 66638784 987140549 714012566 970900999 416761697 568675731 740275568 609366897 919841504 754045619 518936705 941448883 709196497 557225352 122935879 822866982 61114574 326320621 100463685 103555634 392818469 806745645 168316202 128517608 478629859 701134211 30674701 682077379 675123521 345237465 979693552 741762305 184894365 546222469 565179655 601656062 114898200 157971574 63539310 887256055 912017193 582476014 681221289 621213689 139701366 804157167 296597022 53332291 130477788 397060706 9404276 375812608 203806350 177720478 356846568 682436209 878854688 387521268 217029939 406494560 585275084 49239842 773216 770169449 595462311 565952870 371825510 562876862 723924444 435364819 450132916 635941636 870357184 131354204 109671676 862574901 788027723 406268697 915907192 771021862 803329402 925311467 146834469 859652103 103031944 356197388 394604663 834402983 743718655 611634601 93413895 181510091 660874443 94187110 951679539 108853105 660139980 176021400 671729966 384064423 611386218 121862881 872522410 334259753 105733436 982194085 196834654 746277510 240979133 112741845 369815723 896824886 890569663 369166544 756476988 846117959 725363931 3598003 533037293 321598938 615232603 626451187 503109028 128623397 720638297 307304918 237476501 380778276 483326317 909206466 617359050 94712534 883585698 489881459 281488638 841835486 324591895 478323291 440629347 418087379 443581487 662961422 314912264 186667502 32127965 923905603 32785460 610008247 927503605 565822752 784123536 395252560 44790291 139748915 523875956 765428587 447053832 613868809 146206862 930380148 375591626 616082263 877609033 111693676 105963721 159097671 953529161 283071967 489937313 246674859 701159345 933518800 909636280 868587960 120186301 794280596 792493562 5488112 256805195 572513519 423827215 40928730 967766078 468617505 33193997 344158385 234046091 480247828 958027193 232769304 410627976 333618819 848851566 140753360 445312494 807331638 299851030 251358006 942919956 789788343 350549216 496595652 575823494 112701848 365183611 548526146 906982443 10193525 406530609 16303989 582707043 830357823 909749071 402989472 298975328 942943067 747147856 385537770 423190894 705175049 618307074 686335221 891310219 319674991 827088581 189139064 979522981 126939610 440497069 922442936 769244304 791046284 271554940 197584149 903748131 636738550 598626646 663246926 499448426 5157254 532067266 82155468 835515077 441816336 337661291 987006756 237275754 84809147 372544525 660466648 642500547 843367950 199318220 533810765 15559293 26406800 722949828 995082273 5862762 15963248 770041560 627623417 659525883 41596499 825207566 415790366 530851401 276350563 79037291 30299826 281507817 463620908 964971646 969539245 905437244 302632936 956546000 142712997 239958434 181606876 655695996 882458980 24974826 855014216 268786096 40534118 733937367 991735923 888132742 739800128 860215522 658174301 219939897 519741405 552287152 45147462 935531770 83138552 174014376 867085412 113438377 455522192 183222671 930926374 277577788 88659914 86075662 86640139 83889263 326034095 268247015 592101610 208493075 145738192 299632177 477279170 38788661 33569544 321531445 926921402 625886023 34263318 437612054 845825919 554004722 989899205 743489732 342052843 925554108 917504108 61654606 891508837 225542651 244877277 822435210 503120439 186053542 908510871 589760577 122459156 87061318 710523943 567077118 295554392 856262134 866709294 625349913 747567146 752795189 946881357 527004899 231197564 981144675 964616953 929539834 387665748 807032509 525545918 582234943 585102969 295566377 643889548 476611805 521109027 741283176 151563366 876745817 927336718 912590589 319022746 902312225 999651906 29546688 469389342 147722649 738325174 188614988 773072561 485892319 793926528 572470270 12897218 25124091 406131296 830030522 807180277 793797043 489579382 332726194 228548337 74682350 628292570 872437885 403810506 1917948 466237412 407890224 878663765 246090481 320480812 50202862 148402706 172649069 79749549 470308399 320371717 818074722 658923386 93444277 156483393 305366266 665914546 21896962 183006708 72045841 704443835 990186984 718359236 46539568 175429529 946907572 121221918 803722098 671861808 377548775 658156398 138099220 785438998 389336514 236706052 958436161 439539375 385108757 131085229 519288923 855417156 451456945 189879997 366856893 397417574 198879741 672223158 63332119 220776702 855229866 987894312 925220536 697933201 558769899 971760103 873362730 358193822 945498372 529601179 882571982 175563499 187757576 873187553 813518848 577094089 109893604 771955009 16633463 347518713 755556589 388438738 55452220 59529886 430835086 422309112 456947459 629714826 947048622 372795929 850491527 654794839 213206592 628228414 352728039 771976490 452504868 78607120 982686664 250519592 608208299 865258645 278599442 795965874 590962549 92118289 225576315 700856152 716589649 94726129 48374864 472146238 335681218 103827083 531676123 766516303 378652547 988623581 396231128 178217520 213935861 99239006 833012358 427142453 579983771 38256748 51635294 32488639 116863868 34321957 135524582 725072166 752096953 414124023 373554391 343059501 358758663 599130705 896432005 75348312 546373186 797323220 400010901 882054403 753666655 931687023 648570706 132319201 772826955 897318185 163053072 986762815 996557191 996065429 266421619 429057313 34322176 318056913 314062303 151186043 352378869 449586884 876258208 104475822 716227258 102328951 300051674 74985921 701459655 49000030 2850584 100349192 846323250 402861484 982403595 599989904 187064858 483490652 584825456 959891812 380808836 747878527 799170978 229882378 596460307 65592597 658939691 630782482 236165861 973001993 634484877 588544729 275105229 363259436 545536902 991332486 465588386 698104928 918834758 19564393 747104957 921685341 119913584 593428206 324546824 102317178 45934461 511611681 585807829 483276268 324019844 819133017 83671146 975707174 49015394 680131452 893816122 560471436 163430286 129981982 385989781 797915162 571043062 513611361 161174597 116579964 357460198 626762983 667201243 276294956 646327375 414306199 50496648 766240958 860250757 375043472 721074488 906185217 739171504 159398668 241977837 63191348 978531684 325648982 891414873 880063430 5780434 785230994 293051217 169210719 767729327 679040997 967125880 338772388 45168709 980816828 307868703 402628907 460096162 975069945 678923862 106423536 241892496 729420509 725180846 102143252 956980332 298771685 860844820 696151836 458170352 102822656 611859535 436702036 280987990 355790759 169281817 286768423 141021752 462333033 308495493 761267430 141374030 128137724 100039817 39059090 108954551 260424872 441687996 569050713 88011168 120611857 527990600 182420015 702548718 105687797 137079618 512045401 404459481 997924438 60713588 862629833 953263445 672573122 151848220 86767786 28363880 321130036 373536208 21901983 783463068 682031700 635685764 777353449 810169423 588241933 816412539 771640326 848666804 110616886 193207390 789194323 83745095 721197989 971614338 786293812 679402138 108693955 150855564 83861618 959134744 211569152 799007802 764914541 884142273 803372373 851682326 765022505 124502408 77734886 639440839 760481828 759766585 127642955 390351628 422452360 715884887 59280518 46609037 417068042 169897404 239816426 206262364 253642498 961014414 30393053 892452661 492932903 139087008 43308224 429310873 98221751 254877375 80835026 715652643 991536000 884207399 567334969 609074856 861226158 645069854 101032046 474224337 257352790 228675000 864575965 532321501 944559886 776372834 578930537 361627927 946270237 818746962 420406643 52429086 632277728 450799695 944881746 125210630 589886702 840706322 554521502 540624805 95583696 635356528 108793799 939636047 372080278 676128767 548710902 233306435 173714972 649742948 707530772 283584114 878417947 424623088 815905614 675494185 53512273 394836151 37122111 999782510 66099464 310045105 904727947 698377191 760844800 702126045 823587821 203247853 542832366 230625674 743872657 490932413 718498553 852666456 283084812 90578830 381311574 831795713 176401617 407542898 334055012 883932388 691127011 64989311 161071827 507032624 740483495 214584099 754385126 630121957 66882960 820484590 940167062 971610907 518861780 553528213 526253303 194965952 756776065 69085668 278107978 353165074 412534432 996606530 58347881 695619243 87185360 439659454 379931308 116103328 847202351 566502671 35715 390845713 631491981 13623893 897878337 224491827 80724343 504779814 707130136 147607303 325264403 499813549 971734561 696642535 53341761 497987863 891608486 810117825 419589882 22232815 15799250 684640665 18839345 74147130 232776260 958541056 513806584 612707567 74644383 213525286 31726589 927196449 604370999 663218570 940820341 354765687 740226748 21544683 859545500 447356883 21668337 37326255 947170431 993402897 733968789 853028543 343907111 478093626 515662720 616013344 500326441 531461969 300654009 371682137 605609099 533430268 330223192 119415682 998654186 257383926 185457319 30380774 184580374 642344669 546115695 977917066 997110355 286342443 851978100 709172207 586215677 873646437 599014813 385902460 719565685 185499953 238931002 915989148 663593578 754593721 532002491 16436370 138572042 685172851 388118506 744181140 71119470 570858049 716113173 69773655 828241974 901570491 100154429 12822347 396431512 498786475 843255764 246058218 785128917 695233864 955230424 223860946 421396652 406761588 609763405 993478688 592261540 848694406 909467835 108371470 455804479 293986678 124807839 594376520 979159528 365442697 191074011 50278998 936300745 907187183 972569004 764542719 661274025 925239784 629881417 57705536 424026259 325653533 303763754 61671527 20887396 111510529 285532472 294800399 518272117 895295876 140795438 110533656 596506634 50263273 71421477 904827464 196766302 196229316 351720335 28442181 561672012 542794345 931237530 350489108 449981527 903806534 115031826 111255551 681562669 597429595 21477439 105588927 923083127 177757544 19776806 796486874 289268072 157825629 943803624 660056540 53121505 84599061 623106548 502144490 987378685 694528024 259488305 36661338 890757339 611208639 65103519 304945702 154002983 996341048 655434810 456500861 752663933 622982987 420272763 286742954 72928933 441750201 244848232 848528411 619507744 264625037 497531636 761292168 422450666 441335259 421348707 328088522 378450672 44455254 682749363 365829356 591499630 942237667 402490694 334773320 553446305 320110564 639719022 559965639 168967963 147670183 16466499 921631896 623169521 436739261 60891201 696098454 731005814 305739432 397143216 203029909 570364469 894674852 964322076 845331486 188526462 238187135 25936359 566977133 135158740 708685721 932806489 726658369 650923387 187813534 61431689 56886043 507924097 553667062 616851681 676892059 701337244 485834531 451040306 177023116 922573791 511931506 873121569 506095956 817670938 122781137 709125865 240551758 17455988 673447940 85883243 205982449 911635074 111819601 772959582 46793814 673021673 558282422 625968534 176461411 598612307 687400222 233347453 106536403 93583635 702715485 635944813 794920878 188550015 939501471 971943994 963640157 303949328 697581914 469736113 121620265 820363050 31378329 214688374 690335389 704826268 153087968 896317838 468977694 117423920 521793771 368287859 790445592 932592544 994256392 966907002 531204850 534172966 52770806 490257604 627756600 755486290 978718768 275193830 796552656 918220238 99654175 760192813 74685918 649752440 82445277 48822534 322631842 113823605 263510908 12967230 671166224 269115227 761801419 140143917 386539147 136111541 360948127 29501090 68704084 207720871 848924444 452425285 594410188 901695249 942682888 74683139 509697891 773918008 349876968 158766898 544654597 302047494 918959710 619340514 951799934 853921338 668163048 274431775 967744942 931673955 139915356 491427518 53305533 901716775 484087786 439844679 37828315 845035913 321862121 106532399 905273135 170786564 411474035 499683322 924998164 206673275 574366460 287212406 980591282 776759780 445979304 525245878 78807273 217455365 144586392 30607206 71376703 665265791 157555332 891637996 449456097 297470688 383065513 502761629 51703814 867153299 942606308 89532128 564705563 116984780 48580878 322495049 287771343 460054913 822178370 65285858 666728187 249061181 352498264 499835820 25820960 798477567 25081697 957144585 15932931 22184440 840268142 87309633 539966582 997823474 831463981 989422678 147810513 67045845 492184307 199514326 934199143 287306966 141562805 351421057 404291745 190143683 673916105 544579439 502714947 348610826 609865296 21959485 450188359 962363559 521795304 328525670 760841125 399393352 285670254 629290408 274094144 125938396 569116392 814060725 976278221 400580372 803483403 976605085 467626217 148184061 28635762 254341711 288007378 170198566 458279120 692299122 360342248 132195224 89394912 863057194 333322402 699260207 885016678 783510760 661623766 259328333 112036429 274981242 658721685 250223035 904271649 932815828 228677782 325904393 746876552 57472354 726484764 402876306 34077438 46627332 403576718 62713199 153485395 691584095 85428116 611764514 236399568 445770364 596476089 325794479 161343909 929798490 25054686 898876939 565825601 539194803 158205271 530378382 814176044 816926955 633117768 570964045 602259134 861795549 896868437 201652038 771784254 475869552 604528343 658378043 375013236 8105061 573607593 528498630 552205507 659035708 140263143 788605075 104806071 736739231 114399553 118666332 519054073 139454238 17543270 937396025 531165392 28264892 320290758 197857788 697708199 953408525 768821832 299967332 667720425 518206620 501619369 439504678 846592523 958664064 97882720 221605758 819285476 524006664 750104387 371490982 183042372 742883881 12612408 140364794 332139464 127011961 111547477 851193536 118982550 129090746 641105912 650147942 9871990 961396670 848005729 707580188 914805194 469343912 860063871 435041971 840066883 214199592 874546648 686659405 172863655 824945720 760781515 992149130 201468735 363402253 216156463 384511106 106286134 228768871 377392252 438425597 208297183 488939728 142135484 327279732 470546826 783241395 829944025 480418815 597154416 530466105 40515354 364475962 999810016 900579224 799517932 692393250 114778815 526580931 231569007 140158821 204043002 992350521 984824302 405511737 355752773 53497117 790022842 314555258 282265987 19931445 752980854 490563169 508871173 747632689 670359252 979417998 383390436 500303277 312353164 980544851 30769381 352868517 345020812 883095749 105964092 144538743 428005350 73259259 523636026 659574356 65934431 727679027 651924876 50758733 133190763 860194001 104255849 775729957 174749258 239038187 795661401 780246464 729601355 304532573 527879152 252476958 136466922 911269587 752780234 448820085 744330790 636065967 801688601 89351601 371678067 760169045 86406696 799683416 833428303 462559073 311774124 899362733 190238099 963698999 802637817 175945214 676409351 906893665 951675170 851158609 145931851 747336570 483921424 728049557 904385495 11800575 980526515 40852416 775586514 585823100 489672501 372433655 74405418 143877453 314301607 298599836 904046497 253224654 98283252 589991151 715783726 262573727 341870236 906021825 78789077 144508052 81967038 755198428 903918069 886158559 458873388 902366271 486011480 942794811 482932180 390396974 807111737 315975046 283765742 435214602 754314497 773438242 807648256 828719915 769832046 121949863 127319750 526394895 375174516 78119353 116386045 90958242 193209431 310772632 849496418 271998508 307797036 783979807 27196935 64231456 522654717 486070322 819114078 8666196 281381484 154562609 251579522 88493220 470537654 535345263 523707822 77368503 161299856 183872429 906088417 931131901 305822291 885924518 457526795 533513159 816560223 426429192 476987752 9769653 589718175 179000521 134284512 897515210 962980327 161481446 814263017 338151395 500068119 633377095 346817590 781449602 787939703 598397111 869942822 110993709 133742373 246166995 188362211 147558580 430039423 946966979 78690481 588378066 685407848 388733627 121891224 354484422 815162818 598878975 216770427 257397345 777879495 351054938 7428906 593376173 512536384 821691923 931527567 12604502 307585369 130861508 646570456 95525071 581774971 369029629 59035131 568033695 615196623 99913693 715592275 897752397 46880671 794282755 486130462 732288519 35532733 460538037 86772940 850695551 59417011 156059718 108092895 689812857 507114656 115521800 135705381 19651039 789730074 919749299 884771892 97315442 50610807 383858699 45356865 484902129 752888327 104391995 52935823 220601301 56822040 768528097 118353698 103702710 415327203 457000511 688507580 450859936 917538548 627796872 154071838 829471910 783856589 114681084 371801119 290971244 82719235 507506499 163138634 872449309 279772150 900426878 822281102 182899308 284285576 867637966 667801436 37173903 824546313 720737258 110291555 881368352 341781707 228645252 837587413 609625261 685645763 526094993 60485196 455700662 6408216 67073385 285172571 790264804 34270820 656973689 81236048 116990055 16996540 96891033 841955715 296768689 997317910 664236816 479667996 134119838 384391134 147469431 23810092 61453798 720723040 134101646 795338501 915021098 215263250 632925913 524646359 900909012 11537257 437647906 209126025 17945472 357237643 494298595 808210276 391508462 3788636 741962675 508498516 20785175 691370059 202970582 170070215 541204321 867207398 502254562 675324158 104114883 502240344 551650601 18085032 75479735 685752246 813423532 990500833 901015495 298865796 367663543 654440858 310403053 805311448 863566882 180864876 15065442 210381829 989075151 406573904 66686816 583554177 915072419 87471990 127440588 118043001 110058556 668644908 837766750 612313117 196485417 794397984 114553460 748136017 812483015 42549546 286404614 625906546 33050378 39936461 924772341 400713920 694377318 87691745 58541720 410460552 268556621 73607161 473358732 110148123 480181064 540045547 546218652 247769835 480033888 673659239 218329187 590092443 342304146 908612288 54921911 538789562 703010271 21991722 139441930 368009637 64541267 425846543 993916182 97591645 465783003 771204874 350821916 12676673 711412971 261879987 423137224 979969591 335487148 896495955 942634065 668184563 289057853 488852716 915954397 769091740 15028306 986799935 211700534 357332451 895412222 266622444 748638364 450938844 141130517 888080293 818948480 205671783 313926836 665381013 155779779 779709838 289102239 359118047 792386510 515209 620998033 68040085 833001151 956485180 817052391 628151567 477186095 106110243 117004283 245656843 875201982 132032588 232456778 86902515 341881391 980385351 206041310 90519754 283840547 347171826 831116399 102789026 405359961 145043234 620686391 561139739 777269423 762304981 920257785 422172285 615336541 393772170 342728721 300854043 202773701 159781112 929005609 679959795 118407706 898526243 925616638 993609688 883075183 10589767 933028554 77472925 990975117 991586216 20509030 274815663 191274393 851625428 230121041 596634353 849185013 703323783 10290444 478970788 465628763 930548228 901143072 80965303 176836749 96388144 234335697 379610450 256169255 163341305 59570244 374576961 61867548 985186881 220703000 797459082 995776647 6247905 874932006 839268116 997834120 895441035 114083778 41624865 747066463 196721170 638259217 448767827 900044952 648549660 927738614 218190066 431614240 681398037 151671720 608450988 777786181 386007416 988061437 33955435 401865073 47631681 261048747 316248972 885334913 334268098 113708053 733627912 340516003 988640058 425412379 190866474 736597444 392012508 232491338 336180258 588733678 870750555 784948085 341294981 371816566 712686698 412001399 803430805 246601087 563673118 411881793 24387267 802196886 252459581 910859053 204061958 152607613 24424152 520310929 37942526 358692249 486535333 624086789 699208251 327691742 49499167 742591077 64289185 294028026 975082414 400469443 882761703 698349320 37933879 76573036 70165886 750620576 488574434 726113042 997221662 904763903 137994834 874125280 706960788 242970767 784984333 763539097 395578379 809408484 136366377 286037256 20617084 622901709 910124044 719825335 950593450 812139562 314932763 14882635 106167588 142531528 267868429 841445642 840880848 305802307 770535029 763563085 908939234 111625814 342192478 758677248 16389717 332703664 632802527 575866856 575674430 270303211 339405953 971252808 932228046 475772329 257290064 952845130 98674038 19930459 525186816 901783839 684586373 840119578 769182825 643270312 982651105 37051253 337232305 676048304 195369911 107767334 292127740 104309145 219393147 634320218 715502744 88299215 967023881 200821622 664166071 542698310 471124833 3572023 366467469 255869230 331860703 623757532 208714359 283051092 496204343 733901174 37351283 180790715 426537103 806534107 824061026 409188208 696101712 13809682 85236511 891471622 121577015 229880603 848297118 193486514 864200820 416316213 281785728 831224700 617137835 945951798 226439361 88262667 802040172 592906829 196648248 133900875 69180713 405362607 269468318 565385055 991780132 306819600 598692121 418317235 113353707 275269498 680021794 661971770 289079179 617774656 405959743 410656194 847655258 106773213 604142707 711856077 523089425 885928434 395597128 140227259 684396584 474552840 81006277 486436755 67459669 277654525 472853981 989156733 535533483 594838651 407058139 527313614 901658250 5750259 798147200 867528308 281019756 478168993 382016429 570098934 95943649 787976172 833271479 796115258 894749384 289930537 360487687 417838808 28375323 756084814 410582419 712771906 83154006 491588695 51725012 3130026 621759571 524578993 992286758 157293053 119417643 399344896 537123019 873592244 257611506 335270218 593636904 538631261 665955563 975653332 961246546 614415563 616145855 794518025 410530820 510895238 84448561 771018506 781250398 112823883 379619672 191832816 678112140 462773677 535937862 729837152 465903702 157697433 106932496 310706811 167506837 78866490 710051706 704629855 952458733 967663211 39900073 398611988 358810823 558371987 226781672 172573720 172787549 842927526 967091744 435834720 206339116 904056657 59369578 987589513 869396891 438989249 31938680 400025383 754279277 567876541 129862534 72699330 578090325 236795029 383406140 745597162 315661518 93457845 450227016 120636602 913637407 342643440 371764942 124964581 901015426 598546613 297538300 926319326 293990490 117146396 362154046 352845957 873719404 421523623 192951821 595632646 713029223 224890500 995658028 467308499 645283393 125520561 540007828 223373717 214831941 923413967 968970878 383009810 869388163 271714246 503646412 635541921 466874037 875411353 613022853 220405815 326474317 910561152 146725140 472981158 880223899 361395537 825827115 753943302 782919159 18778935 202092300 348464733 96185787 197750327 815773231 741469179 175787240 208297410 964842895 243135532 984227728 786330125 626145342 706132242 910560722 129791753 194190514 377434758 857719457 807213366 597840572 36710125 570290870 597082064 509691282 450514768 958477600 188034748 56974422 593913111 206813683 259066721 942377843 302999469 309333399 610667426 44468647 485120638 818964835 861827893 728256170 655708915 500674369 206917863 361841156 263751442 189225967 556031670 641186200 46945423 215761387 91543123 936171899 786052256 688625186 298379532 89083376 499619138 486414280 146057797 93532248 693227962 257640869 35910090 848743782 566974267 499093867 745728780 52094905 170575054 460073024 632867426 826283968 960747393 839785288 40641475 77015186 29011254 596673144 718201385 928473028 812434531 662260860 717161278 451003138 203402397 15540809 540086513 703021534 501955088 686144309 796553781 47699401 943785177 684980223 896443182 363275796 36590441 494688313 267887052 207165494 954761337 900754477 33449461 768025081 593056116 74090936 845040266 474583721 523280431 415758003 255573100 188231313 78018862 972734377 639234451 281421258 840791537 179320963 984442792 195262977 717981624 633512924 242962377 514283152 171009498 991921911 877558947 207599939 486610223 145445998 414765432 293887911 898716826 300731245 61912991 344289293 374822180 906953257 818873013 898102610 175227611 926962464 86333923 253246472 752213192 578084725 387184081 593004729 757405687 224143224 788267705 327903662 857656148 883746433 842186814 881181997 875668343 719745760 88781935 214794918 717708110 356063719 508682828 616424935 656794963 423112171 960714228 884133494 182581779 632103592 634752455 357809389 411582408 573602729 611055860 163795599 151687453 998239940 609316679 761609492 74899516 250100735 89513153 932555663 133847168 931699966 666254011 862031862 503962078 607552298 76826779 74186539 963616016 438025959 690611473 472927330 861138129 503842052 209577175 43719907 988461996 844329629 254045647 400044403 417932358 865101506 416356353 422136162 715857797 25673032 183745653 790757312 275773766 125775158 575829326 262137285 57475123 94599689 124169147 413953552 702151986 53512277 488140090 518284353 344054587 31267915 991211682 57709067 387626318 53305208 101428973 376088313 897634836 207990971 628649067 168083545 73092476 45005420 590219707 641466625 70678451 773965359 284740288 198968568 899740516 713085966 461105853 809731991 807685654 437791351 76201894 509837639 491303627 416858336 28121991 835358214 448126250 871850024 893067280 835752567 925155231 847012605 64357232 675306418 55003575 693006298 843389963 980612403 590528069 433609669 474595379 513722871 60091379 611852018 712691439 812348247 324937983 26313643 474596589 132623636 464104993 550798482 494977626 807924971 967656817 375615968 495799536 268299418 99982343 241383168 956568337 877653925 88395772 20925568 552960343 995915698 566448217 248866657 829044452 9492638 682476325 156156182 523215508 595084055 768008200 88423298 407432301 945462534 114736940 882028889 930602522 431358284 285343723 278096499 239283255 105516891 653712467 735082790 226332661 606211161 976465957 182900997 483865086 917378080 56342916 889341780 765810130 475307484 138208436 447370933 484800121 673201112 456043467 8015629 268285166 76568018 96438926 528233819 22030551 63692218 262779059 952633072 495050501 548122781 83245923 734333755 506156024 736958389 321932897 732488684 195685901 150915205 915389680 679550986 920809637 824248947 421409117 539136118 299556430 559617552 986507050 784356551 85335015 295066868 644888531 353620181 371634885 741327456 881853999 393665436 805019673 144633057 198814859 152586526 545272190 282060781 886920280 51428213 871535521 61369528 636433248 67221422 64801085 404339279 599288759 985610721 228588225 20697876 524746838 380661006 432831779 363770239 17533908 518166794 658837107 662422438 871786974 30471991 256266246 606157324 276653778 61285918 603306732 327984989 66388795 1095273 610045769 953309075 905039837 334097642 867194954 541473084 401319063 931996038 945812362 607821 917606758 26916938 873822048 294869947 407577944 306653827 511156538 425111851 824820620 22509996 87534289 549123945 52981986 196316886 7797620 182152116 110119155 463620703 510137104 176507950 464715976 972699224 129817024 222272164 306796865 849528329 763745248 560632279 781524367 562073961 413756452 551647476 441507251 287578499 699033775 849085194 446748677 210190312 126713396 124085648 232700307 66764036 673209592 138198644 263080921 533523563 172867111 373200076 997144266 683004214 549708025 314376593 508219790 532041400 536648756 815016654 234086080 152910355 228165285 15610446 714984316 641921736 419774274 9007918 929500234 118808048 858093111 228765263 181514711 837322858 352850910 266731369 904086894 26060502 404930012 19684166 412100416 577797123 245400593 409244681 113317688 795108617 723621273 621537477 179666368 112786381 289070483 413752448 265696735 517235767 281879245 980681050 11673854 554169870 989688967 941174087 525494269 700298429 22455701 707008979 390137639 375306611 973740347 146740884 253883464 231186711 166425049 665983879 661500185 411825642 75228560 774817872 59450610 651366184 248871701 91633330 764152564 390458535 505385777 29849299 907694301 639781373 863046700 919368154 193951243 705252019 713058592 719445511 258066799 735514293 278970842 648204437 110820903 105227540 794945320 217220718 188930602 813886721 883204596 850430786 78228714 810949507 477765010 137679323 314832043 726636710 229312652 78984606 117095244 587214780 961350256 877305896 226996153 676913308 649190401 273463747 234681678 214765344 992909257 345264828 802795988 124396450 993469265 766133242 82140342 640930936 983353959 271070943 307334008 866558555 121501729 385562721 530024413 599266738 523242044 844856455 178419799 605071047 776357413 148031394 192285827 590224020 877853641 271798331 119653679 379560393 545262077 354335356 594325736 390687685 699600184 249638076 515084135 545585800 15771317 597224476 39033087 999125276 868295418 346367095 718200182 842313498 731929815 100740946 294096587 107688210 945597401 472516385 712759257 721954813 473064130 757561435 164695184 350917770 29359765 284348863 730478162 574621841 638684218 177320250 965309525 190800753 426958325 332910011 588902904 295245993 782650838 627935991 146887620 503462608 826819437 865087801 345776105 411265603 965828747 639872692 518953813 763942499 964905428 84229421 338413663 437969558 841790855 503108846 641403679 723666971 787457708 224398193 150805163 278658278 401718442 116114687 469459030 681193118 301541050 58361934 976439110 84191887 538814276 123326730 440170846 218150064 840930882 785946951 629415666 659275980 278335994 885830 423218478 95757773 85115250 761632140 533727330 779422456 117257338 27647361 503089426 904715045 252045553 653894588 183373322 653763994 622525627 505348704 187473463 776583028 416226989 163912572 713291266 955041264 139755653 153462112 25707679 980686535 791925414 655123344 639962514 70261407 656009174 915697344 18535531 741124423 529845835 552262861 373063231 647103172 579910221 876152656 551818217 831955773 382563596 587707890 338236118 857605574 93056593 525709580 634188601 509283581 542138503 199996218 316841196 681894156 353458329 342548874 662580690 145383742 997672218 155059555 68161500 506197743 70756898 86697031 99838517 453119085 491476243 472901747 100222256 923902815 201570755 504556824 608374939 584134350 92264714 946611056 294256275 37837658 324836987 928444875 547121239 866975489 128441092 716478786 401385996 334415773 59027660 63966685 332315866 909216229 71542592 252993718 267930323 994815841 192207100 367768839 447934925 536199694 840670586 400673533 460102508 42241340 905230356 68477446 478892041 997495069 867604853 773148315 35332727 44958191 554109541 434970317 764450031 535066984 3965454 165836027 869482756 62993113 82319063 54314974 824725693 6378006 159825043 92656015 1193847 352032142 312941206 301645123 888231835 153611791 702318655 200850694 48369482 607549011 121844491 527261522 457560431 841965695 300409836 345409509 886923885 854519376 632896177 503890267 242102711 636861631 669726293 111585467 552371095 604561708 18416792 229613140 610939713 178241834 174785506 612133559 382790327 487726711 913778682 123538513 641338501 468613688 324389206 689707982 76162698 298750048 69485855 386239481 140715742 369895690 584165341 880155978 76931417 217061518 384046244 319034128 853923148 906288889 283135946 258810594 510850596 154069089 488423733 121790308 332310922 663209239 586440219 715101248 150935949 352735252 838639760 644790802 821348939 15545317 187015135 750027989 314295364 256500990 988783821 307527457 626396679 572949161 187683434 555844448 642527030 424246029 874878575 348966529 330534917 10530872 607777123 693901864 164599960 96200855 668208524 349427233 759410093 107165094 64528480 762862394 459900345 755684591 407653195 133765635 623746259 594668329 736309975 938041622 851169318 725093795 98085430 330082349 150559308 285768863 885926796 793086337 710014891 613321722 142052866 893066160 476368945 602346340 586968023 640968904 698547194 107692898 990396136 310473639 214857991 907440967 73336032 674758335 515641909 333505578 661040322 139388167 780690258 397350296 929946140 484375928 974960443 28031569 814458276 125519750 166316783 552901423 771122438 728848025 18739496 765691655 621914184 495108440 220554346 61398559 988593695 919101540 169091456 831506182 82091530 383949447 591463500 7943913 911224133 107105408 193965842 572264454 99009926 974656099 822131102 881472417 459032026 797091544 762020337 126006653 775127645 780853471 531424427 398766434 509701495 550163922 16974441 984132031 897788713 237528786 45530589 886382407 9146677 67138396 570404940 91238206 303604194 161868439 951698470 214828327 121490198 145664311 639609132 73016475 120320410 461740233 807005243 431868787 111348128 421541931 410391792 738992124 202395401 941816218 137758558 564613248 344496492 7249350 548745278 242285204 97294487 446792218 981183963 106441164 366446965 551588902 50195721 670051159 565973693 1894191 884879485 687463890 74853 377004968 612996717 972911614 838745201 420001959 257296753 802609680 841543890 667688544 541601804 896455642 609504761 531876713 461068889 954001252 391642414 862330518 48802808 488936900 161639087 29986770 595378063 528086052 434092023 498090136 198137210 65715 352500678 935533046 540045957 352575530 312538013 5559025 178003496 3799565 425560983 435300248 806409245 119621224 102988791 200527400 16076866 565009903 584920464 329662106 371527507 976562877 44508976 420330314 465499776 206148062 302833435 913394191 734234113 589441809 411484326 932371322 442023876 763985003 720420719 982069832 969076884 32958732 987628856 147080379 889274648 265706190 582380626 548200244 237843766 537885768 748727643 106436983 102895671 186164458 436099088 474423177 162727334 480608063 747269842 480743462 686756125 50103276 394137652 273506589 492061436 658138329 58394263 934085311 274639683 778814981 768671494 243716566 664290064 608816701 243313297 553564712 874522891 825693922 101764955 112366656 216096042 703008950 71319990 318991712 889173407 507419077 645931240 904417093 840543492 393201081 385160554 379815968 295820708 631814557 653322556 787882143 289952885 711716818 574483806 564592567 490531799 343155299 660825484 7338214 951972000 904138780 560902925 679011242 582349054 515184232 643894249 798445095 70709533 715214238 117436806 812399291 75149666 615884397 716816383 915693157 9085477 954493288 148025476 157422536 586307844 801348032 797821030 728777080 513064849 372304835 145885998 856112999 567976486 806711482 863451213 372464837 710850261 276870489 51476078 145715666 792054720 547886678 944160760 715280604 115617267 914113917 527679895 43283284 529998313 97012629 958976441 391600141 51505917 107001916 401539028 490330112 760866299 199360058 71623544 126447500 424181244 217509541 982560498 992157729 24221022 846011710 364622565 587587635 122882199 268614994 733303300 767453270 669018023 677464060 335250226 784635289 444094328 862930120 827918573 974092641 812459100 639411365 218209133 716481368 598929632 619748161 59327832 212312283 671624570 130951375 338759782 95805813 348460915 321320279 87963542 372681937 19848341 305102458 960269571 995246891 426233804 546089222 615216512 95251826 76069633 950466737 732403467 520163961 665913208 412838391 346772953 478372308 52249755 564982085 47370027 503695738 37246597 106697858 716008020 708871166 237649232 54767801 657193331 586110147 228604432 597673224 958792083 100969124 902775681 771578005 96216014 181525836 170183578 711432525 276777662 246253211 514415614 9181128 766417171 180328821 274535870 113190123 511217480 179301976 530688559 558587507 682997713 567935156 665285364 251522085 129322673 902934596 158806237 786516003 489044742 239927020 236705578 300353176 340896143 139481259 924447532 437112156 173523446 94631109 1061033 450301107 340884319 515476646 311998586 107301489 548321818 586534455 73007963 59539298 765836430 603696522 618126804 301350495 24148029 135928519 405388931 5987053 38863114 564195167 792503056 380424207 804122187 29208633 680777382 145018329 21206243 457741265 434646837 47246041 552372374 288224221 497547147 745773044 803700866 662062085 705590885 204539035 101112891 778598847 264078332 866949321 234811720 734721487 20816167 111476100 870650006 426205097 117463153 909513119 842916615 909966208 142453678 499555153 791691192 823231059 497089834 665413787 133488676 931736670 712659827 685861049 72477242 62723325 284150444 876178107 724785409 989741328 80717141 825898300 620856527 197311825 545363972 855668246 932033311 418696490 967144346 655199668 844901586 84607498 417229139 540334552 847090057 559682816 39889705 491297600 235430226 536979538 9227738 368918901 321232559 574403916 54779949 393709800 637127241 191446745 122404258 214429001 181188072 55637750 892843652 802044598 105465926 290723975 510229196 37499237 709420464 329889893 545215256 406838401 267013742 962444394 947172953 966620150 522127209 987062657 310434101 757557435 376558546 319661839 126476335 550307456 894065754 33772636 944017255 383709346 77735732 918937864 450654699 258923803 974575613 343498350 913484753 80041539 634222325 276230300 970057127 196159140 606120192 367788734 602997541 725650285 330233128 550170493 692270434 704876688 389749501 2704534 314950474 618824398 174882724 293943161 169131853 921464830 180232148 965665459 157690527 257967879 884603322 608345225 516891681 711695286 951843575 282892785 644253176 438582251 559123084 466826654 634741390 17759627 834615388 90255282 743409911 17364867 640425774 288196696 722241554 882691626 143417582 37192028 501516023 318300305 183651540 523164227 92281486 363883687 488829685 249972013 621851565 225949358 858317237 138743245 790160996 662677163 274152382 286930523 101259413 833275465 753757177 588517155 851035092 440888916 678772436 594445002 310770134 171714562 882641698 33011687 54406187 26059279 922720066 408438562 196875935 106371605 931602788 289157421 322771643 272948825 539129433 944623207 351414534 249963021 935882804 141575529 912640184 210035185 428506052 866415948 43310649 34779580 307449454 746862092 328184847 986221890 193823446 638954980 10452803 76465143 524483018 917375341 955040773 299719436 178330254 4433059 258607392 109933042 146106831 581379035 235398218 685236263 526002241 586812751 935199284 314401396 580904632 700355819 524436580 9410683 566771766 420263581 896706614 874221220 19642024 224891460 712959461 213465469 863846439 575928615 142446963 240845808 493303955 97487735 540565243 671634209 954437146 799172635 634083602 100543976 380551669 721998171 638296591 759070261 161327273 426012226 73471657 742231904 126368044 450424588 604158938 545656161 870688168 500865551 272393732 890330192 578273362 985353192 103795660 294636152 413798158 98758975 535481960 907102113 48763061 76047202 431252673 3200206 875219836 917852626 103744182 108287856 639850796 594557124 867358117 801178068 20569349 793346125 395926324 146937392 243770712 85261 545109904 966975232 353467164 817503636 709821775 931740525 655373179 666133786 226376677 69171337 764892760 761858636 828789801 813655821 690422189 112558825 816856026 418158377 30411450 773116559 526446232 522778597 220190034 246320700 176473016 240759382 39666824 572399339 240213125 135953888 572484600 785323029 102929119 925951763 455343016 665267245 710208639 110716194 331401030 936585315 32403882 96293790 550960302 861193682 762465962 93898843 973752506 431838339 512057219 4163955 57471250 38503450 379458903 277661283 137340502 555931919 518420665 29523677 128331257 611150141 17993916 553332208 248989521 120923034 331800322 704332536 638706630 42008961 815048730 970107660 831110627 847452611 918917801 234587281 561162645 533900114 328486123 534915150 965738452 840543341 391595457 23209701 731563142 771054359 300870984 868903643 179502629 671808000 750943672 307833886 282958140 768937587 861166093 531947661 742376973 45482767 88796548 381083602 87491727 903845277 203707613 918602353 603814240 975141765 5705985 17493236 509041878 334192107 552408385 327296682 174735447 796520193 350506382 906298589 420090904 503893717 627718583 599593532 175701716 231178606 907427417 311176208 116193 621109862 843123868 742493165 666592628 931920415 976093118 606600706 688282044 32317083 377719410 144612635 7458847 383425395 162105870 369017077 717617501 567030606 696313758 892352948 363550799 46820139 651167888 783641702 403230208 131402822 235751585 578931923 362581428 143179002 890108130 215213972 616805215 585748349 957707136 135914194 370185116 786316605 742514899 910983511 818633687 120234308 55596145 826092534 356176054 70218366 47625962 73793555 637248971 743939719 818662854 853316121 643276209 322347093 489474174 46506416 453749914 725225759 477954691 668847693 720921112 220579172 884061664 190242678 806327521 694285151 326156871 29028988 480601756 921188121 940012498 151751794 893938780 848124994 977844327 250114834 770859711 25470288 176424740 260625033 621926358 995087593 113941154 265202567 317434685 603415327 164225334 623700950 181157437 642180024 292548643 902078548 862759196 29126658 92321225 521603068 723411809 270994447 550632055 56529916 192182567 343160904 208281709 86121347 43802249 38642388 188752532 814661959 64112675 365177271 75286991 538555385 212781215 41744496 803757951 530215899 497676175 967983284 6433200 678833611 462679660 298981842 580912159 325438855 328108500 525749735 847041922 51520308 796744182 250190328 108050223 988926748 445867583 168848283 927564446 489669831 207490670 968833329 156848141 124119697 186526951 84651483 662675081 399308165 126395979 318949383 929524063 476588505 139449018 935957263 155422115 602128677 87455456 588850625 927567531 268080307 114600360 627125804 172116966 911344541 729832483 132683540 752787640 175700065 301531823 532868438 517886247 509022492 354218118 674734387 633142188 540745069 611902222 295817268 940053233 590814552 614766650 722093648 67403056 754215668 510567262 75341522 208860696 598022717 664192147 136428227 866103024 778792506 616070382 38219989 542653398 198419217 23419881 147957389 374119281 324951703 533342178 892005528 833974194 887560296 419256266 467116382 428305364 31158487 615450001 220874948 474489390 82733003 942968595 541892445 836948670 453535856 617233967 45809365 904074925 133942465 34753943 622694300 912734970 503340677 513430640 307904719 701759893 536850520 308378459 928395525 861802222 841720637 672917404 695776416 729280932 92173670 15409149 10102647 975848508 630859149 230977594 302854250 713592151 26462541 844746694 403057172 479998396 314497012 301382889 236589672 448439476 188653183 859283971 213690797 544510211 372714611 374111867 98786455 909565130 682490326 27181980 623883704 524210962 700099383 172176471 106008245 644789404 187585619 116110891 473154264 670961119 199604836 776008513 237069622 226067376 473271558 640126793 558582124 640284922 794026033 795171795 88724397 982679216 654455766 154931546 379705778 879686728 529043412 478492233 641768209 64050089 505674212 265651912 588261050 58289946 437828382 546785646 555595702 477930352 515412888 28749965 148891471 715017724 657274829 385961092 793601451 983062738 878604236 352183574 623347659 672630269 147355369 564588408 507825836 654327486 572036305 887531613 386530565 101079716 218540197 28298773 17646157 724214408 146467037 605907206 635020706 584295418 5209204 190616407 62225770 520622091 71882723 63633592 88156166 581673903 302111035 881757617 564736640 180715270 86457542 40600651 705861890 86329262 457705410 66204077 740656747 29741714 953735690 127187311 983337781 24792238 8002436 983937 749006646 154469472 459407495 236543703 591281241 464616698 427160109 506023362 985238788 351559183 569656953 73394954 933233085 871767987 955152570 350486076 904999609 41610111 391086726 610861498 127939373 848792135 677065575 721112471 731050200 483317616 700816134 714387981 508109853 561334921 567888269 109632850 715804392 27295763 346176552 159601984 491912460 625853012 665625346 329667600 977412194 87798650 403062553 910645278 959566637 210731474 113647706 717082597 104857936 504734431 180460446 85313660 206042918 857526020 658942483 937093117 193359987 212274968 503997449 553986192 773609888 71885718 663619041 341930631 951697832 862311945 501532614 296126644 488164956 167157959 625794243 318093502 254956609 28856795 81255131 67039597 92104620 194902836 784122193 49478907 699637267 964582638 134792567 758196536 674625010 793735049 547806004 720501348 6010016 51803453 274487539 632136255 976205522 790622932 974066885 780419705 652934876 475599498 76546348 993616183 495273809 702340590 311709684 750230417 583713736 392964815 669786365 528334707 587867650 306424909 577813614 140021268 123523898 712606180 898217803 798148907 358857580 298540159 371166607 217383947 202859963 645654145 849520201 31581836 288793428 676103437 812001540 941728303 4219286 888547888 787860838 499493094 443404829 99570521 102239862 879634917 345051687 772026226 407969623 785435689 78451134 985783236 925456956 201975032 550905767 676191111 852640290 762279698 974731269 223806896 979663644 30107583 721977393 681700196 61689418 10770820 210319984 873690957 805015475 214539270 614755196 592876312 714032363 58160025 544963184 816272225 790311293 742531223 588298450 50797267 527966911 519265936 36580503 305940218 721240967 440002621 834647680 426397608 54798671 661895300 650204504 34462314 692002882 224698248 568678862 753692299 235469067 778998845 627383256 40484541 993538114 94654803 485877204 560086829 5331179 883356740 376359053 795642471 625887962 817173854 846439738 6371224 336439789 735536592 164827793 910197107 28055564 999475473 336594715 82854234 661370772 839315570 117316548 205890006 64013817 538511761 959582304 151999235 170026957 439481911 45000128 16081423 534136714 530877331 576168251 539467892 266750422 805043655 335110363 892638383 622217508 34066452 751525958 811173649 769603043 916353751 721370755 797658606 915829223 910481821 880512840 429716346 749797390 850345739 635606351 666327558 241373851 447705007 818326793 411400807 887186917 863326920 279998581 421323630 246720602 856166831 960791522 513471024 513726837 148418236 258625758 135944345 182484687 10151716 799634345 952087729 926505466 373521451 602262686 694851040 284003272 482775525 977083737 886317013 185637615 465206440 552644571 427011465 912911446 223487715 838412272 800098362 86814634 118410852 73938344 333535235 827094035 887246217 847006258 193337223 35664452 105632016 181797919 70665490 968300083 981432263 875269570 747321900 354953714 477532255 294689291 491473337 812824132 271773027 377790349 998461746 736979466 782951271 425473211 502407263 6438985 116401834 155021977 93253618 87329037 228960320 279305205 766939423 116206536 978827814 960276646 4387339 936976181 142074564 927569180 905276263 123506827 802838749 505114514 330976892 132887355 799803804 822450228 945711486 71576831 52756928