题目描述

小火车的 ddl 赶不完了，他不愿意也没时间去思考题目背景到底应该怎么写了。

有一种神奇的函数被称为布尔函数，它的定义域为所有长度为 $ n $ 的 01 数组，而值为 $ 0 $ 或 $ 1 $。而有四种集合的元素都是布尔函数，它们被称为是 $ Z, P, D, A $ 集合。

• $ Z $ 集合的元素是所有满足 $ f(0,0, \ldots ,0)=0 $ 的布尔函数。
• $ P $ 集合的元素是所有满足 $ f(1,1, \ldots,1)=1 $ 的布尔函数。
• $ D $ 集合的元素是所有满足 $ \text{not}(f(x_1,x_2, \ldots ,x_n)) = f(\text{not}(x_1),\text{not}(x_2),\ldots,\text{not}(x_n)) $ 的布尔函数。
• $ A $ 集 合 的 元 素 则 比 较 复 杂 ， 它 们 都 得 满 足 若 $ f(x1,\ldots,x{i-1},a,x_{i+1},\ldots,x_n)=f(x1,\ldots,x{i-1},b,x_{i+1},\ldots,x_n) $ 则 $ f(y1,\ldots,y{i-1},a,y_{i+1},\ldots,y_n)=f(y1,\ldots,y{i-1},b,y_{i+1},\ldots,y_n) $ 其中的 $ i,a,b,x,y,n $ 都为任意值。

现在给你一个由 ZPDA^v!()\ 几种字符组成的表达式，表示一个布尔函数组成的集合，其中 ^ 表示交集，v 表示并集，! 表示补集，\ 表示差集，! 的优先级要高于其余三种运算符，但比 () 要低。请问这个集合中含有多少布尔函数？

输入格式

第一行一个整数 $ n $，第二行一个字符串表示表达式，保证表达式合法。

输出格式

一行一个整数表示答案，答案对 $ 1000003 $ 取模。

样例

input

2
Z

output

8

数据范围与提示

令 $ L $ 表示表达式长度；
对于 $ 20\% $ 的数据 $ n = 1, L \leq 5 $，无括号；
对于 $ 50\% $ 的数据满足 $ n \leq 4, L \leq 15 $，无括号；
对于 $ 100\% $ 的数据满足 $ n, L \leq 100 $。