D. Роман ба тоонууд

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Роман бол Uzhland-н маш алдартай залуу математикч юм. Харамсалтай нь Сережа үүнтэй санал нийлэхгүй байна. Сережагийн бодлыг өөрчлөхийн тулд Роман ямар нэг математикийн асуудлыг шийдвэрлэхэд бэлэн байна. Жаахан бодсоны эцэст Сережа Романаас $m$ модулиар $n$ тооны ойрхон хэдэн тоо байдгыг асуув.

Дараах тохиолдолд $x$ тоог $m$ модулиар $n$ тооны ойрхон тоо гэж үзнэ:

  • энэ тоог $n$ тооны цифрүүдийг дахин байрлуулж гаргаж авна,
  • энэ тоо нь тэгээр эхлээгүй байна,
  • $x$ тоог $m$-д хуваасны дараа үлдэгдэл нь 0-тэй тэнцүү байна.

Роман бол сайн математикч, гэхдээ ийм тоонуудын тоо түүнд хэтэрхий их байгаа тул тэр чамаас тусламж хүсэж байна.

Оролт

Эхний мөр нь $n$ $(1 ≤ n < 10^{18})$ ба $m$ $(1 ≤ m ≤ 100)$ бүхэл тоонуудыг агуулна.

Гаралт

Нэг мөрөнд нэг бүхэл тоо хэвлэнэ. Энэ нь $m$ модулиар $n$ тооны ойрхон тоонуудын тоо юм.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
104 2
Гаралт
3
Оролт
223 4
Гаралт
1
Оролт
7067678 8
Гаралт
47

Тэмдэглэл

Эхний жишээний шаардсан тоонууд нь: 104, 140, 410.

Хоёр дахь жишээний шаардсан тоо бол 232.

Сэтгэгдлүүдийг ачааллаж байна...