Given distinct digits x and y$,$ a positive number Mis "compact" if the number obtained by adding the digits of M can only have x or y as its digits. For example if x$=2$ y$=3$ all of the following are valiosum of digits of a compact number: $22,33,23$

HISTORY

RULES

Find the number of "compact" numbers of length exactly n Since the answer can be large, return answer modulo $1$e$9+7$ as output

$6$ README

Constraints: $1<=$x y$<=91<=$n$<=1000$

SETTINGS

Sample

INPUT $($x$,$y$,$n$)(1,2,2)$

OUTPUT $18$