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 … c_n}\) cu proprietatea \(\overline{c_n c_1 c_2 … c_{n-1}} = 2 \times \overline{c_1 c_2 … 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 … c_n}_{(b)}\), are proprietatea că \(\overline{c_n c_1 c_2 … c_{n-1}}_{(b)} = a \times \overline{c_1 c_2 … 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 … c_n}_{(b)}\) modulo \(10^9 + 7 \) în baza 10.

Restricții și precizări

• \( 2 ≤ a < b \)
• \(a \times b ≤ 10^6 \)
• \(c_1, c_n \neq 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 \( 105 \, 263 \, 157 \, 894 \, 736 \, 842 \).