该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

R0 is very interested in numbers. His two favorite digits are $a$ and $b$. So if a positive integer wants to win his favor, this positive integer needs to be $a$ or $b$ in every digit, and the sum of all digits must be a multiple of $k$, because he thinks $k$ is a great divisor.

For example, let's say his favorite numbers are $1$ and $2$, and $k$ is $6$, then number $12$ or $221160$ can't meet the requirements, but numbers $1221$ can.

Now R0 is wondering, how many positive integer of length exactly $n$ are there can get his favor.

As this number can be rather large, he asks you to count the remainder after dividing it by $1000000007 (10^9 + 7)$.

输入格式

The only line contains four integers $a, b, k, n$ $(1 \le a < b \le 9 , 1\le k \le5000, 1 \le n \le 10^{6})$.

输出格式

Print the answer to the problem modulo $1000000007$ ($10^9 + 7$).

样例

1 2 6 2

0

样例

2 3 3 10

341