int stairs(int n)
{
    vector<long> q(n + 1, 0);
    q[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = n; j >= i; --j) {
            q[j] += q[j - i];
        }
    }
    return q[n];
}