5 49 1000000000
6 6 6 9 6
177810759 579834911 509948357 278301275 548105657 482883154 563331773 637296567 810309096 164214948 992462170 749797878 479523225 406128142 492764342 762606919 388145265 612552210 43602447 121128457 256118979 597805569 539566623 163303425 848100196 309923222 94611176 77799835 951911399 660429701 878419324 523336511 662660384 882432337 594369507 456014632 706897967 88909826 958478255 961532088 791189767 953071119 788694624 139155646 209477043 682659623 563921194 334325932 193601598