int count(string a, string b, int m, int n)
{
    // If both first and second string is empty,
    // or if second string is empty, return 1
    if ((m == 0 && n == 0) || n == 0)
        return 1;
 
    // If only first string is empty and second
    // string is not empty, return 0
    if (m == 0)
        return 0;
 
    // If last characters are same
    // Recur for remaining strings by
    // 1. considering last characters of both strings
    // 2. ignoring last character of first string
    if (a[m - 1] == b[n - 1])
        return count(a, b, m - 1, n - 1) +
               count(a, b, m - 1, n);
    else
        // If last characters are different, ignore
        // last char of first string and recur for
        // remaining string
        return count(a, b, m - 1, n);
}

  int dp[500][500];
    int solve(string S1, string S2, int m, int n)
    {
        if(m==0 && n==0 || n==0)
        return 1;
        if(m==0)
        return 0;
        
        if(dp[m][n]!=-1)
        return dp[m][n];
        if(S1[m-1]==S2[n-1])
        return dp[m][n] = solve(S1,S2,m-1,n-1) + solve(S1,S2,m-1,n);
        else return dp[m][n] = solve(S1,S2,m-1,n);
        
        return dp[m][n];
    }
    int countWays(string S1, string S2){
        
        int m=S1.length(),n=S2.length();
        memset(dp,-1,sizeof(dp));
        return solve(S1,S2,m,n);
    }

int count(string a, string b)
{
    int m = a.length();
    int n = b.length();
 
    // Create a table to store results of sub-problems
    int DP[m + 1][n + 1] = { { 0 } };
 
    // If first string is empty
    for (int i = 0; i <= n; ++i)
        DP[0][i] = 0;
 
    // If second string is empty
    for (int i = 0; i <= m; ++i)
        DP[i][0] = 1;
 
    // Fill lookup[][] in bottom up manner
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            // If last characters are same, we have two
            // options -
            // 1. consider last characters of both strings
            //    in solution
            // 2. ignore last character of first string
            if (a[i - 1] == b[j - 1])
                DP[i][j] = DP[i - 1][j - 1] +
                               DP[i - 1][j];
                 
            else
                // If last character are different, ignore
                // last character of first string
                DP[i][j] = DP[i - 1][j];
        }
    }
 
    return DP[m][n];
}