#include <stdio.h>

const int N = 1e6 + 10;
int k,m;
long long  ans, t = 0, n = 0;

void quickPower(long long a, long long b) {
    ans = 1;
       while(b--)
    {
       ans = ans*a%10000000;//小心越界！！一定要取模
       
    }
    // 将ans的每一位存入数组u中
    int u[9];
    int j = 0;
    while (ans) {
        u[++j] = ans % 10;
        ans /= 10;
    }
    
    for(int i = 7;i >= 1;i--)
    {
        if(i > j)u[i] = 0;//位数不够则赋值为0
        printf("%d",u[i]);
    }//输出密码
}


int main() {
    
   scanf("%d %d", &k, &m);
    char b[N], p[N];
    scanf("%s", b + 1);
    scanf("%s", p+1);
    
    for (int i = 1; i <= m; i++) {
        t = (t * 10 + p[i] - '0') % 10000000;//转换为数字
    }
    
        n = 0;
    
     for (int i = 1; i <= k-m+1; i++) {
           int j = 1;
           int h = i;
           while (j <= m && b[i] == p[j]) {
              j++;
              i++;
           }
           if (j == m + 1) {
              n++;
           }
           i = h;
       }
    
   quickPower(t, n);  // 计算t的n次方

    return 0;
}
```
`