#include 
#include

//#include 
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int MOD =  750083;
string a, b;
int dp[1111][1111];
int rec(int i, int j) {
    if(i == -1 and j == -1) {
        return 0;
    }
    if(i == -1) {
        return j + 1;
    }
    if(j == -1) {
        return i + 1;
    }
    if(dp[i][j] != -1) {
        return dp[i][j];
    }
    int result = 2e9;
    if(a[i] == b[j]) {
        result = min(result, rec(i - 1, j - 1) + 1);
    }
    result = min(result, rec(i - 1, j) + 1);
    result = min(result, rec(i, j - 1) + 1);
    return dp[i][j] = result;
}
int comb_dp[1111][111];
int comb_rec(int i, int j) {
    if(i == -1 or j == -1) {
        return 1;
    }
    if(comb_dp[i][j] != -1) {
        return comb_dp[i][j];
    }
    int result = 0;
    
    if(a[i] == b[j]) {
        result += comb_rec(i - 1, j - 1);
        result %= MOD;
    }
    else {
        if(rec(i - 1, j) == rec(i, j - 1)) {
            result += comb_rec(i, j - 1) + comb_rec(i - 1, j);
            result %= MOD;
        }
        else if(rec(i - 1, j) < rec(i, j - 1)) {
            result += comb_rec(i - 1, j);
            result %= MOD;
        }
        else {
            result += comb_rec(i, j - 1);
            result %= MOD;
        }
    }
    return comb_dp[i][j] = result;
}
int main()
{
    cin >> a >> b;
    memset(dp, -1, sizeof dp);
    memset(comb_dp, -1, sizeof comb_dp);
  rec(a.size() - 1, b.size() - 1);
    cout << comb_rec(a.size() - 1, b.size() - 1) << endl;
    return 0;
}
/*
 
 **/