考点：组合数学 · 数论 · 基础数学

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 元素值域：N ≤ 1e18（注意整数类型选择，避免溢出）
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：组合数学

用计数原理（加法/乘法原理）与组合数公式统计方案数。

思路框架（组合数学 通法 · 非本题专属）

1. 判断是分类计数（相加）还是分步计数（相乘）。
2. 识别是否重复/是否有序，决定用排列 A(n,m) 还是组合 C(n,m)。
3. 组合数递推 C[i][j] = C[i-1][j-1] + C[i-1][j]，或预处理阶乘与逆元。
4. 答案通常要求对 1e9+7 取模。

实现要点：阶乘预处理 + 费马小定理求逆元可以在 O(1) 内算任意组合数。

复杂度：时间 O(n) 预处理 / O(1) 查询 ｜ 空间 O(n)

该范式的通法易错点

• 把排列和组合搞混。
• 取模意义下直接做除法（应乘逆元）。
• 方案数溢出未取模。

对照本题

• 元素值域最大到 1e18 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

• 输入：4
• 输出：1

样例 2

• 输入：6
• 输出：2