#!/bin/python3

import sys

def no(dp,s,i,j):
    if i==j:
        return dp[i][j]
    elif dp[i][j]!=1:
        return dp[i][j]
    else:
        n=len(s)
        dp=[[0 for i in range(n)] for j in range(n)]
        if i==j:
            dp[i][j]=1
            return dp[i][j]
        else:
            dp[i][j]=(2+no(dp,s,i+1,j-1))%(10**9+7) if s[i]!=s[j] else (3+no(dp,s,i+1,j-1))%(10**9+7)
            return dp[i][j]

    
n,q = input().strip().split(' ')
n,q = [int(n),int(q)]
s = input().strip()
dp=[[1 for i in range(len(s))] for j in range(len(s))]
for a0 in range(q):
    # your code goes here
    t=[int(s) for s in input().strip()]
    if t[0]==2:
        print(no(dp,s,i,j))