问题描述小媛有一台打字机，只能打出“A”、“B”、“C”三个字符。一天，小元打出一个长度为N的字符串1，然后发现可以通过打字机的快捷操作快速改写这个字符串。众所周知，一个快捷操作必须同时在不同位置改写K个字符，并且改写的字符必须换成打字机可以打出的其他字符。例如，当K=2时，“AB”可以改写为“CA”或“BC”，但不能改写为“AA”（恰好要改写K个字符）或“EF”。请问有多少种方法可以通过M快捷操作将字符串1重写为目标字符串2？输出方案号对1000000007取模的结果。时间限制：C/C++1秒，其他语言2秒空间限制：C/C++32M，其他语言64M输入说明第一行输入三个整数，N,M,K。下一个两行输入原始字符串1和目标字符串2。1≤N≤1001≤M≤1000≤K≤N输出描述方案数模1000000007输入示例1323AAACCC输出示例11示例描述1onlyAAA->BBB->CCC一个方案输入示例2222AAAA输出示例24实例解释2AA->BB->AAAA->BC->AAAA->CB->AAAA->CC->AA4种方案的求解采用了动态规划的思想，其迭代公式如下：N,M,K=map(int,input().strip().split())s1=input()s2=input()ifK==0:ifs1==s2:print(1)print(0)else:b=[1]foriinrange(K):b.append(b[-1]*2)c=[[1]*(N+1)foriinrange(N+1)]foriinrange(1,N+1):forjinrange(1,min(i,K+1)):c[i][j]=c[i-1][j]+c[i-1][j-1]d=[[0]*(N+1)对于范围内的i(N+1)]对于范围内的p(N+1):对于范围内的i(max(0,K-N+p),min(p,K)+1):temp=b[i]*c[p][i]*c[N-p][K-i]forjinrange(K-i+1):if0<=p-i+j<=N:d[p][p-i+j]+=temp*c[K-i][j]ans=[0foriinrange(N+1)]same=sum(p==qforp,qinzip(s1,s2))ans[N]=1foriinrange(M):t=[]forjinrange(N+1):tt=0forpin范围(N+1):tt+=ans[p]*d[j][p]t.append(tt%1000000007)ans=tprint(ans[same])
