void sos(int *dp, bool inv) {
    if (!inv) {
        for (int i = 0;i < n;++i)
            for (int s = 0;s < 1<<n;++s)
                if (s>>i&1) {
                    add(dp[s], dp[s^(1<<i)]);
                }
    }
    else {
        for (int i = n-1;i >= 0;--i)
            for (int s = 0;s < 1<<n;++s)
                if (s>>i&1) {
                    add(dp[s], p - dp[s^(1<<i)]);
                }
    }
}