序列dp（Python）

思路：很经典的s, t子序列匹配板子题，如果说题目要求判断s的子序列中有没有t，就可以直接用双指针，不过本题是要求算具体的数量，就该用子序列dp来做了。然后加了一个多输入，对于python来说要用try-except语句来实现。最终，输出答案即可

代码：

import sys
input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

def solve():
    mod = 2_000_120_420_010_122
    try:
        def fuc(s, t):
            s = s.lower()
            t = t.lower()

            m, n = len(s), len(t)
            dp = [[0] * (n + 1) for _ in range(m + 1)]

            for i in range(m + 1): # 初始化空串t的方案数为1，空串能直接匹配
                dp[i][0] = 1

            for i, x in enumerate(s):
                for j, y in enumerate(t):
                    dp[i + 1][j + 1] = dp[i][j + 1] # 假设不能选，赋初值
                    if x == y: # 可以选，额外添加值
                        dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % mod

            return dp[m][n]

        s = I()
        while s:
            print(fuc(s, "Cwbc"))
            s = I()
    except:
        pass

tt = 1
# tt = II()
for _ in range(tt):
    solve()