#P4258. 基因串
基因串
基因串
题目描述
基因串由 A、C、G、T 四种字符组成。已知基因串 ,其长度为 。对每个 ,求有多少个长度为 的基因串与 的最长公共子序列长度恰好为 。答案对 取模。
子序列保留字符原来的相对顺序,可以跳过字符。
输入格式
第一行一个非空基因串 。第二行一个正整数 。
输出格式
输出 行。第 行表示最长公共子序列长度恰为 的基因串数量对 取模的结果。
样例 #1
样例输入 #1
GTT
10
样例输出 #1
1024
116050
434050
497452