== include(page="template/taskheader" task_id="wordle") ==

== include(page="template/taskheader" task_id="police") ==

The new, popular word game Wordle spreads so fast that its contagiousness has reached Luca.

Fearsome William is still free, and the Police is searching him in Murder Boulevard!

For those of you who have not yet heard about it, in Wordle you have to guess a 5-letter word in a limited number of attempts. After each attempt you get to know, for each position, whether your guess had the right letter in the right position, a letter present in the word but not in the right position, or a completely wrong letter.

This street is $L$ meters long, and currently William is at $x=0$, trying to reach his nest at $x=L$.

Intrigued by the characteristics of the word game, Luca has decided to create his own more generic version. In this version, one needs to guess an $N$-letter word. Every possible sequence of letters of the English alphabet constitutes a potentially valid guess, but it is guaranteed that the word to guess does not contain the same letter twice.

Along this street there are $N$ semaphores at positions $X[i]$.

You are in the middle of a game: you already guessed some letters but you still have to figure out some of them, which are indicated in the input with an underscore (_). You wonder: how many words could be a valid solution for the game, given the letters you know?

All the traffic lights are synchronized: at $t=0$ the green triggers, and will stay green for $T$ seconds; at $t=T$ the red triggers, and will stay red for $T$ seconds; and then the cycle repeats.
 
William wants to reach his nest as quickly as possible, but he doesn't want to attract too much attention.
 
Therefore, he travels at a constant speed of $1$ meter per second (the speed limit), and he will stop and wait if he's at a red semaphore.
 
Since he's very impatient, sometimes he may cross the red semaphore without waiting for the green, but he can do so at most $R$ times.
 
Which is the least amount of time William needs to reach his nest?

h2. Date de intrare

The first line of the input file $wordle.in$ contains the only integer $N$. The second line contains $N$ letters $L[i]$: either an uppercase letter of the English alphabet or an underscore.

The first line of the input file $police.in$ contains 4 integers: $N$ (the number of semaphores), $R$ (the number of semaphores William can skip), $T$ (the half-period of the semaphores), and $L$ (the length of the street).
 
The second line contains $N$ integers: the coordinates X[i].

h2. Date de ieşire

The output file $wordle.out$ contains a single line with an integer: the number of possible solutions.

The output file $police.out$ contains a single line with an integer: the minimum time in seconds that will be needed to reach the nest.

h2. Restricţii

* $N < L &le; 10^9$
* $X[i] < L$, for each semaphore
* $X[i] < X[i+1]$ for each $i$ from $0$ to $n-2$

* For tests worth $15$ more points, $R = 0$.
* For tests worth $15$ more points, $N ≤ 20$ and $L ≤ 1000$.
* For tests worth $25$ more points, $N, T ≤ 100$ and $L ≤ 1000$.
* For tests worth $15$ more points, $N ≤ 300$.
 

h2. Exemplu