AtCoder Beginner Contest 211 [ C - chokudai ] https://atcoder.jp/contests/abc211/tasks/abc211_c

abc211_c.py

'''
[問題]
https://atcoder.jp/contests/abc211/tasks/abc211_c

[解説]
AtCoder Beginner Contest 211 C問題 解説
https://www.youtube.com/watch?v=Zu9S_kJ-7tk
snukeさん

dpで解くのね
'''

import sys

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

S = input()
S = S.replace('\n', '')
LEN_S = len(S)

MOD = 10**9 + 7

T = "chokudai"
LEN_T = len(T)

#dp = [ [0] * (LEN_S) for _ in range(LEN_T)]
# なんで？これがAC。上と変わらんくないか？+1が必要っぽいがループに影響なくない？
dp = [ [0] * (LEN_S+1) for _ in range(LEN_T)]

for j in range(LEN_T):
    for i in range(LEN_S):
        if S[i] == T[j]:

            if j == 0 and i == 0:
                dp[j][i] = 1
                continue

            if j == 0:
                dp[j][i] = dp[j][i - 1] + 1
                continue

            dp[j][i] = (dp[j][i - 1] + dp[j - 1][i - 1]) % MOD

        else:
            dp[j][i] = dp[j][i - 1]

print(dp[LEN_T-1][LEN_S-1])