pascal

Triunghiul lui Pascal este un aranjament geometric de numere ce poartă numele celebrului matematician francez Blaise Pascal (19 iunie 1623 – 19 august 1662), deoarece el a fost prima persoană care a descoperit importanţa tuturor modelelor din componenţa acestuia.

Triunghiul începe cu numărul $1$. Acest rând este considerat rândul $0$ al triunghiului. Restul numerelor din acest triunghi se formează ca suma celor două numere de deasupra (considerând că toate numerele din afara triunghiului sunt întotdeauna zero). Prin urmare, rândul $1$ va fi format din $1 = 0 + 1$, $1 = 1 + 0$, iar rândul $2$ va fi format din $1 = 0 + 1$, $2 = 1 + 1$, $1 = 1 + 0$.

Fie $n$ și $p$ două numere naturale nenule cu proprietățile:

• $p$ este număr prim;
• $n+1$ este o putere naturală a lui $p$.

Notăm cu $M(p)$ numărul de multipli de $p$ din primele $n+1$ rânduri ale triunghiului lui Pascal.

Cerință

Să se scrie un program care citeşte numerele naturale $n$ şi $p$ și determină numărul $M(p)$.

Date de intrare

Fișierul de intrare pascal.in conține pe prima linie numerele naturale $n$ și $p$ separate printr-un spațiu.

Date de ieșire

Fișierul de ieșire pascal.out va conține pe prima linie numărul $M(p)$ cu semnificația de mai sus.

Restricții și precizări

• $2 \leq n \leq 10^9$
• $2 \leq p \leq 10^3$
• $30\%$ din teste au $n \leq 10^4$.
• $50\%$ din teste au $n \leq 10^6$.

Exemplul 1

pascal.in

7 2

pascal.out

9

Explicație

În primele $8$ rânduri ale triunghiului se găsesc $9$ multipli de $2$: $2$, $4$, $6$, $4$, $10$, $10$, $6$, $20$, $6$.

Exemplul 2

pascal.in

2196 13 

pascal.out

1660932

Explicație

În primele $2 \ 197$ rânduri ale triunghiului se găsesc $1 \ 660 \ 932$ multipli de $13$.

Exemplul 3

pascal.in

282475248 7

pascal.out

39599936523348201

Explicație

În primele $282 \ 475 \ 249$ rânduri ale triunghiului se găsesc $39 \ 599 \ 936 \ 523 \ 348 \ 201$ multipli de $7$.