「2017 山东二轮集训 Day3」第二题

传统 1000 ms 512 MiB

$13$ 通过 $34$ 提交

题目描述

小火车的 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

令 $L$ 表示表达式长度；