Problem 68: Distinct Subsequences

Problem Statement: Given two strings s and t, count the number of distinct subsequences of s which equals t. Print the result modulo 10^9+7.

Input

The first line contains s and the second line contains t.

Output

Print the number of distinct subsequences of s that equal t modulo 10^9+7.

Examples


Input:
rabbbit
rabbit

Output:
3

Solution Explanation

Use dynamic programming where dp[i][j] denotes the number of ways t[0..j-1] appears as a subsequence in s[0..i-1]. Transition based on matching characters.

Solution in C++


#include 
#include 
#include 
using namespace std;

const int MOD = 1000000007;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector> dp(n + 1, vector(m + 1, 0));
    for(int i = 0; i <= n; i++)
        dp[i][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j] = dp[i - 1][j];
            if(s[i - 1] == t[j - 1])
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
        }
    }
    cout << dp[n][m] << "\n";
    return 0;
}