You can Refer This Code

Btw , this Problem originally is form codechef here

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <sstream>
using namespace std;

#define int long long
#define INF 1e18
#define pb push_back
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ppb pop_back
#define lld long double
#define mod 1000007
#define bn << '\n';
#define cbbn cout << '\n\n';
#define cbn cout << '\n';
#define debug cout << "HERE----------------------------\n";
#define inputv(v) for (auto &i : v){cin >> i;}
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define vi vector<int>
#define vs vector<string>
#define vb vector<bool>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, n, a) for (int i = n; i >= a; i--)
#define pii pair<int, int>
#define vpi vector<pair<int, int>>
#define vvi vector<vector<int>>
#define vvpi vector<vector<pair<int, int>>>
#define sz(a) a.size()
#define clean(v,x) memset(v,x,sizeof(v));

template <typename T, typename T1> T amax(T &a, T1 b){if (b > a)a = b;	return a;}
template <typename T, typename T1> T amin(T &a, T1 b){if (b < a)a = b;return a;}
template <typename T> std::istream &operator>>(std::istream &input, std::vector<T> &data){for (T &x : data)input >> x;return input;}
template <typename T> std::ostream &operator<<(std::ostream &output, const std::pair<T, T> &data){output << "(" << data.first << "," << data.second << ")";	return output;}
template <typename T> std::ostream &operator<<(std::ostream &output, const std::vector<T> &data){for (const T &x : data)	output << x << " ";	return output;}

//=============================================================================================================================


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////// DO NOT TOUCH BEFORE THIS LINE ///////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////


//=================================================SOLVE-ANS===================================================================

int lenDP[1001][1001];
int countDP[1001][1001];

int lcs(string &a, string &b)
{
    clean(lenDP, 0);
    int n = a.length();
    int m = b.length();
    rep(i,1,n+1)
    {
        rep(j,1,m+1)
        {
            if(a[i-1]==b[j-1])
            {
                lenDP[i][j] = lenDP[i - 1][j - 1] + 1;
                lenDP[i][j] %= mod;
            }
            else
            {
                lenDP[i][j] = max({lenDP[i - 1][j], lenDP[i][j - 1], lenDP[i - 1][j - 1]});
                lenDP[i][j] %= mod;
            }
        }
    }

    return lenDP[n][m];
}


int lcsCT(string &a, string &b)
{
    clean(countDP, 0);
    int n = a.length();
    int m = b.length();

    rep(i,1,n+1)
    {
        rep(j,1,m+1)
        {
            if(i==1 || j==1)
            {
                countDP[i][j] = 1;
            }
            else 
            {
                if(a[i-1]==b[j-1])
                {
                    countDP[i][j] = countDP[i - 1][j - 1];
                }
                else
                {
                    if(lenDP[i-1][j]==lenDP[i][j])
                    {
                        countDP[i][j] += countDP[i - 1][j];
                        countDP[i][j] %= mod;
                    }
                    if(lenDP[i][j-1]==lenDP[i][j])
                    {
                        countDP[i][j] += countDP[i][j - 1];
                        countDP[i][j] %= mod;
                    }
                    if(lenDP[i-1][j-1]==lenDP[i][j])
                    {
                        countDP[i][j] -= countDP[i - 1][j - 1];
                        countDP[i][j] += mod;
                        countDP[i][j] %= mod;
                    }
                }
            
            }
        }
    }

    return countDP[n][m];
}


void Here_We_Go()
{
    string a, b;
    cin >> a >> b;

    int len = lcs(a, b);
    int ct = lcsCT(a, b);

    // cout << len << " " << ct bn
    cout<<ct<<endl;
}

int32_t main()
{

    FAST/* 
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif */
    int tc = 1;
    cin >> tc;
    rep(i, 1, tc + 1)
    {
        cout << "Case " << i << ": ";
        Here_We_Go();
    }
}