1000ms

Difficulty: 5

所属公司 : 美团

时间 :2023年10月7日

算法标签>暴力枚举

DP

题目描述

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

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

输入描述

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

输出描述

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

样例

输入

tazixx

输出

说明

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