408720: GYM103270 J Particular Pupper

Edison is a smart pupper but he's very particular about the amount of food he eats. He insists that the number of kibbles in his bowl must be an integer with exactly $$$n$$$ non-zero digits. However, Edison has even more rules for his food.

Edison has two favorite digits $$$x$$$ and $$$y$$$. He considers a number to be 'excellent' if its decimal representation consists of only $$$x$$$ and $$$y$$$ and the sum of all of its digits also only consists of $$$x$$$ and $$$y$$$ in its decimal representation. For example, if Edison's favorite digits are $$$1$$$ and $$$3$$$ then $$$111$$$ and $$$11333$$$ are excellent but $$$13$$$ and $$$31$$$ aren't.

Given Edison's favorite two digits $$$x$$$ and $$$y$$$ as well as his requirement for the number to be an excellent number with $$$n$$$ non-zero digits, tell Edison how many numbers satisfy his constraints. Note, this answer may be quite large so he will be happy if you give the answer modulo $$$1000000007$$$ $$$(10^9 + 7)$$$.

The first and only line of input contains three space-separated integers, $$$x$$$, $$$y$$$, and $$$n$$$ where $$$x$$$ and $$$y$$$ are Edison's favorite two digits (it could be that $$$x = y$$$) and then $$$n$$$ is the length of the intended amount of food. It is true that $$$1 \leq x, y \leq 9$$$ and $$$1 \leq n \leq 10^{6}$$$.

A single integer representing the number of excellent numbers with exactly $$$n$$$ non-zero digits modulo $$$1000000007$$$ $$$(10^9 + 7)$$$.

1 3 3

1

2 3 10

165