题目描述

在一个遥远的王国中，预言家留下了一段神秘的预言：某种神圣序列如果以特定方式从古老的文本中被发现，将解开宇宙的秘密。这段序列被称为“神秘序列”。

国王下令所有的学者必须寻找这一序列，原始的文本中包含了大量随机字符。学者们的任务是计算在给定的文本中，有多少种方法可以找到这个固定的序列 igetac，而无需改变文本的内容或顺序，但可以选择不连续的字符。

你的任务是帮助国王计算在所给文本中满足条件的 igetac 的非连续子序列数量，并输出结果对 $1e9 + 7$ 取模。

注意：非连续子序列的定义为：给定字符串 $a$，如果通过从 $a$ 中删除若干字符（或不删除）可以得到 $b$，那么 $b$ 是 $a$ 的非连续子序列。

输入格式

第一行输入一个字符串 $S$。

输出格式

输出一个整数，表示取余后的答案。

样例

igetac

1

dashcoding

0

数据范围

• $8≤∣S∣≤10^5$；
• $S$ 由小写英文字母组成。