Робота#5225
Ватсон займається важливою справою. З послідовності 1, 2, \ldots, N він випадковим чином вибирає строго зростаючу підпослідовність довжини . Рибка теж хоче приєднатися, але Ватсон відмовляється повідомити обрані числа безпосередньо; натомість погоджується для кожного із обраних чисел сказати, є воно простим чи ні.
Щоб виконати завдання, Рибка повинна, за отриманим описом простоти чисел, визначити, які числа підпослідовності вона може встановити однозначно. Ваше завдання — визначити кількість елементів підпослідовності, які Рибка може встановити однозначно.
У першому рядку задано два цілих числа та .
У другому рядку міститься рядок з символів, кожен з яких є або , — опис підпослідовності: -ий символ , якщо -ий елемент підпослідовності простий, і , якщо ні.
0 \le N, M < 3 \cdot 10^4 (M \le N).
Виведіть одне число — кількість елементів підпослідовності, які Рибка може визначити однозначно.
Приклад 1
У першому прикладі рівно три простих числа: .
У другому прикладі три числа не є простими: .
У третьому прикладі перше число може бути або , друге число повинно бути , а третє — .
У четвертому прикладі можливі варіанти: ; і так далі. Жодне число не можна визначити однозначно.