553 2
742028094 668883587 952056581 789330324 640213064 645311785 114169544 645960787 474988946 708992635 329171109 219537390 456641548 116700695 840865065 758742667 524590253 851936513 255985119 408181906 157130054 277123300 667883468 377527377 23644875 573144862 767269019 308455605 159890610 296706039 203825991 610700777 407148360 665433868 386883118 306237284 397018557 553616572 459682847 891685033 426063910 128265566 829935671 238912725 695489980 574703448 677351144 316815120 592543588 917366478 345089072 582603280 892169215 32258591 70950035 403737303 413066064 722664639 350160749 642663345 754110336 381946515 739593935 176154572 887664968 702956363 327235601 619132801 674742555 908806888 50567676 127679858 249107016 199306091 649631443 7763146 124481482 42638525 53416646 744787926 817198355 418166167 451458902 307229082 893044263 122483523 436396138 952659731 442751138 589736383 582274369 636111085 620957180 221179684 869514132 252304251 308306688 601016490 861666579 902436780 158966910 219365684 555121985 477280481 714065908 443031263 196972092 37182503 393803179 7696385 747826906 251545726 576958113 109104394 286506329 336142860 229769922 373732913 76329698 340660100 988672576 158581490 832501418 39440699 225524476 143167596 352830387 417602145 693440276 116093275 755034239 699727381 285423288 927159830 585443051 956281190 622765165 532077980 365913163 767317376 118364478 446386970 140840809 662828 581054391 413352963 997612969 653613270 183571960 791971409 330600857 629592131 429617807 340222253 430633935 817238078 628473373 217480648 747875530 18045633 24361324 922255704 985399191 255114494 757949557 284024990 865668867 313368470 423036628 36196632 653255573 929360822 296463044 680153739 638316649 688728118 785963871 280080584 819345299 46484485 433697199 97220203 45550460 24176184 915970740 357546590 981243731 417643868 889700351 306243376 23772179 430403086 181676706 638626801 884396816 980876169 340447404 943059170 584540696 826195422 195351673 303363188 636283071 987483525 618254642 933298098 289185572 549424755 120326906 300079759 121845813 713810104 89464177 484960973 959591156 217335536 782947733 937188880 414965923 517619919 709183950 498511202 139760751 358480428 118803697 441567941 143945076 309318393 543800144 273239410 726622529 172231877 781695690 377049512 526671702 397925850 541227934 237877375 37703839 288791132 318134726 379049690 790357968 816402885 368338200 442108637 797939116 368366554 544304340 65543443 553949362 670501300 735733366 779852170 16141870 719153144 769052944 16309729 810728518 649689286 468308324 153033578 737251007 403323450 753137277 697480924 168735882 280645631 423814263 684267078 617739539 179948146 377183715 655465100 934463583 469588642 483215370 555062564 553298395 588913296 582324079 799577133 805626003 462416074 928986477 725426658 977015926 93934377 717234051 679241031 731925506 179606481 507108352 383492952 785379912 356345877 424657530 455278317 555716305 12918779 683830986 335228317 177256478 952744568 886446196 599348067 668150541 341558779 782488239 635278431 955563448 916112702 645773992 145575461 353426124 595625016 408732360 771607541 51254475 889999272 45247379 842161756 741186231 822003395 490803616 205066683 41754481 959079385 548500889 654642833 406714102 557141486 595339065 48385016 93646268 820168436 915012289 950118558 35852439 636852265 324516009 542119972 493052004 564842115 990862139 28607209 825994843 691287698 760461369 94430784 342278094 333439956 293030509 815978427 655691915 818360498 323839642 794729595 192016728 162248246 847267439 472041318 816256893 982219800 147423294 998383998 992512103 860204172 489762403 902995916 332493367 604113425 200172203 349578666 442874038 423601971 790792404 799767426 462558638 533847423 453674902 392727185 292301389 961538395 109157567 470848669 601284509 621448778 392124586 232325851 648790579 997765949 628185587 49211187 950523394 359283217 469035216 352085401 785592843 105052927 628659416 767113002 800889452 199188434 632099647 927294674 949542144 830883615 255588159 583812912 791012865 724281467 118757190 884782695 29422899 942928044 882873866 779836512 19428126 589965129 101327355 595278226 996455524 159802379 203768384 698728166 275209727 414732380 388822943 754463907 155418903 98884964 85260705 273731011 651549765 535558235 878403905 383333010 178146787 604515602 361107553 352685790 230252341 280628392 220074659 128732398 131942002 957688362 83517269 56787356 801288167 782620108 369037670 360845943 353254496 475842981 745763430 127933666 485221925 951835529 138466330 800088175 551643717 363005538 907627870 569599165 837340612 303927420 816690076 163234776 332008073 576980674 792100225 322800317 11899628 859303947 890436917 152938049 538977163 688685475 538381454 149460182 140264420 80631898 233455092 782783497 297841242 922344292 286174582 513849515 531229798 222088606 289926348 964764271 772344276 571475264 987578886 181376604 228002140 311342923 167672299 239576840 751614812 171852171 123796297 686960212 560520677 806317074 377712417 2705187 261533248 286139016 242448625 689708316 787144537 115901729 894553546 846548889 574127237 72832107 679072222 543129821 482170712 393081856 518556498 2026581 84959687 302287492 253736435 223620711 225159458 923785495 260059271 476332111 131303303 698061910 326326742 147382706 213519404 714866760 677024649 233873295 934032887 587721934 441499827 186531402 304126779 656025783 514723641 388550331 730020416 555081059 631986900
55916601 909440718 45813114 763976595 457725362 444182743 284635760 593649353 101225839 232924754 115926523 540476402 882862649 630251905 395695979 977573460 232707819 880795770 558823509 498684019 700740717 161988521 852540855 8689553 821136719 33103870 941825569 131539138 423868633 508791647 407895411 417265231 203213451 241157672 45356897 325528633 25999464 437462155 162200086 415269433 506552659 889059905 221434803 792797787 628936933 562481090 803305407 806309773 109179523 730658352 671439684 782292354 103289799 931280272 504485699 784235289 210420290 314142160 658889486 932786815 444030896 726562268 351041324 418400884 381744022 530841387 101033332 875729614 775860942 563983153 166762807 843218706 350153782 458033976 601490543 331943284 555446210 612779718 623079407 64693990 969084813 978674340 70568860 440572710 461771083 935503325 420696429 845964017 778599856 817699228 352193531 439032971 994374791 780896335 605566832 984031526 67940217 952416079 627941933 621990027 203103539 766611525 624645940 771604475 367558397 439969775 874416436 604500026 906257091 27287154 5913374 208560525 798587939 605322201 660282926 622994508 161948645 365897356 554091274 214249657 69311950 252930768 957347437 330020318 721914943 562933247 382075177 354214260 168009407 23163725 439604278 267197833 460205014 243377843 978472348 847448035 688812568 468671022 131361083 71558340 422297054 192687247 362423494 601059615 190628263 394533534 985776444 989720242 905855316 813078216 336279581 390102098 550943718 260783165 810816783 964338436 147303480 608307036 156289237 941850970 196527840 314317895 276731999 306284704 551363383 625389662 501950073 36904607 639957179 973597431 89830033 341513988 40914034 166755735 229809338 548720750 204133354 889316044 548483299 879052457 326134015 24441004 6211339 563282394 894497519 420191604 797062673 874368498 778334422 595576073 179097795 165568175 232816353 776717585 73378600 867368551 589384182 491056941 543629783 377260739 672853501 873293791 618649467 320032453 967671208 943073557 450812496 182079011 137543175 744171102 342523902 575685586 726408142 875313927 120196252 94312367 897604753 631428947 943191196 46619662 402917537 704662160 112121499 872113652 897207357 298981011 869618307 954665437 940043093 745292312 282083502 946285405 361389279 546106888 49978590 222681083 827932309 558627368 161718527 19330791 247044640 396220041 816136004 725204575 189550849 175597422 960497756 80410337 704012307 434818585 530878572 916441927 31478359 982911061 206922119 288752172 825107132 757952636 568063144 24934628 411192333 913980833 735280303 689616604 332807809 245186222 959502138 184230127 782927590 776416907 70672134 487004228 168093640 966249611 919623058 615031859 638623416 139927155 35820372 85176772 802851060 93512783 518072281 457302956 348765898 107729204 836613768 295367312 440761335 787086082 729349561 172666788 804735176 241983358 832427947 127284639 765996639 72970463 975947829 233760734 545630011 297159696 237259437 620161947 748011264 215853578 789190193 965549621 276138860 507444477 179141476 792528385 840270325 682147910 620675545 451433210 772286667 803583929 171090095 74113490 548557676 580944438 780705270 197348152 757038935 25205910 294361709 489119788 525791276 193352385 813225723 72124957 357979988 531544308 881789675 67377120 744454119 55533113 648208531 409255041 367733187 484716744 157502959 226279449 61482691 152628093 394413799 283392350 455469233 444296985 513380538 682558387 381585036 61857884 859994481 364747418 994779976 491275719 955472144 798082701 823462587 999502772 410326724 880998244 5234436 14433228 563644276 251071604 126696614 994449399 893849875 306586103 310236035 284756727 715618355 198844925 819688166 755462429 683366418 931380623 80048135 50882363 361828171 374824104 441340861 151528398 710057923 723596644 148019460 38524313 98729506 844369318 487493994 419854293 942653020 525842334 80959689 311451799 234789535 769021667 746182715 53581618 627564926 860448623 471483808 857744376 193501605 558750203 252919869 547049205 190078580 972139342 538847808 386140175 244399412 505136598 819442876 639725252 493611162 638251359 593939351 519308718 789099407 552951857 936683528 201062973 152434371 670770471 334304506 409305843 163796447 977135252 871629 257734920 792935098 233390028 143714243 491076485 14942999 336098534 698835193 7349138 440302646 997496958 196157681 255322737 827222911 833007067 947912459 87676353 632518824 666954601 112331686 864797196 109688347 392323316 592330413 397490352 801531352 165793945 43576945 73957313 576973035 513709888 7009718 17494130 747192281 731475689 334614514 3362732 200944625 934583553 71805290 478430028 119720632 22653963 963616328 672682896 242252013 838749674 952327639 783531318 475266244 392600321 638641217 880571260 500554675 310123400 637428247 915187387 744799724 403835129 840880899 967784069 565944792 646208106 935733960 896623806 986276520 401983584 984493380 872555761 473976043 942081961 438493276 74753506 880703694 22975331 603057240 412260057 487338614 513634697 138585350 125955680 398753954 226283903 859744965 877183238 63940422 555433285 444248208 15421842 592981203 634298172 708911093 999814063 251441023 309330503 199851878 385636729 630308607 637543968 566200482 573208110 506544583 190655121 263911612 133256266 597920324 628937057 813663506 238516668 166385346 780526242 124593528 600712672 31302560 306829868 335569104 889916215 380441041 647037847 300817829