终于，你进入了你心仪的啤酒厂酒窖，本以为那里会堆放着成堆的啤酒桶。你迫不及待地想要检查这些桶，甚至想看看里面的内容（实际上，内容非常非常多……）。不幸的是，你只发现了五个桶，它们全都空空如也，干涸见底。前四个桶上各画着一个数字，第五个桶上贴着一张纸条。在黑暗的桶后，墙上有一扇低矮且几乎难以察觉的门，显然通往另一个更深层的酒窖，你希望那里藏着一大堆装满酒的桶。门上锁着一把看起来沉重而复杂的锁。在没有其他更好的办法的情况下，你坐下来研究第五个桶上的纸条。

纸条的内容如下：

将画在第一、第二、第三和第四个桶上的数字分别记为 $A$、$B$、$K$ 和 $C$。数字 $A$、$B$ 和 $C$ 均为个位数。

现在想象一下，在遥远的未来，某台功能极其强大的计算机（由量子酵母驱动）打印出了所有满足以下条件的数字列表：这些数字恰好有 $K$ 位，且每一位数字都等于 $A$ 或 $B$。随后，另一台同样强大的计算机以该列表和数值 $C$ 作为输入，计算出数字 $C$ 在整个列表中出现的总次数。

将所得结果对 $1\,000\,000\,007$ 取模，即为打开门锁所需的密码，输入该密码即可进入下层酒窖。

你决定用随身携带的笔记本计算出这个数字。

输入格式

输入包含一行，由四个整数 $A, B, K, C$ ($1 \le A, B, C \le 9, 0 \le K \le 1000$) 组成，分别代表画在前四个桶上的数字。

输出格式

输出一个整数，即打开门锁的密码。

样例

输入 1

1 2 3 2

输出 1

12

输入 2

6 5 2 6

输出 2

4