Cerința

Se dau a, b, c și p numere naturale, astfel încât a ≥ b + c și p număr prim. Să se afle dacă numărul $\frac{a!}{b!\cdot c!}$ este divizibil cu p, și să se afle exponentul lui p în descompunerea în factori primi a acestui număr.

Date de intrare

Programul citește de la tastatură numerele a, b, c și p, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul e, reprezentând exponentul lui p în descompunerea în factori primi a numărului natural $\frac{a!}{b!\cdot c!}$. Dacă numărul nu este divizibil cu p, atunci se va afișa 0.

Restricții și precizări

• 1 ≤ a , b , c ≤ 1.000.000.000
• a ≥ b + c
• 2 ≤ p ≤ 1.000

Exemplu:

Intrare

12 4 5 3

Ieșire

3

Explicație

Știm de la matematică faptul că numărul $\frac{a!}{b!\cdot c!}=\frac{(b+c)!\cdot (b+c+1)\cdot (b+c+2)\cdot \dots \cdot (a-1)\cdot a}{b!\cdot c!}=C_{b+c}^b\cdot (b+c+1)\cdot (b+c+2)\cdot \dots \cdot (a-1)\cdot a$ este natural, deci putem vorbi despre divizibilitatea lui prin p ( Numărul $C_{b+c}^b$ reprezintă combinări de $b+c$ elemente luate câte $b$ ).

De asemenea se știe că exponentul numărului prim p în descompunerea în factori primi a numărului a! este $\left[\frac{a}{p}\right]+\left[\frac{a}{p^2}\right]+\left[\frac{a}{p^3}\right]+\dots$, unde prin $\left[x\right]$ am notat partea întreagă a lui $x$.

În exemplul dat avem $\frac{12!}{4!\cdot 5!}=3^3\cdot 7\cdot 8\cdot 10\cdot 11$, deci exponentul este 3.