思路：二进制枚举

数据范围$n\le 20$，因此可以考虑暴力枚举每一个子序列，判断枚举的子序列是否满足条件

我们可以使用DFS枚举，也可以使用二进制枚举，枚举选/不选第$i$个字符，最终构成最终的字符串即可。

首先，我们遍历所有可能的删除方案。由于不能删除两个连续的字符，我们可以使用位运算来表示删除方案。对于字符串中的每个字符，我们都有两种选择：删除它或保留它。因此，总共有2^n种可能的删除方案，其中n是字符串的长度。

然后，对于每一种删除方案，我们检查删除后的字符串是否是好串。我们使用一个标志变量来表示当前的删除方案是否有效。如果删除后的字符串中存在两个连续的字符被删除，我们就将标志变量设置为false。

题目描述

一个好串定义为，当且仅当这个串中包含"tazi"连续子串。例如"tazige","shuaitazi"都是好串，而taxxxzi不是好串。

现在你可以删除一些字符使给定的串变成好串，但不能删除两个连续的字符，求有多少种方案可以使原串变成好串。

输入描述

输入一行，表示原字符串。长度不超过20。

输出描述

输出一个整数，表示方案数。

样例

输入

tazixx

输出

3

说明

第一种什么都不删，第二种删除第一个'x'，第三种删除第二个'x'。