← 返回题目列表

Codeforces · 677/C

C. 万尼亚和标签

中文机器翻译题面 查看原题

走在街上时,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