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 \( { a! \over 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 \( { a! \over 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 \( { a! \over b!\ \cdot \ c! }\ =\ {(b+c)!\ \cdot \ (b+c+1)\ \cdot\ (b+c+2) \cdot…\ \cdot (a-1)\cdot\ a \over b!\ \cdot \ c! } = C_{b+c}^{b}\ \cdot (b+c+1) \cdot (b+c+2)\cdot …\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 [ a \over p \right ]+\left [ a \over p^{2} \right ]+\left [ a \over p^{3} \right ]+… \), unde prin \( \left [ x \right ] \) am notat partea întreagă a lui \( x \).

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