222 2
675579943 421172675 731131178 793244367 813109620 279819541 32406209 988451081 785275109 436147027 560194212 358356745 868678737 367739318 99751846 289751867 711442548 704298313 580569402 721032501 725840323 185720744 333238760 20968255 757778437 767800268 905842660 431679986 739839993 7418274 741425401 845963402 372089682 682278194 349572817 492145699 423903528 49041571 103697091 24881190 33013025 675698515 309580960 14519173 415036919 500265830 886967357 188650245 974053033 587079002 13276139 637473488 104817218 255006449 91872875 777769855 37061388 963523205 832830866 963516102 813498643 208640938 415614163 504235069 912473875 290641929 637394635 619604822 95567060 848375444 114185736 170685898 956125051 284376172 835092877 588090680 291935855 52808332 517638516 995887928 721523443 600848328 762444154 874752054 792765230 864364614 651888014 362679785 110952173 569603636 683489938 861919129 7918006 866184883 62328935 964112897 255487428 416391361 219976945 883007070 499479238 956560035 479115143 639349259 486915321 215148576 347549181 831321965 214604779 525372148 436129008 777898336 398043116 552791699 325866491 933923752 462311146 972600596 808323851 435872215 986163430 605613294 472053385 159245873 796144142 212748190 654104211 2008372 817386826 334579732 306870998 873113122 707103765 331959184 868919045 487815619 829931495 626564416 600543015 72766523 748364725 88298968 810520717 476660038 191238555 80662418 861586286 977865442 903869989 415871347 966179890 522658630 78909882 832445722 235916043 358535042 725257138 186531603 386667318 345987786 924144159 40634318 232967079 908409749 990096842 986582895 922944373 879772597 899751813 243767296 230354951 849852274 701115928 658801579 515283034 9557362 582657905 261919312 614677442 523790969 356805316 823748368 421168607 268680718 868439995 568446002 776155335 452881278 108160950 598784578 173543806 173208492 309585651 663114159 208977836 260540107 464682352 636931562 143782601 13153154 886921551 942494193 143798630 124359956 693750109 75122761 484315332 170693307 574850152 248096110 225389628 84218400 761550584 686561446 706972702 334813353 607407797 843680462 478489020 291234582 628440115 514562027
363799170 463454158 57128412 979227344 528903359 648608597 407065626 407063083 81863713 889756115 904651125 415410816 252118355 613600664 129090437 215448039 801313796 938420940 449768267 459211741 414462306 347172161 499077029 595664941 107466141 510800918 968009472 839207927 43207912 102864085 178863483 141842746 826135609 265132556 848195574 681159038 785995279 936686798 368667151 36671231 203489246 29416679 972995382 818451190 162902380 905452690 678681226 870916265 373382138 878781636 157754055 564313458 304112891 988410330 721692245 336933154 84726055 948598544 531450892 77720505 689310851 771449189 999531595 549944624 705012432 983688900 336504477 61779733 260399944 749929567 746399318 382830386 336052193 300915594 142872764 107578640 806806068 86939691 878375648 135635069 805105503 407790492 363914508 449485710 26730638 151923796 280806554 711127559 881353957 121975199 551054316 333502749 441625928 477475649 341849048 440965897 761943161 863105924 811629636 325346191 491700786 108114045 948209861 583433209 210559718 414015345 954544802 453112659 771532125 418543405 306722386 384243367 442140147 213928123 509374598 18479257 816342781 72894044 102007500 528268473 814919045 446498430 839635177 759581930 83836188 845256476 971851163 950873625 66626733 993599048 727082763 485068907 141843848 248533643 774112650 295933585 731915118 50663052 301103266 730126426 742209006 543420180 223662443 184838577 627361237 420532143 269453798 32201412 847882375 637812506 825586577 879391448 327188888 220643306 317886323 942424072 260507474 478616509 445730562 379244690 217564554 700644197 993995870 659836470 949050718 922227094 112895716 686390303 282270685 918517797 748298458 687083043 576528618 62701626 481574666 49405703 79046510 964452685 363047922 999223668 906899433 806261419 899332978 342149482 333128145 226342790 324585166 530577944 499184350 89703963 273644359 154410168 534843303 268242245 427113906 499864111 295290893 166701808 651811709 222632074 456668422 395768657 133740499 769231821 101203395 363625692 285569620 435998760 877711112 660080278 178393876 12449880 726063237 976940024 611115495 869066224 207134572 266460846 891687691 217214809 168612866 424539211