Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
C. Гоё тоонууд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Виталя бол маш сонин хүн. Тэр $a$ ба $b$ гэсэн хоёр тоонд дуртай. Хэрвээ тухайн аравтын тооны орон нь $a$ ба $b$ тоонуудыг агуулж байвал уг тоог Виталя сайн эерэг бүхэл тоо гэж нэрлэдэг. Хэрвээ оронгуудын нийлбэр нь сайн тоо бол тэр тоог Виталя маш сайн тоо гэж нэрлэдэг.
Жишээлбэл Виталя-гийн дуртай тоонууд нь $1$ ба $3$ бол $13$ болон $311$ нь сайн тоо, $12$ сайн тоо биш юм. Түүнчлэн $111$ нь маш сайн тоо бол $11$ нь сайн тоо биш юм.
Одоо Виталяа яг $n$ урттай тоонд хэдэн ширхэг маш сайн тоо байгаа бол гэж бодож байна. Энэ тоо харьцангуй их байж болох учир тэр үүнийг хувааж үлдэгдэлийг нь тоолж асууна $1000000007$ $(10^{9} + 7)$.
Тооны урт гэдэг нь түүний аравтын төлөөлөл нь тэгээр эхлээгүй оронгийн тоо юм.
Оролт
Эхний мөрөнд гурван бүхэл $a$, $b$, $n$ $(1 ≤ a < b ≤ 9, 1 ≤ n ≤ 10^{6})$ гэсэн тоонууд агуулагдана.
Гаралт
Нэг мөрөнд бодлогын хариултыг $1000000007$ $(10^{9} + 7)$ гэж модулиар хэвлэнэ.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
1 3 3
Гаралт
1
Оролт
2 3 10
Гаралт
165