

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
文字列 S が与えられます。
このうち 8 文字を選び下線を引き、下線を引いた文字が左から順に c
, h
, o
, k
, u
, d
, a
, i
となるようにする方法は何通りありますか?
ただし答えは非常に大きくなる可能性があるので、(10^9 + 7) で割った余りを出力してください。
制約
- 8 \leq |S| \leq 10^5
- S は英小文字からなる
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを (10^9 + 7) で割った余りを出力せよ。
入力例 1
chchokudai
出力例 1
3
chchokudai
chchokudai
chchokudai
上の 3 つが条件を満たします。
chchokudai
は、条件を満たさないことに注意してください。
入力例 2
atcoderrr
出力例 2
0
答えが 0 通りになることもあります。
入力例 3
chokudaichokudaichokudai
出力例 3
45
Score : 300 points
Problem Statement
You are given a string S.
How many ways are there to choose and underline eight of its characters so that those characters read c
, h
, o
, k
, u
, d
, a
, i
from left to right?
Since the count can be enormous, print it modulo (10^9 + 7).
Constraints
- 8 \leq |S| \leq 10^5
- S consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the number of ways modulo (10^9 + 7).
Sample Input 1
chchokudai
Sample Output 1
3
We have three valid ways:
chchokudai
chchokudai
chchokudai
while the following is invalid:
chchokudai
Sample Input 2
atcoderrr
Sample Output 2
0
The answer may be 0.
Sample Input 3
chokudaichokudaichokudai
Sample Output 3
45