题目背景

在数学中，某个序列的 子序列 是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。

在本题中，一个字符串的子序列指这个字符串通过去除其中的某些字符但不破坏剩下来的字符的相对位置组成的一个新的字符串。

题目描述

给你一个长度不超过 $1000$ 的字符串 $s$，求字符串中包含多少子序列 “HETAO”？
（如果两个子序列中的任意相同字符在原字符串中的位置不同，就是为不同的子序列）

输入格式

输入共一行，包含一个长度不超过 $1000$ 的字符串。数据保证字符串中仅包含大写英文字母。

输出格式

一个整数，表示字符串中有多少个不同的子序列等于 “HETAO”。

样例

HHEETAO

4

HEHETAO

3

HHEETTAAOO

32

数据范围

• 对于 $20\%$ 的数据，字符串长度 $\le 20$；
• 对于 $40\%$ 的数据，字符串长度 $\le 50$；
• 对于 $60\%$ 的数据，字符串长度 $\le 100$；
• 对于 $100\%$ 的数据，字符串长度 $\le 1000$。