题目描述

小火车的 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(x_1,\ldots,x_{i-1},a,x_{i+1},\ldots,x_n)=f(x_1,\ldots,x_{i-1},b,x_{i+1},\ldots,x_n)$ 则 $f(y_1,\ldots,y_{i-1},a,y_{i+1},\ldots,y_n)=f(y_1,\ldots,y_{i-1},b,y_{i+1},\ldots,y_n)$ 其中的 $i,a,b,x,y,n$ 都为任意值。

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

输入格式

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

输出格式

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

样例

2
Z

8

数据范围与提示

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