Ваня шёл по улице и увидел надпись «Hide&Seek». Поскольку Ваня — программист, ему сразу пришла идея воспользоваться операцией & (побитовое И) для этих двух слов в 64-ричной системе счисления (0..9A..Za..z-_) и получить новое слово. Теперь Ваня придумал некоторую строку s и задался вопросом, сколько существует различных пар слов длины |s| (длина строки s), побитовое И которых равно данному слову s? Поскольку ответ может быть очень большим, Ваня просит вас вычислить его по модулю 109 + 7.
Для перевода букв слова в 64-ричную систему счисления Ваня использует следующее соответствие знаков и чисел:
- цифрам от «0» до «9» соответствуют числа от 0 до 9;
- буквам от «A» до «Z» соответствуют числа от 10 до 35;
- буквам от «a» до «z» соответствуют числа от 36 до 61;
- символу «-» соответствует число 62;
- символу «_» соответствует число 63.
Выходные данные
Выведите единственное целое число — количество возможных пар слов, побитовое И которых равняется строке s, по модулю 109 + 7.
Примечание
Для подробного описания функции побитовое И можно посмотреть соответствующую статью в Википедии.
В первом примере возможны 3 варианта:
- z&_ = 61&63 = 61 = z
- _&z = 63&61 = 61 = z
- z&z = 61&61 = 61 = z
Примеры
| № | Входные данные | Выходные данные |
|
1
|
z
|
3
|
|
2
|
V_V
|
9
|
|
3
|
Codeforces
|
130653412
|