Nhận xét: giá trị kì vọng của hàm call(a, b) và call(c, d) sẽ bằng nhau nếu ~b - a = d - c~.

Gọi ~f[i]~ là giá trị kì vọng của hàm call(l, r) với ~r - l + 1 = i~. Ta có công thức quy hoạch động sau:

~f[i] = (1 + f[i]) + \sum \limits_{j = 1}^{i - 2} (1 + f[j] + f[i - j - 1]) + (1 + f[i])~

~\Rightarrow f[i] = i + 2 \cdot f[i] + \sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])~

~\Rightarrow (i - 2) \cdot f[i] = i + \sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])~

~\Rightarrow f[i] = \dfrac{i + \sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])}{i - 2}~

Để tính nhanh ~\sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])~, ta có thể sử dụng prefix sum (tổng tiền tố).

Độ phức tạp: ~O(n)~.

Code mẫu

#include <bits/stdc++.h>
#define len(x) ((int)(x).size())
using namespace std;
#define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u)
// DEBUGING TEMPLETE ////////////////////////////////////////////////////////////////////////
#define db(val) "["#val" = "<<(val)<<"] "
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL   
#   define clog cerr << setw(__db_level * 2) << setfill(' ') << "" << setw(0)
#   define DB() debug_block CONCAT(dbbl, __LINE__)
    int __db_level = 0;
    struct debug_block {
    debug_block() { clog << "{" << endl; ++__db_level; }
    ~debug_block() { --__db_level; clog << "}" << endl; }
    };
#else
#   define clog if (0) cerr
#   define DB(...)
#endif
template<class U, class V> print_op(pair<U, V>) {
    return out << "(" << u.first << ", " << u.second << ")";
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con) { 
    out << "{";
    for (auto beg = con.begin(), it = beg; it != con.end(); ++it) 
    out << (it == beg ? "" : ", ") << *it;
    return out << "}";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}
template<class ...U> print_op(tuple<U...>) {
    return print_tuple_utils<0, tuple<U...>>(out, u);
}
// ACTUAL SOLUTION START HERE ////////////////////////////////////////////////////////////////

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rng(124124);

int randnum(int l, int r) {
    return std::uniform_int_distribution<long long>(l, r)(rng);
}

int call(int l, int r) {
    if (r - l <= 1) return 0;
    int idx = randnum(l, r);
    if (idx == l || idx == r) return 1 + call(l, r);
    return 1 + call(l, idx - 1) * call(idx + 1, r);
}

const int MOD = 1e9 + 7;

void add(int& a, int b) {
    a += b;
    while (a >= MOD) a -= MOD;
    while (a < 0) a += MOD;
}

int prod(int a, int b) {
    return 1ll * a * b % MOD;
}

int bpow(int a, int b) {
    int c = 1;
    while (b) {
        if (b & 1) c = prod(c, a);
        a = prod(a, a);
        b >>= 1;
    }
    return c;
}

const int N = 1e6 + 5;

int dp[N];
int n;

void solve() {
    cin >> n;
    dp[1] = dp[2] = 0;
    for (int i = 3; i <= n; ++ i) {
        int x = prod(2, dp[i - 2]);
        x = prod(x, bpow(i, MOD - 2));
        add(x, 1);
        x = prod(x, i);
        x = prod(x, bpow(i - 2, MOD - 2));
        dp[i] = dp[i - 1];
        add(dp[i], x);
    }
    int res = dp[n];
    add(res, -dp[n - 1]);
    cout << res << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    solve();
    return 0;
}