Problem B. 你说的对，但是这是签到 II

时间限制 : 1000 ms

空间限制 : 256 MB

题目背景

pzr 最近学习了二进制枚举，这是一种状态压缩的技巧。例如有 $n$ 件物品，需要枚举各个物品选与不选的情况，不必写 $n$ 重循环 for iter_k in (0, 1):，特别是 $n$ 比较大或者 $n$ 的值可能变化时。我们可以将 $n$ 件物品的选与不选用 $0$ 和 $1$ 表示，再将这 $n$ 件物品的状态拼成一个 $n$ 位二进制数，范围是 $[0, 2^n-1]$。通过 for mask in range(0, 2 ** n): 枚举这些状态，既不重复又不遗漏。

题目描述

pzr 有一个长度为 $n$ 的字符串 $s=s_1s_2\cdots s_n$。

pzr 喜欢回文串，所以他在 $s$ 的末尾依次添加 $s_{n-1},s_{n-2},\cdots,s_1$，构造出字符串 $t$ ，即 $t=s_1s_2\cdots s_n s_{n-1} s_{n-2}\cdots s_1$。例如，$s=accba$，则 $t=accbabcca$。

现在，pzr 希望用 黑白两种颜色 将字符串 $t$ 染色，其中每个字符可以染成黑色，也可以染成白色。这样，被染成黑色的字符构成一个子序列，被染成白色的字符构成一个子序列。

在总共 $2^{2n-1}$ 种染色方案中，考虑满足以下条件的染色方案数：

• 至少有一个字符被染成黑色，至少有一个字符被染成白色。
• 被染成黑色的字符构成的子序列，其字典序 严格大于 被染成白色的字符构成的子序列。

pzr 想知道，有多少满足条件的染色方案数？请帮助他解决这个问题。

输入格式

仅一个字符串 $s$

输出格式

仅一个非负整数，表示满足条件的方案数。

可以证明，答案一定在 32 位整数可表示的范围内。

样例输入1

ba

样例输出1

3

样例1解释

t = 'bab'

有 $8$ 种染色方法，其中 $3$ 种满足要求，即：

'BBW': 将第一个字符和第二个字符染成黑色，则黑色子序列为 ba，白色子序列为 'b'，符合要求。

'BWB': 将第一个字符和第三个字符染成黑色，则黑色子序列为 bb，白色子序列为 'a'，符合要求。

'BWW': 将第一个字符染成黑色，则黑色子序列为 'b'，白色子序列为 'ab'，符合要求。

样例输入2

z

样例输出2

0

样例2解释

最终字符串的长度为 $1$，没有办法满足条件（至少有一个字符被染成黑色，至少有一个字符被染成白色）。

数据范围与约定

$1\le |s|\le 10$，$s$ 仅由小写字母组成。