G. Неслучайные числа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для генерации псевдослучайных чисел используют различные методы. Одним из таких методов является использование булевых рекуррентных выражений. В таком случае, псевдослучайное число представляется в виде битовой последовательности, такой что каждый следующий бит вычисляется из предыдущих по некоторой формуле. Однако такое задание фактически определяет последовательность по первым ее членам.

Альтернативой может служить использование булевых уравнений. Будем говорить, что битовая последовательность x1, x2, x3, …, xn удовлетворяет некоторому уравнению

F(xi, xi - 1, ..., xi - k) = 1,
если это уравнение верно для любых xi, xi - 1, … xi - k., при i > k. Напишите программу, которая по заданному уравнению найдет количество последовательностей длины n, удовлетворяющих этому уравнению.
Входные данные

Первая строка входного файла содержит целое число n (2 ≤ n ≤ 103). Вторая строка содержит левую часть уравнения, закодированного следующим способом:

  • бит с индексом xi - r (0 ≤ r ≤ 9, r < n) обозначается как r, то есть xi - 5 будет обозначено как 5
  • операция «и» (конъюнкция) обозначается как «&»
  • операция «или» (дизъюнкция) обозначается как «|»
  • операция «исключающее или» (сложение по модулю 2) обозначается как «+»
  • операция «не» (отрицание) обозначается как «-» (знак минус)
  • в уравнении допускаются скобки, операции в скобках выполняются раньше чем другие
  • бинарные операции не стоящие в скобках считаются одноранговыми и выполняются строго слева направо
  • пробелы внутри соотношения не допускаются

Длина левой части уравнения не превосходит 1000 символов.

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

Выходной файл содержит единственное число — количество битовых последовательностей длинны n удовлетворяющих уравнению. Число должно быть выведено по модулю 260.

Примеры
Входные данные
3
(0+2)|(0&2)
Выходные данные
6
Входные данные
4
(0+2)|-(0&2)
Выходные данные
9
Примечание

Первый пример кодирует уравнение (xi + xi - 2)|(xi&xi - 2) = 1, которому удовлетворяют следующие последовательности: 001, 011, 100, 101, 110, 111. Второй пример кодирует уравнение (xi + xi - 2)|( - (xi&xi - 2)) = 1, которому удовлетворяют последовательности: 0000, 0001, 0010, 0011, 0100, 0110, 1000, 1001, 1100.