почему 1 вычитается из мод, где мод = 1000000007 в расчете

Question

ссылка вопроса

http://codeforces.com/contest/615/problem/D звено раствора http://codeforces.com/contest/615/submission/15260890

В ниже коде я не могу понять, почему 1 вычитается из мод где мод = 1000000007

ll d = 1; 
ll ans = 1; 
for (auto x : cnt) { 
    ll cnt = x.se; 
    ll p = x.fi; 
    ll fp = binPow(p, (cnt + 1) * cnt/2, MOD); 
    ans = binPow(ans, (cnt + 1), MOD) * binPow(fp, d, MOD) % MOD; 
    d = d * (x.se + 1) % (MOD - 1);//why ?? 
} 

Answer 1

Помимо того, что есть код не имеет особого смысла, так как из контекста, как это, есть малая теорема Ферма:

Всякий раз, когда MOD простое число, а 10^9+7 это, можно уменьшить показатели, как

a^(MOD-1) == 1 mod MOD. 

Это означает, что

a^b == a^(b mod (MOD-1)) mod MOD. 

---

Как к кода, который является эффективным для его задачи, рассмотрите n=m*p^e, где m состоящий из простых чисел, меньших, чем p.

Затем для каждого фактора f из m есть факторы 1*f, p*f, ^2*f,...,p^e*f of n. Продукт над всеми факторами n, таким образом, является продуктом над

p^(0+1+2+...+e) * f^(e+1) = p^(e*(e+1)/2) * f^(e+1) 

над всеми факторами f из m. Ввод числа факторов, как d и продукт факторов m как ans результатов в комбинированной формуле

ans = ans^(e+1) * p^(d*e*(e+1)/2) 
d = d*(e+1) 

, который теперь может быть рекурсивно применяется к списку главных факторов и их кратности.