给定一个字符串，你有一个未知的长度为的字符串，且，其中指的是最长公共子序列。
中的字符都必须是个大写字母之一。
现在你需要回答有多少满足题意的，对取模。
第一行一个字符串。
第二行一个正整数。
一个整数表示答案。
CAPCAK 1
896
CHMAUTTYYVIUEPFZSV 3
271916449
特殊性质：保证字典序不降
特殊性质：保证中只出现过至多种字符。