问题简述
序列中有 $n$ 个元素，满足 $A_1 \leqslant A_2 \leqslant \cdots \leqslant A_n$
从中选取任意 $k$ 个元素，他们的和为 $\sum_{k} a[\cdots]$
从中选取任意 $k+1$ 个元素，他们的和为 $\sum_{k+1} a[\cdots]$
必须保证 $\sum_{k} a[\cdots] < \sum_{k+1} a[\cdots]$，求满足条件的方案数

注意到此时 $A_1 \leqslant A_2 \leqslant \cdots \leqslant A_n$
所以原问题可以转换成为
$$ \sum_{i=1}^{k+1} a_i \geqslant \sum_{i=n-k+1}^{n} a_i $$

先证明一个性质，如果 $n-k+1 = k+1$，即 $k = \lfloor \frac{n}{2}\rfloor$ 满足
则对所有的 $1 \leqslant k \leqslant n-1$ 均满足
证明如下

问题转换为满足
$$ \sum_{i=1}^{k+1} a_i \geqslant \sum_{i=n-k+1}^{n} a_i \quad (k = \left \lfloor \frac{n}{2} \right \rfloor) $$

• 构造差分序列 $x_i= a_i - a_{i-1}$
  令 $x_0 = 1$，这是因为得分不能为 $0$，可能所有题目得分都是一样的
  此时 $\sum_{i=1}^{n} x_i = 0$ 不满足题意
  所以令 $x_0 = 1$，则此时 $a_n \geqslant 1$ 成立
  $$ a_n = 1 + \left(\sum_{i = 1}^{n}x_i \right) $$
• $\left \lfloor \frac{n}{2} \right \rfloor = \frac{n-1}{2}$
  $$ \begin{gathered} \sum_{i=1}^{\frac{n+1}{2}} a_i \geqslant \sum_{i = \frac{n+1}{2} + 1}^{n} a_i \\\ \Rightarrow \ 2 \left(\sum_{i=1}^{\frac{n+1}{2}} a_i \right)\geqslant \sum_{i = 1}^{n} a_i \\\ \Rightarrow 2 \sum_{i=1}^{\frac{n+1}{2}} \left( \frac{n+1}{2} - i + 1 \right) x_i \geqslant \sum_{i=1}^{n}(n-i+1)x_i \end{gathered} $$
  移项，上式可以写成
  $\sum_{i = 1}^{n} C_i\cdot x_i \leqslant 0$
  $$ C_i = \begin{cases} n-i+1 && i > \frac{n+1}{2} \\\ i-2 && i \leqslant \frac{n+1}{2} \end{cases} $$
• $\left \lfloor \frac{n}{2} \right \rfloor = \frac{n}{2}$
  同理可以求出
  $$ \begin{gathered} 2 \left( \sum_{i=1}^{\frac{n}{2}}a_i \right) \geqslant \left( \sum_{i=1}^{n} a_i \right) - a_{\frac{n}{2} + 1} \\\ 2\left( \sum_{i=1}^{\frac{n}{2}} \left(\frac{n}{2} - i+1 \right) x_i \right) \geqslant \sum_{i=1}^{n}\left( n-i+1 \right)x_i - \sum_{i=1}^{\frac{n}{2}+1} x_i \end{gathered} $$
  写成如下形式
  $\sum_{i=1}^{n}C_i \cdot x_i \leqslant 0$
  $$ C_i = \begin{cases} n-i && i = \frac{n}{2} + 1 \\\ n-i+1 && i > \frac{n}{2} + 1 \\\ i-2 && i \leqslant \frac{n}{2} \end{cases} $$
  注意到 $i=\frac{n}{2} + 1$ 时候，此时 $i-2=n-i$
  综上所述
  $$ C_i = \begin{cases} n-i+1 && i > \left\lfloor \frac{n}{2} \right\rfloor + 1 \\\ i-2 && i \leqslant \left\lfloor \frac{n}{2} \right\rfloor + 1 \end{cases} $$
• 问题转换为满足以下条件
  $$ \begin{cases} \sum_{i =1}^{n} C_i x_i \leqslant 0 \\\ 1 + \left( \sum_{i=1}^{n}x_i \right) \leqslant n \end{cases} $$
  合法的 $x_i$ 取值方案数（注意此时 $x_i$ 未知），其中
  $$ C_i = \begin{cases} n-i+1 && i > \left\lfloor \frac{n}{2} \right\rfloor + 1 \\\ i-2 && i \leqslant \left\lfloor \frac{n}{2} \right\rfloor + 1 \end{cases} $$
  这是一个线性约束条件，对 $i$ 归纳，只要 $x_1$ 满足约束
  可以递推出其余的 $x_2 \cdots x_n$ 方案
  化简得到
  $$ \begin{cases} x_1 \leqslant (n-1) - \left( \sum_{i=2}^{n} x_i \right) \\\ x_1 \geqslant \sum_{i=2}^{n} C_ix_i \end{cases} $$
  将不等式看作关于 $x_1$ 取值区间的两个端点，$x_1$ 能取的值一共有
  $$ \textbf{cnt} = \max\left( 0, n - \sum_{i=2}^{n}(C_i + 1)x_i \right) $$
• 这个问题可以用 $O(n^2)$ 的 dp 解决
  假设满足 $\sum_{i=2}^{n}\left( C_i+1 \right) x_i = P$，此时对于$\{x_i\}$ 序列，合法的方案数有 $f(P)$ 个
  （注意此时 $x_i$ 未知）
  则最后的答案是
  $(n-P) \cdot f(P)$
• $f(P)$ 可以通过完全背包的刷表法解决
  $f(P) = \sum_{i=2}^{n} (C_i+1)x_i$，此时背包的物品种类 $i \in [2, n]$
  每一种物品的个数 $x_i$ 未知，但每一种物品可以重复选
  第 $i$ 种物品的体积为 $V_i = C_i+1$
  $\sum V_ix_i = P$ 其实相当于背包的容积为 $P$，$P \in [0 \cdots n]$，对于第 $i$ 阶段递推式
  $P \in [V_i\cdots n]$
• $f(i,P) \leftarrow f(i,P) + f(i, P-V_i), \quad P\in [V_i \to n]$
  $f(0) = 1$，此时我们有 $\forall i, \ x_i = 0$

const int maxn = 5000 + 10;
int n, m, C[maxn];
ll f[maxn];

void prework() {
    for (int i = 1; i <= n; i++) {
        int mid = n / 2;
        if (i > mid + 1) C[i] = n-i+2;
        else C[i] = i-1;
    }
}

void dp() {
    memset(f, 0, sizeof f);
    f[0] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = C[i]; j <= n; j++) {
            f[j] = (f[j] + f[j-C[i]]) % m;
        }
    }

    ll ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = (ans + 1ll * (n-i) * f[i]) % m;

    }
    printf("%lld\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m;

    // prework
    prework();
    // dp
    dp();
}