Hide
Problem C
Avoiding Subsequence
Languages
en
is
You are given a pattern string $S$. Find the number of words consisting of upper case English characters of length $n$ such that $S$ does not appear as a subsequence in that word.
Input
The first line of input contains a string of upper case English characters of length at least $1$ and at most $100$. This is the pattern $S$. The second and last line of input contains a positive integer $n$ satisfying $1 \leq n \leq 10^{18}$, the length of the words to count.
Output
Print the number of words consisting of upper case English characters of length $n$ that do not contain $S$ as a subsequence. Because this value might be very big, print it modulo $10^9 + 7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
ABBA 4 |
456975 |
| Sample Input 2 | Sample Output 2 |
|---|---|
X 20 |
697814725 |
