1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class cnf {

    public static void main(String[] args) {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            int n = Integer.parseInt(reader.readLine());
            String input = reader.readLine();

            long counter = 0;

            int[] solution = new int[n + 1];

            String[] clauses = input
                    .replace("(", "")
                    .replace(")", "")
                    .replace("x", "")
                    .replace("v", "")
                    .replace("~", "-")
                    .replace("  ", " ")
                    .split("\\^");

            int[][] sentences = new int[clauses.length][];
            int[][] result = new int[clauses.length][];

            String[] temp;

            for (int i = 0; i < clauses.length; i++) {
                clauses[i] = clauses[i].trim();
                temp = clauses[i].split(" ");

                sentences[i] = new int[temp.length];
                result[i] = new int[temp.length];

                for (int j = 0; j < temp.length; j++) {
                    sentences[i][j] = Integer.parseInt(temp[j]);
                }
            }

            String solutionStr = null;

            for (long i = 0; i < power(2,n); i++) {
                solutionStr = new StringBuilder(Long.toBinaryString(i)).reverse().toString();

                for (int j = 0; j < solutionStr.length(); j++) {
                    solution[j + 1] = solutionStr.charAt(j) == '1' ? 1 : 0;
                }

                if (isPassingSolution(sentences, solution, result)) {
                    counter++;
                }
            }

            System.out.println(counter);

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static long power(long base, long power) {
        long result = 1;
        for (int i = 0; i < power; i++) {
            result *= base;
        }

        return result;
    }

    private static boolean isPassingSolution(int[][] sentences, int[] solution, int[][] result) {

        for (int i = 0; i < sentences.length; i++) {
            for (int j = 0; j < sentences[i].length; j++) {
                if (sentences[i][j] > 0) {
                    result[i][j] = solution[sentences[i][j]];
                } else {
                    if (solution[-sentences[i][j]] == 1) {
                        result[i][j] = 0;
                    } else {
                        result[i][j] = 1;
                    }
                }
            }
        }

        int zeroCount = 0;

        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                if (result[i][j] == 0) {
                    zeroCount++;
                }
            }
            if (result[i].length == zeroCount) {
                return false;
            }

            zeroCount = 0;
        }

        return true;
    }
}