ارسال شماره 964

import java.util.*;

public class Main {

    private static final int[][] BETWEEN = new int[10][10];

    static {
        int[] row = {0, 0,0,0, 1,1,1, 2,2,2};
        int[] col = {0, 0,1,2, 0,1,2, 0,1,2};

        for (int a = 1; a <= 9; a++) {
            for (int b = 1; b <= 9; b++) {
                if (a == b) continue;
                int dr = row[b] - row[a];
                int dc = col[b] - col[a];
                if (dr % 2 == 0 && dc % 2 == 0) {
                    int mr = row[a] + dr / 2;
                    int mc = col[a] + dc / 2;
                    for (int n = 1; n <= 9; n++) {
                        if (row[n] == mr && col[n] == mc) {
                            BETWEEN[a][b] = n;
                            break;
                        }
                    }
                }
            }
        }
    }

    public static int countPatterns(boolean[] mandatory) {
        int count = 0;
        boolean[] visited = new boolean[10];

        for (int start = 1; start <= 9; start++) {
            if (!mandatory[start]) continue;
            visited[start] = true;
            count += backtrack(start, visited, mandatory);
            visited[start] = false;
        }

        return count;
    }

    private static int backtrack(int last, boolean[] visited, boolean[] mandatory) {
        boolean allVisited = true;
        for (int n = 1; n <= 9; n++) {
            if (mandatory[n] && !visited[n]) { allVisited = false; break; }
        }
        int count = allVisited ? 1 : 0;

        for (int nxt = 1; nxt <= 9; nxt++) {
            if (!mandatory[nxt] || visited[nxt]) continue;
            int mid = BETWEEN[last][nxt];
            if (mid != 0 && !visited[mid]) continue;
            visited[nxt] = true;
            count += backtrack(nxt, visited, mandatory);
            visited[nxt] = false;
        }

        return count;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        boolean[] mandatory = new boolean[10];
        for (int i = 0; i < k; i++) mandatory[sc.nextInt()] = true;
        System.out.println(countPatterns(mandatory));
    }
}