Виталя бол маш сонин хүн. Тэр $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)$ гэж модулиар хэвлэнэ.