这道题显然是一道 dp。转移方程式也很好推，我们记 \(f_{i,j}\) 为前 \(i\) 位且第 \(i\) 位为 \(j\) 的 DNA 序列数量。而对于输入的字符串，我们用 \(vis_{i,j}=0\) 表示第 \(i\) 个字母后面不能放第 \(j\) 个字母。那么转移方程式即为：
\[f_{i,j}= \sum \limits_{k=1}^{m}{f_{i-1,k} \times vis_{k,j}}
\]
但是一看 \(n\) 的范围 \(10^{15}\)，那这样的话我们就要考虑用矩阵加速来优化转移。把上面提到的 \(vis\) 写成一个矩阵，而对于 \(f\) 我们将 \(f_{1,i}\) 初始化好再进行矩阵快速幂转移，这样转移次数是 \(n-1\) 次。即：
\[ans=f \times vis^{n-1}
\]
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 55
const int mod=1e9+7;
inline int read(){
int f=1,w=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
w=(w<<1)+(w<<3)+(c^48);
c=getchar();
}
return f*w;
}
int n,m,k;
bool vis[65][65];
struct matrix{
int a[65][65];
matrix operator *(const matrix &x)const{
matrix ans;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
ans.a[i][j]=0;
for(int k=1;k<=N;k++){
ans.a[i][j]=(ans.a[i][j]+a[i][k]*x.a[k][j]%mod)%mod;
}
}
}
return ans;
}
}base;
int trans(char c){
if(c>='a'&&c<='z'){
return c-'a'+1;
}else{
return c-'A'+27;
}
}
matrix f;
void quickpow(matrix base,int p,matrix &res){
while(p){
if(p&1) res=res*base;
p>>=1;
base=base*base;
}
}
matrix ans;
void init(){
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
base.a[i][j]=1;
}
}
for(int i=1;i<=N;i++){
ans.a[i][i]=1;
}
for(int i=1;i<=m;i++){
f.a[1][i]=1;
}
}
signed main(){
n=read();
m=read();
k=read();
init();
for(int i=1;i<=k;i++){
string s;
cin>>s;
int x,y;
x=trans(s[0]),y=trans(s[1]);
// vis[x][y]=1;
base.a[x][y]=0;
}
quickpow(base,n-1,ans);
f=f*ans;
int res=0;
for(int i=1;i<=m;i++){
(res+=f.a[1][i])%=mod;
}
cout<<res<<endl;
return 0;
}