#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a>i)&1) dp[i][b]=1; return; } for(Int nb=b;nb;nb=b&(nb-1)){ if(bc[nb]!=bc[b^nb]) continue; vector x,y; for(Int i=0;i>i)&1) x.emplace_back(i); if(((b^nb)>>i)&1) y.emplace_back(i); } dfs(nb); dfs(b^nb); for(Int i:x){ for(Int j:y){ if(a[i][j]>0) dp[i][b]+=dp[i][nb]*dp[j][b^nb]; if(a[i][j]<0) dp[j][b]+=dp[i][nb]*dp[j][b^nb]; } } } } signed main(){ memset(dp,-1,sizeof(dp)); for(Int i=0;i>a[i][j]; for(Int i=0;i<(1<