Cerința

Nicușor, primarul capitalei, a fost invitat în seara zilei de 5 septembrie 2024 la jurnalul de seară al Digi 24. Acesta a fost provocat să rezolve o problemă “de clasa a patra” propusă de către o profesoară: “Care este cel mai mic număr natural nenul care are proprietatea că dacă mutăm ultima sa cifră în fața primei cifre, valoarea noului număr este egală cu dublul numărului inițial”. Cu alte cuvinte, acestuia i s-a cerut să găsească cel mai mic număr nenul de forma $\overline{c_1{c}_2\dots c_n}$ cu proprietatea $\overline{c_n{c}_1{c}_2\dots c_{n-1}}=2\times \overline{c_1{c}_2\dots c_n}$.

După ce a rezolvat problema, Nicușor a decis să o generalizeze, astfel propunând o variantă pentru clasa a cincea: Care este cel mai mic număr natural nenul, care, scris in baza b ca ${\overline{c_1{c}_2\dots c_n}}_{(b)}$, are proprietatea că ${\overline{c_n{c}_1{c}_2\dots c_{n-1}}}_{(b)}=a\times {\overline{c_1{c}_2\dots c_n}}_{(b)}$ unde 2 ≤ a < b.

Date de intrare

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

Date de ieșire

Deoarece rezultatul poate fi foarte mare, se va afișa ${\overline{c_1{c}_2\dots c_n}}_{(b)}$ modulo ${10}^9+7$ în baza 10.

Restricții și precizări

• $2\le a<b$
• $a\times b\le {10}^6$
• $c_1,c_n\ne 0$
• pentru 20 de puncte, $b=10$

Exemplu :

Intrare

2 10

Ieșire

157894743

Explicație

Exemplul corespunde cu întrebarea primită de Nicușor Dan. Răspunsul este $105263157894736842$.