题目描述

给定一个字符串$S$。有多少种方法可以选择并标记其中的八个字符，使得这些字符从左到右读起来是 "c"、"h"、"o"、"k"、"u"、"d"、"a"、"i"？

输入格式

输入字符串：

$S$

输出格式

由于计数结果可能非常大，请输出其对 $(10^9 + 7)$ 取模的结果。

输入输出样例 #1

输入 #1

chchokudai

输出 #1

3

输入输出样例 #2

输入 #2

atcoderrr

输出 #2

0

输入输出样例 #3

输入 #3

chokudaichokudaichokudai

输出 #3

45

说明/提示

样例 1 解释

我们有三种有效的方法：

• chchokudai
• chchokudai
• chchokudai

而以下方法是无效的：

chchokudai

样例 2 解释

答案可能为 $0$。

数据范围

• $8\ \leq\ |S|\ \leq\ 10^5$
• $S$ 由小写英文字母组成。