题目描述

给定一个只由小写英文字母组成的字符串 $t$。小明很喜欢 s、m、z、x 这 $4$ 个字符。

他想从字符串 $t$ 中从左到右选择 $4$ 个字符，使得选出的字符从左到右正好是：

smzx

请你输出有多少种不同的选择方式。由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模后的结果。

注意：选择的是子序列，被选择的字符不要求连续，但相对顺序必须保持不变。

例如，若选择的位置不同，即使选出的字符内容相同，也算作不同的选择方式。

输入格式

输入一行一个字符串 $t$。

输出格式

输出一个整数，表示答案对 $10^9+7$ 取模后的结果。

样例 1

输入

ssmmzzxx

输出

16

说明

样例 1 中，可以从 $2$ 个 s 中选一个，从 $2$ 个 m 中选一个，从 $2$ 个 z 中选一个，从 $2$ 个 x 中选一个，因此共有：

种选择方式。

样例 2

输入

smzxsmzxsmzx

输出

15

数据范围与子任务

对于所有数据，满足：

• $1 \le |t| < 100000$；
• $t$ 只由小写英文字母组成。