### 题目大意

• $\sum{a_i} = m$
• $2a_i \leq a_{i-1} + a_{i + 1} \quad(2\leq i \leq n – 1)$

$n,m \leq 10^5$

### 心路历程

(想看题解的可以跳过这段)

$$\sum_{i=1}^n \frac {i(i+1)}2 c_i = m$$

### 题解

$$a_{i-k} \geq a_i + k\quad (1 \leq k \leq i – 1)$$

• 给每一位 $+1$，即总体 $+n$。
• 对于 $i$左边的数，选择最前面的 $k$个数，分别加上 $(k,k-1,…,2,1)$
• 对于 $i$右边的数，选择最后面的 $k$个数，分别加上 $(1,2,…,k-1,k)$

#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf LLONG_MAX
#define mp std::make_pair
#define mod 1000000007
#define lowbit(x) (x & -x)
#define N 500005
#define clr(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
#define idx(i, u) ((i) * (nn) + (u))
#define eps (1e-8)
{
int x = 0; bool flag = 0; char ch = getchar();
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') flag = 1, ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
if (flag) x = -x; return x;
}
inline ll pow (ll x, int y)
{
ll ret = 1;
while (y)
{
if (y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
ll n, m, f[N], c[N], p, ans;
int main ()
{
f[0] = 1;
fo (i, n, m)
f[i] = (f[i] + f[i - n]) % mod;
fo (i, 1, n)
c[i] = c[i - 1] + i;
fo (i, 1, n - 1)
{
if (c[i] > m) break;
fo (j, c[i], m)
f[j] = (f[j] + f[j - c[i]]) % mod;
}
p = m;
ans = f[p];
fo (i, 1, n - 1)
{
p -= i;
if (p < 0) break;
ll now = c[n - i];
fd (j, m, now)
f[j] = (f[j] - f[j - now]) % mod;
fo (j, c[i], m)
f[j] = (f[j] + f[j - c[i]]) % mod;
ans = (ans + f[p]) % mod;
}
printf("%lld", (ans + mod) % mod);
}