D. Математикийн лекц

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

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

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

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

Амар Математикт дургүй ба амархан уйдчихдаг тул Математикийнхаа лекцэн дээрээ унтчихдаг байжээ. Нэг удаа багш нь Амарыг унтаж байсан хэмээн сэжиглэн түүнээс асуулт асууж гэнэ.

Эхлээд багш Амарт хоёр бүхэл тоо $n$ ба $k$-г өгнө. Тэгээд Амараас дараах нөхцлийг хангах $x > 0$ бүхэл тоо хичнээн байхыг асуужээ:

  • $x$-н (тэгээр эхлээгүй гэж тооцно) аравтын бичлэгт яг $n$ цифр байна;
  • Дараахь нөхцлийг хангах $y > 0$ бүхэл тоо оршин байдаг:
    • $y\ mod\ k = 0$;
    • $y$-н аравтын бичлэг нь $x$-н аравтын бичлэгийн ямар нэгэн сүүл хэсэг нь байна.

($S$ тэмдэгт мөрийн "сүүл хэсэг" гэдэг нь энэ тэмдэгт мөрийг урдаас нь арилгах замаар гаргаж чадах хоосон биш тэмдэгт мөрийг хэлнэ)

Хариу хэт том тоо байж болох тул Амар хариугаа $m$-д хуваан үлдэгдлийг нь хэлэхэд болно.

Амарт энэхүү хүнд байдлаас гарахад нь туслаарай.

Оролт

Оролтонд $n, k, m$ ($1 ≤ n ≤ 1000$, $1 ≤ k ≤ 100$, $1 ≤ m ≤ 10^{9}$) гэсэн гурван бүхэл тоо байна.

Гаралт

Хариуг $m$-д хуваасан үлдэгдлийг хэвлэнэ.

Орчуулсан: Бат-Од

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

Оролт
1 2 1000
Гаралт
4
Оролт
2 2 1000
Гаралт
45
Оролт
5 3 1103
Гаралт
590
Сэтгэгдлүүдийг ачааллаж байна...