Description

布尔可满足性问题（SAT）在计算机科学中被认为是一个非常困难的问题。在这个问题中，给定一个布尔公式，你需要判断该公式的变量是否可以被一致地替换为真或假，使得公式的结果为真。SAT 是已知的 NP 完全问题。此外，即使在 $3-CNF$ 公式（$3-SAT$）的情况下，它也是 NP 完全的。然而，例如，对于 $2-CNF$ 公式（$2-SAT$）的 SAT 问题是在 $P$ 中的。

#SAT 是 SAT 问题的扩展。在这个问题中，你需要检查是否可能，并计算赋值给变量的方式的数量。这个问题即使对于 $2-CNF$ 公式也是已知的 #P 完全问题。我们要求你解决 #1-DNF-SAT，这是 $1-DNF$ 公式的 #SAT 问题。

你被给定一个 $1-DNF$ 形式的布尔公式。这意味着它是一个或多个子句的析取（逻辑或），每个子句正好是一个文字，每个文字要么是变量，要么是它的否定（逻辑非）。

形式化地：

$\langle \text{formula} \rangle ::= \langle \text{clause} \rangle \ | \ \langle \text{formula} \rangle \lor \langle \text{clause} \rangle$

$\langle \text{clause} \rangle ::= \langle \text{literal} \rangle$

$\langle \text{literal} \rangle ::= \langle \text{variable} \rangle \ | \ eg \langle \text{variable} \rangle$

$\langle \text{variable} \rangle ::= A \ldots Z \ | \ a \ldots z$

你的任务是找到将所有变量替换为真和假（同一变量的所有出现应替换为相同的值）的方法的数量，使得公式的结果为真。

Input Format

输入文件的唯一一行包含一个 $1-DNF$ 形式的逻辑公式（不超过 $1000$ 个符号）。逻辑操作由 ‘|’（析取）和 ‘~’（否定）表示。变量是 ‘A’ 到 ‘Z’ 和 ‘a’ 到 ‘z’（大写和小写字母是不同的变量）。公式不包含空格或语法中未提到的其他字符。

Output Format

输出一个整数——给定公式的 #SAT 问题的答案。

a

1

B|~B

2

c|~C

3

i|c|p|c

7

Hint

时间限制：3 秒，内存限制：512 MB。

题面翻译由 ChatGPT-4o 提供。