堆石子

题目描述

有 $m$ 堆石子，编号为 $1,2,\cdots,m$，其石子数量分别记为 $a_1, a_2, \cdots, a_m$。

现在要求第 1 堆石子恰有 $n$ 个（即 $a_1 = n$），并且此后每堆石子的数量严格小于前一堆，即 $a_i < a_{i-1}$（$2 \le i \le m$）。此外，每堆至少需要有一个石子，即 $a_i \ge 1$（$1 \le i \le m$）。

在总石子数量不设限制的情况下，给定 $m \ge 2, n \ge 1$，有多少个满足要求的石子堆放方案？

两个方案不同，当且仅当，两个方案中至少有一堆石子数量不同。

如果不存在满足要求的方案，输出 $0$。由于方案数可能很大，请输出方案数对 $10^9+7$ 取模后的结果。

输入格式

输入一行两个正整数 $m$ 和 $n$。

输出格式

输出一个整数，表示总方案数对 $10^9+7$ 取模后的结果。

样例输入 #1

3 5

样例输出 #1

6

样例解释 1

有 $(5,4,3)$、$(5,4,2)$、$(5,4,1)$、$(5,3,2)$、$(5,3,1)$ 和 $(5,2,1)$ 共计 6 种方案。

数据范围

参考程序

#include <iostream>
using namespace std;

const int MOD = (int)1e9 + 7;

int qpow(int base, int exp) {
    if (!exp) return 1;
    if (exp & 1) return (long long)base * qpow((long long)base * base % MOD, exp >> 1) % MOD;
    return qpow((long long)base * base % MOD, exp >> 1);
}

int comb(int n, int m) {
    if (m > n) return 0;
    int ans = 1;
    for (int i = 0; i < m; ++i) {
        ans = (long long)ans * (n - i) % MOD;
        ans = (long long)ans * qpow(i + 1, MOD - 2) % MOD;
    }
    return ans;
}

int main() {
    int m, n;
    cin >> m >> n;
    cout << comb(n - 1, m - 1) << endl;
    return 0;
}