Curse word P33851

This problem is based upon a true story. One day, Professor Oak realized that his flat had no insurance for several years, so his plan was to find a good deal and sign an insurance in a week. Only two days later (still with no insurance) he received a phone call alerting him that a huge water leak from his flat had seriously affected five other flats. The thoughts that crossed Prof. Oak’s mind were so outrageous that, later, he tried to excuse himself through combinatorial arguments. He pretended that he had just thought a random string. Because, there are so many strings that contain a given curse word, right?

Input

Input consists of several cases, each with a curse word s and two natural numbers n and m. Assume 1 ≤ | s | ≤ 10, | s | ≤ n ≤ 10⁹, 1 ≤ m ≤ 26, and that s has only lowercase letters chosen among the first m of the alphabet.

Output

For every case, print the number of words made up of exactly n lowercase letters chosen among the first m of the alphabet that contain the substring s one or more times. Since this number can be very large, compute it modulo 10⁹ + 7.