Wow, those are some big numbers! My very wimpy C++ BigNumber class times out for test cases with alphabets of size around 500.

For example, answer for

370 1

113

is the number (more than 750 digits)

1129486192863670815372730620783152644645169 1442473318546501048909340350384155216314327 4388928275082280890440415255439241910001546 2010749396855372214202134439383005223993275 8536596323384816629416049833306137266457487 4322049800510021109373025249471015248831329 7130400883899674846529159641866613001987231 7911193788754442584927477720429127563216884 6008787920431360644080198580955955254473662 7756954418383722891987501053820677434636345 5978890805684775481410610470681630942556410 6409125700551210297628302316146986808029677 2380837979049654271185843505158957683435991 5743631040336861132082488759019517356369043 6639985261394938004139680810790315701841724 9032123262350144516972365274229892284882967 6141813989374499877422091577973968474227765

01855821264609860903760