chokudai

题目描述

给定一个字符串 $S$。

求有多少种方式从 $S$ 中选出 8 个字符并加下划线,使得这些字符从左到右读起来依次为 c、h、o、k、u、d、a、i。

由于答案可能很大,请对 $(10^9 + 7)$ 取模后输出。

输入格式

输入按以下格式从标准输入给出：

$S$

输出格式

输出方案数对 $(10^9 + 7)$ 取模后的值。

样例

chchokudai

3

有 3 种合法方案(原文中以下划线标出了选中的 8 个字符)：

chchokudai

chchokudai

chchokudai

而如下方案不合法：

chchokudai

atcoderrr

0

答案可能为 $0$。

chokudaichokudaichokudai

45

数据范围

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