916 42488
993637510 832546481 388975689 512678153 28344283 907255092 972248910 662963168 717386527 588440965 272602903 887736706 953159224 359109833 714484674 983129617 337061475 26246774 157299821 442424322 676708309 52054136 209614168 971631543 697942573 307297479 741488050 254208692 939867939 898881271 659316528 217979335 425808242 510187625 442839827 880817118 85611533 689605586 530425942 386760782 665289333 133800839 685084881 782388049 38929649 799973718 273698607 882901508 630539122 212893433 71892668 261946030 577235447 92269450 802537473 991911676 865768954 195543209 22177089 502940365 370318129 862381645 702409995 368808718 1301695 648427420 213558081 107241110 115796873 305102776 656844165 146587762 814135382 828797080 142295669 266009421 199362508 124548182 999242132 742140870 884539383 229037018 52295481 656591245 664574072 237255918 328727750 584172819 763864817 809365742 115791034 381104890 26925881 584645994 394538240 892007307 564985814 306489575 786841613 707519425 492486326 417912357 407416199 9637387 27150755 728025106 609371885 229071255 291285388 228458599 748074845 424096333 418360540 331608095 65004567 948827094 38649651 470657302 809744597 312786392 317828304 41233410 305010234 344829947 49222469 197150581 102022102 90492463 879662145 416103039 360129641 845287520 233803376 2033322 32710413 275292889 720985552 303434690 132357775 923651697 891315513 781061367 611441955 340839382 930816310 295975802 113262038 476295211 493403272 377519425 400868525 964980884 190716458 759123466 741592438 377882745 463641986 611123422 716237083 682095628 469324779 200648878 691894665 594620320 762773634 15945719 346025837 29590261 597780385 217549746 2869928 661412780 843245152 61432371 849049735 800320458 309762837 554023936 941793630 108080848 54980529 145437244 923867481 396939817 973656712 432476045 792713080 442914285 495851608 907540829 169829751 529580932 355354672 740117793 955854262 572260678 287372595 61234610 682464208 443580105 540135794 355322237 306548730 454980842 595424220 594553542 114112791 288535018 434324234 513108995 475578411 912520142 70056539 493081420 549674284 156034144 596452914 523215111 645976380 38535956 942756828 291692242 872142279 267314285 762385309 675036183 759051480 562901175 698311118 524499278 899425899 900806102 489927324 557849760 671177695 302742784 48552268 93067838 129025889 54644782 97926215 710314969 940236266 140526353 55429998 481413288 690625621 977688965 280453715 777959461 835570223 837335976 568192704 943686271 201936819 812048841 657123278 730190041 427127823 530895471 765860163 883047671 220112368 445714170 698648212 270332283 873938496 122033835 597667932 767704395 645590540 48283244 42059348 514350086 418334985 83215147 352571135 713186086 929783984 766598546 389395219 425081071 883683968 583967238 114840597 209894121 65198337 842443318 181144814 35075108 434252147 960494563 774330754 674382225 636121961 33306184 960866256 462456249 620826585 851684742 744023454 898813621 55603834 943695154 6856976 230074363 517862782 896451232 204490465 539483077 140447711 957413925 135326040 228781192 308382214 470676197 680135058 312534911 561276794 324084734 434027646 336616212 670550641 216097533 999077726 940104674 156035106 500640456 772405357 684369937 86257808 931923630 314156422 293918851 707459388 283464517 502052022 681502954 171371850 478096569 589113033 796724037 508711243 429508770 887155943 682516537 385249229 275540817 919344027 121079349 494537717 243772186 599121427 232988631 525998447 602100105 885562129 796995730 946492058 17887742 680042971 86796587 742233310 572921398 410915646 340101773 164768434 323721344 997797169 776798109 832842976 575522663 659701828 921034145 584094431 527562645 111766224 295431654 769757342 352809784 154041101 588503850 677215675 305319342 290998027 744566440 129674926 825463015 932096499 12989454 226768360 639545560 795301826 856459382 952208933 594134020 723991670 324021156 43455093 871594738 227219898 714058382 567661630 474050762 774152727 519181995 914023610 899006195 817814091 1706469 638269566 994842340 119886341 749106458 39932604 882538300 892177325 499020228 847161684 206953021 63438422 198574429 421783247 620565078 215215387 611450663 327669478 244828711 799250514 764485976 635743945 670844811 120845415 442836115 585588863 37707596 571905709 9053683 762223873 847907482 131199499 617189902 301543584 909363876 814624341 665073960 944092293 700724212 600459044 47872615 88620712 996038180 723710732 970661169 70202780 922326199 668152918 719927046 414759837 553784442 468910291 658439262 388273458 335696829 38115591 211864445 114045189 142434064 493838216 20700947 138105407 86134539 557189942 369997302 349201718 358815677 118236031 623203064 232634043 223367950 679201840 568403737 592839671 254036074 750934724 277863780 709846685 862492564 620513566 331634112 459284699 666209325 648630387 955192987 4696093 800667336 698239344 352054758 730394239 712180932 700756323 750818238 161636359 366014088 943156492 88708367 906035381 940014248 24490740 587129329 202782514 490343189 284896035 64750198 910796656 258375877 190728801 913282119 770755792 839578597 360546527 606445764 224315359 116504141 539864122 566769199 519124880 220771026 552767572 554715815 781033482 261975901 261305588 396684687 638680806 434914788 434247245 251158711 64750667 296777972 559308983 647175804 375359502 53033315 69142253 875574113 645902173 709590667 26672208 829053804 996073196 357090006 983813439 28068306 925258631 497439587 499430306 675036123 351492650 629041991 763224212 70729425 748344139 773699007 371089909 763832001 581861677 149255209 854833678 73402782 431942656 216380098 550376463 910429484 562534491 284230651 22876946 492869279 104200633 626641385 716999993 112700877 211427527 484624220 32307498 146703485 954123343 533103601 414548809 31658858 102610037 783788785 838756828 428176207 452932888 750123753 496814513 91438849 819942891 489761227 907421913 928100945 68202031 122861647 686117527 816719996 697117787 361574337 435709892 960969138 715871510 309004107 816545022 70962073 373328532 457502665 801934314 703517688 463614620 679857744 942964666 178423336 42645334 857198999 140212748 940961471 49971395 911473016 361613592 671750009 102907826 669135487 733803755 564640961 840100127 918200143 456691979 467043683 49824230 737082598 263842333 160393045 936875549 475384436 231776073 447435264 557868394 198968794 352730174 228356425 675801550 712884608 585149868 180881265 526550993 300767910 122504469 153832993 657753496 802374240 983523887 645254401 745365121 416885306 905525794 957892765 151692528 623302177 456394302 971173991 440710326 760412792 495943925 146018172 594844020 37689251 98518924 729593750 246274383 375602542 143488512 32258896 220806870 624832646 614737987 66795635 195197825 511184664 303856271 605169135 64516512 578520249 650835481 525470746 367188495 194647789 585108781 911557385 808280259 344049248 640837176 552902090 639089155 234922072 226516626 321771427 476831095 709518648 377298365 671218248 33420787 678507239 333991199 356035929 497603916 141867607 258719394 34892646 44897842 657258776 672038423 828293779 25216024 886869691 318636824 809539304 866164773 984292241 227434333 41301463 665753758 858228901 36633610 920395812 790138969 395028434 4180978 626442947 739235386 910843935 407055105 467781379 452656791 397770713 485477460 465110771 944150726 448770695 18305592 483871029 132672675 617620255 140293861 424811288 548357538 685990065 717106047 407893527 644303044 472881349 776648659 124257498 393546536 602907739 115635985 196491005 78706754 887223817 419831825 547965400 207289516 831670934 157022033 540701015 295034214 777574792 862954686 291135752 861473999 72099232 428593098 887149868 706490026 53381815 782049698 985577164 858424203 734447613 628597881 613405419 742483563 596984102 885597675 493364227 488354147 709452671 41810809 515980445 962048398 677644938 465978188 384067263 149478211 574519928 421835392 370923785 853045927 887272869 250105899 791738585 450144277 116914595 207533188 98080008 862269434 959429015 473488307 555961856 952380665 204069305 120293734 661357313 520395726 731720598 69508073 539236981 473790510 753691420 980749268 252541551 850715144 502116240 112389413 938490169 318639006 346330715 297731989 26654261 290075814 425481998 446829602 219591182 502683242 724991382 993513986 548501968 104301355 450679105 918414174 711855462 803132040 493375703 905513522 73337325 173989134 406780682 35964727 622081119 600377147 353201433 580215904 839597809 946120192 725705785 383573675 281267823 612001646 535975884 134846196 561954652 35804170 822655406 563564818 364186076 323520562 196587800 17400143 388939644 849130447 496671473 674255261 701307431 685068978 598670774 256571714 377033188 898321526 497003952 522835593 835013863 645623538 527463870 184587535 985950456 104390173 685423560 707749388 766322675 371354664 7689473 937385180 439851015 399626884 255912237 269508094 446031373 974229195 792011959 31685501 923950448 416940352 223909233 332643437 39920654 280526128 142292787