Knowing that a clock wraps around at 12 lets you answer "what time is it in 1000 hours?" without counting every hour.
Clues that point here
→ "Return the answer modulo 10⁹ + 7"
→ Divisibility, GCD, LCM
→ Count primes
→ Huge exponents
→ Count arrangements (nCr)
Not this pattern when
✕ The counts are small enough to simulate directly
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Number Theory and Combinatorics · template
static final long MOD = 1_000_000_007L;
long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
long power(long base, long exp) { // fast exponentiation
long result = 1; base %= MOD;
while (exp > 0) {
if ((exp & 1) == 1) result = result * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return result;
}