因为直接求联通图不好求,可以考虑容斥,先求出无向图总数(连通块数至少为$1$),再减去不合法的数量(联通块至少为$2$),无向图总数可以通过判断一条边的有无,最多也就$2^{n*(n-1)/2}$条边。

因此也就是$2^{n*(n-1)/2}$种无向图。

假设已经求到了前$i-1$大小的联通图的方案数,不妨令连通块至少为2的方案中的其中一个连通块方案包含$1$这个点,方便去重,同时变成了一个子问题,因此可以通过枚举$j$的大小,再选出$j-1$个点与$i$形成连通块。

那么有

$f_i=2^{i*(i-1)/2}-\sum_{j=1}^{i-1}f_j*C_{i-1}^{j-1}*2^{(i-j)*(i-j-1)/2}$

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define gc getchar()
#define ll long long
using namespace std;
const int mod=1e9+7;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
inline ll pow_mod(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        b>>=1;a=a*a%mod;
    }
    return ans;
}
ll f[51],p[51],inv[51];
ll calc(int n,int m){return p[m]*inv[n]%mod*inv[m-n]%mod;}
/*
f[i]=pow_mod(2,i*(i-1)/2)-Σf[j]*C_{i-1}^{j-1}*2^{(i-j)*(i-j-1)/2}
意思为有i个点的无向图的总个数-枚举含1的联通块大小为j的形状的方案(i-1个数从中选出j-1个数)*可选择联通快大小为j的方案*剩余联通块形状可能的方案
换句话说,就是联通块至少为1的个数-联通块至少为2的个数=联通块为1的个数。 
*/
int main()
{
    p[0]=1;for(int i=1;i<=50;i++)p[i]=p[i-1]*i%mod;
    inv[50]=pow_mod(p[50],mod-2);for(int i=49;i;i--)inv[i]=inv[i+1]*(i+1)%mod;
    inv[0]=1;
    f[1]=1;//只有1这个点。 
    for(int i=2;i<=50;i++)
    {
        f[i]=pow_mod(2,i*(i-1)/2);
        ll sum=0;
        for(int j=1;j<i;j++)
            sum=(sum+f[j]*calc(j-1,i-1)%mod*pow_mod(2,(i-j)*(i-j-1)/2)%mod)%mod;
        f[i]=((f[i]-sum)%mod+mod)%mod;
    }
    int n;
    while(qr(n),n)qw(f[n]),puts("");
    return 0;
}