package main

func numDistinct(s string, t string) int {
	m, n := len(s), len(t)
	if m < n {
		return 0
	}
	dp := make([][]int, m+1) // dp[i, j] means num distinct between s[0...i-1] and t[0...j-1]
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][0] = 1
	}
	// if s[i-1] == t[i-1], dp[i, j] = dp[i-1, j-1] + dp[i-1, j]
	// else dp[i, j] = dp[i-1, j]
	for i := 1; i <= m; i++ {
		for j := 1; j <= n && j <= i; j++ {
			if s[i-1] == t[j-1] {
				dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
			} else {
				dp[i][j] = dp[i-1][j]
			}
		}
	}
	return dp[m][n]
}

// func main() {
// 	println(numDistinct("rabbbit", "rabbit"), 3)
// 	println(numDistinct("babgbag", "bag"), 5)
// }