Эрт үед хоёр хоорондоо тоглодог дараах тоглоом их түгээмэл байлаа. Эхлээд эхний тоглогч $9$-н цифрээс тогтсон $s_1$ тэмдэгт мөр бичнэ. Энэ тэмдэгт мөрөөр дүрслэгдэх тоо нь $a$-аас хэтрэхгүй. Дараа нь хоёр дахь тоглогч $s_1$ тэмдэгт мөрийг харж байгаад $9$-н цифрээс тогтох $s_2$ тэмдэгт мөрийг бичнэ. Энэ дүрслэгдэх тоо нь $b$-ээс хэтрэхгүй.

Энд $a$, $b$ хоёр нь өгөгдсөн тогтмол тоо. $s_1$, $s_2$-г тоглогчид өөрсдөө сонгоно. Тэмдэгт мөр тэгээр эхэлж болно.

Одоо энэ хоёр тэмдэгт мөрийг залгуулсан бичихэд үүсэх тоо ($s_1 s_2$) $mod$-д хуваагдвал хоёр дахь тоглогч хожно. Хуваагдахгүй бол эхний тоглогч хожно. Танд $a$, $b$, $mod$ өгөгдсөн бол алдаагүй тогловол аль тоглогч хожихыг тооцоолж хэлнэ үү. Хэрвээ эхний тоглогч хожих бол эхний тоглогчийн бичих $s_1$-н бага утгыг олно уу.

Оролт

Нэг мөрөнд $a$, $b$, $mod$ ($0 ≤ a, b ≤ 10^9; 1 ≤ mod ≤ 10^7$) бүхэл тоонууд.

Гаралт

Хэрвээ эхний тоглогч хожихоор бол "1" гэж бичээд зай аваад $s_1$-н хамгийн бага утгыг хэвлэнэ. Хоёр дахь тоглогч хожих бол "2" гэж хэвлэнэ.

$s_1$-н хамгийн бага утга гэдэгт $s_1$-н боломжит утгуудын цагаан толгойн эхэнд байрлах утгыг хэлнэ.