Beer Barrels

At last you have entered the cellar of your favorite brewery, where you expected to find many large piles of beer barrels. You are eager to inspect the barrels and maybe even their contents (a lot and lot of contents, actually...). Unfortunately, you find only five barrels, all hopelessly empty and dry. Some numbers are painted on the first four barrels, one number on each of them. A note is attached to the fifth barrel. Behind the barrels in the dark, there is a low and barely discernible door in the wall, leading quite obviously to another lower cellar where you hope a whole slew of full barrels is kept hidden. The door is locked with a heavy and complex looking lock. With no obvious further constructive action in mind, you sit down to study the note on the fifth barrel.

Its essence is the following.

Denote the numbers painted on the first, second, third and fourth barrel by A, B, K and C. Numbers A, B and C are just single digits.

Now imagine that in the distant future some incredibly powerful computer (powered by quantum yeast) prints a list of all numbers which have exactly K digits and in which each digit is equal to A or B. Another equally mighty computer then takes the list and also the value C as the input and calculates the number of occurrences of digit C in the whole list.

The resulting number taken modulo 1 000 000 007 is to be typed into the door lock to open it and to gain access to the lower cellar.

You decide to calculate that number in your notebook you took with you.

The input consists of a single line with four integers A, B, K, C (1 ≤ A, B, C ≤ 9, 0 ≤ K ≤ 1000) which represent the numbers painted on the first four barrels.

Output a single integer which opens the door lock.