由i个点和j个点组成的二分图个数为 $3^{ij}$，减去不联通的部分得到得到由i，j个点组成的联通二分图个数
$g_{i,j} = 3_{ij} - \sum_{k=1}^i \sum_{l=0}^j g_{k,l} C_{i-1,k-1} C_{j,l} 3^{(i-k)(j-l)}$
然后再dp一遍
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i)
#define dwn(i, j, k) for (int i = int(j); i >= int(k); -- i)
typedef long long LL;
const LL MOD = ;
const int N = ;
LL fac[N], inv[N], pw[N * N], g[N][N], f[N];
inline LL comb(LL n, LL m) {
return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int main() {
fac[] = ; rep(i, , N - ) fac[i] = fac[i - ] * i % MOD;
inv[] = inv[] = ;
rep(i, , N - ) inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
rep(i, , N - ) (inv[i] *= inv[i - ]) %= MOD;
pw[] = ;
rep(i, , N * N - ) pw[i] = pw[i - ] * % MOD;
rep(i, , ) rep(j, , - i) {
g[i][j] = pw[i * j]; // A集合中i 个点标号 1 -i， B集合中j个点标号1-j
// 枚举A集合中第一个点所在联通二分图
rep(k, , i) rep(l, , j) {
if (k == i && l == j) continue;
g[i][j] += MOD - g[k][l] * comb(i - , k - ) % MOD * comb(j, l) % MOD * pw[(i - k) * (j - l)] % MOD;
g[i][j] %= MOD;
}
}
f[] = ;
rep(i, , )
rep(j, , i - )
rep(k, , i - - j) {
f[i] += g[j + ][k] * comb(i - , j) % MOD * comb(i - - j, k) % MOD * f[i - - j - k] % MOD;
f[i] %= MOD;
} int n;
while (scanf("%d", &n), n) {
cout << f[n] << '\n';
}
}