SP9445 CLONES - Attack of the Clones

布尔函数是一种形如 $f: B^n \to B$ 的映射，其中 $B = \{0, 1\}$，$n$ 是函数的参数个数。我们称某些布尔函数为投影函数：$p_n^k(x_1, \ldots, x_n) = x_k$。如果有一个 $m$ 元函数 $f$ 和多个 $n$ 元函数 $g_1, \ldots, g_m$，可以通过复合得到新的 $n$ 元函数：$h(x_1, \ldots, x_n) = f(g_1(x_1, \ldots, x_n), \ldots, g_m(x_1, \ldots, x_n))$。一个在复合操作下不变且包含所有投影函数的函数集称为“克隆”。最简单的克隆是所有布尔函数的集合。还有一些特殊的克隆： - $Z$ 是所有保 0 函数的集合，即 $f(0, \ldots, 0) = 0$； - $P$ 是所有保 1 函数的集合，即 $f(1, \ldots, 1) = 1$； - $D$ 是所有自对偶函数的集合，即 $\neg f(x_1, \ldots, x_n) = f(\neg x_1, \ldots, \neg x_n)$； - $A$ 是所有仿射函数的集合，即如果 $f(a_1, \ldots, c, \ldots, a_n) = f(a_1, \ldots, d, \ldots, a_n)$，那么 $f(b_1, \ldots, c, \ldots, b_n) = f(b_1, \ldots, d, \ldots, b_n)$，这里 $c$ 和 $d$ 位于某个位置 $i$。这个性质对每个合适的 $i$ 和所有 $a_1, \ldots, a_n$，$b_1, \ldots, b_n$ 以及 $c$ 和 $d$ 都成立。 我们现在对上面定义的这些集合关心的是：不同组合下有多少个 $n$ 元函数。例如，对于 $n = 2$，在 $Z$ 中恰好有 8 个函数，在 $Z$ 和 $P$ 的交集中有 4 个函数，而在 $A$ 的补集中则有 8 个函数。

第一行是一个整数 $n$，表示我们研究的布尔函数的参数个数。第二行是一个整数 $q$，表示需要处理的查询数量。接下来的 $q$ 行每行是一个集合表达式。表达式中可以使用以下字符：'Z', 'P', 'D', 'A' 表示前文定义的集合；'v' 表示并集；'^' 表示交集；'!' 表示补集；'\\' 表示差集。此外，括号 '(' 和 ')' 用于设置操作优先级。括号内的操作优先级最高，其次是补集 '!'，然后并集、交集和差集 'v', '^', '\\' 优先级相同。题目保证每个表达式都是合法的。请参考样例了解集合表达式的更多例子。

对于每个输入查询，输出表示的集合中 $n$ 元函数的数量，并对 1000003 取模。 **本翻译由 AI 自动生成**