986 975
623296998 706309230 892697907 715589576 937406855 887708050 309507082 306167029 807805285 484947519 669469281 899958215 985118689 912692356 320635410 51567178 333204890 550149337 80198876 692973597 750216005 77028736 676396163 91593423 289834829 525340924 661856786 512032483 958805977 800174899 62545874 940801211 345353211 830838761 770776008 714492826 398694511 820889393 510387187 81993455 158982941 559921116 398296860 304375131 476891923 15533840 824910859 901221725 607283818 577665807 165909595 518441401 101189016 957397814 883958296 303463199 557817673 211079232 777554049 951839880 489108313 919924791 608833888 681760719 214000815 30985332 24224609 541628219 686961577 19012891 933194543 70608110 418622419 36929392 993996884 581845573 579663303 69492170 402140948 906392721 218725154 970118485 249317856 591223469 221984125 275629752 195752068 105189198 261019974 852323667 981557595 440070968 366560878 683779697 807104209 673416686 994523164 369752208 682865661 282839340 292025400 746159812 852261804 712895820 537386053 917059631 628181942 184736965 432003754 370469696 84375106 72421006 470956741 234700915 598988760 489197203 375893383 414727627 490088609 831953184 145224187 643141897 566717600 115244294 727520599 344241741 139301475 6460002 451441053 413748530 440447224 837721861 870253355 912913656 902656807 731823380 873891640 656794728 64497454 291836993 722349746 269618604 512754421 37790076 785098127 124817252 409094184 156010156 657150424 550672936 518296217 692536884 403726404 993714785 710162005 596265781 845353059 497789363 995815843 64604730 684781529 29765395 499419745 767731048 845438192 209659851 119146930 512825435 274888790 555672471 649223123 998198953 837569608 949031074 932293740 223830528 883248248 460092752 270266289 786359439 669680854 714701502 471888032 645170988 489798962 613862098 80049058 350751352 725863344 452738664 400563427 219605999 608890027 772334797 747759086 772780225 123147685 505051514 326381058 510098376 177631745 169129988 585493285 796892171 345350974 200816718 319631666 974604668 894499519 211272229 195753504 761886927 122581596 121449475 749527877 299567210 384691539 6629962 710529427 756328168 342793475 956875082 224917851 573566388 913508827 998104178 310501082 803604131 240902502 458890601 941452542 880454921 675767186 89130601 977700907 396308616 513777899 355894598 593932898 304879951 770213631 675989889 309969304 871741615 418059466 966852847 570112635 236896647 228694685 157186989 761305562 172815762 367658172 276856752 704955206 103328653 236556529 390362200 238469241 157301885 265607507 82265406 13807489 813060887 674536353 539736552 528236948 46038751 797274251 338520171 131835499 856987203 661256353 202771343 205894385 885838067 382139323 933287915 734799084 49776206 356124534 740048049 815034329 654790229 705836655 768951262 671421193 638497102 40057434 574385642 693884793 408466581 971737346 173695104 431927365 548728543 344047454 511267875 667623803 542808801 816850625 107756776 471316852 983495706 364294029 198433221 821913552 310874318 560864285 508547481 717493223 655937466 967957417 305570142 61206786 199611344 382658045 46810367 737094778 816781977 386031618 598046590 379604144 745999665 33515257 684050009 224144227 618657864 170242348 980741734 10064310 962909927 659397408 513046921 704497743 384652922 938891299 336980380 85816557 291920325 246477742 544682759 273013262 735340333 810502505 624348581 391399797 422817942 552348576 316947183 319002852 177767501 583093569 460823838 96522330 905324072 953550227 552172857 233329036 963356239 26645436 376548888 988640746 960910488 777655990 123192845 242632106 427807528 449634047 189186054 907740195 158283786 96123006 331299285 737448129 366187281 896038003 737384095 361839181 184082995 459293542 297416518 609128134 156046557 365250920 989364089 32157505 577494304 200299262 702796025 570002699 369413735 534339587 106080864 685589331 489044939 238731018 725986082 363918159 601785246 808717144 979653288 522881269 540431696 269494228 305106980 475584137 560961847 138689539 882802626 336182588 447259866 811299376 651176733 215913849 125156504 620168368 67556133 746435002 195199572 801794577 925355991 470212398 578136542 163909557 892141260 222368081 754772519 269980876 289017318 717350803 207317910 668116310 519964388 747231409 325676597 31607923 914736855 943413748 504538283 167759752 95829760 534046111 234359313 301720041 239771277 602476227 857427359 719955920 380564706 268858103 869442616 948364483 350011434 454094293 318966526 199310692 264319464 589746974 200521686 645049916 640785792 196062494 39323849 458924508 20260519 205768852 376964894 915137401 718245563 864283369 388771300 238482252 888773718 463384832 738132659 59096147 739769245 996615906 450857645 809504480 931333506 951778725 606991234 515182234 259083891 969792255 55584798 899185545 818705707 780256150 774547271 499942290 896285032 585206991 499428420 440173462 79465322 24210695 596255704 326095404 902847752 825978526 308675579 834977059 76366968 258134647 463946941 712453466 882254195 561033545 55645198 928271637 142438382 851461897 582102658 336106128 504425543 140309489 764865329 835102895 340376761 85460799 998205770 949616592 675970234 286639857 783986476 512404682 903960519 639723161 978298513 976618587 391792848 877993289 917701945 352562173 915969453 497638675 41856976 970975680 452375584 982287434 42791065 598010918 907952708 734843802 70624038 692827814 233959735 36657247 312092514 955527827 559650087 493278460 182428620 85823416 308598696 330869553 153289378 654518971 707459488 247162322 832621093 704052937 78551026 740033735 475321942 643849208 550963470 12415103 793424158 703807996 903965913 566545057 444133980 720911526 977008437 270109182 26001831 508111911 416344215 452364873 599540018 111391439 552365735 912269758 80952018 130218334 104342362 222161019 950141198 397478317 822763628 392271847 890358339 790804623 166044279 305188972 521781783 524292550 432447721 519698312 347739226 269923456 313673733 208945712 468909678 374465227 880261650 695199675 440539384 415344727 828612427 110927756 889737416 189722530 202144874 17109318 960848251 292974094 473480459 735838412 4749471 724613469 583614928 538207752 564995388 749761017 349162442 217186210 846350662 172287569 878468486 88680210 67467634 627793508 440409486 284468561 233874915 142036014 857473203 908444115 676235166 506375378 367744892 616520008 236953588 487952176 103857547 426260822 365728287 671997458 443269089 806271260 147293202 285714006 904067565 765606166 685637481 923965929 965343914 657639217 837552739 60825694 716316160 46912351 183062363 337596290 349922164 160655607 77333380 474581291 288888463 956824608 255044768 644177355 480260330 902962983 901799116 670247942 645948423 882059962 559290611 488407491 400168854 179310520 29698208 713444324 731728565 240668697 427915747 651540368 784325496 136248241 880865107 180100694 524360982 772328338 648010936 424936607 994388076 700571094 672417467 397317979 858738890 888074473 761115522 911109837 61533595 974662240 435920334 615714183 836903038 718471084 676553154 437081302 230922417 406816108 601897477 8020936 16114224 70082200 914178500 170733802 855294405 666998466 696540114 352793890 750675093 663351048 333286882 634078362 560860384 119807638 330697971 664590282 28363767 524879581 980967190 434037745 41417843 80081297 47629760 159237797 733880714 952007113 865392911 158742080 332178431 371399533 494562712 407471947 70749995 661340405 223388805 876617367 244780317 504782675 953059801 126724520 479052980 477269572 240671725 948899859 935497399 577869200 956810451 889398207 671466094 438681126 711978152 126483528 433385853 317354438 585946533 841373591 399616173 284764722 44777536 838924434 38542458 117965500 354636014 567271252 702842536 25663925 496797378 616634375 802854463 938712805 856531862 422145570 957005442 457485836 266742497 149481683 700502014 428881397 368872019 28989349 230884764 840133895 819227025 891282146 151285780 28341415 889518931 215703605 331301275 192182859 126591911 704414859 840223386 942668251 590451849 550962118 337584174 768489217 550553239 439821241 587631372 175489682 179802536 234491754 74684887 707757762 471994957 968460997 933396511 937224705 676619810 550526139 722818382 981888508 79885683 882709216 141894003 810902068 322110822 545162370 976084561 867409061 913921512 841878209 488019646 448817650 747548283 978058192 365254656 284613659 218876814 700484157 815952206 760341125 271237415 953870112 753635386 693886671 549832143 420449530 264264595 981071558 726007837 381936148 824313044 151034650 836678661 74450514 695700012 926843383 57235762 97522195 809796422 766276979 983456043 910172923 698350716 162391693 873799219 840031378 30613136 811574036 465542037 504565231 176096625 80211785 770106122 793311932 804414201 692708094 573600904 909018330 442495313 207632436 915129426 187364152 308392763 846599740 943626417 817155301 422379218 659404588 946373341 921227723 952115468 416519767 366264711 141369112 107972276 572717805 441830299 242663219 205554132 145389525 678566951 881100457 241308913 55596411 313698960 855877174 123040019 861664060 678046950 74586198 619572009 326091758 374959814 177153330 847225943 415542090 233583011 517440893 337326208 546849273 475521518 129953934 90137739 570193444 609846210 687665532 421660190 871236082 176286882 376577655 716083219 988336920 436377864 619848711 900236947 834262032 521371432 907114052 944027305 891050780 87970879 247881287 319865332 395860413 549471485 886207419 224594444 40198445 655086315 566493900 114187627 262101737 180875604 220128940 105182346 647795369 620424272 360932411 697353001 213290156 209623771 577199727 732759848 872768608 15188922 196589579 630924595 7103486 560704064 178952879 745238409
898202653 338400199 698691055 115614800 816753779 981626417 732152233 875763075 711259028 808785666 771554941 482842045 880055479 223690484 635037063 611004566 757294768 311952803 775780745 101799462 62622177 578623927 735871431 589715323 199775235 26174903 705274220 578496920 597334753 927236081 488993438 709104771 199411875 970448373 857055436 41052041 511611005 516597468 719611349 831546413 753855107 892646849 574487740 176033710 322038973 178720441 96571674 538415077 234693981 753236742 489181352 806325983 718391842 272771951 575439163 506635212 779813685 532870452 796120163 525848578 959179035 638101979 970430352 894560324 460763536 258267041 728540002 517376101 849163159 941122905 893954879 65484695 178929453 762886092 519479378 291346340 924524074 373342134 70905657 534310830 891176518 719403218 108905795 292108412 255530392 703405818 377312651 943951641 72766429 830570314 643895046 545465380 571009509 246591067 350927381 46069673 763025161 229730199 189738293 959566239 686989328 8149179 911098405 55243236 704383386 385047831 824935862 695097802 538896854 292168127 894449032 67356475 252916848 378995681 55520524 996553481 649950866 102233434 194048666 526134730 166425446 197393737 854074948 632816584 557144965 111083311 15637644 597644943 867209728 645362051 908697967 362305950 713061570 455760823 430052992 899569221 498746196 334117739 284012707 712930364 694915093 963803747 428461319 482931708 750905327 143719608 79863250 351510896 805411199 764026198 942241925 877586083 260491869 809542538 167822124 864027832 333568104 370597767 728037834 625522918 700900785 881653852 53706779 375268104 393375705 15106227 602064152 683255050 444973455 286232367 973123781 690188035 423908633 265176485 262785551 416238208 862505991 17123210 301943071 303429664 632282949 268980877 164557771 663643804 971331091 889194932 733704002 195246971 163408936 135059840 198480477 985062688 823781221 286407581 569585856 673850075 344329754 769702430 35958105 436256055 115202010 307520224 843548160 911490445 362825893 298651457 781869162 989276251 210358919 29944408 2351533 86915945 753589036 235751412 165723881 350973960 760617761 369565353 393508347 916749458 382299333 993956785 122196610 73064694 830715735 955567714 995763900 786969298 714210665 513858914 845507308 805829126 867729564 222379828 643516656 265789093 134682314 496526956 48158517 813342726 251370672 981271168 957492522 91412451 855900222 92229794 186306658 446547221 909708129 95921034 743320589 650533400 44492354 133108389 665965141 949297794 697626245 58117293 753529874 547197331 852242101 185132232 577413652 255259574 364297448 111746700 601569289 535596316 16754066 200527973 290990732 72955895 633662489 507304283 889014680 930869273 986094205 264080279 70300376 610671578 360228991 463604359 236876970 109593505 904572112 131502164 364384763 245298487 3348119 3151289 503419358 464105718 35951977 300503392 304175648 417971039 317979574 483693089 648851460 62708438 262571302 393447137 160495137 974622214 40114528 783375638 470220211 720767601 437273049 690567184 643738231 863339355 104239198 297927921 447160291 571808539 9916116 957449576 802601225 19428847 401715575 803613877 44746327 5972843 909870635 458767302 400129532 894655985 443174123 153387901 538153563 256354482 773217419 198764562 623886263 103172794 386235890 653049869 730664455 208914825 701942857 133802941 240136845 724429415 911792643 912826689 591828884 72092134 40051988 647341599 88790759 162005828 646121816 749521329 644873693 728889044 947071117 281745238 482386261 718501217 759357078 897969010 50549286 242829838 328124466 439671289 694235065 989188358 456824870 65953129 441809616 790719963 910098782 192693352 443357627 551553595 16618497 743482601 402988587 331524134 53011924 856330379 735887498 592257295 155688832 870645312 971320476 18018261 933672249 351878391 410753389 66113698 894358070 98753667 236539180 176401036 802870342 873795822 488061973 550967499 224294352 767021068 149093162 473317788 271601258 19220723 903305408 336364878 306682010 908542670 170295756 833035603 549127122 628488260 776244921 424571509 659121291 35478577 34991526 947306097 256877120 896116100 381515198 81433575 239685371 71231455 389491064 1147209 731605145 40470467 284599520 276473218 79730446 909202751 118238924 83553052 816287785 498300572 703106704 3352968 476413157 352016278 104003495 769080370 467290286 429857554 570623180 804659908 107869766 527112479 581223637 203602979 99467756 813054579 909823138 376537271 826062400 437646614 483641585 287054801 687129060 425807545 588709304 937118703 697074446 618161361 664936718 423482626 128893203 960840944 99717015 27650475 608772855 844268504 12195767 183039318 530403750 433572209 899015578 269378615 941720286 170206532 592457987 725745367 408751651 306786670 717576509 670420450 979942985 477739731 197184736 394694634 590931972 115841290 820324836 741665828 97380107 425747389 973410277 924007511 603343152 481099550 682437570 214098947 13782670 332612117 593872943 428916323 955961103 981920458 519732698 768432081 212821226 950577537 512816365 76326284 791228762 142319350 828890209 990808454 203658464 646128884 430754951 673950726 364230661 273453584 528800288 12498114 859462291 781150770 43555974 286915751 487885641 743991479 274272269 11482270 399733292 696419275 112846689 256553667 656036999 77783449 580988849 588748197 789042242 955141179 572763174 624237275 659343194 81327660 490614024 96733533 30031773 389842782 988228506 292033784 444084642 399951500 108624053 179553640 947356334 145282903 58216474 162845429 282318628 885110147 555000924 749576684 170243152 39579935 620180235 289250165 132839666 860617006 726878448 461913715 603752954 52133526 864625140 279267869 332116254 699034120 744574469 640945166 628094541 567470436 924328820 24712536 657107622 643587221 993566570 158541762 74308593 729051202 76638010 477009429 32533696 82967171 807275838 314337757 567488331 172499604 244266718 86990811 115026849 1483315 400984441 8867736 943150747 926358059 441681112 708038840 272666220 863134999 425961499 519626352 101038198 652410527 250409787 851234397 679651821 461432962 601802789 442862502 755584748 944167016 811228662 432941899 258360141 583064095 928050360 566475505 710142607 306613587 276694217 994531681 520335102 285041707 229051101 836154030 600201556 880477037 689212401 651698211 544278074 195104962 158824477 895420764 640050890 904603753 973252205 80631622 240815107 834695814 826418758 453317285 960300072 71770277 663175549 679053863 504533426 57270967 523954622 18977804 348193745 906929980 878482156 213772324 600619258 869002009 404156221 549750065 785012831 631660997 767371415 984767986 541963533 435491382 486536010 585815360 943146090 972830218 442725173 926081464 268196337 956644823 130282459 74279455 146612650 567931962 961680331 670977857 855069885 445012526 686378606 738075106 76006451 8334678 598685175 551132836 171517634 761378905 345541657 777762995 201556016 423020695 290798968 123743443 32588957 435774737 358745663 521535140 298418493 403627575 552644753 817495313 849814143 377098653 803609515 12898216 286471751 380255029 314212274 746945162 61209924 775893520 303747930 101589447 436580726 800666313 4000042 851245978 263374804 604053134 702111531 381223537 593610124 743894365 608027775 894254965 715757059 996489337 662779553 532019093 216579820 477735653 116202699 566773365 531678356 823151700 729071221 184834041 921849938 89810311 415883049 524918570 446265244 617469265 190747899 161198129 840670736 142224190 978519172 128547002 746337149 855055005 402894753 331086699 49843146 84685364 191847228 360325214 492295475 608275980 460332702 632404910 646639071 501985550 245698538 431995921 691826753 458068822 164293180 10043391 853646155 621445965 653591319 276327532 916451506 98276356 456319276 933628190 895162748 522891074 295639049 844612492 715641859 507291794 36111324 450225667 722475249 68069610 347595933 39180384 132207967 739686425 484081893 752353826 144172897 405351854 344218155 186282089 778078909 165968715 616361888 443395717 574142259 566167858 624413464 178686622 227248517 141332342 416855078 116235683 325438874 53633559 106563803 217282409 323386054 358663208 524623159 779850604 522972409 239321606 578541081 517257459 706016347 611975935 44289976 552696053 239267761 801117238 868430206 935872380 488761887 140663861 38594147 78287032 511541861 279903572 876279774 238009223 59349044 67144137 677338397 485545972 286779040 576265471 731565976 697243090 346899810 147281870 963114587 374983607 740405966 351091667 659401103 464418521 28540027 586311733 666069960 550949917 938505950 915974150 76431895 244499982 383280317 216856488 198283813 784915281 474858252 136661345 750733791 72760430 458432113 585675150 269525780 103512108 545513118 342523654 100396497 387964467 583083481 486450822 447015865 280654782 181343052 488254619 892679573 547926937 364873241 430783131 953551636 177178043 759712091 388748408 692797173 365494353 390552414 303814568 513267159 676627727 586629584 867864193 114978282 887171279 893426554 654040316 107485533 212423391 554152487 976947234 225862121 54204475 878201677 898415284 192344956 870126765 911532315 770590840 604259220 271914432 916741562 721161448 89986624 973111839 379003026 939537890 326820386 67459150 345965185 135593394 749894513 612498023 989430668 857246090 873226605 335176540 899868595 84704362 266388955 287154490 529934575 457488132 530931219 987450851 132100838 824587075 262381138 471986259 867601469 855468165 666309507 399156165 544296436 566789691 753877036 784419634 748430552 279238644 225554434 570209732 915724123 728796969 562764814