A fair has n tokens with values 1, 2, ..., n, one of each. A bundle is any subset of the tokens, including the empty bundle. A bundle is even-split if its total value is divisible by n, so it can be shared equally by n people.
Return the number of even-split bundles, modulo 10**9 + 7.
Examples
Input: n = 4
Output: 4
Explanation: {}, {4}, {1, 3} and {1, 3, 4} have totals 0, 4, 4 and 8.
Input: n = 6
Output: 12
Constraints
1 <= n <= 10**12- The exact count has roughly
n / 3.3decimal digits, so it must be found without building it digit by digit, and without any table indexed by sums or residues. - Every value of
nin the range is allowed.
Goals
- Count subsets with a sum condition using a closed formula over divisors
- Factor a number up to 10**12 by trial division and enumerate its divisors with Euler's phi
- Divide exactly under a modulus even when the divisor shares a factor with the modulus