まず、\(A_{i,j}=1\) であるような \((i, j)\) の間に辺を張ります。
このとき、\(G\) に閉路ができる場合は、\(G\) は木になり得ないので、答えは \(0\) です。
そうでなければ、\(G\) の \(1\) つの連結成分を \(1\) つの頂点に圧縮して、再び頂点と頂点の間に辺を張って木を作る問題にすることができます。

行列木定理

行列木定理 (Kirchhoff’s theorem) とは、無向グラフ \(G\) の ラプラシアン行列 の 余因子 が全て \(G\) の全域木の個数に等しいという定理です。

この問題は、連結成分を圧縮したものを頂点、\(A_{i,j}=-1\) である部分を辺とした無向グラフの全域木の個数を求める問題と見ることができるので、 このグラフのラプラシアン行列を求め、 最後の行と最後の列を取り除き、行列式を \(\bmod (10^9+7)\) で求めることで解くことができます。
行列式は、ガウスの消去法で高速に求められます。時間計算量は \(O(N^3)\) です。

回答例 (C++)

#include <iostream>
#include <vector>
#include <valarray>
#include <atcoder/modint>
#include <atcoder/dsu>
using namespace std;
using Modint = atcoder::modint1000000007;

int main(){
    int N;
    cin >> N;
    vector A(N, vector<int>(N));
    for(auto& v : A) for(int& i : v) cin >> i;
    atcoder::dsu uf(N);
    for(int i = 0; i < N; i++) for(int j = i + 1; j < N; j++) if(A[i][j] == 1){
        if(uf.same(i, j)) return puts("0") & 0;
        uf.merge(i, j);
    }
    vector m(N, valarray(Modint(0), N));
    for(int i = 0; i < N; i++) for(int j = i + 1; j < N; j++) if(A[i][j] == -1){
        const int x = uf.leader(i), y = uf.leader(j);
        m[x][x]++; m[y][y]++; m[x][y]--; m[y][x]--;
    }
    for(int i = 0; i < N; i++){
        const int x = uf.leader(i), y = i;
        m[x][x]++; m[y][y]++; m[x][y]--; m[y][x]--;
    }

    N--;
    Modint ans = 1;
    for(int i = 0; i < N; i++){
        if(m[i][i].val() == 0){
            for(int j = i + 1; j < N; j++) if(m[j][i].val()){
                swap(m[i], m[j]);
                ans *= -1;
                break;
            }
            if(m[i][i].val() == 0) return puts("0") & 0;
        }
        ans *= m[i][i];
        m[i] *= m[i][i].inv();
        for(int j = i + 1; j < N; j++) m[j] -= m[i] * m[j][i];
    }
    cout << ans.val() << endl;
}

回答例 (Python)

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def root(self, x):
        if self.data[x] < 0:
            return x
        ans = self.root(self.data[x])
        self.data[x] = ans
        return ans
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.data[x] > self.data[y]:
            x, y = y, x
        self.data[x] += self.data[y]
        self.data[y] = x
        return True

MOD = 1000000007
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]

uf = UnionFind(N)
for i in range(N):
    for j in range(i):
        if A[i][j] == 1:
            if not uf.unite(i, j):
                exit(print(0))

m = [[0] * N for i in range(N)]
for i in range(N):
    for j in range(i):
        if A[i][j] == -1:
            x = uf.root(i)
            y = uf.root(j)
            m[x][x] += 1
            m[y][y] += 1
            m[x][y] -= 1
            m[y][x] -= 1

for i in range(N):
    x = uf.root(i)
    y = i
    m[x][x] += 1
    m[y][y] += 1
    m[x][y] -= 1
    m[y][x] -= 1

N -= 1
ans = 1

for i in range(N):
    if m[i][i] == 0:
        for j in range(i + 1, N):
            if m[j][i] == 0:
                continue
            m[i], m[j] = m[j], m[i]
            ans *= -1
            break
        else:
            exit(print(0))
    ans *= m[i][i]
    ans %= MOD
    inv = pow(m[i][i], MOD - 2, MOD)
    for j in range(i, N):
        m[i][j] *= inv
        m[i][j] %= MOD
    for j in range(i + 1, N):
        x = m[j][i]
        for k in range(i, N):
            m[j][k] -= m[i][k] * x
            m[j][k] %= MOD

print(ans)