走在街上时,Vanya 看到了一个标签“捉迷藏”。因为他是一名程序员,所以他使用 & 作为这两个以 64 为基数的整数表示的单词的按位与,并得到了新单词。现在,Vanya 想到了一些字符串 s,并想知道长度为 |s| 的单词对的数量。 (s 的长度),使得它们的按位与等于 s。由于这个数字可能很大,因此输出它对 109 + 7 求模。
要将字符串表示为以 64 Vanya 为基数的数字系统中的数字,请使用以下规则:
- 从“0”到“9”的数字对应于从0到9的整数;
- 从“A”到“Z”的字母对应于从10到35的整数;
- 从“a”到“z”的字母对应于从36到61的整数;
- 字母“-”对应整数62;
- 字母“_”对应于整数 63。
输入
输入中唯一一行包含单个单词 s (1 ≤ |s| ≤ 100 000),由数字、小写英文字母、字符“-”和“_”组成。
输出
打印单个整数 - 可能的单词对的数量,使得它们的按位 AND 等于字符串 s 模 109 + 7。
示例
输入 #1
z
输出 #1
3
输入 #2
V_V
输出 #2
9
输入 #3
Codeforces
输出 #3
130653412
注意
有关按位 AND 的详细定义,我们建议您查看维基百科中的相应文章。
在第一个示例中,有 3 种可能的解决方案:
1. z&_ = 61&63 = 61 = z
2. _&z = 63&61 = 61 = z
3.z&z = 61&61 = 61 = z