62 100 295069321 237372484 341984485 181236823 801524338 666837040 688736718 329946543 689835290 69147109 429051717 297039267 994981871 641316297 177317303 716280497 890433341 261353159 219436037 262368551 608174202 286706241 443943901 389514600 873583583 182900063 57792044 413619101 484896972 399540762 740662914 59173214 366671422 773391204 100838935 812407398 221261803 863515242 583723522 559370859 891533307 526702718 164779602 400990177 84574827 336633043 704547067 451647997 3484540 638826111 71428243 7798416 979980799 200645084 681177270 220431210 800599151 289235914 815728483 749698860 283003514 25084424 390425204 759227623 34843855 623575845 578673279 535461781 741005950 912308487 415338906 321281173 868602466 687341679 778434430 180998010 318658968 529401882 505039579 91280763 290793854 391945832 927301560 846454138 844060565 613108597 674300876 563172155 346497714 987173863 618352140 250749752 456230892 502823988 472418799 880632857 956503303 848177716 257769651 721140678 100 339230155 601759355 180088596 974857117 252809194 505762222 322166280 641332700 614886146 917259636 622640880 220872059 908680919 77376656 814803974 371416413 278845404 580181099 429571217 379771385 450220750 29652517 942847341 405779381 128174527 958033253 66099521 60039522 531744225 99206600 468761342 362568594 686657769 493990479 431772678 448163077 750677190 407821977 915015305 638204560 221977122 921767565 91741045 454482683 404535241 507541170 999130688 432880774 740011553 513162671 372938028 523895937 900207836 991345978 623550397 969757183 41377726 461158424 48469347 331165660 759435166 676792855 277863451 337130517 318446947 350347889 706450431 33891578 183989560 101765583 421735837 214151783 676939365 93376952 757739382 802031574 159620828 113213239 70866731 287808099 790064379 484831748 568556831 669064119 564145519 551243715 160586974 14365946 861774011 485926108 611836299 234809027 911172343 19264860 67180899 430004764 466534881 613103222 816032531 761038981 100 764145589 780422099 755639114 465548408 341237391 939649503 894999185 690081948 932977370 931499545 466235804 590667095 79850969 440394997 664212120 57889354 315757597 702213069 857178628 471776834 929488159 516459198 781785925 449780756 726014108 350000964 538861494 342212448 114456828 275452772 196745613 526591604 122983392 722882614 534283050 302473290 180447503 532758730 152616162 207004798 293497860 879658190 684308157 771876326 415651845 653365842 56595722 92302387 65751378 233250437 745952370 276452428 223653924 463349736 380560574 577411211 146801851 233917366 488594540 498141349 478058061 983052133 697750887 712691380 903878823 333657974 844193241 563173883 932744222 667280025 533100667 319015864 819371531 25960397 723793616 148754272 108493903 605773876 247068271 238431010 438648768 590189668 177973162 952454971 538927185 224217755 551092250 199272471 183819 564192075 231918009 70823555 768656254 913134786 506952909 434840847 368243778 899328456 106148507 439939512 100 400155458 285184125 430327390 341357397 686936134 202496126 982129580 314764801 252554513 982126845 129723686 879146902 223228234 7738554 6301694 744531419 371282502 906761602 314976006 235178741 993753393 906289968 656923927 494389688 772689564 182066972 445194570 756014155 651103092 467470133 532973632 904704146 182686908 146963392 920758523 245113059 719257521 352140880 933730186 983426815 339903341 463136057 850782125 500294732 340054888 676039188 21770271 610516655 778884790 683609912 471708216 140198565 829461035 490083376 88094370 716805146 992448479 972201757 504458370 986180888 48635138 718783706 750796724 34735949 321872797 336863491 977891830 336332462 188337319 242231956 51541192 644740720 282102227 57463203 380441272 84689049 252056854 75135724 308624877 779257739 49895744 476064544 575849546 952400533 160533446 34843264 290425968 424998735 29039282 242975733 365321085 129416718 966627497 68951226 301119581 228598048 158891251 92778648 503885361 519693823 100 492440316 207175987 598737648 146684156 183878447 617125150 407739414 289073924 13489835 611375507 340096530 392279381 971205536 23447246 434711997 461511090 958163831 571498544 694115048 714842791 584103410 246467193 272287514 600434845 31251460 273124957 602745155 782702597 711351261 434395040 979276235 800341312 74820293 617324326 665169908 51798766 428197135 605183029 26863759 546960745 115075849 464483955 458847171 222390329 676678215 367561184 333783541 339213510 199898414 2157429 97800719 187909415 682410821 638984353 798442115 269958508 624670133 475341838 671222467 501923082 971561711 522110466 91467297 601475560 543267409 854483366 333442198 282958500 934289693 187754907 27412311 663795517 210054409 329286409 240626258 280932163 611416956 985058207 156757524 135829352 860836176 366360311 799598829 176122887 701515583 679973638 434887616 431784621 224300824 745158779 372789328 498457838 398644570 499025951 443991614 376247619 400717924 208533458 737549567 591247520 100 890387594 361249178 562185000 87072644 990373886 736603660 547187442 718105717 663292068 982199065 772420273 528015336 415710880 42480166 942262010 610276725 446819471 681439343 129394188 979355931 551724748 25884433 402623662 487306605 56506059 52893834 748591918 347932372 859354483 788808923 843291968 880073240 537418113 719149842 776002167 300980396 291526486 790631018 93256261 758638019 320741175 489482529 109967027 592605865 773810658 512851127 838158621 907260193 609143879 362333149 186380554 759356281 101629814 814991894 138723041 701751968 30119466 437143350 62729015 812671469 320750220 317456543 310506359 772725518 203994869 574336712 599992573 57043801 125907212 507290374 125262059 65603612 703078459 539703942 207406067 912820471 345705697 34833767 344958700 288270875 170733835 715265965 7380440 638319117 740082492 244258381 767481878 816547763 644271164 114914354 586517082 779417306 30488732 382686889 31905670 31249232 522952686 258744742 591356782 879792695 100 636710523 223025370 590050405 82107882 1408085 390123983 650912019 711840242 756601469 98144234 269896145 999133441 586426515 257572652 605661876 216550541 492573645 342259861 937279675 32266913 318798797 709608150 505587585 62510499 517838320 368713598 218900929 917267870 240909505 416198735 451023054 73755068 986005438 17994845 544296601 298759349 397206262 3602405 382633025 836012540 29405665 842878377 320337977 543248831 646871288 207751601 939661848 313913134 123131672 283378205 868127330 937442196 927025926 813118147 106706926 279228478 891402128 321316909 691172645 180550388 378007110 332180608 930475726 112380878 966412353 921313935 492363148 649464105 212749090 311963501 330307735 314822711 516608728 526361000 836061026 943386825 31850948 495664548 390815190 809116409 977534905 376224472 821271833 361056398 195505844 355407890 261134026 635812240 885007979 262250693 778588492 522905826 834732525 996615688 591249184 889439621 464648796 899127043 282024518 659943418 100 600833852 288047711 459436039 395029728 633656538 429436222 416846696 547865602 375161478 805554716 92465784 125634874 855809127 860526678 617094797 90695851 91735015 996399024 13134020 370793309 378978400 919468357 207991458 965618977 111145894 547553032 512303538 220610319 373513352 604364988 965446445 543984320 642534947 803628996 661526456 249407743 398198612 866174641 728439484 393856316 532226129 132398632 981073030 609669942 29111675 296611152 781062623 59934041 552517570 248911572 16963946 697716358 629573427 748027072 267969914 992297579 936868764 870819934 949500237 611841161 299489318 280861389 319423634 368961739 593395457 478228964 855198010 633515035 659760284 304135068 993995472 184223023 479785938 998653583 649242417 275335739 683495799 966364567 874834971 190486377 415521302 399510121 253007954 148376723 374487685 395017412 7844593 372579372 863698659 166614249 900141385 856346725 404622763 998576197 107015119 471704550 842549165 84613606 580770031 96590697 100 236440033 440391358 694759121 19669847 532606133 601952070 964385766 124561757 902956104 812941472 176499499 48984278 124285331 402356744 631700642 674883529 760471613 891948064 818677071 162775452 261070343 313625297 142285148 158585607 16194349 494629494 767171110 635642844 867561544 569014662 527367177 960635621 912012604 280271662 949965699 378308928 450292912 598790430 164429396 926240504 7989321 524149396 664598871 873121358 986241284 722442703 113618668 795130664 38525979 945699666 551847092 907739273 453749141 735505523 609252473 573057415 91180926 715730765 94772274 449120497 706672906 146123913 151808197 186677699 487913962 38782879 559330188 81314890 555330399 636287690 494382501 670295890 463767438 532749748 784504720 646714806 578601068 858875029 321571785 205717718 69727775 142659106 642908679 700511717 922539742 890292621 699545260 101138985 249104482 230074644 46219897 156112044 460922744 618850588 848593473 618228248 283884531 782137885 133962423 305271549 100 348987534 791216348 417895865 224919473 885057243 811502217 869527957 277310918 968101203 679467395 990566580 878831705 194906354 991856189 182775000 670377644 38417220 309611488 942573047 458477127 45429793 289898662 178211951 384786059 368696993 114827703 151224911 498694239 648310409 748319643 591116238 802430064 286219387 986157359 669899545 669449163 357505263 282404612 292917748 217301988 440715156 723969842 412361763 735204776 610088925 399812680 416384055 520460577 975195658 606991385 806296279 478618585 794877565 38255291 746244699 114060058 762229509 411680601 876011506 254590672 872178451 223861119 9638537 976327181 879893820 551246367 251144952 649290224 20099701 198161328 99971533 435710146 453956810 489479170 470517442 852354021 564866207 732604841 189736590 805583520 318046133 674466628 302601917 753673844 705652628 417023856 349368127 892266925 604002264 581549800 625040617 119741580 385563300 949002607 719576905 620699635 696766869 663225681 360896277 608518831 100 422163386 686005159 49254140 374998020 432960263 573516961 919286026 516689375 279505012 938779044 469029952 796346137 246700419 222496182 299289659 478475196 321153950 199773380 360314218 960700885 19620035 918797147 33703226 44994037 843746483 70990448 243415053 19552206 321304012 56118725 734866783 296336434 226820082 887665208 134786216 762037501 82217315 602081329 983600589 339072469 470519541 855058246 534218020 839588972 799610862 106367691 240620515 315106791 15854795 433814399 189191276 212802334 517078153 736996576 326418501 955328327 776094732 262347029 587626095 122175477 787591302 577598094 8988607 479442743 769464018 207159056 908442613 427037343 710360791 346837932 819732491 133277201 645933235 987769085 269166072 103115411 776458211 629053672 62104772 913577451 338469612 871760454 183250235 461411603 965884539 804712962 353659391 153681654 12655318 263880971 429356267 160656162 921363292 388101715 983116932 570110242 176396875 879832042 679239903 711965223 100 930759468 845765729 348621289 832582047 942653078 906231734 722633248 418091312 765311237 11958399 77054112 49753076 650832354 364448683 982880284 175091000 445970570 795396022 972089574 291582984 801973154 94882893 841052347 903393878 483453753 136580272 264367261 654310651 923640161 608804299 873031209 381567750 637785344 105794122 629375197 671297039 569354015 322017568 262146406 875253783 963938263 12705857 586026117 294998284 151477722 28485533 169635993 912965014 68554488 639111459 674726734 619787243 392694232 19031459 465784869 351838245 75356291 249258770 782213059 311790746 303798895 535428330 596238120 407475538 710490526 295309716 350235023 304269071 938493954 935802676 773527375 765871312 872206526 383206317 362129787 90913955 894436572 399068084 887644613 637391431 199337631 429140374 886141154 557895125 773391396 998661179 790398530 526952350 277067374 492104119 904861234 423315375 880060121 540678298 965783340 261241265 863902281 48453520 32264078 797608744 100 419810068 896138469 899184270 11594031 373865728 527949740 85710151 547172151 626652732 865113307 936215494 905219673 748968826 227912221 294595344 299938254 83132617 228762487 64734649 478857633 660903579 119091876 446137322 332436369 648346941 178380018 119909351 989355321 538049618 241915111 126527074 431163515 717499154 150978522 807208603 879272317 738094413 999780573 885125215 197247015 952198601 462286767 805188988 225118433 609092062 124218425 614812234 45211919 656750254 126841102 498636106 167963371 685348313 991595839 816706599 818498916 142341986 668059337 486125007 688826552 684780819 673466230 957426712 69582234 203584708 479795040 352702400 989084132 35019406 155041134 182061077 302304283 452570436 946398217 984876298 491421676 970833731 854572838 490682675 314137114 600872086 444970956 297911443 439218194 758298529 887608505 214596798 894123986 214819358 999646739 274674008 6820453 281784738 292528162 736459396 667749458 265752524 406211167 910583179 156349458 100 443600516 423895850 790485243 721418096 539753506 307722112 419415474 790539680 504951332 800751646 79941919 889372558 947344441 708636453 634762212 135434580 40669471 253755409 608019259 221382212 230473707 302960093 195633950 342713341 426217406 98424194 631561648 726137009 939838733 66952176 26553356 143624223 228701447 78535389 358634771 377174335 659137161 600729998 896440870 34218612 736191752 386953990 489020681 211748608 623241999 736921411 875925840 916275781 314069753 592273639 598772376 524296566 700231711 151105636 373494929 730924368 805166632 617813191 172444425 767555349 123136094 889072605 559687196 230860989 45986038 208682116 217609696 101172970 366691569 562924668 513709647 776797196 207868661 576608753 212025779 615913792 453688374 259385355 54454522 446292399 449073397 698773977 779868976 900129316 261006121 20734383 19678477 30271187 605553825 425980095 301822469 116684106 629473102 778734915 998120290 432418408 135608078 575155361 919162099 341781563 100 843472834 955812640 182125033 631975276 19557173 852052954 933955909 232759310 779509236 497858627 216575540 819618007 717912537 766705682 82090182 672673082 500130242 903377007 954184348 318277714 358978157 123129323 889924675 613650448 438399800 453350562 190396686 896072408 368871355 767113775 729430593 962931497 390393470 74548699 49352266 816190582 860142941 660234764 660136122 469073835 100363585 475217476 102479400 436541724 853033615 573667952 4672248 474197961 950371691 939437100 76335462 669333915 379500387 30974149 730734909 448400864 997873966 984979110 636240630 784592044 613830552 589120927 530176208 597777891 61597977 690582411 70715039 904093834 136918790 906594717 876816634 400825824 160929079 648857886 63177430 823793288 374039664 986982422 161095470 712176453 164343632 515140059 278031534 698206296 49790322 495802713 382745819 149318804 175813402 317919287 502973367 187999468 17418720 992038017 141001244 945439255 110638157 707731025 98023170 874909556 100 76693513 180864861 723364125 518110077 719563642 489444572 255807027 785671608 247398039 830152909 754199837 759441402 326528013 444242110 434206277 944688419 26017736 990027560 99010632 639548455 747571595 147875394 452989433 303289492 923546261 143015082 279304292 366185802 210086012 613978672 301397482 181121750 656812225 565241823 53814332 938606061 203077250 628450929 207582851 137751748 340504061 753807676 566518183 268718285 270825121 588770952 613163459 876662308 423597685 454897521 333796832 209913396 29375680 828812105 129887962 327851022 33453830 934708282 860654854 142719138 813947922 611524290 450871317 932511732 298209334 514439589 856017855 47286956 342936536 474263722 218213832 438594838 872678846 750969226 85875160 419316456 851039949 436601431 631517008 113346034 279419910 104476174 783502661 26673673 340030820 666911055 462527539 33069690 498545269 807892682 385455772 338164049 971570840 219368638 389409455 186319028 397717882 471547400 925949688 424729838 100 477853909 399549194 985506871 220708714 825104989 213484156 590249848 60469643 516706765 377716030 353887699 91006645 120603400 356405034 15147820 438074026 301263451 898633505 410400806 929999708 507411689 964760974 491869497 565886109 90498431 208232254 845663037 735359321 771693366 317972207 988183064 181864939 68248428 994016214 449885483 456209652 127529466 126907899 859371646 277034942 570084846 627812996 402404702 229080432 79217714 374512623 484222321 749164119 64883757 728944895 166741672 536837598 8256017 376956269 388737693 680672178 236425790 647035729 803363593 692337269 996967095 531083559 201134925 183141345 209786359 824442327 566723300 491035406 636238210 126120828 568732605 151411249 132942121 959477955 717465679 154283206 29610172 172981180 686921502 271018058 295964240 690961407 520275187 659891900 423679701 587155272 514173177 313911984 87643925 960754657 894477740 667884250 153980772 157669099 892392988 853714218 71256058 89783755 209217936 881396093 100 27388854 862432323 782486587 708723449 513676870 203260769 700301752 93498067 438816272 577558509 293802164 419023356 633568932 412765960 727925833 597314727 950067570 610654086 185623451 273456111 568357216 163998263 233291794 992773994 597833561 477922969 351251728 573051847 44517616 502987611 505194814 54767259 504038380 392544961 634011070 660132492 169218894 334589955 782059328 340945205 606273370 844283095 398080249 457797290 58435995 202557655 914381703 871139149 145235376 104699408 49951197 110762988 584341338 26315286 467113749 165096511 157819746 467726658 925300796 57833122 718449006 717691022 239050338 474743359 832704803 840232171 294470672 883814947 826417294 299270289 101150322 455322839 924219246 228452235 824402972 610239842 79280891 100701470 821045855 16844577 952363408 337897795 52380686 754184811 766461892 220292833 410595978 633965260 955588883 838415654 207911488 378101764 12639393 604844965 246373382 48112660 618614263 898048082 978376652 578239334 100 866560268 400513256 381539518 718206648 938226828 920587601 900267043 125267831 263475022 289311051 53329169 190184550 217046651 81478620 85506334 455823524 923149563 892644073 371237023 268940098 606403488 359938823 576221026 760249954 911413759 898103953 102204942 373177768 963594637 562540931 139394074 870332582 312378715 680494403 369459602 991365404 222447984 858890048 206829276 399717417 986943998 931729325 894897388 814392822 96256658 370569203 947920779 887161805 661915121 789687758 925772722 18914675 267650917 315904900 223926022 758335230 236716329 577130777 603231065 168487911 564041606 305089613 356170218 304372109 790114246 527438405 235772922 137013652 389398976 260379320 689517466 961702100 50117074 56156354 998672134 217913029 852899929 955417429 197505662 474359790 508722284 866120653 749143330 244225174 169433963 598857356 50815305 77163232 278422496 955058676 477268820 262581755 851720256 851461261 193700949 584368165 858090823 308268661 938711801 797893852 100 237054710 997507434 69649715 116402994 36647933 228573601 882753445 874925996 109384220 730127525 803164844 488462467 41721510 641688032 869312873 564495947 955555095 182297437 39475918 327253022 781902278 867078761 477072493 151055710 402539952 596339896 119377240 621660434 899608728 403564004 796729468 295375452 307876205 518297020 476675650 994605485 993450812 331052029 892061492 777601636 213675803 493656438 905858023 165653222 470002671 959571694 898530599 426591804 867981250 587394417 152760580 655839240 293532316 202247655 109403412 212474847 389244677 571237331 481803863 959227071 441479000 274093809 891182109 825499294 407870766 770403915 928842577 737843780 5206541 330710485 887913874 743289129 871726726 876427699 401687075 127626002 594296091 286072135 16543503 294753193 349996392 173056925 72750581 79829445 997589814 626323284 964491877 555237308 616024665 594724604 149626986 952296122 382371358 749694293 749038452 856862864 595939926 833354554 443581498 895222039 100 418425208 643833900 196724617 637224096 55702279 985885175 242856878 794300892 149691592 144249800 626286948 25170190 833284022 705723426 232128492 933648785 465463460 165779215 153663313 226616131 123154027 57653646 788573868 462619536 593493057 662120950 514022229 236271178 205413881 366856410 249550620 595199551 231144876 961438818 380583181 946691419 281832707 446079631 218573356 599463372 140207392 219541360 565709946 752508405 847781268 288336204 579201591 545062640 301914757 237360147 471853716 849354106 630160558 58528530 731219185 186508102 312764663 656788065 231672841 30808452 413322845 476236046 841419645 5561905 456928306 601572054 447620804 618668602 957340533 265886697 792846504 430816013 715550733 420430583 441750391 860981678 681045834 586959070 114880842 294444892 287395357 869615481 173337762 63758411 596938616 28446551 661315669 470279890 812703778 543918041 733000988 148311881 20902985 135827351 789793913 884098785 569818196 84579632 725582550 504273913 100 950475636 91419590 784918099 770935569 979859890 51904630 929250863 361638292 341028634 614297224 612865524 356052731 195685092 497309560 898101906 428395224 99174945 252929726 184989550 851001464 858107064 206308247 427934386 671817849 730831032 112864026 424062234 697117803 270079325 220220975 424066843 330039144 304114330 803397451 207317695 169649106 885559158 819005971 101534548 906363783 950449163 588718420 725544633 320199685 453194388 509647905 933508166 768886307 631682648 867106273 488508775 18638832 618723087 668850202 378615248 349000203 860506851 253490961 92112431 224659695 966205910 214400141 866860643 196216411 300571399 816815953 990283494 876849028 307781894 254784785 103676609 608481397 452918229 625484470 784291521 474323698 330763234 74667421 957277311 23457696 763798390 866206149 856872569 908101070 655626395 428259703 435429253 252543004 261546260 934949611 172246461 217760685 503594201 386879203 845810921 374849356 40665150 421591191 296234782 40010619 100 460330894 827145928 735596693 73014792 900724448 244009875 608479726 493620944 44316213 527091806 816380670 581044075 209952664 348784460 714613378 734894748 215633124 679613027 969661505 641604800 315717333 813488755 81208832 803881668 130725107 205464446 36165034 999909742 546996840 735790986 614437284 798362590 646717114 181931127 258977170 812474986 950894107 40185919 117883907 318081431 735998683 26557209 268975362 851751061 607292413 471562351 90330722 775807600 757932112 344001583 551615026 825866471 641573246 608820896 812617884 55148431 100447741 690486860 247804333 278869305 798420952 494497259 538536041 705322157 555632067 594480675 378578748 270241489 208416989 61174079 109564621 411469125 290885811 88829809 476860939 539041818 911094437 252445178 164255153 288975125 31439881 822586763 475825730 37752810 484943023 884377613 576527336 343989098 523761067 201351152 384101388 263556268 37588505 239810383 559333489 109390557 597244608 429575977 979890010 467592539 100 137507858 109691315 199526208 373104915 708386434 71587759 971218625 386279851 907541748 493911772 716256672 466024141 603163889 831485638 377095849 320546564 788857120 545621853 704881266 665739314 330494996 763474374 229536830 800716338 568464563 782925833 279395484 783786439 258296934 473486816 992882898 747611031 501122915 465718396 458697108 229658007 942711816 48357702 750741518 783116013 906640481 206812896 325020338 377306616 668110102 861374988 970589027 22636131 108876065 947695321 352927512 321208405 716599493 84751951 782610733 557535359 266003336 738247127 650586068 139497343 161142167 136967942 731255362 417166420 573282151 322265991 298943501 539766241 817596218 587627837 820618658 87012346 376697237 707635747 208363582 148075554 447680694 469403369 451779892 614497282 378609888 741995259 933184379 404947445 450813856 944915551 1244991 503489425 375186465 377643656 888583068 584811041 421934769 970994904 991333199 60985028 78442456 139255159 91033022 933234481 100 99588612 193740919 671370295 397479232 715257620 152718596 406082293 93583221 706218436 461250934 847039176 501078437 890387007 800665800 207398015 131702186 966827649 186048721 645961285 525853489 892041245 338145945 611177616 482002481 903842012 230705464 519712433 252292956 595174487 193193035 169739978 412576543 196048869 231512620 22914761 294976100 153403959 104377487 1197324 416286437 812262255 984411926 765089061 177212048 974122705 148079764 881627828 549398252 158842053 664131956 186319401 232428310 364964212 67878823 553018918 960974265 590206806 840592763 287965018 897445094 391628416 187581580 463894888 753337834 876467576 162645597 80728697 63777674 268596141 824348803 525811534 969464568 366387673 712927721 536781467 502190327 579750075 415820285 763551941 863579196 306796789 395056511 635868501 622106596 152991108 916674191 422078587 208915842 885227247 96297863 649223839 850299786 922112616 949383483 743961589 492870533 886182657 215926098 565610666 286283321 100 808333338 852551900 540431512 124862481 555365829 573873650 620171803 612945162 651286478 583530534 475018921 642874230 382335226 425602983 456189523 965371814 751239148 919715622 61527664 157609174 142417118 381209841 330864413 297544148 690677066 124741980 397525010 41444470 21683535 457525432 563077340 5512705 833401793 132721372 174836355 470795342 185533678 218465199 251149794 178676285 301119548 452727004 202321078 82721411 869110875 661844883 269256910 309688010 373513222 298803363 972227607 737908216 451291432 521243560 254055354 42903621 490642900 753281354 79900992 146589432 605991091 172225119 944140367 921564531 326974097 792217080 470782589 687889902 204662558 11612901 755584856 202652574 949315041 939462477 790957454 111569352 421666760 971855564 742105085 957304394 53764510 495620388 943902466 386567748 381309864 445540846 226124634 590773587 105766615 606927395 253838016 985129909 289455079 245060806 901654492 985516703 677688018 307402311 39946368 629761944 100 924580520 689501058 283621801 474469935 102421916 248266225 280787637 211590783 21208747 18041054 852886 679565428 875857258 183586746 275998535 548378531 472026322 112721590 399290335 648565379 557836107 18035265 562570233 252722161 782779591 266256190 252230349 107481085 537079608 831252503 868700329 824029440 569605862 793896163 848252286 414252363 103948794 377165397 971052505 514839374 980146071 902301880 681605379 481335314 208043633 689889948 492372318 930233941 916855209 159562022 835560335 695972217 495675895 932840489 78427083 742057714 522822486 260569489 60103032 21525831 419878112 925841974 384421318 138462306 251516179 681886035 619368435 326368306 636724894 990613655 162513923 719794875 488423905 769774895 931475208 512728004 173549590 269313107 793994425 976542547 630648420 898255353 76247889 682375494 861917656 79864370 430633354 713769196 626922957 727908244 390379600 106907890 987403305 910638351 536176933 433679174 32326338 683951506 680081818 232282012 100 913139720 315265044 597300720 710761904 484374451 431320438 590018516 990627702 596389578 977121602 28940732 981270577 695221171 366254969 842008308 188227706 136471073 268843050 255185183 396739363 266563535 639587301 948060117 767621264 394072158 412311072 774160289 732223878 593219151 493775678 855722610 581303197 941060498 794917086 252059650 189451284 324471116 702588574 773207917 918343407 9534837 781119162 901572331 353861488 657930378 855107775 435134850 504735561 370239562 316630335 201900682 260296070 743572699 134597495 107683799 523881264 804833441 209481126 919841044 423103431 419951029 495168476 704301393 824468051 798326470 554873803 883507721 224440010 924274291 633733984 947697239 407958087 425473339 769661498 501305232 582454242 626398798 285335358 237278277 353787920 73268483 404051080 534624535 306697019 726921051 22340834 809495481 934009806 655412237 391259549 399680308 985606111 150938791 190488264 662822599 659880322 540045052 790712739 789638881 722472854 100 126631700 818198671 883445199 919730097 292546311 167055075 110280761 253788744 422383580 834121513 589578058 468187260 840815700 724941623 238100787 560763161 86883479 539518921 374690013 88291009 246759565 971421365 564262984 485841618 633824161 794155377 297055171 643567578 127707768 481466382 810599123 219652739 69839037 677754109 598213672 85532686 503834336 25582930 135470393 386612874 862602590 814806753 137309359 852162041 553492701 977230721 271823430 724059771 116015050 206275309 250801528 624081945 657799275 123302815 631317523 904620018 573841338 590072114 23969911 32532582 183105748 590885191 745323562 201411023 243512853 718756415 221127658 474675454 307921930 198488971 698232463 513346415 155876087 987039170 339461826 752832996 722167096 135426629 531729807 397677043 179731743 676582775 833955622 568215634 73267956 352900756 616858721 398857753 898713528 627556160 265348152 733613758 357680370 351848395 16582010 809460536 306215706 112076628 649642757 623341479 100 783877322 250673773 718508333 977171820 58382768 393996001 330065914 969051693 239910955 157861390 763839052 389034693 254670282 144042960 578243853 448635983 443722706 26495604 812662016 158368683 283592320 747769132 207315544 743470790 564003914 659722833 146700035 763543110 795478578 529915443 964817538 16818868 363927939 168172855 669699799 279647812 628422588 261787128 97742641 994295932 108842518 54584523 168160643 238219015 9000940 901916742 875544598 393554987 310833746 263834725 197188814 419589712 501202989 858609973 783550541 757959454 395341489 734518339 734562355 325998413 517399747 357493871 424820241 728719150 935790991 636971042 362665348 85863072 542505947 184810818 965163381 235191323 317031811 913525239 293133205 211386265 506779814 916456330 111514075 237112426 697369703 381632648 627037167 452146978 292669817 827932840 44999340 261266892 811967042 809067128 423257515 27281556 683570056 911681565 373347478 443376235 762787861 852439203 34283876 834397112 100 161505675 459470703 444829463 598592522 925244981 382838463 383528572 30933408 483570980 90812735 359470271 596895235 698322213 479295265 905897860 739847561 71103415 993426948 164380885 55365938 227815658 167903301 525569484 248170227 712299199 532338618 368406636 73924050 450277260 61797565 458992585 53832593 184097601 538639308 767554612 329147981 368649463 143190177 809801832 936115088 415060117 265016100 680412588 965811934 715096066 472362347 868380770 158166612 72632943 459214345 565902260 300167992 568463589 966778725 617836009 835589595 648885603 11586033 723103753 72110663 742938398 863820591 468281424 111592261 850949700 842478464 753607722 342234438 690124241 839582670 487398844 419419366 896716948 51780725 306467532 307162243 943200199 713320399 68471083 688956953 501379088 445337368 708717504 785558862 654467745 386201205 655913360 33308355 253588937 978666279 37590471 700920886 520856882 419905233 498618583 186268936 640648501 373825243 182264615 481216973 100 303426156 945830683 361462472 423698002 721759035 76383574 465736314 946347200 132694906 431495604 671807447 784479941 185854987 344708836 355480605 154517320 410307509 852768879 511581571 791501575 480838554 772569792 997549905 273134905 788906176 218315680 502591808 27641630 483244726 314251930 50057287 605757732 869069513 251514181 839751286 24065505 222873286 531335487 704167514 447501695 20215111 407149101 486084087 545105487 567976381 463380550 802567959 178598807 606414922 748897958 870077284 822084745 546322586 649600939 953180217 537311842 587577369 222521314 384031980 694357787 198216252 110129201 469594082 823323816 767272828 752176465 259184957 523968285 685381774 76611088 494716064 917372828 357989686 335716117 600692973 70992916 971315896 776305775 950694209 844338517 787350111 429067054 82316759 756880643 736284721 717643087 808500175 277557257 129309084 678902527 86970289 711660513 884083203 166561329 119199681 809404101 264088984 711946294 887927692 514019561 100 298569727 616485362 24744068 748409675 288696864 116326697 890865623 834187887 213362578 936998166 798381180 576565637 256267632 594549844 483485517 645930569 64707381 641619321 200409038 305007906 368001185 335321012 977881098 600308574 445478186 5896304 338874013 105280183 812535597 140370261 964916193 325828823 551555591 653211697 713103399 894670556 193580789 506536333 610633484 448228168 536194051 975179558 524318438 318579554 130512235 23734588 504763678 354527792 461219130 331523200 556058795 451325282 604695217 8886424 402544817 759443924 711587310 261042527 752585818 846205674 695984714 764137913 70118798 265426830 618125550 624324982 460323160 44304488 707150040 984115100 703809368 881064828 936985825 687514973 327018655 333416079 35835842 814309755 496284138 77305931 517640254 219011409 568716874 814701683 112061844 257906403 256491566 301565005 166260887 144622107 912110116 30826834 727018944 671540733 885436387 208666336 599693185 202375511 988429011 577190821 100 654782792 268720129 658420316 455547018 316837508 667831358 55568443 878353063 608016433 18408246 817388445 260677646 611820643 509191725 544629611 807607893 370173953 936275669 627880994 514311800 943278012 633915345 971431618 838900060 796800051 298533173 225236668 101230862 418924216 241245572 735267358 237113951 472800670 356372495 846955554 725849914 557116371 841887639 628919820 270311006 845305428 102278245 930682440 890149830 498863867 719449634 369234718 899616380 990059583 275566515 355736781 801594117 691077591 946650226 698796170 504754983 174999842 269957882 106695871 643160992 271053330 42883962 96672990 845299806 176116100 371527723 227213068 571970721 567466813 726806889 29618382 406793997 697138703 685967841 761086306 846914471 529900840 461759389 698920970 281636146 546697563 613597221 291717799 985559506 954540899 194475050 624908122 583600355 746261238 338160833 679789444 419297650 552225584 813055770 605428537 325729644 11133544 688157918 510528995 458946453 100 818347597 499069856 522449245 234841727 155758410 942412036 862945217 788868625 508208135 615033232 740552729 567534555 752685613 137815486 562268843 420949519 102992135 791978464 91758999 367752691 289642901 968391605 299275953 678264364 514531380 575898650 972834511 539116225 960880234 994608935 12787547 898923150 964731507 690777155 633338465 929814252 777023427 976540607 212618889 470605406 321056065 633613137 551609677 652271961 316875409 317485363 53868944 686006988 588924095 146865856 344498339 25029595 900380696 898387085 161064848 669494546 681907679 627595334 953445379 525505425 114668550 312852556 119136186 473349587 448942879 528435585 290499972 782515665 843719437 584353548 540549454 759155984 245264653 322984179 994173759 327629657 969804136 718793169 414904885 669087572 558861956 392780407 808726796 79138373 5770560 457100718 420341355 547284087 583242090 489022521 63263361 677441205 744934082 167847762 619197895 381846328 96164278 190127616 172495894 492176938 100 453008903 57917954 915729079 619802640 710992567 348539117 185731619 256303086 329435971 308237477 870034749 682458894 520135083 860351527 835818439 140690729 319408247 811167933 181439091 564173966 630432055 293625703 290963043 385929706 669277172 479698319 546275936 474855854 562605745 296731687 194765782 814511335 876317378 86867614 811415386 821381526 462789681 562594405 342826870 324495238 532035939 395658624 339397231 156471424 452180876 138813917 885989469 220030115 79800267 335142398 393632917 455866467 97368405 515908289 249793670 227804218 745417388 223434792 870857067 361025811 980709571 534465874 566746383 786803155 425225368 519629185 796262341 133409651 629340052 365979137 180724080 882958766 616725708 604437265 378322968 26896373 684058914 666365344 282555058 326749029 963846451 258034444 801842355 493748451 879181461 150347832 636792981 878128046 203002788 285002565 576695519 991951026 557186935 668311356 198947513 614198996 316452125 285913142 548672625 928594210 100 868187663 977513268 108189919 888012548 205230921 514175234 584576373 790339275 149131244 684344190 495184714 652920083 876835736 747299426 247128625 244434864 79445241 945034915 962361105 451584364 635946419 619320499 485213670 66409099 285264431 703566845 369270804 618464609 350709608 650745036 922901711 630432671 960138602 241132896 686245542 335093440 605916089 303394324 307069287 734602030 441891142 920822106 211009479 991081220 323533961 112818629 541022006 898304380 446273266 398886225 422724248 916573256 287565724 124823235 657432323 504934820 766987343 724490978 547603155 725078022 104057190 127808238 362538273 659269292 961474160 609714024 149499415 704259678 72501990 369157427 107185488 355017848 567266433 528234124 648521419 425419514 93734086 975757488 704453064 838308095 958867811 919798271 989159350 439414217 408462632 107309249 785380420 271199061 484138010 6282806 732455110 798683104 881408772 222857068 649872121 814304603 658793994 451679926 346700297 404968620 100 790840974 396310739 371031018 314937307 43952615 635207925 294414915 622520293 825758805 379138296 635119239 27928309 473714172 133315008 606245909 878939971 915180367 345981890 301551307 357712092 886300395 735494503 170148663 3435861 806996700 714683247 345729170 546866512 687215740 710357734 652831992 482255637 737709644 461081193 123150159 129859737 16421603 968262745 944430244 162469993 726523026 482794032 210577041 928574266 432637433 294947730 713335053 409741331 752383355 363775194 714922511 642835474 697200808 134586096 702170847 677871715 650797998 623295654 25345362 915701239 960950401 958453774 444536796 104422313 148304815 266710716 167050414 295667154 395975818 769984407 734133722 139480554 621585931 106123133 94510277 946012827 242306253 208870668 447346955 987740373 169795927 859734396 552177802 862238356 745354140 657603005 620567800 162939662 229679226 341099060 597886331 863159086 729250236 159194766 224000892 935342595 833897956 247111060 900547260 585637643 100 778360462 833643438 789272077 293841328 484952580 7398530 185202258 717443892 98034765 352087183 273407991 816093042 700725744 870757714 361161977 400167584 705929824 977700661 677900586 254065488 310162632 150408928 354220625 448143478 530009299 418868055 436820650 990348256 245616083 811387609 481665659 115012230 352062990 228163357 395317522 49388571 61097393 878179313 164676796 755439384 916841857 59525000 639736451 240163702 308050793 91425385 374970878 59377041 256531674 891862812 594617158 704614472 153195500 414759029 580222381 853726307 721692017 351626542 418500400 437218060 262102726 296723554 710834795 211327042 369561866 43138375 867688423 555612378 722850752 271038215 679977481 600409958 635741180 836242052 112756655 342513545 65581826 74431104 347410861 157945055 493087892 472220327 158002426 181216884 199603790 427807356 322246238 581996347 951574747 878505472 228633309 11266747 113597005 877654529 498042624 119546212 244863495 712566372 410976474 219406276 100 514949367 636166855 288775371 993467754 114686763 213030684 620194288 629205861 105366297 241596535 99733911 174466430 407201309 156315627 635560067 880364395 518319694 71047251 723730212 113476952 793320169 189318809 45210147 689918895 835387989 100064879 7694209 82785156 754198430 417393737 489601770 256849197 14102378 391695820 396388295 583541712 939120623 910757805 142694325 769803958 989911492 919593384 803751778 514578656 592629394 822144857 76768753 202836235 473742102 366108937 911771125 776674466 749955065 303458794 919167920 897479378 917603735 180336415 959123346 419635322 392449615 481658484 759964915 414361820 508849111 239107593 709176976 326554396 960185856 880851500 150243524 652367539 552685843 352844474 832591846 266542395 559675208 666657384 124613572 570996323 35728397 132730240 949139917 178535971 682014476 846904830 878120741 953168685 556980486 939291404 364147671 291888669 700693017 695231849 930457161 43669755 920158850 119196182 474580126 978318740 100 91899028 637769638 59922401 808076977 946154442 329824329 757327466 839570517 551411860 200699741 734829957 889653825 530195158 338303888 380962779 828296567 370342507 734808496 300408295 447259143 978336841 961798025 543349117 982212094 320733399 798757091 200699991 71751194 344900952 641376890 890155315 319614081 252308249 362597185 724439272 797262072 79672968 308681702 598282782 645051973 679910860 900454099 893493952 165209215 742278486 818208254 476848633 35628311 26524539 600480361 224252240 49420218 785620380 173546381 651772830 177940279 631244053 208836715 27792388 126274301 12240150 574878791 578251627 411092101 284873899 117081982 189713784 95118121 445940006 951830328 971658708 283055429 194896568 105749068 495289533 646818025 226980953 377153055 77505555 356819245 598043779 210933355 37097900 740013613 939100621 908259121 310300689 346277807 329647062 938855380 73649522 427519621 271785075 865392396 386256831 784539387 978851238 640436314 297003057 46363048 100 44939569 826647724 774556295 60712622 57047205 524352399 422627825 784804884 656540221 884761965 224910066 127138600 65171969 675481789 966278369 248329080 530282916 912286675 49453267 311315874 721390819 958904387 804451959 392082046 990530601 984828813 6583235 670507083 511180037 613546796 778792451 779064589 154566683 162814959 144027434 857135545 854544886 891374117 192197796 640143386 123472809 965710134 713277233 827203555 309307477 70908717 205915749 655262519 570249391 76897344 545913195 863102976 494675554 838878612 838566295 711338499 667335852 250350019 129135929 618621306 331549915 590138641 619969159 683968970 507697837 603048676 478898271 377473436 659893085 524894771 283518410 3327626 594078534 135187933 427856786 499858798 432560994 926090873 667930510 438872074 669961293 216348404 573412481 33111993 779029200 892391357 511024318 115584088 827238201 115018135 944305716 481325828 118346427 733342843 546782407 201677869 770038987 587747798 727030484 167447043 100 263965909 928290806 53405436 329559203 947204545 169149654 673266085 409094133 48520185 152193272 277652222 142856485 160821023 959961598 401290167 362354539 440862419 601198301 723696019 631456966 644621911 711231220 195393040 780850408 518455245 214911901 392375882 302570750 216147754 482011900 824616973 830677811 642562345 737204931 374683357 702093051 507220212 782542128 58803764 155303349 327785718 726811900 783891664 854603119 838132467 688121130 371441385 493825944 271568502 692995428 974347725 381928471 501499504 57685975 150872168 944837598 761265713 913006605 841579623 515539302 587505547 823684502 203518710 360177191 949714233 505618387 156748635 789556752 282665400 229772291 834519271 390505951 441744118 817361837 299977503 774832140 888057018 557690808 160362197 4366625 759542770 45665691 59305034 885694681 956782953 401573246 916066506 277423233 265303236 63488450 198413199 82746875 725137188 518539729 987980958 8769547 41550346 646578572 960868146 975254802 100 276409120 589178435 843535130 328706281 908965366 954294673 15082340 998261375 10985739 480023106 171549533 745876056 47791873 945639863 982691956 247100793 84738557 227979644 922316848 96938693 807555511 664094524 498809902 700951094 819485226 782118086 845919970 412900862 67783155 513203311 203531166 988695865 428303566 353878729 331978095 660702956 604063148 319241655 226426477 286957653 575616198 580128757 114887687 282337854 338128238 273515229 247711622 466398140 28731892 723548021 971852215 223672597 614842245 967568878 183753912 134361798 5233719 78293954 371430636 777289254 667302154 528291178 706068389 511278228 76321007 827698974 24523198 935222562 380163896 865954739 8223281 77695800 181334190 304926129 26014186 328424240 261002899 776739386 549650330 714357256 88777859 858976318 32918395 708796041 899561512 452028215 700001927 222947179 829649088 374137848 550905544 538715417 198407400 245966784 590989419 68566100 750170771 360895006 65517459 305232323 100 559233787 732219912 904540572 368616314 543752651 831303689 451955875 113191444 329828965 276726948 611725066 491904740 552904855 447307847 926699471 906345339 300046614 293603702 467834731 122413271 996282698 956116121 966104265 540725965 425382760 952981837 667315948 833610673 126347766 10712635 334560050 66201333 783255919 783967254 51920794 592811423 442732736 362211998 356771944 494136542 622086211 877297536 325603527 501170516 904909942 77854369 448435509 102184499 543769133 145591830 273608342 463836018 286871301 537312508 971493763 159130010 869681694 881711747 943881104 212297014 25103215 800310916 715592441 5878972 827938986 519096460 404992252 109483351 774753794 505109026 109477881 259447372 903517995 446456468 160701299 12603388 489062837 742565003 813523203 629952011 470357481 132730977 957804128 459072046 134003568 690603320 509358136 35613332 657252502 302206184 934940265 211171455 809408292 510598007 439150976 986741238 490226118 583739233 704281760 867460371 100 966853629 679806681 71496305 846788442 145813656 825333968 497302568 43540542 221033309 702993771 367219824 88640623 425621322 804146262 125390944 321412932 578834484 984896958 944403513 8916739 972361775 97270275 582791603 501593448 69471897 788969785 673726982 101007851 817889116 521898830 629688104 248306576 289481440 709428645 114926406 760882543 169378097 504113707 295495639 762473946 703739670 245015680 952129088 296923283 904801066 321066891 214910719 580851936 995221661 58078564 485951465 875866361 404057628 933254994 137902451 747463353 457196096 463006693 330781488 152994914 184611838 130104824 559576166 342699488 438592504 512981086 379474492 960703020 723372040 26979670 367975205 825417252 929782954 942411072 192118683 869423994 68246371 916327662 288221279 533454288 429685582 168206819 492934385 689799219 200869690 207727111 691474106 350714502 710629386 422702522 868790079 958552469 600682623 149640585 379872843 330339816 103597531 1618461 210366058 198951709 100 239145682 375375890 74192102 62918534 590004850 498580622 880346560 667567082 823651211 545021020 4314858 340825629 521043022 364821642 277968705 596884229 685141207 394564458 950683676 487669125 3846164 943123421 44220931 328158785 348175312 231759010 854190924 666884396 565916999 13803577 375509814 200048813 472815226 565333010 803797010 481252516 707088517 368058104 970116414 313515047 416882895 721672352 732720621 599197657 497469965 403031166 359947275 14999423 8793434 448601648 490317557 890802847 142139868 942513332 998051902 33207419 752495238 801435847 562291107 475099134 327719231 925999380 867722548 269594192 319369480 980747772 618431511 239599076 436211434 471808327 964398130 690064737 56030672 976645951 230184524 884524020 365777641 893638942 362878685 404012567 958711862 248673687 196993058 950471516 119837402 113012118 105787667 497183835 695864743 863933157 722842038 831808128 760146480 74836225 583523875 697228526 747184984 583052972 581262035 186512521 100 662500229 641482350 124189249 219934054 330435921 547621316 170926445 676317242 959744577 218287758 724666297 372761107 518712561 203259627 629983787 422670273 403503936 60238931 874286699 125458029 770567129 641500440 634913085 621012717 690675227 407989738 148673423 199985145 114087601 251814423 14580747 250524117 276431415 551381110 224632076 560036326 825640942 691411393 214891725 835141592 576541750 341467669 430531929 159985071 421862426 625389176 488516762 534963755 778319717 288542328 375052899 318258356 558834612 60977463 765373777 63811339 62498463 45905371 662713675 327937756 759585390 418645237 591274932 180100810 309439955 148040362 780247966 447048229 568904676 658427130 341512660 539792290 998266881 172853029 515145303 211323751 433101081 130371481 829743914 874559350 64533825 637597593 419216299 156399361 125020998 180900831 737427196 583026049 834535740 481819009 832397469 47270299 147510136 117235067 181213882 88593202 742742889 939636716 7204810 765266049 100 817249271 204035522 830980946 640675954 86497661 293742575 560727393 24547888 773050460 246263344 711980601 881478852 874884392 854051851 771460485 213413852 558456955 928028447 642633818 527569481 361100776 756014219 664361215 6175643 369985948 932824706 842627869 129950487 298928210 425498179 623927001 660615469 629645421 178441647 52722000 817346243 886773650 63701895 136553287 926854572 763457010 955069810 897673135 642543666 722112795 391011687 856039971 522268052 416848671 770015958 669725577 702401176 45811652 814689241 138455568 327722560 778879242 74521783 943478278 709273228 319886836 201667703 576095421 64096269 935283648 412537268 858872444 978917583 240955396 750322956 756333623 184931568 251269747 711618253 721053355 234189593 181391701 183470029 992798047 171492231 886810810 757956800 984160905 415982916 76462145 367515980 95106064 169831267 441220638 747026703 353954167 76117082 233192832 430294086 607257992 323052911 644039677 796397224 877573473 602103160 100 787712632 64452257 410021455 962146060 364564075 58223350 593222303 707349437 119868082 105035139 497823143 179152083 540656908 259146854 496054143 535939827 129819349 873737528 886864059 899000474 368906513 744202828 561722778 784071459 737923478 332015105 956457928 855620211 267030070 319520567 753494327 987990944 368446045 959571875 997307165 443709025 695895670 512215790 932729134 894894133 526196946 831042604 944244433 651240100 296753446 894199561 790034824 15689185 745158743 872621509 333228498 945506961 712693450 954469717 142376586 214030238 943409099 830322521 169227212 161540061 193181393 618104257 880782716 389518241 39339693 210436457 349128332 928771532 394347705 951136400 625882944 498223189 243192748 393794854 949937680 263401284 494991249 520943226 929120319 782578334 470775096 522140686 772474785 284570296 462395405 32388698 989258987 679566411 271285688 880347279 138029324 54734353 921271241 824025207 705767515 899931398 756617855 900585823 197580859 328858791 100 852481007 15978641 48298791 474421933 891466908 972482568 444885405 372461527 735485520 222276150 891399332 248918375 960702738 52722474 471011046 218504945 146114829 182361851 576685721 189544548 43465185 558570004 292247826 303616393 373355397 121052115 222789950 263884568 307853972 255884990 272575380 988765001 485815971 72759068 65499496 714233631 293429612 302426327 717750058 643143569 556659627 139455550 430542403 431041550 546247626 990303676 780585242 399090519 202277969 498208963 460149287 92439793 457448279 67069680 382925368 697186946 381680687 712993254 564275770 413149037 755767290 697975068 727656887 835791730 595063137 770114486 623004433 884280105 699846028 936202406 358934789 126357351 757663410 389812707 128936569 365550000 340755287 222058631 764447168 885146094 916954253 236083777 725021516 356423902 769572117 882618177 229655406 447674013 997388478 296620817 641863477 327456668 604860128 572438773 117538909 339799090 338898325 860234717 564809224 585835495 100 579828167 881430312 447939683 969947717 615633744 365402042 799625360 832768109 40921153 95615507 359206962 757816750 102461362 734979322 76510582 637713589 373344308 524459018 968585393 897247204 509181344 744356901 447722237 19277073 97878553 905011832 247716926 647514096 443804640 185423594 396322656 345167257 16644484 53137812 124182532 86259076 849932234 274956606 610433874 379473180 756391231 781316458 494157448 605203834 507347687 411305255 979271903 843960446 784533850 353228719 308323792 395305426 239483160 771126599 43229405 439153810 386623461 538757930 471675554 721792554 362261853 844326772 517234509 98508280 749996039 11144717 147033922 983796243 33378750 704234215 877558088 83284095 592692274 493400837 590216555 743803510 102174584 642307900 544770951 720628436 921401769 184464261 837594294 67406451 235212265 687492966 141980895 632054297 39104412 642608023 257461641 614957758 737897060 453640164 920554607 414796624 669299194 309658822 349386850 967201178 100 823369129 86263274 855340684 213660232 824402136 599221724 212735381 481241029 630213581 176933781 867628798 523606743 425604668 34156305 473993151 652837001 910656653 552189463 669918249 175252190 244350953 720406795 300420380 163201406 958885486 538928035 559542303 816885226 854074685 565945773 693675864 784689173 411778594 437090662 120762362 538332144 351455013 698140614 403331536 124209544 827154901 676939223 743520907 511724661 68047398 931769078 754650115 707318782 307363307 25310635 527761941 858712533 321312323 987950775 921427622 111458056 285444676 498017942 759664084 358479805 423930445 6743127 691531458 697242577 810388285 885306156 812463467 590490687 981406816 675846666 23916798 154108223 244730343 301664708 874121557 965760568 350181999 891941139 590792043 89403339 728390160 749170500 189765786 682104693 806787755 966907505 273160543 673958713 453845494 992504514 217608598 891286609 763135500 275570687 211588243 258750393 342594077 283932221 789259328 669517004 100 750507566 73100717 25411714 317276425 589996568 448179635 202195258 484496178 971154220 137108976 423447109 494677660 239574486 785388463 183287109 931569738 848900681 150712582 643741731 564426118 623581491 607597789 216080851 337700432 960175268 420981052 590619431 700470045 753762333 876987908 871605351 692278941 676966816 744413052 911636825 724259574 181827909 934097335 798136168 920513417 420007054 398675262 3504939 917506500 261014442 692006984 997322358 726021251 199128892 699358940 984208238 954946659 991854942 760120242 81356595 76790871 522482530 727804561 242131231 64528156 740441679 984844328 792276938 943592731 23188062 892955647 55899480 316644493 94344302 398529655 730226614 872430987 955663537 643161844 601048634 589190688 599876507 166265233 457524973 129469297 957715265 321807157 238183751 892274643 664872737 441918073 356760036 239818701 978710641 76099235 629054413 398278340 862327030 434998307 447181235 759641398 758544634 621413017 144785338 770250430 100 539718221 49621394 924573534 755602167 450236866 363408315 393661042 229624468 90423837 313500507 398906395 142496404 481150934 515920818 128415870 633413198 636997831 429908163 481342866 972250014 377653103 369561637 346932459 914853423 284388659 407169416 104814271 850628992 123392456 215263004 310082268 364122153 749832757 50365064 38020626 114976788 982843352 86891653 709145676 981365349 628274227 346968363 35166104 741047078 23660580 516597058 920441201 429193596 933472163 429638716 999293477 549348015 13640905 708793667 585056324 618142983 335498916 676729239 812422334 966390549 457923108 887201032 993015891 580970486 588060383 79507012 760668415 838830948 726303551 155126856 746727484 159883838 778745115 39913073 562497098 269524424 270869159 81338941 507510817 216038517 587988615 460947414 751144377 391267900 830650873 997659004 342072580 263123296 597498209 24901658 133904352 198330903 432472638 602627086 157070778 717269541 899572861 318274322 346684187 938105932 100 213661416 617607696 919132172 123265554 423497216 391708189 473842822 897075871 832551562 628139505 184547277 197544751 48593131 545687613 302211272 892214049 607072928 755557456 380850574 344888850 680334889 391496380 778145210 264598583 606946170 237196268 562588424 580443584 347570132 878607330 271073528 172643486 553594392 415737321 298441697 424051558 377051775 52600940 518770710 254133235 892584798 898146793 397547953 704962143 945482824 667236434 186692958 39356954 60542373 356331841 851960190 603644937 378592403 404170396 557469830 141464771 10061008 271216156 150310721 838324197 683563125 686945667 56849471 364250066 409174743 39114346 849330099 13136010 610742812 704242664 995717254 433151079 639236013 435825073 533411363 164180363 345346163 145484675 806754014 53592887 781779620 863180506 391482838 925073542 372525088 876799600 906701123 526017563 937369008 737742710 534227549 604085377 71087186 780786940 294321589 98704532 632381163 865510073 320469528 465496435 100 83371862 200727170 950434951 204958799 18307639 851291422 292560096 9344496 93620113 900743382 24098391 297895116 483892022 759000774 61948297 461469817 42025919 995747932 115182411 272481260 569184087 227661103 323466045 205576608 340779974 268420146 381164822 141430077 808187667 273837579 813189433 898857459 801651648 467082349 297715772 126354859 647586575 893303519 973964844 467415131 424352906 328687263 30280117 701287259 541636784 99580644 991605425 910715829 298637608 496850995 781062766 151170926 375998936 34837439 129300225 427226680 36102702 366500506 415462050 341270531 895043304 298611218 506953914 591952442 181444346 584351476 978889144 511614053 571343215 494796077 805530009 653623866 518882804 798280217 33708412 13636746 889376838 197259663 980055120 198021263 279096909 495143189 440974979 51203058 606578984 847092521 286030163 703832775 877595796 420172024 227957343 602794963 507467691 313624450 275707837 252852856 22436314 551378692 256901858 415165701 100 275503495 681008121 507615351 133036365 537436569 541650241 322766095 226326918 753324615 847195369 909795041 667593663 419826791 203975551 657624210 259775923 655702043 212131851 869416564 866533899 430662468 627895844 223048579 901742633 10247655 596418668 28879177 712035709 239798103 685873072 948527443 436427663 22413867 745357692 647162643 171750320 983857103 847304090 873202862 408258207 226692068 704064011 208952348 567005321 198571537 825285832 333822110 70279269 211363572 142314730 761009556 770911544 676328097 943141679 583961467 924043102 372638056 795435763 943094799 997123567 849459676 100932009 799098388 116237933 441417428 795434169 426968312 325723887 120939286 33413529 755432059 707775397 327237481 241206800 858034259 30295640 876148051 602526901 797267009 820801611 859999415 160047569 74746140 128963186 131772218 326221053 561688700 836550266 470718642 543386731 781168605 121590320 363729878 281721047 988032428 899770965 57643495 400283124 399039990 863967484 100 699294076 140169692 400850183 804809404 603385055 158435428 749025245 113668833 498328238 129767513 457889789 478707535 73675196 161736225 753912538 922699577 361344356 618075771 294071458 751951377 529898730 993934190 207391309 547494042 366282690 564796909 794108846 278670792 127295004 272476420 252241655 137465209 302822497 411108433 64180102 580155550 308566412 204444535 491186552 373843004 542036115 591928479 527147005 40550374 319783799 992583593 174310544 173570545 773048160 175287850 66733505 788955480 335768499 307961543 460562389 930010168 852652628 287736308 324791702 418435872 908016377 54777708 724864645 564973173 417446897 172577931 406521538 400603503 332220325 877632544 300341209 732828520 983270904 267137864 970756111 455851666 194629453 900135139 221308171 516471093 546912222 281938623 473220718 466583588 130772179 195667122 101070129 847727648 146103694 234259423 151199414 155613820 109534518 8076759 930314113 413246332 465489176 483661980 669179910 564118655 100 827114601 357770932 688566190 941384689 60818772 116871990 550339501 973987598 887502490 290470752 209398815 245126585 221525976 168682675 52630571 934227497 475417213 315639492 935453315 850601591 115666243 582122203 435382044 478100675 94710909 665409606 825688533 734165536 767629894 798058779 598540578 347524835 910645678 848438491 456904469 648805943 365703875 303785974 201402940 787315901 178913346 904726816 675795589 104761371 653593813 678147976 585809858 966416148 413154712 911177766 822055499 561047168 756203528 25278785 354914121 637970956 241449512 237228526 796096163 956753303 156478667 733120535 801026511 763079035 436413295 876453655 986399393 945758278 395759854 672174236 723846294 251882530 525593292 434093302 162957239 316236859 911647048 991523317 785288146 887698237 537880196 212806975 865101837 152442052 665724099 968051710 941432098 204409884 891579727 927189274 125081861 424012339 740665164 624757429 360988805 884143395 982730808 590120159 863004288 558882744 100 799434834 973887995 8682841 789794776 774009835 192513316 741138405 895841557 919547801 323830242 724599707 851545444 183053541 535301834 777033991 447852044 516670459 473432657 154261553 351686321 482200014 128083212 755403417 857564628 753968410 725452684 54876810 616770035 274027304 778797951 520758639 379034931 923404199 245458339 112312708 997344267 435826057 851024049 56059050 395011324 948719579 17444567 732241305 643510851 633674540 338867926 342938903 101630610 299550655 702069184 55341544 954537640 525163509 848664703 848146714 387401898 168736329 716181645 616537321 22647793 741011896 619333612 995014868 284523621 378030180 218520058 602371394 765506890 895076183 363992632 460255050 606329687 976924933 83443019 428600255 883849938 274216086 56334382 364594874 78951835 799730235 563804556 879381713 99369178 302111420 805079903 337903983 383978672 243320868 944441647 807128008 738683127 590750904 615752409 36594039 98575491 134435162 986901624 662104057 929347175 100 555203272 427351605 132537067 811716046 331306443 85229533 919143388 942285389 998407800 735962500 320013025 450745352 311678480 587064631 404495309 218806823 424949693 778489353 287698853 108831918 63678334 882958000 548187617 782364217 650998587 815741531 540807829 857685153 620911751 10413082 806645161 921051940 486578258 743453451 898079589 948598342 400476196 333816374 717368462 33087006 589506385 845216975 346113850 145501161 159658889 140403819 397870760 74207946 110474616 377273521 189449208 299253971 904592243 764742715 499388585 643301095 713725728 337104043 811933300 887162996 935668269 982074608 432891992 393449234 419672383 111404558 971770349 630937947 588601784 299383183 288499599 252573895 50340379 666568043 411446851 609481175 867297570 76151111 331558430 452550817 598456454 391532246 260531484 722371928 925239072 332210305 324241900 28044457 472542355 556051953 733712820 644325431 335623294 607513944 68101828 906390554 893382838 708889605 892159262 582370903