Unary — минималистический диалект Brainfuck, в котором программы записываются с использованием единственного токена.
Программы на Brainfuck используют 8 команд: «+», «-», «[», «]», «<», «>», «.» и «,» (их смысл в данной задаче не важен). Программу на Unary можно получить из программы на Brainfuck следующим образом. Прежде всего, каждая команда заменяется бинарным кодом следующим образом:
- «>» → 1000,
- «<» → 1001,
- «+» → 1010,
- «-» → 1011,
- «.» → 1100,
- «,» → 1101,
- «[» → 1110,
- «]» → 1111.
Затем полученные коды конкатенируются в одно двоичное число в том же порядке, в котором они шли в программе. Наконец, это число записывается в унарной системе счисления — это и будет эквивалентная программа на Unary.
Вам дана программа на Brainfuck. Вычислите длину эквивалентной программы на Unary и выведите ее остаток от деления на 1000003 (106 + 3).
Выходные данные
Выведите длину эквивалентной программы на Unary по модулю 1000003 (106 + 3).
Примечание
Запись числа n в унарной системе счисления выглядит как единица, записанная n раз. Например, десятичное число 5, записанное в унарной системе, будет выглядеть как 11111.
В первом примере после замены команд Brainfuck на бинарные коды получим 1101 1100, после их конкатенации — 11011100 в двоичной системе, то есть 220 в десятичной. Именно столько единиц будет в эквивалентной программе на Unary.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
,.
|
220
|
|
2
|
++++[>,.<-]
|
61425
|