其实只要考虑长度为 2 的子串不能出现就好了

设 f[i][j] 表示考虑前 i 个字符，第 i 个字符即末位为 j 时的方案数

$f[i][j]=\sum\limits_{k=0}^{25}$f[i-1][k]·b[k][j]

其中 b[k][j] 表示 kj 这个子串能否出现

答案 ans = $\sum\limits_{j=0}^{25}f[n][j]$

非常简单的递推式，但发现 n 高达 $10^{15}$，不难想到矩阵快速幂加速运算