#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
typedef unsigned long long int uLL;
inline int _Int() { int x; scanf("%d",&x); return x; }
LL bigMod(LL A,LL P,int M){ LL R=1; for(A%=M; P; P>>=1) { if(P&1) R=(R*A)%M; A=(A*A)%M; } return R; } /** (A^P) % M **/
LL bigMul(LL A,LL B,LL M) { LL R=0; for(A%=M; B; B>>=1) { if(B&1) R=(R+A)%M; A=(A+A)%M; } return R; } /** (A*B) % M **/
LL negMod(LL A,LL B) { return ( ( ( A % B ) + B) % B ); } /** (A % B) when A is negative or positive **/
LL invMod(LL A,LL M) { return bigMod( A , M-2, M ); } /** (A^(-1)) % M */
uLL _pow(uLL A,int P) { uLL R=1; for(; P; P>>=1) { if(P&1) R=(R*A); A=(A*A); } return R; } /** (A^P) **/
template<class T>T GCD(T x, T y) { while(x) x^=y^=x^=y%=x; return y; } /** Greatest Common Divisor( a , b ) **/
template<class T> bool inRng( T u, T v, T x ) { return u<=x && x<=v; } /** check ( u <= x <=v ) */
#define myMemset(a,b) memset(a,b,sizeof(a))
#define pi            acos(-1)
#define pb            push_back
#define myDebug(x)    cout<<#x<<" : "<<x<<"\n"
/*************************************************************************************************************************
**                                            Syed Zafrul Lipu (ShockProof)                                              *
**                                            CSE, University of Asia Pacific                                            *
**************************************************************************************************************************/

const int MOD = 1000000000+7;

char s[1000];

LL dp[500 + 3][500 + 3];

LL goo(int i, int j) {
    if( i>=j ) return (i==j);
    if(dp[i][j]!=-1) return dp[i][j];
    if( s[i] != s[j] ) {
        dp[i][j] = goo( i+1,j ) + goo( i,j-1 ) - goo( i+1,j-1 );
        return negMod( dp[i][j] , MOD );
    }
    dp[i][j] = goo( i+1,j ) + goo( i,j-1 ) + 1;
    return dp[i][j] %= MOD;
}

void Main()
{
    memset(dp,-1,sizeof(dp));
    int n = _Int();
    int q = _Int();
    scanf("%s",s);
    while( q-- ) {
        _Int();
        int u = _Int();
        int v = _Int();
        printf("%lld\n", goo(u,v) );
    }
}

int main()
{
    Main();
    return 0;
}