Problem: You are given a tournament — complete directed graph.

In one operation you can pick any vertex v and change the direction of all edges with v on one of the ends (i.e all edges u → v change their orientation to v → u and vice versa).

You want to make the tournament strongly connected with the smallest possible number of such operations if it is possible. 

Also, if it is possible, you need to find the number of ways to make this number of operations to make graph strongly connected (two ways are different if for some i vertex that we chose on i-th operation in one way is different from vertex that we chose on i-th operation in another way). You only need to find this value modulo 998 244 353.

Input

The first line of input contains one integer n (3 ≤ n ≤ 2000): the number of vertices in the tournament.

Following n lines contain a description of the given tournament, each of them contains a binary string of length n. If j-th character of i-th string is equal to '1', then the graph has an edge i → j.

It is guaranteed that there are no edges i → i and the graph has exactly one edge among i → j and j → i for different i and j.

Output

If it is not possible to convert tournament to strongly connected with the given operations, output "-1".

Otherwise, output two integers: the smallest number of operations that you need to make the given graph strongly connected and the number of ways to do this number of operations to make graph strongly connected, modulo 998 244 353.

Examples

Input


3
010
001
100


Output


0 1


Input


4
0010
1000
0100
1110


Output


-1


Input


6
010000
001000
100000
111001
111100
111010


Output


2 18

Solution (in JAVA):

Solution:
//package com.company;

import java.io.*;
import java.util.*;

public class Main {
    public static class Task {
        int n;
        int[][] graph;
        int[] deg;
        int[] cpDeg;
        boolean scc() {
            System.arraycopy(deg, 0, cpDeg, 0, n);
            Arrays.sort(cpDeg);
            int tot = 0;
            for (int i = 1; i < n; i++) {
                tot += cpDeg[n - i];
                int bui = i * (n - i) + i * (i - 1) / 2;
                if (tot == bui) return false;
            }
            for (int i = 1; i < n; i++) {
                tot += cpDeg[i - 1];
                int bui = i * (i - 1) / 2;
                if (tot == bui) return false;
            }
            return true;
        }

        void flip(int u) {
            for (int i = 0; i < u; i++) {
                deg[u] -= graph[u][i];
                deg[i] += graph[u][i];
                graph[u][i] = -graph[u][i];
            }
            for (int i = u + 1; i < n; i++) {
                deg[u] += graph[i][u];
                deg[i] -= graph[i][u];
                graph[i][u] = -graph[i][u];
            }
        }

        int dfs(int depth, int i) { // < mod
            if (depth == 0) {
                if (scc()) return 1;
                else return 0;
            }
            int sum = 0;
            for (int j = i; j < n; j++) {
                if (System.currentTimeMillis() - TIME_START >= 1500) return  sum;

                flip(j);
                sum += dfs(depth - 1, j + 1);
                flip(j);
            }
            return sum;
        }
        int mod = 998244353;

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            n = sc.nextInt();
            graph = new int[n][n];
            deg = new int[n];
            cpDeg = new int[n];
            for (int i = 0; i < n; i++) {
                String s = sc.next();
                for (int j = 0; j < n; j++) {
                    int y = s.charAt(j) - '0';
                    if (i < j) {
                        if (y == 1) deg[i]++;
                        if (y == 0) deg[j]++;
                    }
                    if (y == 0 && i != j) y = -1;
                    graph[i][j] = y;
                }
            }
            if (scc()) {
                pw.println("0 1");
                return;
            }
//            for (int i = 0; i < n; i++) {
//                if (deg[i] == 0 || deg[i] == n - 1) {
//                    pw.println(-1);
//                    return;
//                }
//            }
            long tot = 1;
            for (int i = 1; i <= n; i++) {
                if (System.currentTimeMillis() - TIME_START >= 1500) break;
                long ret = (long) dfs(i, 0) * tot % mod;
                tot = tot * (i + 1) % mod;
                if (ret > 0) {
                    pw.println(i + " " + ret);
                    return;
                }
            }
            pw.println(-1);
        }
    }

    static long TIME_START, TIME_END;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("input_line"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("input_line"));

        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
        System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
        System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}