Work#5225
Watson is engaged in important work. From the sequence 1, 2, \ldots, N, he randomly chooses a strictly increasing subsequence of length . Rybka wants to join in, but Watson refuses to share the chosen numbers directly; instead, he agrees to tell, for each selected number, whether it is prime or not.
To proceed, Rybka needs to uniquely determine the values of the chosen subsequence based solely on Watson's primality answers. Your task is to count how many items in the subsequence Rybka can uniquely identify.
The first line contains two integers and .
The second line contains a string of characters, each either or , describing the subsequence: the -th character is if the -th element in the subsequence is prime, and if it is not.
0 \le N, M < 3 \cdot 10^4 (M \le N).
Print a single integer: the number of elements from the subsequence that Rybka can uniquely determine.
Example 1
In the first sample, there are exactly three primes: .
In the second sample, there are three integers which are not prime: .
In the third sample, the first number can be or , the second number must be , and the third must be .
In the fourth sample, possible options include ; ; and so on. No number can be uniquely determined.