1019
912964157 673729218 439937666 670103775 116837215 903835650 932881039 190270761 737704760 508289155 153189721 771206145 421383688 536522209 122998249 414589879 987486425 241824889 478250550 668036082 834526868 842683602 51095225 366820535 688102263 194123714 619710674 458769802 845092135 178379188 942172938 992720138 361849419 641010765 552647330 403711601 161107996 178438556 155889236 4306399 614801577 923073527 395266879 178211206 436494226 863078637 610541700 575942930 879687215 726841856 108924996 905743077 900654219 181092164 84829524 638184298 765594239 839209940 468276816 581296500 879133071 476870635 314448283 951975916 435208353 735219981 233549290 98053223 116076055 26342817 235236706 674226599 657469432 198352309 123717187 278609934 622075867 683395316 420545460 453629013 150524102 748383187 700211424 478092714 116892876 381836120 477667888 901703078 313342467 949294698 612475265 455132664 843836426 435414785 712273631 598627834 262427260 545267329 17423782 275575200 291888571 255415314 933624876 964044195 400112999 627765840 263806719 12019970 820602554 4555413 59364717 643012255 799988112 597713506 133411908 257887276 394599635 919662295 690354199 898604260 951209519 860175792 613624724 84749489 791423019 912258599 839703974 593005339 659150229 861044475 379588511 345280717 360516709 409781253 486208607 279935763 80869880 445697209 329663149 609462562 940296706 342326839 227288714 799249499 83604562 569763586 675950032 666878137 390360044 845710235 17388045 717237903 71329388 537268462 275182537 591184561 292138536 43900429 320501144 46156684 707390816 518440624 587048493 186924185 349586012 238524636 962651434 343571221 532847376 426330244 209867494 467930844 475159959 563823963 785821984 859863853 281370713 857931589 459484422 544107754 987984258 91142411 565601568 402635452 274624238 785715695 44532738 844219776 477106366 175604373 204913579 529325399 607874602 293955438 179025098 54843220 774972249 117369493 735700243 493212711 251944099 197575746 726458703 74096587 396483776 892475292 589512250 86748700 595248394 719895527 928809092 582495645 889938534 947123546 737386693 462888388 859588977 529471726 272432982 891009709 820789908 944226532 84665959 148157829 738847162 356245009 627438860 629116740 454248276 771206125 54778276 806713839 689641825 289208893 945425416 618758388 948274166 488084877 831498227 390793037 889242197 199694883 91070053 843391686 473020024 152797415 527448359 203947279 549108739 4758354 67283162 21259098 790314767 236536275 757657590 136663082 626591532 449552438 571297702 391330972 51412360 96294065 674367788 608939202 101625527 379250170 109246852 461485339 696914959 399325939 204373150 184319735 83968811 606973958 262165427 102195479 396862752 776382600 399292029 904368211 798650229 823082685 982579003 555640672 974904380 291053115 237642292 353596867 573610144 867329577 950128722 678850395 863016538 353495762 644845047 964746233 755445851 384263135 891638545 904097142 855081157 87873340 209016550 598292880 267660170 253389618 570413284 749266636 261336944 781099151 648197484 123771805 554017257 304950079 847298252 71914814 375156528 399495573 235352987 429334422 925494308 220919552 947758323 304965942 38403204 136832484 757068824 424028496 158094577 186680720 851988943 813000345 971579417 484489552 306959594 176062116 915956097 729341034 255675934 992158377 3061018 181618176 703202167 786947981 431028326 984801224 535523913 817173088 518034115 888930827 687434853 4348864 761577845 534111373 534587615 523621514 861883312 457426655 722685212 866632162 100669843 63903268 784243126 300496576 558706271 346946841 994454619 622927787 200233186 635684624 47756154 616680960 115310737 835991314 378059821 572435037 991302960 70017653 430510528 465888797 651694112 525326144 335409138 10387610 707799832 868649704 313856634 142031596 374127079 878924333 500890619 208146079 671001191 59140641 32971179 510360222 423887651 516000054 309398662 804609337 278020081 155518662 734208095 428068439 530488625 857408622 16242560 582045660 809650001 847895192 450554483 740204367 657536761 304570387 373276550 735537692 31532452 26066945 185483338 465885925 345339879 915891081 639183935 560400440 557891139 311461728 140523118 750047135 805503703 527907932 507774781 796329110 27889269 880881115 776994979 455661866 430933986 460133546 491776390 234098276 777354043 802363158 218425734 929665132 305058252 486467508 344757409 168043649 982237577 192307944 845649405 344603146 133556107 247828596 540468695 286684865 345809043 720603938 188286694 820374516 879719072 289366087 373743397 281218289 820876721 890214778 777053122 999125194 670607824 346839827 626870427 366801027 546713879 917496576 974642185 937439595 272959092 42303079 720020212 352325744 387452501 304431276 460593137 623918840 855834431 858191542 847160798 106432047 40531788 278981656 936434659 82866946 199682801 19051329 753362259 750674442 908830711 216059574 88440872 604395590 986775480 52527465 297875064 68883512 132984389 930190109 529403560 176298370 227539966 231599739 336341454 577992419 510728328 560980965 767464736 121183484 411376834 139793117 635849006 95598486 344492646 652939933 886140258 128213828 894426461 701990792 667040802 368574932 599785854 22493033 997251293 672390408 483887581 248303886 318890307 239307587 97350686 876932134 243561243 428276681 955796466 795731894 262635447 687108600 389833397 249844922 878764899 109664843 458757922 737435056 322400099 273760141 166024273 972610120 72041384 777950580 524777512 984094763 920220862 960014822 267612287 989501720 620642381 836913006 568487918 43861362 368295643 583956943 17286641 274046872 190781306 262828383 121661150 759770715 444458634 479810319 257738420 578660296 574838322 227799782 729807983 510182620 637948569 854522209 498687273 437748589 484338871 806061992 276906840 338435668 538159562 353933178 212177799 825977770 805950758 556701083 485021159 679590520 902009436 161603561 384032173 611924550 179011144 181087971 952577184 513730143 393742902 52709878 220948573 330793242 56571140 560242255 130787184 526809984 40736407 222847524 68744917 911142619 698029777 681499626 995171164 747919644 623143840 720154361 930492312 661580949 690156610 538866911 224758968 470353183 656141446 925589825 726340468 160200452 457960656 634695106 497455502 642159196 94712511 712534953 60962743 370575644 419765558 482691614 985846981 223213489 67264329 127773048 303710054 378661193 239648904 532519158 334182905 274475286 64955847 612290103 980873583 685090538 970124571 191446478 109950843 16634836 430796883 564562794 799383259 465129521 986790607 713028113 903286145 711111256 923658321 6172534 2535952 116066799 479924948 990887170 131135369 811304871 172369082 688186778 577741102 141950427 774204030 250335760 570445232 405364964 177385253 261902618 433377176 445059143 770426235 625234187 699211059 332438234 52472135 834327947 952837451 390606130 470234558 803152957 275175155 550367310 772492021 393735201 238073890 449587825 448365441 485320406 292853046 831577926 928502513 892415256 550944477 77857617 156965590 340199440 124028960 905798241 72845695 611940739 271716730 755210456 976532939 758160113 65450492 314198829 586149116 12953112 337566827 533354200 215428088 724960515 735185539 14262887 855317984 489634372 499903305 742570787 346096507 116302580 180376267 534637874 446221396 409396653 957376740 433878206 834995049 755182674 970759311 898625999 811406433 37477717 921818012 45382849 804081164 267034849 623127328 767181151 879183680 956961487 339554994 683069890 473720041 644867577 387244045 701988130 452403014 767674932 828297560 647428827 692107497 567073740 378871214 453201414 126651683 188840919 155897599 975175559 469962912 443484344 224227109 276588959 3625600 526277466 3661548 544606333 509435356 657479229 229048565 915869746 174848708 505145535 657293706 132059927 225244717 677966659 133838344 311657947 312223871 448079050 563139544 510641880 749705124 489473133 100314205 709094204 502327127 236269708 95606964 684050485 412494443 578802240 482032188 96156343 243520517 688637559 122451600 593089752 725263797 339769247 610697169 414898529 643529453 305762887 400861535 24053603 130997377 957844889 666164472 942389080 8001342 861476927 728885343 230846044 906173126 593808551 766793833 590713670 126835165 597307504 443691260 553117092 769355345 793498257 545520618 302549256 276205527 292870219 724151596 671117577 529366789 918624281 703125370 150900885 684327625 793996726 846616748 544052593 23724117 324673714 154889138 444106656 209463123 727819176 843387199 68754260 323642054 492076467 403422750 333512420 236433968 570100780 542978566 111778672 57306981 771131287 536457526 395868170 424023346 945162480 22625443 853807223 349560813 963503676 951952160 976336018 102075882 508731396 445108247 432350568 883103469 205878879 280028892 969665519 691752586 91283695 999062595 70988999 38511401 210709457 712929271 782701513 611347121 530561065 643348416 565944942 885145261 243613492 468065656 382779649 432510176 177583798 441951499 176712571 170370767 593131045 937310138 762442722 40258067 971393065 689888178 876863053 827971761 257864098 79154200 799768299 795362091 14508511 31245328 348769459 507412708 751128081 543512762 619297980 540761173 47446577 999613610 990093024 137735741 738487904 935025054 301952889 559472696 228975301 106128870 328457754 464363625 237913074 710075873 249822705 503207810 590653650 458820555 388885244 470705554 474897734 27015991 936351390 197753161 636259921 801883624 492497716 424904670 921471409 121132419 528574326 20375564 465786153 941320708 474710432 471404544 289383041 754716775 680460907 571597499 947619684 500858234 528065007 23371580 574271346 615029693 890189547 766241352 869863024 765557899 923954353 293861593 270215304 94549970 333789658 777173549 135871241 183367384 640421059 173864465 659410628 444181356 810263133 667864482 193470148 808884201 625107728 525408887 7542480 302684788 280032564 84276829 554184248 162823983 56640797 365121959 691170316 699841001 849109738 87163277 568052835 981746457 557171110 589368636