思路与算法

定义不等式迫使第三项在第一项另一侧，此后每项都向相反方向扩展已有极值。固定一个大小k≥3的数值子集，倒着去掉交替两侧的极值后，排列只有起始方向的两种。因此答案2Σ(k=3..n)C(n,k)=2^(n+1)-n²-n-2。逐十进制位计算n模MOD及2^n：新指数为旧指数×10+当前位，对应旧幂的10次方乘2^位。

正确性说明

不等式的严格性排除重复值，并保证新值总在当前区间相反外侧；逆向构造固定子集时每步删除哪侧最大/最小已由方向确定，给出恰两种且互不重合。二项式全集扣除k=0,1,2后得到公式。逐位幂更新是指数恒等式，不需要把5001位n放进机器整数。

复杂度

令L为十进制长度，逐位固定次小幂运算，时间O(L)、输入空间O(L)，额外状态O(1)。n=10^5000有5001位，包含边界。

易错点

n²只使用n的模值相乘；所有模减法最终归一。不能把该规则误解为一般上下交替排列，极值必须逐步向外扩展。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long pw(long long a, int n) {
    long long r = 1;
    while (n) {
        if (n & 1)
            r = r * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return r;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    long long v = 0, p = 1;
    for (char c : s) {
        v = (v * 10 + c - '0') % MOD;
        p = pw(p, 10) * pw(2, c - '0') % MOD;
    }
    cout << ((2 * p - v * v % MOD - v - 2) % MOD + MOD) % MOD << '\n';
}