D. Тэмдэглэлийн цаас

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

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

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

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

Ник нэгэн хэвийн биш юманд ер бусаар татагддаг сонин зантай билээ. Тэр аравтын тооллын системд дургүй бөгөөд өөр тооллын системийг эзэмшихээр шийджээ.

$b$-тын тооллын систем түүний сонирхлыг татаж байгаа бөгөөд тэр эхлээд тэмдэглэлийн цаасан дээрээ $n$ оронтой бүх тоонуудыг (тоонууд 0-ээр эхлэхгүй) бичиж үзэхийг хүсэж байлаа. Никэд байгаа цаас бүр яг $c$ тоо бичиж хүрэлцэхээр байлаа.

Ник тоонуудыг бичиж байгаад цаас дүүрэнгүүт дараагийн цаасан дээр бичиж эхэлнэ. Тийм бол Ник хамгийн сүүлийн цаасан дээр хэдэн тоо бичиж таарах вэ?

Оролт

Ганц мөрөнд $b$, $n$, $c$ тоонууд зайгаар тусгаарлагдан байрлана. ($2 ≤ b < 10^{10^6}; 1 ≤ n < 10^{10^6}, 1 ≤ c ≤ 10^9$).

Гаралт

Сүүлийн хуудсанд бичигдэх тоонуудын тоо.

Орчуулсан: gmunkhbaatarmn

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

Оролт
2 3 3
Гаралт
1
Оролт
2 3 4
Гаралт
4

Тэмдэглэл

In both samples there are exactly $4$ numbers of length $3$ in binary number system. In the first sample Nick writes $3$ numbers on the first page and $1$ on the second page. In the second sample all the $4$ numbers can be written on the first page.

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