10000 2494
456966710 810849254 265574219 36240361 225250117 576449343 827109631 633411015 967082551 220345104 816599850 502726206 510508481 586409049 187722703 552482283 417351465 267399715 99420420 333851215 738000649 855102964 570491827 775608159 864455430 961507071 181960217 198424612 854132784 456765391 247171416 878012689 858915315 261528381 794222779 207947287 641984449 650611660 907126119 182590787 968197713 38698104 436480913 739048426 540852742 979629508 682976998 914950582 152362740 3055645 71116371 313151455 858649569 633574092 747158099 653302965 254914872 204928746 31782515 227521996 236990917 259658498 574475294 521911600 60268320 352538164 414738662 334287943 820177784 171579533 552683927 398874254 141917295 687602065 193208489 867085567 871173276 815134889 759581315 949810178 91270920 836300064 939936003 100328252 326114537 489638251 923509822 748239383 348047461 176124712 702606443 59205515 876528521 486599793 614734527 133037739 394626446 715568177 53891178 157232632 734700929 443576532 715045867 22975126 753907773 497123401 1770709 985327612 822317767 960428687 758139689 386428234 434075339 85198196 433380633 379564892 149027478 250470506 301644654 156408923 139367121 88694682 208588100 71736708 649890559 47226190 615488924 342725152 336069063 780598031 916822901 824032611 626282712 777043027 183702025 214757476 113367144 151716346 421713128 296409991 998521953 447637532 379369852 216622835 208028599 213558903 196551422 507741816 348707017 542902166 976893935 17396587 711579708 247014147 6847553 801678565 313617941 683768233 907469975 321117440 587095652 215713599 391003923 956848432 479865491 510637110 707980889 485734850 172534933 254426292 447833128 384818054 661440811 894666222 591280899 963289612 439517608 371455521 775068598 116917604 923681361 407129754 27409929 241315006 565697763 863880164 154651104 829770798 5055340 81713116 302189052 793190150 25718760 70635240 368485639 503929818 872495038 885995005 770237662 801854838 960804212 746091997 383960257 869659319 662278117 160725430 959647390 632762736 700534757 144793712 536512513 440292041 652349923 348126666 2560198 701520583 159558746 567073617 240740653 463945327 236117963 408281873 794817956 761732407 465827534 533379805 495484762 243090646 989139830 449476042 523350749 348435086 990508921 898201770 179759790 87334374 5654413 181354782 913775558 520641619 716310683 403904368 587329218 535267664 632879541 314507607 565998654 247059807 474065648 240241412 464392375 687410847 762221849 921672021 289825909 968002109 854152247 280871325 791309529 638223576 192258628 120710536 620710488 413559658 230947225 466039639 861915099 610366860 675356684 178273488 837857547 486634270 243844626 301688706 29390591 740029367 302630806 58488343 900489986 246022910 863450 235727785 713509662 627417831 582934869 735703612 630130940 2833359 718248428 326568269 712105576 934189249 709215867 84669867 793676192 721927517 519086505 887720086 270292551 703969169 398382893 584526008 546955141 284414638 629814433 528643050 260101021 87666973 842434801 239089742 376440562 441239100 598488242 797482128 668153636 832540771 191221088 272157682 519196027 290495236 753037433 236939783 525693652 781382866 903432244 92278861 686057990 512344709 935507736 131894161 598047626 206890977 495907207 776041725 86113613 279402981 565813713 671693650 111817767 255269903 609144183 6579288 861321095 552131164 137782872 258502122 786647383 213953818 736283840 908010297 205379739 258690333 435866502 119811038 331294345 291699122 563606489 945461804 584293445 601919635 190753059 96901553 566287996 549546390 997631990 265822392 621782663 296230839 856512914 977755400 821610247 749320550 174095433 89750056 747475074 610528110 375316799 722796905 67725524 129850991 670637556 714810037 583074243 712515469 782617735 621232840 2351322 993500656 822227387 702732696 847669547 681033346 109453247 906305057 977634717 786583571 718923207 936259316 231277037 243961538 786258410 985468920 568859388 461154784 446432727 276979807 140450628 935810431 127078153 928692280 63799229 624328562 93065700 447600712 854634509 677879462 508066488 684569482 505708349 260548702 336965402 871509479 558907010 748002928 54655600 846227017 347934019 67123248 307025441 202924626 125189749 871404530 286325430 73664165 919814115 773613206 36758766 370741746 369899328 810862169 491185803 25466351 48355446 326358937 656229923 429024763 792165869 221369946 146008542 578817029 330511924 487683453 349986667 730486024 265009018 869361549 638617013 748110600 520716649 170175947 757109209 474332012 525015513 370626130 46607622 692412679 435586394 740650594 937730097 43977649 156097917 706578188 121879420 919814209 341602864 952378854 992820249 516609578 810761577 734362971 595156996 133911388 807312439 188957328 541248113 172959007 567823476 152205278 417083130 390662258 432072833 836714200 136952245 808340969 928652972 548234141 503716902 524181200 545393944 841873833 492612725 367763716 549201535 905886974 578353192 715621533 197768038 685912966 779706311 516525499 758830227 556956607 925502339 392782037 823031958 545524148 185253698 700513697 316235624 870879155 975309470 931894297 357365316 877231852 744965609 262133646 434364306 826431114 13973052 292301054 827072415 5480603 262204269 830905303 681549367 698910194 276800888 886469988 226303800 225330342 652684366 663480050 523416404 798525211 225314722 574922065 918892791 475986440 681047062 954127477 84818783 204596677 666324516 575407070 994100144 130816176 351277703 776057484 434187257 768303288 907755876 658072413 611177842 55248061 859785679 245209083 814621443 163058897 924525002 299049762 709212229 135386020 953345762 21702834 600696221 201461994 793175248 846363806 862020151 993552191 250649579 944596544 760838171 800824738 897681223 82463333 728694096 247083215 340206930 328880604 546784124 339005074 20585717 552196507 797932738 311336001 241616137 874665105 458287340 457016223 428946386 805959577 844823198 218973176 719437365 122394799 739456096 787032274 711677358 281403235 20092360 863400837 698500899 691637617 167103014 523428289 749454511 859787167 683763224 822651427 425090168 437504658 118314922 747181252 50695668 894706307 818756707 778419122 714632223 169651651 641512655 327691627 871685688 508162280 585781779 837938446 326758226 740015334 855864002 159216931 662501856 960751829 411571968 927034087 592536295 69576745 264382424 241272741 964961509 210908677 90411522 855744269 149751947 373974755 295848314 809930850 913359823 334119424 729050922 94955564 838471664 183098338 823174248 483495739 190689943 287068602 238363355 461660463 422103981 635387057 249233796 421717081 443208842 57360241 408000073 527866457 931350587 599778899 327071095 365524139 385987944 889603262 747962733 762178581 572316784 445770846 601816183 461125042 246305331 553964380 117544154 486226373 225853427 869800040 289004887 514673241 370108669 283185660 726335721 700492767 736670556 874966831 116186963 628761808 142485967 357292642 143840086 190614608 666704598 211786341 414014530 285821855 595612011 544280002 906979135 769285452 682880616 151623115 641073179 824241060 261304976 233625766 826363998 151005671 76152978 545345340 204721403 78847198 229734483 62559807 315941584 147541966 5302766 983797993 262147305 226459269 129313629 607480828 987307158 529216759 418371936 684317927 298742839 321896066 252522607 219393478 731208921 498806522 308378177 825891757 365051940 308110780 436487987 626089090 28114168 981391664 477412783 314438362 728855455 288025926 730067853 716741151 325287873 189124029 579043589 397694434 281327806 477924391 407960641 363762805 210148402 751395188 442873857 158470643 530995871 482387071 213265452 236573734 80529976 19931213 516559774 451367112 651742803 288606653 686094536 508797221 358381556 663382629 832359465 653936501 285405494 653893379 284105222 919449318 116885533 464128224 980367840 225750516 182394232 279890127 797947632 358285918 570632906 675013845 620742239 15029167 965332206 888031728 328386750 970989112 40633616 773729359 781729414 680877171 241294431 494429755 325960021 632395716 30110617 815537578 778683633 908040077 694011499 386991427 130609324 311582765 236825004 349772068 813938911 70160736 172109737 715120949 256041378 8962639 971581282 763496519 465643232 708004788 943838113 589414502 370332400 339618317 238331714 155257072 774808651 326714579 367253550 527702363 278860865 154911353 664785030 312625556 10547231 155448166 442884880 458247124 966322637 174132636 289571158 569030847 414476451 994688288 664705440 12457511 914518046 429925632 611428723 351904346 627395554 121477714 76636143 128752290 272513237 392494603 726664184 785048111 855170853 620854020 424603870 440340413 481550724 735048490 274825918 755217792 303042945 502742332 520765236 562898043 129675051 449594316 387045627 792408213 252935580 60405265 863185884 77386478 877234073 776102899 334024564 658552788 350824038 250021377 152665812 633204716 485025195 234718043 663515992 493486095 210434481 531780010 204539569 238344139 165378369 467469886 818533497 811243000 376062515 653479466 797546633 853005794 368937818 714757445 256830862 445944541 110967577 656450403 389061734 452525443 119276386 339719997 316539825 766688863 214259685 48166713 90897431 714834318 164697071 159917887 573948206 417535997 957172876 68010624 161173203 101001759 367921050 449030094 408808420 27690705 771611392 694928045 805444921 959494621 703733379 698385456 241658619 280803588 35804087 756118011 140005934 979978377 266013763 445927473 654377705 61852971 887887735 423226760 407173085 373730634 918711490 411651955 210431091 768673690 97467427 842134023 527443673 679489362 473963687 569573667 207820782 775476492 293739710 315022888 719443544 78405495 760734073 777979963 73734187 631166281 603286985 845551880 327996661 151980361 565245179 522998970 809337022 790566686 125735610 910165494 803444853 289618578 16226760 499575056 750252154 211096988 426460242 179702329 843347313 314613263 260095577 715434370 514509171 142235723 955511273 245575547 424702194 565195398 583648979 781962275 388284589 950314664 223710958 631860067 944641206 125397532 664771553 435379923 573336244 111343686 316296887 346688989 308624718 548163796 144639308 32529132 192882611 332162796 709825769 781297069 467356302 973074549 583380073 175742671 398788980 131373748 413856045 224882477 518098262 998893269 306441079 875554357 606946996 472907903 997947674 858318702 570844621 125924281 108966950 473372899 426576865 841946124 394083542 282668342 413098411 776196863 90344165 236753214 743499744 743829810 747930471 782918638 132319815 860183865 314280487 812248779 547433929 70134109 118937257 515594515 672479814 521921055 619685419 748108582 618012150 287402690 306611765 924889832 383989935 734668545 801533967 722514001 45231653 425822224 49551764 829148368 796905505 385289577 256256510 621444710 567456424 894009668 187092462 831711468 623556392 424242494 720529943 411166767 513099790 987723274 292968674 377409403 304812025 112434812 827931032 537951032 473524385 67573867 517837736 68684608 352667470 699416688 353405906 89470042 330838387 22522082 344292014 222243106 602613740 78114366 829104966 324588498 629628780 845578626 182235468 364325672 123316140 349414995 592771553 814937344 489159039 909855454 714368284 406611047 397146047 194704535 814120370 400019027 248484161 364077526 97517166 67283272 991749095 662559045 242801999 49012649 50498506 10610227 668958195 449196326 816907899 396511998 48576771 869220275 88937621 218416945 769047280 117928536 234900525 644361961 757593421 907092957 605134771 917091251 348065271 128171284 350939590 562108420 707520852 177744712 813591989 337689800 625334532 30350568 544190605 398257699 216522798 948589406 915910427 125863649 259028469 747703705 341912966 270927210 872014149 894189617 529672685 629308700 284099615 567330477 337691986 874718936 568457666 360755222 665412395 638338607 724321061 228094864 610550094 89834373 483346639 302495043 270454555 107198734 186385051 878480 272761533 769005451 778303399 369139479 846524172 536638497 628789092 93388529 770476877 556948049 693249926 236435085 815676760 412949664 695428741 140436884 163342113 501466803 816223121 86483657 732223770 503659432 579305774 427461236 125458489 138790425 385092759 859665474 398422678 83046579 876808554 801319036 771858598 577108586 710716026 599841648 547517494 698981513 573757720 338268029 850504070 225227388 178865802 561626715 125907586 888602534 560670918 209739041 681113309 743041721 555323668 687937916 117835062 133645337 158821560 272566594 652221958 100762917 164878386 710928894 302755712 567648725 773391996 561507188 564576905 613909457 31224681 203836857 752598765 554980455 220209777 616011014 455456778 114700028 374240572 831215938 723637012 282509600 253522722 4836470 601431504 106573109 914155174 870154886 448241713 669491481 735226492 927549620 97914540 298398069 111363792 258725187 932061536 324340851 835033356 233239186 134332941 949374506 135823298 778372887 973111645 241500729 478590542 321961092 635717894 842804993 71909485 867931624 921431836 309005901 797045600 910127896 228310715 912286140 693089448 212452991 412675819 905619372 909361338 390859234 707372790 41465508 890358507 991392640 139128807 958099935 604206735 212574105 976503280 754405153 122109789 795140726 863412404 412605115 507313446 367152249 803729260 505203051 262809608 626314574 27600222 252782307 50800361 905838349 179942767 908961251 56657281 237008312 443907882 174910618 866259483 677070102 85817029 439112550 224304865 923341309 257787891 830112354 44988348 467458324 677585501 719436918 532980792 554988857 857879291 691404405 740000014 441591431 801395047 192002886 720363502 677105934 865692629 217687764 666727755 599873429 33638242 369706850 742390453 935551813 337964147 600944471 492597549 654967016 436268432 642178935 788630015 908244426 147005487 162249428 85699368 925186953 616596087 343906518 672875689 260629965 212588291 666574811 112215419 872231780 366489274 693987558 217262013 663305306 783265670 335284720 835457294 69976864 754350857 477278059 432340666 661419476 108907824 987723085 498405236 524856546 917829850 570885749 507034940 100072939 436466515 165837280 991263846 143360870 73538620 254994977 472026034 642401476 961643064 354215412 692297436 320017373 355867256 205423160 924814261 18022050 564499216 196032040 677133476 488552214 153284115 941406758 776214327 495793176 897694937 430905839 381100544 907316244 507058054 703794333 171179917 167480688 4139649 230038671 460026598 912190280 804424875 319757971 826555955 156020372 512218071 943670606 593147662 616762532 400634265 653223017 402819921 276358788 643310654 597910636 671382007 48807920 663276092 336792191 409917772 971973016 8900970 656190952 948334784 542067083 887777661 760101712 166855118 341295689 196827582 841681006 733845455 325538203 110664592 226355850 646440865 445728669 781740050 146680499 654868058 734641172 560900368 710946599 96992260 17309318 335711557 167086028 194193375 976833372 771816329 167363339 179024110 657541123 426528259 56258738 797809263 200506269 399231411 589983929 381377027 695049147 52081494 659493004 220128121 125920035 255952362 878791689 613505317 738849924 242204525 61546475 581143148 561590409 568065627 425345452 794854094 108272073 403460263 877155887 547370467 566561962 161909260 106253530 270168797 917093078 916612494 398918978 373883973 299841377 227344198 98859106 652348140 510943606 736346683 335704795 246252366 323042273 489908298 645323499 108238278 637917629 169338166 581966441 912846235 361795202 14973432 256136801 605599860 392043834 706666221 547416494 229174910 518337510 236168684 146690330 317012079 383311486 75028000 966710971 388787732 25463850 868997420 79437419 780362276 107762404 321577105 917675324 521949836 740835331 191702587 495423682 607275618 87151599 514838934 153444065 817646127 140335467 280288934 639562435 338713537 754688174 519126305 481036847 311918047 844163211 897453120 468998719 90978400 909230900 46013606 217986642 265190657 927925849 113055454 495717805 89316845 204237577 183273044 997200168 804620122 418453000 460477526 668199166 681561062 690508647 177754578 478566300 511957571 7479395 803171421 496067499 239325199 340616575 81374761 78682644 557301202 74347351 914509350 19456017 681237249 309488470 542566372 881725446 670325566 202780914 84793548 866938801 291260868 348586524 204962032 443371195 774391901 590991854 937631330 50425932 296471496 281687250 143568741 982139323 319210404 185496425 288317324 678044449 179163031 672936846 863518237 905148250 109719600 351438483 985083354 991425770 515229821 532213004 732285626 646777088 824303814 41484035 572421182 558568187 725952524 822407202 132082182 649450147 601733126 237372848 182862219 786919251 707861178 764108411 462705394 450791598 959395087 157280395 140237023 581115225 848727078 503480488 642264575 898955450 246828042 97268529 500892940 45251128 425728159 523928543 427022881 483573526 995733907 922938860 110521098 756395239 785717628 217514247 951398992 839873276 116225898 626181800 963925038 262861055 974697797 141749685 715814563 455048610 493085352 296157632 729760463 162332740 396254696 513786839 195578363 497955825 863052041 590467115 642538726 932872533 569144776 744875973 434729299 169556811 831667871 926613436 429734965 303984203 140229650 366032919 615595377 887873488 691496299 269362249 826249868 936816388 198943426 462925497 308745082 95230070 90882748 332225675 267467473 480033187 111624586 536748573 447963707 125047647 752985447 386960654 169414943 226511016 36804217 797229734 119307211 525478234 819724520 567480607 265234866 691777972 363076982 620875329 592903042 358976791 64253398 738167297 895906225 33378793 334648971 378321142 746995384 816651712 119599168 777261766 79807689 341720682 241960670 396036364 36181752 806081862 291384465 148418151 378407775 694460922 548002353 133552303 265097307 833001156 549729086 546053746 14868046 621284894 242425791 228333047 93284713 652552508 433675507 825979230 53232505 543991338 284315967 868227443 945129912 693163150 782007413 325445011 523374785 320996432 31122601 979322238 465514808 421872791 297039572 806632304 806800033 496415343 679997721 561212937 120494675 254400311 911749119 544283259 202209380 906456301 345097720 223795529 43049169 681968301 631020323 451295730 200218260 75440358 888411594 143468571 997549562 778763871 911833198 988394605 767155639 534680675 830844930 175416597 6734095 350909509 781501171 647433891 498206279 37480964 459765430 570641491 710331661 605578163 875212185 143032410 896358340 304444252 668527777 994604129 135806468 679546510 593312130 304247032 603546067 925379879 337333605 374601099 613433128 674554668 857126519 205021496 560226064 988703960 822965837 154091783 275078407 411534462 161453088 452978435 33686762 491308419 692242392 252494546 83053341 147799436 528250924 395342307 318443649 733080749 306842648 234372261 826599110 541378511 310227850 398338609 724828329 828566400 565824488 146728710 171985514 644357636 327607263 756239772 929056508 4084564 977625999 138955388 310671740 573825504 1491676 598438946 612554996 624060830 727243411 181644537 466783795 10848368 437882063 468725745 873510728 864026584 362416096 76287131 561078635 700161339 621448274 911875205 82450249 829855761 749753219 616621694 399745000 227346214 134673220 413895509 25326325 836738867 419243568 923160896 93162658 981160309 622637058 165797128 72483938 797899629 778238863 139823245 315827328 270694762 557028018 873899588 201559228 172287441 559532074 126586233 432989795 540463083 231457160 905130836 450180523 81766404 442374863 297746280 38154776 333035719 113243587 405741114 724322287 956639376 455111520 511960015 747806096 939316638 700271586 169009441 624579691 974615041 674745553 466262041 226379286 686389796 912628672 584641954 329860595 374400711 966588591 558444473 135769572 89041853 476332408 827867865 806313607 281004209 34912676 495173992 417898538 374939214 778679301 924778682 503894824 348789029 330780417 988464496 286563164 294515824 745494995 794992066 949842997 529180543 754538175 119056884 231991537 356909523 189167386 571665708 154960623 481184832 879835314 988613557 235940496 795148402 708862833 409815047 559849325 612228992 331796156 414043565 852605983 387541354 99082264 145402317 71419756 704037544 136829063 766292121 81426956 348387960 591754761 41931935 221362067 508367125 688663010 577934834 128084241 122789954 369401953 421954445 420629940 496143515 417884713 905349213 68441134 932317086 471331058 754442889 251789594 308019815 612765282 901672246 129660061 940795569 988486608 141891968 669296721 370926315 872927000 899421905 939525671 300651772 846437731 971070565 710812340 14764895 927205325 1180461 648373892 666044082 648314630 365137712 545836255 272869641 217659533 376292334 549391089 164555441 395600571 962831603 599713333 505686757 516905905 652391564 243919979 176541301 355357309 469707903 225194667 422970208 686220870 641915623 825549503 588955189 466861763 278762758 831416392 760438234 968112251 326978328 107304804 161009793 107557960 507214757 574204525 971888377 783421633 351177966 342360479 181466549 478392906 823974344 431201766 151094347 743734717 81520876 218093021 879269105 38799450 105515992 830716605 680036346 532046733 163613462 853406970 18553212 323134262 127319868 863090190 1247130 62687513 219150055 125471137 871890701 862984747 68529608 947384175 36251553 838880320 695858783 543185064 992128943 652531897 41040188 560678569 200781449 780988346 779305113 662409637 487304183 370486755 54928405 669374540 113985293 34713647 825749250 801760403 308448310 460698068 794084497 124731239 830382442 737234266 595148076 995891366 314228396 324062157 995200591 419303193 376912649 720552243 685657621 252575119 680422535 835989457 650874946 18575543 78949493 9252294 248836437 510114033 882918418 530743631 850556032 763022388 258271181 519072160 865744206 520577319 195013061 577468237 528531660 589732089 858431741 639586631 747330683 729778864 537950835 110391602 202341106 126351153 674736343 306204824 34188456 183114496 877090447 235771783 464510947 857369253 23126379 960098817 725657393 204610999 972274598 623709609 655150602 778364556 47626342 610685851 508942129 406292596 466978387 329223605 993872320 268193324 300389668 322618373 242216533 323525 205146772 153333503 762863941 889440957 596361774 442089698 971056147 605168015 400098980 510049651 852417023 770605964 971792880 851858746 915801049 731465020 577997318 17459279 700929485 474989258 404060286 543349268 423384641 883169754 491319557 139708522 962870519 788164078 300815163 388579157 745212724 656500900 977638456 920412970 681235784 766245286 359180965 882437320 865930484 386266512 907486889 836954249 631971757 566450529 239602984 383808694 897126897 90778531 237601863 85928164 280108232 323474357 521019420 668697976 723505894 621829059 923545619 903758246 645299084 976263688 243330709 33918725 965061960 284171887 227620600 143598522 647988394 308149172 607380961 859932138 710933666 154862981 26420423 116677281 649688500 292112088 439845530 543248055 112802005 475581531 682271854 957910025 53212819 759693745 595751707 216163122 768236819 529315337 396741108 371663332 514949094 28571023 54643019 798126355 291646680 166908810 523642590 211588432 336906948 420061462 901077569 291627648 50043043 863330252 407938443 486158267 987108083 479050108 438483554 858426698 771103780 652200599 433359463 236402499 268414456 548576433 207010018 132037833 156087027 511238863 331020688 448360423 459478771 18923264 462828950 644165035 504226246 573552028 895761578 311620172 698828186 713737808 813569942 7889321 659002206 289260140 967279191 505739946 141406077 450810289 697974486 876420816 288657076 503254095 58763550 84358305 54545387 235959242 636442568 83252341 161142154 267970614 592378289 192081623 725459341 669308339 205549856 158893603 317130150 757279008 874216500 791422823 306240160 853914376 803920568 457777743 393133917 634751086 4959109 844968538 566325452 209747777 40626544 10070392 343598231 409232470 123854018 29691846 373381899 731125284 837724314 902752073 903800770 122473432 324059487 853555074 731311061 43917924 440531207 637190411 184550210 155713745 71360728 174854761 663666114 813289166 421999536 815962623 45269754 134515266 774458599 582327550 861605541 463737560 428058448 874382501 351912763 930886495 442417713 704898799 465952628 635183111 813973598 80320432 332943494 575434186 751840947 132821358 363510013 71359877 95257773 234122664 534906452 972974291 474593121 262501738 308028865 884134398 83545920 633353803 914008382 961694247 779639022 507040042 311754550 23927180 901033202 993190637 716026597 145757114 769942702 727480133 351617403 820876964 411616565 847940758 166274920 986808832 733362944 976793706 482323151 241569655 92634691 69144034 490059822 355254783 685445431 748372882 96143332 83257146 967812520 954118674 251841431 967412183 852241350 923553826 418953615 885479406 113860385 669833680 865732 756568569 965847020 901936630 538007840 262207628 851745773 969147032 45542517 558293608 662132353 341002208 10324302 867387784 828827269 975165655 475164523 287345433 593104171 544001350 55065580 539548487 454116661 487576603 770409353 604145754 402215324 746682364 893619065 886790397 356191838 124407768 490004232 771462732 459782655 794820104 249036741 388663195 140731019 412703967 467465117 221087838 238507399 979413691 795738669 492990346 771005350 965975975 128891843 12523625 38489566 818560320 735660616 741159420 795666122 724235826 444204814 91074427 146116951 576755696 738416663 443776570 955938927 893579991 929816437 441134793 158136509 245765591 164997044 672885340 602374418 943739477 661659837 913680800 247472619 403743928 850241858 554019874 957577527 972795361 24997938 464651917 854285176 372892179 243096124 654104670 586243595 226703296 540831399 535801184 790128453 512100528 58919599 759781514 762805431 282865540 69250838 651259851 642699030 670526822 111433597 39239540 421396135 98885375 908287523 621782777 104020023 442007207 22799093 787545820 963284678 39221241 969171124 306937976 555544266 63715716 9379711 262899468 809584767 379673354 89397736 205837202 17132452 354976642 444305885 452581011 646361605 897891665 305743972 554450370 403101997 729800671 135800457 351070943 786755165 189409960 264848630 769450703 927021465 242749898 956215261 693166238 512329715 547658680 898758673 153520313 224933858 660926871 232616122 784323502 270662505 361563719 274330633 840574665 385630675 262638872 677621152 661921337 381462841 642772406 355460826 560279256 723474629 148040647 466673367 742336035 362810111 934495206 484211060 923287040 16170142 86810404 970383490 474032810 52284147 392159072 716627718 413713439 816998245 673206445 361224456 665407654 100924412 901619781 895442233 59804483 904626217 560643482 544662633 27497365 590767376 327432473 930886923 331964171 568009505 904633278 279974479 420517007 755923969 463400280 742734138 243035037 318280703 292617593 349292264 610422816 383979421 173898410 219693746 702892754 27617885 962448705 67816669 839997893 406423571 592050597 722699928 939147904 58815610 954640005 134762927 715614135 203834385 783477650 443685307 382260536 2702318 806022643 430323832 981802603 866604763 8136923 27765746 734294417 991145253 500505768 562227153 248841238 736901817 433199831 530721212 722250603 110808002 976501117 856632769 26982254 83825921 190436702 70967990 437058222 282351354 189732841 748540677 81863670 905291201 698191934 651075486 142303159 385106255 41529498 186865072 263280030 677926335 47079551 892772964 680757008 713523849 853438742 818843702 513514984 90152042 849283925 936322682 449179320 977546449 296145071 749768111 870610298 432641485 956927928 790382788 933697262 694333022 788856103 561235648 958950294 660545476 76835444 767847199 433312063 115682538 201569133 673726658 975204460 426274439 356764772 707672435 275040988 781330255 523478820 32204299 492947795 773186635 621431279 838882383 103104020 147550293 124718157 355002464 520722354 197537889 600604215 415979848 446272182 989959665 6579594 946065604 265152958 780402536 8262043 692581216 653577887 26423872 499341123 304845530 311214941 522347639 824479058 914032574 945137523 958985874 808063376 342240596 648433571 620421647 864768192 386144385 337443010 216089290 129935473 862157342 702110007 966235053 203786641 301207969 21619891 335063482 468053974 38841985 549082940 863002930 623017831 10658745 299896647 653204208 793988425 584993713 595486041 332983200 706812612 484818598 607655610 707653066 348144029 105147933 36885084 410289642 842490055 428144660 510320036 200669254 419244974 390245141 181168165 127546048 187486006 943610343 464694201 645375923 549692047 244862218 278323416 75416556 164172117 250866122 374594506 338854601 10190944 897424383 654692116 567336093 878700221 439429869 22414599 642626038 966050210 349841529 741121289 385711918 878387207 722499169 256590495 886996447 675233527 824175908 691922326 454429799 372618513 184199373 482041413 564236666 759368092 114542955 22920315 834100572 802557453 116635105 849786151 47360767 398832855 866671284 758197403 26007038 323464482 788990264 631171000 494218893 79321324 775053786 32355261 463480579 425013425 854105215 336556793 353065208 360672578 703087483 162278281 450059414 440716883 136860651 450803730 827406600 796642964 747916655 977767473 436799987 922931273 834585505 797801923 533800031 515597522 514692388 570203239 253761681 238506865 518025668 655306542 897591012 95425377 42458359 388869755 248335184 811459381 298312255 533627885 263467848 14341057 85454016 796747854 364444458 546539146 684415720 232413444 284441645 542443487 644333432 113970539 273000891 37716890 53347235 999231108 35601158 770165192 833738053 472117949 981381736 174091594 678996736 399009820 105383274 833223688 17525747 261714931 904478911 296780171 402174856 242461177 192874872 574424407 565296500 199733472 533928235 846791400 558516354 517590212 907230373 643441976 10967386 609572128 506453894 335509664 174197185 954774154 75642775 980078771 664564164 629236845 719711760 792309705 634282763 217146909 50373127 390309130 241360428 486052487 587155932 973734561 464571608 622207001 675471934 472482234 213444568 616950394 866389937 246113242 882305949 129788037 63188338 878822797 665249187 748625939 490968046 508839242 959191593 447109634 302663391 249444077 312412027 300985198 33509348 717801242 316249464 53896051 274776014 930366392 857306075 249211582 6661036 746265560 778303507 890995453 613393269 732512428 534593785 632798341 218513511 580593296 977114482 511611267 379228801 572577335 11712404 98143135 697737623 973481758 601877599 193116260 220132142 975195640 999096376 977202894 837002309 319043862 364935108 425062101 695604697 171040410 30187628 663033752 5995146 753550507 628587292 171801268 785338220 195500748 174624661 340314258 907205023 505686292 897424072 295287008 871820033 811723243 900213826 286779567 861970898 67094915 446820245 198604248 528309690 799286803 368369454 504417769 117761481 351133952 352277667 622157807 827359982 871163029 878465659 682364275 403489906 13860415 304308815 180858208 847416186 681449003 18710350 305131115 756844356 83288563 238041868 92029088 700137252 102166875 145717678 169499826 999419499 689089059 233680745 414233837 755290899 107477862 870620571 46224879 251496750 636648862 518571070 257299384 826413150 549945655 716856590 476132621 756481620 279569090 244715266 423338457 37066463 356672032 977404015 610865538 963010608 260685561 555944524 912565072 124267969 595521321 963185041 64475978 332291544 205412613 153947217 327549335 598117279 252249898 280820190 112925796 338071719 158392710 585962764 276493757 573290217 312562744 824310929 661855154 32492429 229454566 42454483 775450434 851264015 369844174 234706461 907902697 729754680 566646345 694959864 790527749 121365599 453018427 896962346 898716050 556538296 156452117 332433376 701069036 943933715 613196513 970935541 66955699 257999011 359537252 185997166 704749800 386648768 353001582 548630365 388403254 962385201 78651934 915743770 455864542 83915768 649360660 686571728 440064241 840051584 581709834 751922599 866396275 741681825 68844958 315299159 113339954 39211762 389368848 992383332 52206666 693984964 690335883 643307060 739189442 685809027 217049493 462528447 722958045 917415335 87950113 256261786 447950926 603986863 864911719 886686079 224686077 709000683 759714247 878291007 604179269 506687240 706223198 647530380 374997235 818374609 868050554 967604515 557785875 619307372 173555819 169730661 744599728 717952788 892269789 789663065 187675150 522212338 567325048 394166404 973097661 14622689 757468841 614414899 465339353 211167771 300563264 480787923 929057381 540807986 285046426 944629570 810962402 272635310 122054346 329694919 138647319 222490788 531282473 210934489 797660570 508070813 100821536 779711563 466330014 230033931 154655801 878258402 50055324 850494689 144620943 90167522 9078879 314336606 539291085 214750058 206685188 386449321 17170480 116405723 110859178 737848826 160635855 65225202 328105612 449639700 761247812 569415497 205904161 835818446 325052509 345988399 765819783 895167268 749347276 944891312 848617177 751194916 394332141 174406033 171645832 657135029 217100328 154217785 104344612 6600794 554230684 294969307 4437514 182630406 24241240 639920428 713900350 819261885 770677149 265841031 493829510 958509440 953752530 121909153 931814531 246211740 180403048 186322944 890218703 106190697 611771944 220089440 397967423 746078654 863884895 989443857 503455327 254199144 288727118 915379988 52266513 703453049 676948340 297643231 55100319 612858111 476946110 145930831 334686904 786509260 167244788 73826776 908709500 872808017 176743626 695913266 233631291 738284550 94847724 597952767 334926195 832077537 111880016 721052144 984169949 422709107 471501245 896720299 265124766 345987044 538978405 641056922 258415409 398041445 376373196 606656652 238252351 270989039 861062583 775605737 140467336 148339040 476565474 874111214 639600452 333911441 660441040 585605802 965964360 747146852 753150136 898907609 668963903 160867514 877935587 888152951 184330643 372622872 983419175 169334334 160368952 95442628 951594300 9273411 782488972 549128718 469113138 331709117 769810160 182283012 77082123 856793841 760960051 174727070 764666620 555355497 592024352 474767096 805781964 171594463 912301235 836129191 96970198 809652728 972993285 749173602 258212565 407153788 109462205 629159716 422563654 234368861 115216547 410139804 77438539 777908497 251402995 320984210 897257344 489115944 767133224 833868373 570678855 489129598 623569826 975726327 563096415 997899002 187529497 821737109 282371590 482860405 886921533 740504049 23614075 296368731 593963110 570983249 115654692 817924729 397830904 691476180 50696813 647883199 265699005 769312411 7988109 754714364 537674795 265026846 421083337 528417607 359463597 338080976 193934936 456138768 523577584 765028853 224708520 212178964 865677010 408377084 522500380 415484526 940216860 629872892 866449609 149634884 905742944 771006018 663302356 280279174 538226300 888919353 37551734 455485904 667102293 316289995 578067054 617846955 842525596 122043025 416832300 877825249 204295511 59848587 402978001 398038767 684396411 740527546 647963192 861260687 652032439 682136410 800794176 94263041 825775869 220311504 361553117 849615533 914100550 613832593 909780533 109755779 766131490 64782463 746682728 742187750 896436048 325828622 388510876 528819141 255126038 399182456 177726484 204347458 681786530 381187443 193506528 887917002 838115260 674138718 918796412 629798230 784464870 516486592 77014599 84722039 744688005 743802741 262139869 604211329 600634233 472638312 658313087 60904702 383396040 952310095 930195050 85829376 956436106 913286320 473714578 608564325 358692854 790869089 615051973 170557881 318579651 273091981 336773050 685233614 575942175 753279780 479929084 920231464 863452905 473963945 852991442 411240521 544128001 233090229 402954772 814698210 124318619 772056013 147990906 823446766 713491782 658256077 761965053 524507465 291094746 901612218 224124327 344051867 21727794 414198160 797697169 409243253 697270904 89105591 902072518 270579210 789467337 70065293 514607307 799143411 750309539 125794736 946140002 937961189 177398632 325912778 129454780 925619013 540330794 477029283 293326084 4573377 354707965 231641052 910443452 187666699 593447685 343461069 965199614 636818861 648033354 145043410 899019552 611541106 745043447 866775523 881738177 465188679 235387646 779545415 631995664 593463426 361583045 900200330 305044951 317718369 604492892 104587620 719281175 648361532 567417217 91783870 269691408 817764922 178196866 693431809 315609031 332782374 403890042 996184759 253547797 152044583 199738249 936026863 464455155 60030400 677195939 820360072 839694117 393808921 411894557 198191959 477050814 897197255 478830847 346605978 319402861 942960280 623579404 225118316 589797710 758465570 674047652 254829747 127206419 74728275 557293011 946187571 860408566 145229324 850799427 936063887 647288026 353092241 757096526 252110644 747130846 233278446 15442450 381671167 410472133 996840557 437958920 75997502 384414642 524815391 777238095 568370757 50477425 232880398 942197848 685979211 812234663 364163938 179323703 457700008 888039031 998561133 423301749 175852021 558920107 292171877 311964408 897423712 193522503 86173325 565242939 526830751 487650066 776935788 220266548 646196205 250438004 806764294 904179845 314378915 318583457 655548516 887669971 706845001 981986769 110613684 744352619 631434763 425225813 614466758 520090894 963833225 389645099 902052713 807839926 341621749 766457264 128848659 363802083 380721454 868407834 666129609 372345646 451933608 262998246 506026775 529958145 939173188 12335900 118882784 25228762 683967257 375475243 178889188 599870855 961136587 608663258 202220198 206125668 173936429 250711017 531747351 775705323 929239078 35958799 938490735 632049721 494153950 390028864 815226577 927409270 77490859 446651829 772413110 163914402 444268612 277367676 930563682 186372067 110819681 66528511 539641576 805265072 46958135 749704735 160647834 597405811 768408382 836577417 410551827 82558665 899080669 76931518 40064 219177145 3160998 474941214 252142052 562595237 461569719 562964921 843252769 66239550 396447229 135443992 34941120 125454350 731367620 91225669 432806873 338101421 515310337 199945227 848461090 865301238 605608704 240043952 342222616 522595327 116081914 786018366 146360646 32459952 573846493 350870957 446957039 141472332 751999922 8500597 276100400 551498201 422669327 903622329 322229793 749046255 671561575 281546193 59526844 586459637 837649341 445894442 55335518 494244315 871426657 621611968 163170989 337713287 103559310 93775854 72160357 33914664 978277931 788917407 808832199 427087076 437405133 175478504 392756841 844525177 976676013 483440040 682826387 812042987 466853712 982080990 866834049 609299401 740323766 211988358 850138628 996616853 98640705 505698793 156592618 927667024 675356872 252661131 803086414 927233928 264892224 180307540 371620224 750537447 246802392 620846176 320010958 173334745 703130185 843999134 617308625 184772114 322201437 394566756 307488167 215752120 835951517 947317806 293842553 606973806 865920084 666904004 753638558 839513938 863036508 501203408 630972524 463336324 409430536 493961991 988996298 390630563 619627707 331859927 657849884 974387968 223238221 218672300 202423020 479770609 743970724 741283476 802243411 548202448 622074767 16671657 390498610 379196396 77630170 746914274 241945585 707995238 436787441 375628421 410558802 472021255 326029188 891699523 905028841 470628609 134133444 372675398 683992605 752347214 625755083 395022584 774089616 193803285 462481104 807137160 876609411 924888154 907818914 839390453 550196100 367108263 463096242 397805441 468415212 276795095 715518042 986563094 808583972 903583258 773897879 578474339 781550764 233044173 57207056 932158479 37063668 686572300 20919569 457305271 503515440 919755078 331676483 425356264 198813382 671619514 59452637 946640186 547892006 591357239 575536886 132123993 526005806 969238763 211204223 542876747 467052349 13398969 90437946 15650405 176274811 82914824 275831890 886921363 499350235 76557213 757276955 761357711 959339819 538172860 576483541 737242795 458361832 124295266 739914653 903436597 859025158 484029486 271041443 150526913 114516870 483848016 709337045 223789682 935402905 167389483 143254543 63136395 885018805 674997212 46000135 709157879 275481829 313041606 65229042 629666788 22149696 203912176 512428961 721144547 186752832 748246922 565856868 791372507 323837821 863496837 605499393 318168143 905249333 631323902 143273218 905454855 632873997 458102484 128047051 1748989 759731967 65189591 756828396 502922323 252690037 201829422 739140662 682445016 675733909 745214617 49020790 331889835 52611550 813597109 290283973 811854596 895821865 702111169 391568436 467974118 628786523 353121127 103787945 688963641 49785775 973992213 704340117 664885158 448759815 81591378 42717131 264819562 23375440 138598539 779544117 980088848 661258358 443279544 100049314 49823860 749560340 286684060 992565386 839005247 745631447 300324426 375281514 925810733 610751380 61548419 916514477 221179571 686083494 6798599 652867842 458793589 72553557 81462659 835204998 880810198 53863864 767029458 454234038 390826431 50553705 754608694 538023856 442805540 6197155 966004502 169200061 943800056 832301781 102567800 253092030 933881701 808552737 53334347 515212481 906141819 656712219 490587602 613472855 900233183 382924588 689348674 720324134 371346345 342975503 382577377 839212907 392185110 690877348 113217044 206609834 214565965 313294392 2090648 743503139 813412408 775982832 565381404 908525455 789297946 30814304 974021181 693136690 442628861 51163114 63163048 19477509 475206181 872897443 789042213 687313702 816874827 673077094 144165250 414492078 17372816 495494392 718715447 332535562 984765651 167236255 35485087 540855932 83898761 122725595 985390824 131403218 813515434 255104482 130483956 829364870 23821979 27897042 460641748 647778755 10888521 853517865 708489104 748778953 429352311 732391106 606138068 898156092 486048629 112692521 561575359 719699446 56203598 529343623 656663547 895004401 729574886 628688567 304982665 336193999 669807891 929655561 803157335 639068915 680679604 752921788 142479390 446900672 759856447 154856683 822819197 204057255 494675803 223249413 989574950 969110356 401957967 563947838 196820 30466937 355933701 684059542 672001218 339242448 635963115 774015664 678740599 212622967 824369581 827427717 329752950 774993204 750536030 444509453 180447896 35385436 461269252 994005789 397119878 796830448 23521049 698251054 753779399 389221203 94562605 91977209 181527903 843719426 38392016 393008966 170942344 788390542 5012814 975008438 870041183 781193159 620170137 366331985 338542798 650301377 338366324 815463251 394124477 550403002 365162028 299425187 575091196 513174129 141305189 597685837 828923547 267371153 398447504 776374371 556477110 361123831 647182713 169015819 393188113 133609161 452296954 426821825 73288768 574574725 402161365 765412550 199665034 629127879 100162188 3274612 232615589 71814531 408336928 32420261 565300909 752456391 869690424 62386989 456138641 248503780 235071389 451879195 320670071 749435482 555007700 591588544 744344828 408236949 433121642 800662655 381805120 850541178 443628543 890736891 642737895 805872249 868991466 680341918 534579101 515247776 202823141 131124964 373302068 557369621 514387807 651741665 297085146 674771974 144494727 744994785 279020852 472176552 534719412 592842020 113061778 788762525 72634548 896773360 55839735 818503625 821764169 946004734 466354432 985425213 694341319 555772299 176554763 367427393 794557104 318616394 132061565 937792055 924971268 227253566 702769778 241339196 202093496 53627244 132657043 685823216 360241951 955536083 290925732 199354311 643506 35541286 61194699 19150851 35532418 947566684 90714016 711719254 854197496 751853035 864090501 549154072 745066296 219223848 593208123 134391288 371384234 133688239 779338444 263507828 462712942 612723632 70203705 912267004 371123994 230470876 911174933 961405133 759818339 173796379 553128579 556532555 708502050 803192113 227046873 586751949 527377439 5485088 163091783 206350850 290882549 523387536 454460843 910103706 829719528 524133431 58299446 985560479 965996790 320623870 71833313 345250701 191006086 289784054 167108341 538404307 370055482 257158251 153232667 57013755 128705296 833691912 70882234 899038105 432591745 900033056 941980717 319764280 132829428 572441663 472747661 971500809 185179474 126794088 405912299 749026717 438167631 209351091 294381710 237412947 1980069 57603263 231401107 998294200 70560491 164708393 337655411 688548254 349380440 917564133 971170634 391148608 523780541 986601847 378756510 424371880 620610794 629130926 129557071 797196925 558683855 623024629 382343014 893734198 25037124 694226367 616489796 172716216 12458753 943537134 895956864 802933570 432082025 472544811 60378638 74319023 284331710 864489765 890340149 8540755 842481645 938492250 983983789 373370779 363434240 114017438 431980730 659932728 284696920 154182956 443110765 135945521 68250268 566711503 877956262 403287411 123347274 840530606 619554061 824498069 480848129 846123195 516071782 692083533 584059874 549526585 25799005 288178324 586729275 599954587 750598914 195186951 279531803 533983616 378305891 110320529 306122343 106962313 75088684 194263254 161015176 133153345 580916984 975893694 853933831 692938776 112294876 76709338 466741392 161517251 4204116 717284830 88372499 863432311 704336422 21182545 603961269 398279274 967615890 640192452 682022033 136892518 684323751 822115443 539992858 984445695 143760979 263843426 535489666 630111432 21269351 866992952 632335740 695229813 24044504 227117263 816928892 260857531 306352963 746472983 755566661 913796834 830260298 150245718 897736776 898621672 404627941 720381065 985385091 783181020 824220422 503552175 708805327 832372518 132901862 947725321 905912603 88425101 574815227 643291875 696675322 896903983 215009790 244539138 364768313 311704522 128789397 299709423 827165885 254111417 901180541 655044766 675422621 212798809 50216611 410599686 464288352 407855638 93847512 114571332 218109997 951357292 824226256 704659166 137144900 270742493 415839029 333350777 521266504 805378575 373269701 531222771 872416296 770795432 83380524 863535902 713312582 907674502 599568683 493040943 557612517 511912779 463143858 423693984 844596873 317289181 934364240 630494662 29855553 593503896 26869511 955845070 377325066 857181628 974196728 995019808 138963447 939698195 191364885 24204825 902417871 769532085 956389655 574799514 167526021 791270721 863826355 76352176 100542122 966825334 484412961 36689081 218328725 341381352 660158057 632281731 563736353 256398335 571057160 637561383 37517880 972830908 941325770 552181754 583030982 958409449 741081384 699438275 187935547 26450796 109176684 166092700 597646010 789941022 205771760 75835966 811746447 641196310 123492336 11635776 910710996 582008494 273552650 238508451 763862901 530759467 828528963 629491123 461157853 167252340 802838425 719196910 196727745 27989977 460318419 4640840 785117198 21456115 273899295 978901668 520855478 209392672 769212266 235547934 892869937 544835830 811109347 35955764 214310522 507101052 672329644 382045875 342332695 159501101 481321340 535441172 472104227 183704557 789828109 750403330 117249750 93844882 561739060 185593286 176906822 853994649 990836339 170363784 269868717 96010826 611930676 348156918 644355914 173659269 279147275 623618516 758557795 733628212 31461249 327037903 70316122 761956676 651076799 698599654 270334411 323869851 785917310 239407763 575626583 582549321 308532509 622987644 73717103 842211164 101166758 569845100 811501990 160634424 566918239 681882403 397409175 863423748 511822883 515491555 315008513 804270350 467384935 311635673 862847001 491796455 553964769 911170258 146224744 436486218 814353652 521420704 865134402 683170202 591967155 236262984 669963229 757868205 401407971 501217316 836004997 880723076 906449294 360305353 72036952 259488046 215292150 570745447 979332065 3178217 59178809 441102989 802597335 831148388 211803473 821304235 852952648 114051760 735633402 118320484 427514538 715706110 715841808 157209376 384021796 934742799 27547363 165041758 460601840 3696122 846374590 951354878 720229184 644776447 247826120 39846286 813181573 247783568 947765296 380732985 310410948 163563085 527388181 878549474 436688493 860886966 385078946 536480782 806862568 635045555 346023242 412671123 164211814 985262963 323515201 398918218 307329534 56571576 679776456 137596546 933416052 572321810 464642101 247229069 202088259 677070919 803809577 402902092 479919142 791539710 48506079 251064141 695395266 816113522 273708426 475066616 152295515 801141636 435904659 141998299 274524221 892558229 202571679 387304106 678736422 900430109 691951864 75985294 125137629 74147111 693761718 834595731 881613608 351150625 413423902 510594402 696691737 90462117 313414369 832592347 434353415 621425863 881805741 303202735 398250039 299709285 710342030 851456224 537655889 572669097 734258723 430296878 245573454 576999125 845769792 916642860 47703430 817987060 83286633 845779091 715821373 14466406 850689852 786308789 639040937 555549125 65940949 15748191 340548178 999005547 472983771 866910741 223959133 783436764 967614768 185506100 676290332 53594284 123413205 659140082 153691703 504392666 89017885 771860039 158822858 985014166 693637273 349723564 878904155 650218692 917497102 305314145 904432691 642463098 65782312 989677347 187442777 549387647 282040739 854552406 249397752 831592437 555610997 364424584 424019923 510333746 263395158 22006950 720306912 250404154 629494253 985905853 605270511 587380130 313331916 674023074 100554903 693017346 974854715 164460071 919704297 72016383 412330736 459276982 559237439 843488786 712411376 810876138 546123457 156529421 740521109 439003866 771387743 426887406 739507252 421789382 584120148 527715808 499706481 745899837 172414536 884368641 398625530 737767929 825797261 618268855 905779731 815558979 539960412 600657868 508992612 40806305 363350112 137343033 73848325 999809374 471908610 847242949 156322636 952359613 833509963 273992545 710440131 309590529 277803195 996873794 725442983 255661942 191969436 182034825 41949076 654204439 829647396 509238842 993998448 390025225 961779864 379372634 118804322 411651804 603308381 783235395 549949096 144959066 896733778 890483258 792057183 164841974 65982772 90278331 690256060 557624044 721048203 502419601 723126081 684793358 298827382 330966423 113078297 249247724 989328827 629806893 846992924 643809415 974373060 529952437 633839879 442181360 909395643 351035771 626441393 938408237 604880013 888384223 387177666 6143519 886077636 504224621 463223707 31110611 238329882 135460078 53417159 335708956 572452624 602549349 961271797 616952352 247981378 144590792 830076541 242630979 661973622 147565757 341504499 105944654 754984575 774058147 913063727 659966742 844638223 287982695 687024095 951318753 202357000 201076534 785483039 611125727 117209076 431927937 144790884 902666217 207429421 919962131 781993443 393161774 810168870 705812331 59095277 45174621 379107166 672529882 646672204 880769896 633506433 525538933 708863280 958030005 789399823 409784743 98718899 705983200 589678764 671528181 9857236 938884904 488491112 971685619 741259315 71907393 524393473 404116045 446612519 590494354 669009213 129116648 379919917 131374827 754516528 370356002 331556986 311213156 507414010 310707859 155944979 756077730 631479477 538766680 565876615 273920176 814199389 276962931 871307203 553890629 569974761 463919746 77494129 759803022 232728398 44473031 147202830 478546021 102944370 475296079 581802230 90814361 711648195 57942993 800176522 807507693 885090043 548872817 853689718 32464889 88266817 546287549 836847491 166365380 741291003 348418827 580049143 316446702 879357949 626051343 710165764 709560946 482178497 909405029 938271669 859940755 331727057 271594908 777676164 598575289 275230648 465889839 115152084 298723453 457890788 182422725 711835261 189504922 241453135 505725791 684230079 819880798 555360494 488934162 42900280 697905398 135730199 811477404 489128059 251297287 140274141 130512366 892536494 894975976 576954751 83925819 177075532 251394096 48143440 575471473 352211339 421494627 31797135 916780649 280564566 978436853 112270505 36818654 748976175 634527484 309717438 144997728 25845777 982825706 748510755 86130007 491296138 821688257 70806124 949288554 962185968 51604171 191208740 910259759 722447782 910445682 47312235 133294234 741927909 660187026 455749816 429434217 538319763 256762178 92449790 981641993 764681487 712290108 812134817 612896619 926325838 122604955 670775665 343299164 647728772 122632335 749069666 599353574 998247103 530496280 354891660 290461656 877798748 583829637 65061490 520156171 446388440 180574549 512663029 751108591 391081289 317707613 390041404 809592047 606449562 804789788 31793301 289822784 285749059 290595547 433172500 474587504 56098816 56338374 311956713 430892802 206418214 175613613 24842442 747093123 552237508 840314402 349474525 604331129 276475715 567375438 670993529 471148056 190743948 174526640 46307054 381749049 745157211 89710721 310692878 38994283 939220367 854915186 612809827 644835734 923481187 361588755 95199775 314486714 498097285 56307073 204688693 140651455 708129335 813602592 591748449 395907600 673688802 134621590 185344950 728800829 375565454 986818618 311219385 52337003 526136838 390272035 50916595 697367750 181999236 602791335 173963350 895308610 58993139 266446514 248291872 314874628 470711034 806784089 330809931 812720264 634618182 555972361 261176279 599834732 428296205 916094756 149276546 738462541 150412926 443130865 784685269 330676786 854604797 761540789 859906369 351538208 11234730 237367794 439942956 592030829 677041475 870344838 689629848 81444830 758312633 329587729 448760605 317104120 701501817 298068278 957470801 201705717 359111783 473659820 530376724 957225241 298829522 346268373 444242140 50606768 196238480 372212138 716543060 98105868 701767976 334337900 578008208 761262132 911140887 166511271 484923247 427556993 381371891 974006219 599441377 271828986 594666963 802295261 312701715 117535856 930564163 183103173 750301491 721671384 831114253 474543389 962098334 385850405 879329943 500678223 864824575 346830152 888365714 718136504 840079238 765023886 750592451 424995292 40521927 592095932 502971300 440220356 675696660 919586449 634859636 402830621 819507228 927668853 47904543 997549733 362227416 322136596 23750201 811563997 414184630 761008756 635579716 786154977 438032710 716207042 885005922 353365289 956703865 390084877 998243324 937517523 733925820 493876243 546953324 196088675 734118980 250251426 625257212 67484109 394287331 64965638 565477444 219380502 364566525 424324952 549841104 188485144 421791484 752880086 819145689 600407458 225409359 320740386 505719979 259336969 72606931 935157345 500100257 375780064 917749580 610390141 689083390 605240237 391400392 962348668 856840220 839998199 407514630 413610474 996252710 221691801 965483824 87640582 294738499 500083450 778676889 480679143 20779134 868424810 126775292 224714767 311755744 170333206 65686627 34417555 437315932 111060186 930742907 75637437 381085962 540069603 116685449 810835678 924957021 628562121 211820352 163340725 642388794 353900188 28553466 776642130 673787806 885872963 91184965 847534909 176870970 109172444 252107481 713576658 991458833 479961838 789420162 481594071 217618432 126064444 511257010 344461219 678434773 329765779 858672018 29844154 858280027 217126145 505848198 165419628 70811102 448396748 973455529 438983117 404449382 368503541 538846860 498192359 491788220 244335194 532237394 488664717 590900298 755961007 590212439 639358352 585571982 243504848 94211090 609369669 968707805 85232682 30249367 288002566 551493481 325795117 369736667 575419162 438905339 947264426 654057463 83784500 685077039 79906178 717699594 635138898 798655376 595933074 448080400 649884367 83922242 191527817 137802866 471518954 736931982 541341541 520051614 37581056 453648828 760026747 997587132 297415192 397995451 175924292 222547198 960400485 256061481 132860916 273800950 12425551 41935826 737724269 998944339 941914463 948821860 363687187 831458931 136823424 760197582 284910725 440348093 631459727 129986171 221080088 49871219 843120836 932161509 645792137 247583873 747733107 695369080 469609953 515463255 80040532 738496858 595674689 697397370 610240916 439222087 104905240 934110891 383147420 292099098 715890190 100015324 897901931 548986539 585896405 133288467 425463942 353332976 125946945 786080817 557039565 778421879 787085352 382599459 14417970 276556076 321435880 811372596 538293942 721072298 734487663 304502419 351826999 828061157 152025106 930947722 373700343 583682771 75739636 438688420 358943641 787288828 224065136 802884886 614016872 942568864 313030464 648228253 110574002 892109865 766798196 886817595 950723809 918726067 569783933 400844790 430286842 535785718 753969103 436249887 966215949 364527716 937398175 14702288 789389325 633471781 498879182 469135652 549950295 754998011 671891311 699970224 584634664 143448564 819079435 106496505 90421359 64958561 695301016 506845366 706503430 563674714 425742203 306771072 358830045 547790190 902375580 872401254 73566612 330251709 123143228 917971799 950790812 716178735 368923259 808949262 136453535 231998345 452288416 57945936 348904228 614807518 265279224 895634877 374908655 710330306 198388710 151571507 443655704 223726050 724246165 102655054 799398914 766599285 325045266 900541087 501809234 580100966 611592506 835963978 43869576 491363799 342852844 628979002 264437526 724368767 415041858 522816862 20176160 595523536 693136831 632771566 828875714 671624654 529508635 135134300 680422973 648761721 550854274 240843159 419225348 258405296 282159514 518439301 717912278 719731467 782150008 274182950 118903840 953014625 63286613 552812499 789710025 120238005 840971403 750535676 166333978 392404664 370845718 120006186 94484525 725856883 433546531 891726222 536497590 436475671 580391981 861330902 459975838 673308546 811544021 635156880 75186023 179137849 119403507 708101001 545845677 303634507 358562201 772110601 242250481 506885436 186397504 394629252 227889724 644750769 5102459 494389326 320420615 647292921 930241969 57331644 904832877 820378762 339342631 422960477 38736801 107864213 504891444 759997377 287535450 94577092 618362356 184266961 523504844 56760010 491326336 54432407 951981951 537081887 251251530 336401299 316409533 350735104 501981129 144786651 274665226 563236185 571454459 116921825 991700362 144010361 988100716 794702841 297247762 730622147 978930741 379455132 885438622 806414941 74404250 608968467 102581323 231489121 583646471 633196129 411367688 255417596 758045390 553806192 431767807 548654637 264069194 162307235 179448292 234505303 332541187 664147874 319128766 115235103 324577168 107611623 369827868 845935890 85858274 605896500 275651408 337484309 225188942 183417061 970965630 43951851 579461665 283996126 715972722 573539429 529590340 591254915 772588783 658500096 576684441 322032827 230913077 819887780 248460377 109855702 130315340 693560796 425958826 308317100 957259003 734484404 593767493 402471601 622999889 801820164 127926764 994474439 514470890 177958712 697537122 342669002 884587981 16687780 464839360 359610853 403094784 180696946 611769496 495149325 76438857 330782076 191781520 307750616 343892443 186872057 257640241 846601257 696552829 530694209 787965757 615626579 366219711 289706839 660172832 259669469 756647986 374672825 190091270 894004694 682221040 404173772 188534484 105402356 438969799 345664352 857686541 482634713 309546886 541232002 586263991 63211998 826267428 955185217 48342012 165250400 412392690 101487480 20745772 371705602 981400023 272196589 984987618 721223341 846189380 546380095 445049044 606292439 506498652 447260404 91388720 488762450 332781055 103000468 547340106 153372786 124568787 309404343 348751855 871133123 814120481 299656916 665159645 353608895 924678210 412042871 828990016 789055340 500039863 836584626 516696993 378011287 915364432 392205754 669860547 851218846 373977248 167915367 133512186 676824316 31526532 425207803 628394360 905424552 288007854 702990240 821711164 164911899 704388934 30113938 877450189 369914660 279101303 187753913 811629973 191425502 433929084 966208214 503053153 190984600 226662777 187379560 196186018 928938570 185336439 408909288 368328937 990934335 182216788 567783356 847706307 128157856 350420601 290721246 139062105 824456458 816164758 540638037 894817380 537036686 764680614 778813697 227763533 786063434 969642689 890102441 965851056 676326740 836473370 556709600 466563096 958893244 610905655 758472888 206977250 942083112 341136745 668289822 108266168 512744248 786718946 614849078 445788548 527843529 544032152 166931013 470065678 612394010 484771659 638509140 451488521 458350804 135589083 699324236 333770314 980298759 782320165 627387912 675846203 149408171 730550409 599961558 483530067 783226194 569566961 579069839 665043053 760030562 850395093 292954628 115768627 971773341 452800834 37852275 9085324 245803487 671618522 416323834 491586658 237961375 28975759 423980321 229236912 24196836 897444118 478059574 587969766 452201364 813032538 263155045 656933069 480444248 505908614 918642365 544531588 804611284 497331839 898638056 552028732 983944295 932570866 543173229 412698053 52741858 945297650 820576937 882343014 71496221 155826140 745626804 370763849 191794461 173767112 937412173 202000395 86931153 617614157 465657594 180482743 324393020 779796294 704810728 291749424 679706740 459263892 377595831 308864049 630906064 706972541 91836179 122937013 270077880 833228355 72612163 171428530 626640922 110318207 85485713 931286227 949586940 15256948 749256377 839015968 544538411 893950821 652085209 894814879 534247859 577913472 983582933 515828547 644901132 977037993 168497087 989728961 717673538 248519469 922954484 71503930 231482528 152370938 961869417 710911521 186350161 418281918 932703856 745614781 948118742 373989444 912883139 534133706 614825545 609452411 402342334 627130415 876176020 114302250 329291324 997306198 281478010 259655847 466183222 958388243 89713531 365675748 907396860 464992723 76383954 302246203 206338126 56085391 680149322 590408416 752092044 104246938 430835935 63843858 246598809 170781568 873971585 415459503 1292779 365696711 252849330 666049751 314820811 95549580 417091392 390598282 333003025 700863016 800741944 318017102 960498435 939468812 149245029 98433719 204609592 380280897 856560267 921949215 577873937 654707763 529356360 81230242 975795945 959763692 611559549 416154408 227710475 466268261 299763549 734750634 582703886 326133700 846118020 407923687 352607469 278244587 904376491 420122866 587096783 973974332 244627767 280195577 425051725 603505963 184739348 529993354 33931813 954395595 823306773 784891155 870174852 219744981 39974743 917423930 731438462 803044953 957582793 49735533 765631885 718679241 866359530 217807153 914277565 282885902 608862651 339092713 974902556 146896873 553692321 957667901 124004717 433406954 614296984 999373800 27077500 429585014 131891037 455680138 237866916 885584052 251100546 972866182 626603590 28552516 720346183 487769071 273360030 593779056 31775488 938784863 379818260 298940353 189764090 462118248 182015491 718576429 279124 736625132 838658008 815009983 253506514 66446793 228888511 225909202 335855188 416955293 987733116 704234919 345087577 317216690 878406579 515621365 49266420 793282202 586365650 187480884 382546033 762235771 750811789 513958453 841510895 306799594 178411673 832794178 496933726 558683372 460364820 873915235 169980467 121678026 326445417 607917517 59418632 648366110 781823600 604583760 542404952 306448587 202209191 452520016 84835065 884676392 372575063 246105650 374143960 615403945 340984499 369752358 945302076 368010659 657958556 436037417 647674203 28762392 601755928 882869191 829610169 761185371 246138916 780176612 787888079 406029953 832101683 744425677 325977798 390401435 913531906 394013443 12086408 943580781 558351587 752921718 733071948 920200403 203232243 670208149 947509306 904559019 824425434 532561498 422017785 6654883 358407032 829887386 417673410 229951767 352460495 797073922 462816597 243940329 758594460 443972583 156563072 82017548 294095494 128202305 573919794 3611704 98179939 917234520 673274701 480180474 757129994 968235827 882140881 479453310 686482091 753101344 867585678 143209459 623936091 105415117 186052179 613497981 620947751 197221737 552899678 318599912 178061064 148958540 74054081 40007120 942118482 383543657 554097194 494676244 390948171 570702453 904501386 330416738 45906893 52576874 827112410 364586461 937385926 399251234 300039328 903071186 739384750 767027642 190520918 385928490 44878243 576891531 718463488 916729966 236916520 47986968 601409619 562155813 827175238 946957806 936092968 132972544 982318867 306883282 372193124 331485942 869257504 365199212 543557486 754992309 13373635 833133517 258046765 911787141 798918847 1447436 750659508 51976776 647833990 965355227 858418776 389508521 551535832 749800657 277434444 127064795 726642799 824309016 72324583 402376214 945182516 6283851 452579617 768536152 241848628 262950498 152381741 647607430 999931409 794552579 225825392 233001093 79856574 994099405 778951244 875642619 116352060 372177998 137318465 313003899 697179304 64669930 711581917 68622867 228506265 928884810 384618472 629783571 48764400 608169999 103207733 693854936 761665135 506252282 16146510 340196755 670142379 714104820 605035061 120196258 871683397 905755791 983025945 397344954 360571831 711222020 242407149 448815149 912101343 215119721 631578751 278168021 390108752 407566116 927548026 474692300 993270790 400805960 76212435 257991663 285449124 394583703 355708107 201358057 596598561 55822110 160384745 719198499 463402223 573594356 517390966 553364448 912376866 374150259 732782770 663027919 564178739 474978321 190582348 671421130 227656468 112163093 780193910 424257146 651280975 38782200 923118262 94926294 723904936 818113543 112263416 966899314 544634257 612010377 631864890 373206076 82984683 659683175 887487148 826763597 757798965 548805891 821115586 900801771 358116273 219168860 57191166 510114413 550571621 8264507 668994857 7756756 300468582 433527005 852947658 423076400 552987169 989876460 777362659 211455254 765665124 932432703 159425756 390722104 572562392 290839587 128612016 361432738 995539201 739008320 654875170 465545202 486286659 166454071 668990362 262152495 280659474 698441218 933298767 354567658 742917741 74736140 380619537 339647000 688428346 37970510 18502353 715647350 289694722 223689655 917831532 101817008 322051201 112763964 69815961 866812904 161568942 273688607 976249964 972754811 900266295 546898962 480539457 74411319 995177993 72952262 827624447 177273533 510492959 905994827 895013037 107225422 374850854 784682201 986709265 647474196 158950444 780472117 975923859 642652361 115752022 57140179 206931916 181323671 712439244 527181688 737757188 51256920 327768479 121303168 633738874 830407571 406762695 774479162 203589173 242937909 371093991 431460085 524399471 120429698 973275924 320932367 258931510 379358556 794185382 746766967 208442982 220419333 860743771 450819767 633924010 302873140 683695589 637164726 441766217 814594921 474093425 859876850 985001181 672937077 744169117 63049577 665493046 834662532 70761193 486309473 85667173 952699145 701216995 213677259 192988456 230555313 606837775 364789463 798568841 127537344 279819237 329267693 698681596 783736849 690898898 272514231 587868981 409432644 362059089 345550304 486548928 899871016 645859204 365856859 778851583 462387950 464499133 155692747 303251764 374055077 470228027 440122758 200415806 479076238 915697072 134428117 363201794 244884285 978196587 606151345 78081386 263424429 455435355 4409173 868437562 955692823 532143637 956110384 26399795 554736927 503844791 394842622 441612306 284237698 10684780 158181370 409526941 538147277 646624449 106553407 640853120 148811535 472509701 411747487 538715255 653307939 44729321 617487579 114784138 862754043 508486071 226171468 557587127 309062040 131623613 521356506 494865909 520761945 799563999 158905508 889822004 950343700 854046716 160905051 633606731 656337885 135964644 290845384 520314397 540068191 497854475 948373866 502575666 377570276 405447064 779671512 887314154 414130744 314011304 679346330 446041545 984233253 759627097 824493826 592996306 855909522 421998449 481805889 384463569 249162547 43658226 305677236 210603663 694010261 182066487 212267004 225687732 793660597 499083890 745795871 687723913 510873818 154605249 728895627 111038466 397887968 859980569 101235352 4043756 591382277 520152510 615801247 631306577 702851336 853134746 998016435 839061204 317581068 532837800 586201788 943974128 327423720 984105150 535353021 400803269 759988740 232779943 295286984 125459733 940838770 824420860 424383532 976548620 624666924 136742926 280856481 574249018 310915301 183373445 740296426 858230305 637016534 267470158 888333247 409286283 476163865 800993246 440173282 81611358 833783058 608427616 876423753 876362412 491303456 262983886 207875020 437239010 259216238 733612876 578216494 789238876 19923173 897542921 44691338 870420006 430728769 770001733 344772872 552355875 659654786 838140213 383429183 412209764 28724706 739954354 463572943 431122199 593079157 731624437 796277229 73007182 216470505 112713110 99692804 500862426 268000578 706188542 167345784 194627926 635928589 698892906 924359756 493893446 725906370 964414007 101392424 404204905 685555152 524733659 464683835 822507791 243332151 424661104 728439313 184782207 690626580 809637525 73580300 101933830 143416190 836398571 446862015 573447676 191110973 362672207 930590756 717995467 13644133 482790770 498691279 127105657 87651421 826115003 825566194 641830575 651057800 190607814 389316842 652250669 653023539 591611046 925293074 935941335 683628075 754186457 491429501 216554330 209551459 954126319 830661494 288365221 92419600 621548584 517914968 191194369 959377795 405879824 582318112 413986187 798880250 719628104 22990892 717431069 5202419 115086479 185738629 168921910 738824569 723125086 728415940 745572378 315618767 230328998 985851802 122355837 351741802 359701883 857853136 785562771 388348339 107634811 14527477 575578378 492387968 195741449 677245336 167124504 349053627 190156070 422025271 107446511 546140208 626697457 84758728 615263548 351928683 322704048 251861120 546819730 329704222 991504968 303710737 476601959 790166929 883340911 764399283 255404784 691826602 46487724 484011284 606436474 352059488 444771197 516106491 245426483 568994924 991768634 329066122 642425926 428019137 482189671 954056083 848683465 908038301 640024488 797530844 286470667 590118465 83524162 368329082 17909247 466774525 831223288 763412925 92821588 781384786 739589490 32102863 593438815 462618558 920535908 518111451 121209736 161060674 163936969 250652339 355617091 262825654 218458580 546341071 889978733 315375051 835076869 199405240 130668810 772164540 506285518 862331125 822839747 196510675 845107198 410404712 159678393 752441584 813925571 905517339 75940612 708340260 612882801 75618383 382931329 304532213 223054788 857020618 84046335 51329049 408206237 508623910 293562117 503196043 450953674 111099503 683211902 497621030 140275312 252458008 12338555 57420625 40172825 722247203 480418214 356041703 728904694 793289600 685071495 496933444 895218222 176012085 667496294 626104157 736831469 357906202 500407528 533512991 467287490 623706003 472662578 93703694 457532098 699518778 469312395 872190816 561923924 578224241 742116065 273286491 227054593 474832594 305256611 405623216 156659459 224372193 161980805 474217153 978888511 967045414 826751144 189767452 428609460 974700067 752950177 647721524 872719901 209365698 253087599 122727294 907366416 927767246 271784421 247120067 895083963 806458702 761060949 933618306 393387885 801987796 107585210 484209843 942114367 120086068 47680544 693751263 821333263 624827600 345134563 677185178 466759985 820142920 754109077 125491849 959708857 3680401 164225311 441429723 350721826 286492986 548461658 37057300 244246465 857949975 267274740 56920734 249237970 81394126 783024824 246535158 21737450 478107371 253203373 739158883 372798920 885962225 401850785 644037242 358460059 937358531 537174631 666609647 599874736 528768671 326008230 317969981 511878361 286806843 743293195 281821094 979051875 10803768 255069779 642566953 349007242 688361220 326431130 850403183 958453123 32895800 364859152 26905459 805123675 813400696 895902278 127023850 250684490 835762217 861221942 184856195 640360270 369505852 885857398 711195075 105884671 158568242 629829089 872611004 561108193 756642091 902344076 394966215 709699982 743915971 889082274 236595044 997024032 348517359 84972342 491943682 756174162 375997891 45370013 338872485 419759271 629719625 975009346 836511391 504592155 885896899 770281213 939490973 860803061 501431332 896611993 331831491 458417213 407235537 606650692 76357967 971282404 459492408 719652012 436312041 264764852 585742083 717007935 444737654 636298733 876056127 458271269 500894683 347255170 766390250 874933093 887313164 658973849 225152053 577433839 440099978 401401472 380771768 548240208 673186726 914235672 189524959 109316198 920842848 94867881 690474832 399698352 590367094 875950330 650594599 246411041 467272629 150809980 79439481 985679382 6659041 681882768 338507530 751679043 484297560 421905066 518334520 111428977 244420797 593547814 64844125 255432190 979123466 871675560 293895802 630018846 108322087 232015965 292587892 360875494 27947381 369433750 911848747 645043732 465737227 738850242 446010519 49277440 713391797 964930540 841014848 347461127 820303557 645196451 728966918 593663804 586668959 495651156 198533980 126155273 503029654 323330379 535471818 911055651 243242330 572962050 874193928 133798408 633622478 968180015 676697693 806185439 397250248 234210111 486766644 940804299 640803391 862606761 683237107 374473271 245729423 110563922 312009665 499958948 30211562 302987080 206444599 937902586 963559434 686062911 417494379 27680822 392291774 915263885 547558603 117123407 356212875 474514223 348188683 451818218 582228005 296433052 429774875 570255430 338209683 407763750 243970698 756244252 534734125 793583014 300208788 132984101 584167755 97752072 400760096 1801699 344301627 903416435 89997212 445843393 894019389 900494280 578905443 792841170 65135952 152508992 349454761 768628059 708261845 878998993 319010295 412786353 248517079 654586590 377736304 727634460 793929807 501605948 881274294 632810668 913493941 901165450 396850228 416383230 188910952 114329325 697548383 267956653 498230599 798792633 980036246 187671342 244708632 686477424 143125180 425127966 507452136 839695404 919478733 192700073 379080170 138445081 832872837 520735041 43621093 321859048 307870998 431386590 172162938 435138446 478409849 265367642 272210415 850811630 462903415 805632989 800596129 126991811 32817615 443611036 299071790 52967613 738182521 141743355 535419128 281630351 414502495 379639070 672074918 822752219 26086622 950157619 591962079 135141380 738256243 647606588 786744591 223910484 15320068 289015590 242025614 744340762 325351405 70219960 16716626 883895088 818058109 934597743 651209719 138186462 819720461 163381779 379675492 790941668 150062060 416111222 311983490 26889279 566470342 192543373 365368959 675972222 249251745 547315365 161166042 622759555 830383847 838396392 784806392 609654007 466388003 931734310 716143260 612319671 209817766 850504721 835864394 597366697 841090837 72459995 311392386 210760319 913606465 947312014 405839907 529383351 120501633 725541359 666964501 283535988 591112443 666368802 159825610 936859837 528719107 479395174 601469826 433109606 270557283 255572983 424963385 43688149 395791284 924499212 342947521 154449106 169788088 872244748 169802969 748777811 551915692 942931623 99492278 289072277 84687766 878369063 487820823 57608107 467995627 210175163 851961745 460165573 992593511 597629093 455049382 184752214 190002069 224452784 882575311 988322433 981597066 661316323 246783767 419274717 962573232 861980719 399621320 700985176 336799360 453268865 548180386 271854869 378894132 381641360 594724507 227073299 873616996 263857908 536866640 636815763 86852299 233387205 273773489 771594330 960522442 646760113 26000106 180754064 17780781 995314641 808342397 213166093 504900119 809142489 832012661 862696789 925914911 12096425 952135936 890099506 725832436 524162749 195925689 168643103 643555021 767429510 987811491 921565439 399818137 497896555 49955916 122812544 876252695 798898112 149341712 938627169 486783604 267902450 623786330 332757207 649976547 219345157 821504621 890131659 407752643 396259663 473013120 320417115 396277521 6997686 548259700 40084510 300180690 123643537 144603905 800779254 845377723 560835155 690435961 83769901 976026893 224762753 881524045 241807517 790714019 882927399 808835806 465431689 945812859 795020742 65216051 466936121 262243812 319708926 866302735 603269940 530911964 346882427 451743880 573171263 695205409 442642547 791247039 438306582 521797776 619395935 629452092 994805575 325251348 400271114 642116018 850724387 352754009 612478718 315080122 595926649 692587917 667624778 131927836 621668514 699783887 280928717 521197521 356858788 808984878 368729856 876203321 967379704 548046128 552616477 777822583 121345604 312476749 669581283 736371323 50996423 957887583 421706812 858177143 629577053 758416643 240578267 394897027 633145772 853108294 433052228 441412649 556366379 153042308 26665488 718914390 49513564 976387402 251302837 10336994 223418030 266654544 164294205 835948004 555611300 332856999 626618979 31278083 63034661 247943737 63833566 977594801 482655786 574767297 185930785 661316964 695164196 77030024 738489139 594706959 557832898 815205022 525761446 987193075 391252235 906063709 618920225 496507456 259885841 440813747 777179240 564860703 517864177 751404111 299470951 159165160 625987999 541199944 468430945 470124047 200501126 31145292 866114910 711283885 837778059 872713023 342411112 526008584 61756112 701184311 532104739 376511772 87472419 869078198 816370583 510812490 226113654 195616412 615875460 752036335 39945517 853266344 728126467 66962217 726961809 637133042 505742911 512209241 120165821 63898535 692246164 991054910 519691654 247869540 546905379 742241998 597342288 132719704 675655526 365192815 699691686 422833541 309461598 566099996 553096483 179017587 961103315 889648985 414760177 968518383 142419952 808960745 675735714 278882768 283010737 782496262 951525178 3117530 589647181 858633780 404420746 966797480 369654055 992983832 909985980 411302755 258998248 772124881 830726484 67829120 920915519 485170305 22631471 565048691 769464403 612243221 638757359 249547170 984679984 140485518 962286165 124646293 399495719 896140430 402564996 912664078 345656708 505286118 544445369 410819559 796553135 698182743 360382727 826825002 696636227 524946635 306561191 548780392 342428291 355114323 633311182 393568164 781812479 861864140 710399940 118160963 247274460 650359724 894578125 793994885 241005438 609413062 788777015 628188452 196312675 777693182 735525453 764226629 588589480 560539048 358891244 506229916 221065944 782186194 852705244 458891025 365666788 708873313 516215977 218526484 275876390 770986291 156258052 582640202 881766551 492105848 970055700 134492469 199983232 734211154 426476909 452211988 562479434 33107880 828033273 231647438 689539394 442397513 518848738 721265376 970498230 300199060 297344251 156105031 450921743 419133508 831718749 264350470 440917826 25232369 561908559 6366183 466050696 852067508 118225367 6235280 455939208 928017692 994756069 715266234 86025499 174288892 519236233 426129871 959215994 331864831 956921876 891202941 430734066 132364374 700056434 785154627 981808661 629427342 239448686 46102952 259456126 512367601 748093105 919621432 694514470 722717448 515341974 126053775 391462881 261688380 50304896 926199226 993289956 947356659 85444473 313015929 5910469 90550569 105468429 941680113 45311938 279033229 559116741 603725093 35029535 553114377 673148986 374239431 657263369 747881934 818527861 27480127 638449647 498567777 87940191 601415981 797320895 362716563 419787495 86487812 536656000 298357819 969847314 763971408 774781148 134466857 492954122 154524387 430361313 205665257 403495082 524298295 558878729 178614185 930910862 56389914 874702593 741986430 477061303 340664171 544385676 383702290 852469247 813111732 413181132 400934027 977741672 524854376 265104807 562077366 538254327 168223076 365286434 744537141 634976336 376122917 737324422 833671822 506326386 8929385 492461621 7406199 437305877 875371263 459027252 106023592 3420573 274859087 948014094 174263124 413681149 341630434 528460077 98242169 997848922 471861484 369172175 199985880 719700197 584900859 683284953 865086528 311893554 650573611 85531763 833784760 707584480 272720078 948533612 597588059 929517233 161673863 850892357 712368033 725365263 579992571 879829329 757342404 218191716 736000129 617901776 92574260 715604416 508846765 558351123 722118564 847742686 206370387 549283962 28550781 40966227 863223578 322743178 515680653 977828012 106738737 486259749 70584181 983736588 976615757 154816086 483874530 41691269 827231542 474007994 500995968 868381861 925670452 72072886 263851459 759964450 254271146 864875049 96433820 684510241 925857512 9242660 970107155 872849906 919977451 827866591 718697118 836634586 14300873 367555353 596772640 417478099 91203027 514224938 949835414 885586760 999953961 70403658 877346779 457456923 99904425 157306473 658829892 238187156 971684162 442721147 219913311 365707674 189067655 766250338 819985040 792430639 524985443 952690303 435336257 930333561 549027574 849359382 350402318 859351281 625989440 784726341 200669627 607755665 576424673 667219037 586138140 526331570 369932754 923413410 542738227 524140105 116082681 198606622 831640532 605715097 6790642 599648966 156177584 632741591 331180878 596783569 749566317 127530146 569223682 78932040 116712615 59239877 474370887 716271444 220858375 198913764 321986799 538689399 846852856 798633533 162034696 731213892 985517953 681190906 214049027 688309322 406859514 430985636 321859801 97777552 615444013 450097830 151439154 90674274 407579907 437692995 705542978 687672290 58215923 321539801 273527453 103495213 562047220 387080848 70136618 870753534 499066058 186301641 455491478 901925771 452458139 726020096 92989262 681936309 804065464 30243670 281187970 715409185 176119937 788575524 106645580 190105726 607192847 800560419 827687371 45436601 57008844 38503356 791074354 759873605 840034078 479153890 578526153 696005907 511306044 290998228 77204700 989894056 64672977 730057970 48303176 87883351 993203333 740309483 38069339 10075949 371643797 912239908 610811005 380216991 922317248 917240515 491263245 302648800 104126787 233232593 884117333 973194725 126760130 983650659 646226393 728039940 920234728 416182729 292308926 367440666 307621369 15773288 519529704 869154078 868228545 561402282 186681371 76311677 741079303 310737505 696585821 470636467 798751189 724143120 932270490 279903370 449629 269282522 906591184 473848993 533416447 808195147 873625751 379175285 775603335 174473603 967752917 272939560 146300627 121844095 955846773 904850345 690283146 926271404 287358151 261730575 728943654 94903230 582295897 259213622 502436495 672025410 789405810 45062618 582006378 763399318 78777470 727366707 15527257 130978778 147063886 536396758 708250967 690543140 98684363 851501702 514863640 265024565 953044949 294970195 585772676 776894572 956529904 674132724 99611041 64418021 221070981 834970687 935418160 649490275 133450053 550522598 401472892 265898375 916499414 881571348 117330629 547951921 823958098 740743840 478455948 839430594 967499173 978847770 917740944 151176249 145624762 148916622 38948976 200879133 219209633 400934860 905267892 916713802 758359843 346268913 837191867 297878562 207709002 267581321 182499582 836537189 360545605 923988804 833496614 707356968 101861228 323489923 677337979 873739739 80768592 597189279 490372563 13862922 499476667 159677643 989733638 712192594 256903610 426749200 902907698 33030877 254259948 108913448 703169322 747998381 507507695 178599668 206074887 882263354 363798839 421216839 825867355 548785450 723145766 870759522 529651389 369466516 68842248 671156769 844939473 198968613 822990645 843607699 446305711 667304201 35552696 835427147 536947219 198574753 930009145 372010760 541474569 340466981 186452010 746128536 173860451 5002944 873716617 148301312 574922937 308950376 891362143 753021566 566048529 76796791 703564053 418329468 345276546 26364406 470577746 278967006 65132273 766162578 710450979 856293733 949221252 321417335 585919577 337150926 987407418 156916417 653760673 683020544 880711991 157323574 657055887 183821502 623696256 576383744 358160626 432586608 162327660 324818544 655074308 400182524 715619945 64136034 171634101 127401700 412511750 776564400 814755959 419051274 427201731 354464878 739343044 901686711 305017649 54099165 886615920 984541188 81494455 368936365 719814492 297124532 990503148 672315806 123150361 72764065 697460800 228332763 889579043 243780318 787373241 398115472 569473637 375449439 344045404 370545281 114108042 209644997 879343059 173211721 953903721 221318804 103375672 560192700 265657860 402636341 43956880 176978289 84073459 65965618 742305842 42733798 528313687 477263489 938077646 772457726 624731313 804987352 645915595 181166809 406912468 573763425 479832648 513506079 105243024 872048422 164156010 215858048 48828292 765779673 699767210 587040287 803233976 589404682 179221182 415960568 346932598 97195243 506654258 213289791 862746460 479112232 420131946 644397411 789058997 8932967 195507870 469606077 436211859 131004343 21013689 129878307 596350341 337044449 266025652 680839392 199273174 183906270 680245173 574431235 754407624 967587701 659308533 111628720 183606105 157135933 181737051 675331491 960529188 554800932 377970582 887392069 972867533 824358376 787891614 478476686 326651346 387895233 782311849 218607206 515444251 391596633 86531899 231778911 127712765 793712716 373891084 513509266 871644606 490134810 208188604 235859060 93963272 206563741 17776204 459331481 552774322 772787993 274765403 838613581 410895036 807110451 371476567 451056529 376289686 119676677 974929776 21604876 281535330 520629413 176799458 158602898 636639455 694115334 791475116 837334535 768595054 302620681 253615239 827079449 297562466 863449228 121233187 802547902 286138489 774389399 47065638 352113967 605655386 822067023 82913053 147811015 242761958 437375112 282959019 327071853 929736918 314322525 928735190 670582948 538170519 66349478 219573112 806499352 914896689 758869967 911121702 881744005 85510462 290043987 145446453 180444560 166390986 948422715 353867886 574696875 413990656 721487079 722527388 60834250 415565372 657670884 580661346 957453656 698312304 307169951 755324025 748645620 820754533 69166248 365154453 511343104 604999740 235433075 30436702 670473104 642904653 278076437 459949678 137899784 552213634 937716739 330190051 901836366 48582023 497986415 509598326 143271162 112571490 929110537 962959043 818918609 45514066 553212205 748641518 31877257 589328020 610490197 493282981 31763686 841184086 308571573 27962609 939576447 563550107 987775029 546855307 180274497 854246288 40490211 22480422 560334217 878478125 262264738 917323535 623014669 457105008 282520823 307240000 535318278 213361551 907815581 814940642 829094520 371556915 319125613 715777268 826361549 190636144 210496828 407780496 398815219 398368067 812580052 166097869 610462472 725403964 728322835 76563430 7959443 241848114 245613810 56362427 907106619 847074359 750599565 71933077 257707663 50609123 542261039 587704813 556904031 231469478 441386888 604057299 174447757 772377726 202017732 947444748 12584661 955963090 703110599 565662902 210362698 633278023 335351850 227642098 522716149 974589431 692929740 638271384 943294836 304893956 968334297 520455403 151789221 474634809 363546508 321051000 4882986 93634452 657346620 874667243 505019485 648959373 362930161 948235533 171964719 327337444 321615549 477745707 277625199 375754792 615148700 973010437 651304108 609452795 101201348 353474422 606217813 947540844 24438534 718828532 1792296 423232616 864212635 924368421 753819301 537658287 269507207 701592351 483003295 966054953 639837507 44057012 447502859 838435570 370078507 712711637 83607774 138014471 209390039 918614970 94112179 208194777 233046384 671030281 230894173 757619937 482258380 629415723 356026375 909202430 391412156 927058287 7433039 642581084 793137029 517873909 633282397 816441201 732580260 903564476 10324521 395205254 870789022 675576573 801161995 770116646 412152914 402528366 688539089 457861357 166632266 181578008 420995554 130113080 978086956 425726955 701872031 152897452 712201403 788671298 251686733 224584989 149454275 451456833 70775271 108557878 117589996 752924020 850936397 853428927 397079210 558286447 270055962 263565964 194311379 907023590 748904793 370228803 217429338 858829624 956725593 427102021 250118577 763503775 879398657 844060652 739815258 104823030 427991234 443707519 549592651 112470317 691330540 619289732 528706857 979641548 706436568 75931301 358659462 210632839 592344527 268525022 384007033 628911000 863464891 269961260 626102782 135742851 309951191 501486278 324273942 331645493 408936993 115336135 352665147 3609615 783220420 157447261 647222497 690203647 429607327 13040795 139197645 582333239 317684917 854378107 290035466 783173231 715858219 523944464 235166903 593426592 453734358 789456904 289833797 649757510 829793521 211343015 194736988 840176662 354549009 533645760 760306855 114032600 488621100 709775273 806930230 625432763 211187716 11036246 56692718 602557541 398958321 590259877 423611514 413516861 987238043 476040834 785798421 552394930 205186992 647032231 380430349 799726647 594308159 792919407 184034194 768980337 515024826 224300158 831946014 578034851 187226301 740132426 863803617 131147613 199420831 69546367 806682796 750959274 798930399 160873417 653302948 639998486 5366402 462369300 524609098 322018969 859511725 14831851 58891224 493811005 644909461 885288131 704052132 732590934 714955801 291887413 854374845 897803988 131951966 610566804 950255470 775354957 868288522 778510325 161121796 630882211 737204215 224896889 919827872 938996388 749581225 260712375 864552977 972035054 462528538 61481530 42512666 656719498 673427627 40375600 613858774 616202134 411915006 466417804 579222401 701521318 609889188 59283003 758396369 327305166 792045692 166293749 368946256 223364914 943352160 906434400 159181188 546178173 350540729 76940784 189312437 311280490 343256637 1479429 61929016 553664643 109397677 89194786 547182031 520955023 889945512 861559645 980777182 315055684 614543176 501215854 373766819 399133474 529463386 342266978 647733222 685577806 87160941 51158525 402965253 190361929 272677285 872680911 48221156 431939361 898208421 259189973 504548881 381772476 894588055 825393937 115938880 823531828 29582494 336188874 869940614 866524919 925948 267488612 790430010 956548 620858965 806949656 801118693 386778918 51431828 467982009 231810460 579017019 914336999 910306772 98313237 932862120 957666195 313458885 183985935 298334626 270594603 83708357 275619709 321246138 339107119 758862881 74488099 606981857 970306794 599319580 112577398 345022301 548235857 22317550 570211939 132544127 413082598 116576237 143861333 776803401 463640750 997346455 168111502 750876452 145029253 827052905 751013343 651209568 822881831 751777814 937051522 639277987 284026463 418546938 80853095 664809016 230683310 446055318 924928257 717779466 549316580 591013496 138262494 852377769 18311113 985398663 296426019 410036998 338687347 415156646 43261655 667185051 385556343 971062652 88230240 700750838 450190811 295049578 677074141 131385895 52915746 893705363 193051870 36077392 320290538 890067124 462379078 383601435 891247958 47354959 195979127 886503166 93918603 868003481 46157417 745343866 668208333 40146742 691552580 720129661 930855335 552576956 942903745 679076887 183265972 893650116 359073712 728664020 542630082 704446201 196241146 218585543 670927135 434279854 285251132 633130967 6195087 828537449 293424002 325196893 518738669 132387959 323603350 649237793 553254806 203804911 455414950 37944573 880694039 800582344 790140811 410759753 890595571 122745093 175119371 283986850 98804076 713833001 972821317 223185744 519425370 524488346 911809461 405584903 834565661 377389765 287206300 639927278 505287238 928400611 520772235 553956935 297052387 404356894 584194648 212795469 740639418 413532650 164900377 651219771 19748568 36155304 864617520 654726668 494848335 860418194 164091011 787672708 589004591 959117088 830548654 674640712 166162780 494886635 189990651 756105139 632101373 869855637 456802865 812131849 101879154 998317949 612847987 278163083 197749773 578474908 225534507 846715411 465910519 984441610 195266307 652645058 277511903 427251646 227972626 594756388 195587258 974175809 129059980 836397726 406158489 932097136 257781802 962760983 250616 599471583 537587467 967328330 937702753 589780504 939695346 301438806 743741881 398964895 548877331 572794610 966009944 801648133 482660084 347486801 665252690 477722505 753934071 299195329 200723502 164336539 744303961 181746303 369641980 161717360 22314747 413380204 202357327 27580956 41643165 505088336 446908905 984397103 986577289 258468074 824750439 325997525 580537866 546065463 298627577 967374575 523768017 887908542 992683617 333406890 482839564 174248519 425318989 428879140 902061546 196598972 754163065 792303957 276928250 943616569 676652350 181197058 477386120 805053233 817271187 680102825 119857019 496834885 547800545 134181852 624791767 919643275 412526933 539815116 878447348 618698369 543851831 433346533 31007024 441733122 358241642 805345696 706325958 163618803 194920962 804751609 928193925 227942430 336500905 139253396 833500794 7328281 277408937 786173568 633737353 60928310 745736189 892933430 756286586 625099101 187679391 798308847 683471998 269822200 978005179 305468730 760325984 176936860 30916228 561258106 483982488 279812025 193626335 388908854 720701609 394376721 125407868 167486475 938461423 562247009 216760603 499001558 420928044 120677123 317016072 812143444 597787169 924244236 32948037 754752978 568593103 862391637 654783667 770285062 569886680 292294424 248901266 271290409 104581257 422332218 818077907 30331316 51695362 214714469 72789876 676138834 170091734 789504419 951445094 843974278 975850111 126479450 251402353 673803858 561503041 439141818 635610201 229844088 865801139 834045603 488058076 1735486 180484777 838049054 786314507 482414670 17950648 401228209 490461075 198346633 449467428 544587733 871725783 351296976 110406454 313025561 611948164 765411360 916346550 742114810 460862157 400998108 346234242 605513026 331182219 213081335 479775510 370111514 644515271 561829231 854434002 774962459 216441251 981305440 214018399 170807602 469827970 664091179 116047507 691379061 738249297 602127558 794795848 576670965 130081793 35727801 50640293 940324684 903405167 686187267 193711135 223959499 96696105 465989433 522687513 17502675 289570769 182141360 96139136 393218838 280724125 139280182 77177715 539224229 212034513 763734123 729875290 499446418 826426470 969156406 752147672 244408458 36348442 101912891 662693062 308695214 358616063 235475980 748678044 386468901 63004423 458634500 133162109 852354076 993763772 835353966 332633416 521072221 555007693 718636711 639873557 797664310 638270657 420163808 335447822 258524000 390555123 185878004 231039629 341345548 745029194 781220035 929792683 871876776 544376259 831802981 193831409 546917775 701429971 951324498 460523698 900834817 726576996 559894421 861891008 371094771 330266113 740531079 48056825 895723216 598668894 443691839 818133342 807528689 257561245 143573165 324832700 870070637 322786510 916799472 12747312 889580245 168635111 798109550 836428584 829921094 325040430 260898332 428533109 829339082 293085117 906890535 380445715 236454632 683995626 425302406 677236775 35993894 20125451 523909909 565591920 804599532 518731094 431624100 740534037 434593827 330827180 328474738 487299266 241241823 163113746 236655080 603527054 746900092 148520094 524110980 128247022 678045685 881951034 411943345 980241661 805297941 832227922 455818838 77986812 753456454 531584744 214310917 36272122 86448661 957758989 210943646 407942133 665372279 804722795 636417341 892372570 424720895 787927690 563510256 609722945 677824036 725329973 580069782 869092929 400092293 456935006 171363882 535230897 510548586 19475712 468232696 55815209 640016645 372828289 136151998 157176150 316220955 487373873 435401304 670836066 445206308 111109619 435932875 922998961 243819549 836910939 612871414 182286046 593736951 119393426 133112623 71734344 722470383 889273372 501341641 995691240 981327668 941902119 141196595 834433537 648474452 271202617 299861793 807219153 258687669 541515874 265065716 867501102 28366380 986860520 582164966 835812735 989399391 163640579 797926122 501155322 828112235 672601254 190010145 640458615 136530248 971858968 443161568 379132533 376371796 664119419 223003673 819729527 753160715 179063264 557949499 3927544 176999241 217357135 571110892 218830196 272092109 29164718 384455060 561266575 372390768 281577746 253312852 239624121 776851914 615581152 527686623 550909253 408561668 401079720 607317188 581034610 154251123 863021065 863232508 916522447 673651757 914219955 671507368 485130036 752239823 103126811 240399333 842066776 791918879 594705227 389721706 519271084 132100451 887638255 870852574 793848345 28079154 256755013 18419500 125579607 753148681 622763451 371619206 451354238 313694505 793844207 243805894 75471708 905178048 209710187 895775541 80062078 686037044 10108980 4535493 526132670 165127630 816256470 362527389 21479578 285946114 524730965 927365103 367478775 987329472 981229732 877904539 668087090 733609285 722848359 375959385 111523254 150617199 432587063 813455156 938522697 774767986 355278934 926405 721177658 615147376 933742280 893848300 358262787 241115716 170167987 931290736 668983558 39376768 105148085 966306503 630153659 928982942 621040339 83271487 661961339 819479944 403255329 455613452 602254035 139001866 930103213 544761122 246737812 550694749 31869614 211260437 567684447 397908076 711610043 558196115 306724207 246129602 137948610 588622702 365838383 521354973 745005100 534499149 116566595 106645101 394092261 132600280 787403485 303463587 607684261 371080932 289737085 357906131 391780535 670141999 908562415 104201971 439071523 93229492 544057228 27394073 747786062 710725447 859401563 965496761 438651627 68037211