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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MX = 2e5 + 5;
const long long INF = 1e18;
const long double PI = 4 * atan((long double)1);
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
namespace input {
template <class T>
void re(complex<T>& x);
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
void re(long double& x) {
  string t;
  re(t);
  x = stold(t);
}
template <class T, class... Ts>
void re(T& t, Ts&... ts) {
  re(t);
  re(ts...);
}
template <class T>
void re(complex<T>& x) {
  T a, b;
  re(a, b);
  x = cd(a, b);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = (0); i < ((int)a.size()); ++i) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = (0); i < (SZ); ++i) re(a[i]);
}
}  // namespace input
using namespace input;
namespace output {
void pr(int x) { cout << x; }
void pr(long x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(long double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { pr(x ? "true" : "false"); }
template <class T>
void pr(const complex<T>& x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T>
void pr(const T& x);
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("}");
}
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}
void pc() { pr("]\n"); }
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
}  // namespace output
using namespace output;
namespace io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  cin.sync_with_stdio(0);
  cin.tie(0);
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace io
using namespace io;
typedef decay<decltype(MOD)>::type T;
struct mi {
  T val;
  explicit operator T() const { return val; }
  mi() { val = 0; }
  mi(const long long& v) {
    val = (-MOD <= v && v <= MOD) ? v : v % MOD;
    if (val < 0) val += MOD;
  }
  friend void pr(const mi& a) { pr(a.val); }
  friend void re(mi& a) {
    long long x;
    re(x);
    a = mi(x);
  }
  friend bool operator==(const mi& a, const mi& b) { return a.val == b.val; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.val < b.val; }
  mi operator-() const { return mi(-val); }
  mi& operator+=(const mi& m) {
    if ((val += m.val) >= MOD) val -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((val -= m.val) < 0) val += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    val = (long long)val * m.val % MOD;
    return *this;
  }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a != 0);
    return pow(a, MOD - 2);
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
int n, ways;
string g[2000];
pair<int, int> ans = {MOD, MOD};
bool check(vector<int> deg) {
  vector<int> v;
  for (int i = (0); i < (n); ++i) v.push_back(deg[i]);
  sort(begin(v), end(v));
  int sum = 0;
  for (int i = (0); i < ((int)v.size() - 1); ++i) {
    sum += v[i];
    if (sum == i * (i + 1) / 2) return 0;
  }
  return 1;
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  re(n);
  vector<int> deg(n);
  for (int i = (0); i < (n); ++i) {
    re(g[i]);
    for (int j = (0); j < (n); ++j)
      if (g[i][j] == '1') deg[i]++;
  }
  if (check(deg)) {
    ps(0, 1);
    exit(0);
  }
  for (int i = (0); i < (n); ++i) {
    for (int j = (0); j < (n); ++j)
      if (i != j) {
        if (g[i][j] == '0') {
          deg[j]--;
          deg[i]++;
        } else {
          deg[j]++;
          deg[i]--;
        }
      }
    ways += check(deg);
    for (int j = (0); j < (n); ++j)
      if (i != j) {
        if (g[i][j] == '0') {
          deg[j]++;
          deg[i]--;
        } else {
          deg[j]--;
          deg[i]++;
        }
      }
  }
  if (ways)
    ps(1, ways);
  else {
    assert(n <= 6);
    pair<int, long long> ans = {MOD, MOD};
    for (int i = (0); i < (1 << n); ++i) {
      vector<int> deg(n);
      for (int j = (0); j < (n); ++j)
        for (int k = (0); k < (n); ++k)
          if (j != k) {
            int ori = g[j][k] - '0';
            if (i & (1 << j)) ori ^= 1;
            if (i & (1 << k)) ori ^= 1;
            deg[j] += ori;
          }
      int p = __builtin_popcount(i);
      if (check(deg)) {
        if (p < ans.first) ans = {p, 0};
        if (p == ans.first) ans.second++;
      }
    }
    if (ans.first == MOD) {
      ps(-1);
      exit(0);
    }
    for (int i = (1); i < (ans.first + 1); ++i) ans.second *= i;
    ps(ans.first, ans.second);
  }
}