Fişierul intrare/ieşire:	wordle.in, wordle.out	Sursă	IIOT 2021-22 Runda 4
Autor	Giorgio Audrito	Adăugată de	Stefan Dascalescu •stefdascalescu
Timp execuţie pe test	0.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Wordle

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

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.

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.

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?

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.

Date de ieşire

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

Restricţii

• 1 ≤ R ≤ N ≤ 10000
• 1 ≤ T ≤ 1000
• N < L ≤ 10^9
• X[i] < L, for each semaphore
• X[i] < X[i+1] for each i from 0 to n-2

Exemplu

Explicaţie

In the first sample case there are 3 semaphores, of which 1 can be skipped. When William reaches the first semaphore he finds it green, so it will pass.

Then at t=5 he reaches the second semaphore (at x=5), but it is red (since t=3).
He has two choices: wait 1 second that it becomes green, or skip the semaphore.

If he waits, he will start again at t=6, will reach the last semaphore (at t=10) and will skip it since it is red and he still has 1 skip remaining. He reaches his nest at t=11.

If he skips it, he will reach the last semaphore at t=9, but it is red (it just became red). There he has to wait 3 seconds that it becomes green again, leaving it at t=12. He reaches his nest at t=13.

Therefore, the best solution is to wait at the second semaphore and skip the last one, reaching the nest in 11 seconds.

In the second sample case there is only one semaphore.

When William reaches it he finds it red (it just became red), and he will wait since he doesn't have any skip available.

Cum se trimit solutii?