B. Unary
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Unary — минималистический диалект Brainfuck, в котором программы записываются с использованием единственного токена.

Программы на Brainfuck используют 8 команд: «+», «-», «[», «]», «<», «>», «.» и «,» (их смысл в данной задаче не важен). Программу на Unary можно получить из программы на Brainfuck следующим образом. Прежде всего, каждая команда заменяется бинарным кодом следующим образом:

  • «>»  →  1000,
  • «<»  →  1001,
  • «+»  →  1010,
  • «-»  →  1011,
  • «.»  →  1100,
  • «,»  →  1101,
  • «[»  →  1110,
  • «]»  →  1111.

Затем полученные коды конкатенируются в одно двоичное число в том же порядке, в котором они шли в программе. Наконец, это число записывается в унарной системе счисления — это и будет эквивалентная программа на Unary.

Вам дана программа на Brainfuck. Вычислите длину эквивалентной программы на Unary и выведите ее остаток от деления на 1000003 (106 + 3).

Входные данные

В единственной строке входных данных задана строка p — программа на Brainfuck. Строка p содержит от 1 до 100 символов, включительно. Каждый символ строки p будет «+», «-», «[», «]», «<», «>», «.» или «,».

Выходные данные

Выведите длину эквивалентной программы на Unary по модулю 1000003 (106 + 3).

Примеры
Входные данные
,.
Выходные данные
220
Входные данные
++++[>,.<-]
Выходные данные
61425
Примечание

Запись числа n в унарной системе счисления выглядит как единица, записанная n раз. Например, десятичное число 5, записанное в унарной системе, будет выглядеть как 11111.

В первом примере после замены команд Brainfuck на бинарные коды получим 1101 1100, после их конкатенации — 11011100 в двоичной системе, то есть 220 в десятичной. Именно столько единиц будет в эквивалентной программе на Unary.