题目描述

为了规避基于内容的垃圾邮件过滤器，垃圾邮件发送者通常会修改垃圾邮件的文本，以防止其被自动过滤程序识别。对于任何纯文本字符串$s$（仅包含大写字母），设$\Phi(s)$表示通过“垃圾邮件字母表”替换每个字母后得到的字符串：

A 4 （数字4） N || （竖线反斜杠竖线） B |3 （竖线数字3） O 0 （数字0） C ( （左括号） P |0 （竖线数字0） D |) （竖线右括号） Q (,) （左括号逗号右括号） E 3 （数字3） R |? （竖线问号） F |= （竖线等号） S 5 （数字5） G 6 （数字6） T 7 （数字7） H # （井号） U |_| （竖线下划线竖线） I | （竖线） V / （反斜杠正斜杠） J | （下划线竖线） W // （反斜杠正斜杠反斜杠正斜杠） K |< （竖线小于号） X >< （大于号小于号） L | （竖线下划线） Y -/ （减号正斜杠） M |/| （竖线反斜杠正斜杠竖线） Z 2 （数字2）

在这个方案中，任何纯文本消息$s$都对应唯一一个垃圾邮件编码$\Phi(s)$。然而，反过来并不一定成立：一个垃圾邮件编码可能对应多个纯文本消息。

给定一个纯文本消息$s$，你的目标是确定有多少个不同的纯文本消息的垃圾邮件编码是$\Phi(s)$。

输入

输入测试文件包含多个测试用例。每个测试用例由一行组成，包含一个由1到100个大写字母组成的纯文本字符串$s$。文件末尾由单独一行“end”表示。

输出

对于每个测试用例，输出不同的纯文本消息（包括原始消息）的数量，这些消息的垃圾邮件编码是$\Phi(s)$。不同的纯文本消息的数量保证不超过$1,000,000,000$。

输入样例1

BU
UJ
THEQUICKBROWNFOXJUMPEDOVERTHELAZYDOGS
end

输出样例1

6
5
144

提示

在第一个测试用例中，'BU'的垃圾邮件编码是'|3||'。具有此垃圾邮件编码的6个纯文本消息为'BU'、'IEU'、'BIJ'、'IEIJ'、'BLI'和'IELI'。在第二个测试用例中，'UJ'的垃圾邮件编码是'||_|'。具有此垃圾邮件编码的5个纯文本消息为'UJ'、'LU'、'IJJ'、'LLI'和'LIJ'。

来源

斯坦福本地赛 2006