ARC077B TLE

// Problem: D - 11
// Contest: AtCoder - AtCoder Beginner Contest 066
// URL: https://atcoder.jp/contests/abc066/tasks/arc077_b
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m)); }
template <class T> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n)); }
template <class T, T init> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m, init)); }
template <class T, T init> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n, init)); }

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;

int main(int argc, char **argv)
{
    int n;
    cin >> n;
    vi a(n + 1);
    map<int, int> cnt;
    int last_seg = 0;
    int first_seg = 0;
    for (int i = 0; i <= n; ++i) {
        cin >> a[i];
        if (cnt.count(a[i])) {
            first_seg = cnt[a[i]];
            last_seg = n - i;
        }
        // cnt.insert(a[i]);
        cnt[a[i]] = i;
    }
    last_seg += first_seg;
    dbg(last_seg);

    const int mod = int(1e9) + 7;
    vi cnp1(n + 3), cnm1(n);
    cnp1[0] = 1;
    for (int i = 1; i < n; ++i)
        for (int j = i; j > 0; --j)
            cnp1[j] = (cnp1[j] + cnp1[j - 1]) % mod;
    cnm1 = cnp1;
    for (int j = n; j > 0; --j)
        cnp1[j] = (cnp1[j] + cnp1[j - 1]) % mod;
    for (int j = n + 1; j > 0; --j)
        cnp1[j] = (cnp1[j] + cnp1[j - 1]) % mod;

    int k = n + 1;
    vi dup(k + 1), no_dup(k + 1);
    dup[1] = 0, dup[2] = 1;
    auto comb = [last_seg, mod](int n, int r) {
        static vi f(last_seg + 1);
        if (f[0] == 0) {
            f[0] = 1;
            for (int i = 1; i <= last_seg; ++i)
                for (int j = i; j > 0; --j)
                    f[j] = (f[j] + f[j - 1]) % mod;
        }
        return r <= last_seg ? f[r] : 0;
    };
    for (int i = 1; i <= k; ++i) {
        dup[i] = (i <= 2 ? i - 1 : cnm1[i - 2]);
        int repeat = comb(last_seg, i - 1);
        no_dup[i] = ((ll(cnp1[i]) - dup[i] - repeat) % mod + mod) % mod;
        // dbg(i, dup[i], no_dup[i], repeat);
        cout << (ll(dup[i]) + no_dup[i] + mod) % mod << endl;
    }
    return 0;
};