תיאור הבעיה

עבור מספר שלם $n$ ($1 \le n$), המחרוזת הנוצרת על ידי הצבה לסירוגין של $n+1$ מופעים של 'I' ו-$n$ מופעים של 'O', החל מ-'I', נקראת $P_n$. כאן 'I' ו-'O' הן אותיות גדולות באנגלית.

• $P_1$: IOI
• $P_2$: IOIOI
• $P_3$: IOIOIOI
• $P_n$: IOIOIO $\cdots$ OI ($n$ מופעים של 'O')

איור 1-1: המחרוזת $P_n$ עבור מספר שלם $n$ ($1 \le n$)

בהינתן מספר שלם $n$ ומחרוזת $s$ המורכבת אך ורק מ-'I' ומ-'O', כתבו תוכנית המדפיסה בכמה מקומות במחרוזת $s$ מופיעה המחרוזת $P_n$.

קלט

הקלט מורכב מ-$3$ שורות: - בשורה ה-$1$ כתוב מספר שלם $n$ ($1 \le n \le 1000000$). - בשורה ה-$2$ כתוב מספר שלם $m$ ($1 \le m \le 1000000$), כאשר $m$ מייצג את מספר התווים במחרוזת $s$. - בשורה ה-$3$ כתובה המחרוזת $s$, המורכבת אך ורק מ-'I' ומ-'O'.

בכל נתוני הבדיקה מתקיים $2n + 1 \le m$. בנוסף, עבור $50\%$ מהניקוד מתקיים $n \le 100$ וכן $m \le 10000$.

פלט

הדפיסו שורה $1$ בלבד המכילה מספר שלם המייצג בכמה מקומות במחרוזת $s$ מופיעה המחרוזת $P_n$. אם $P_n$ אינה מופיעה כלל ב-$s$, הדפיסו את המספר השלם $0$.

Sample 1

1
13
OOIOIOIOIIOII

4

Sample 2

2
13
OOIOIOIOIIOII

2

הסבר לדוגמאות

כאשר המספר השלם $n$ הוא $1$ והמחרוזת $s$ היא OOIOIOIOIIOII, המחרוזת $P_1$, כלומר IOI, מופיעה ב-$4$ מקומות כפי שמוצג באיור 1-2 להלן, ולכן המספר השלם שיש להדפיס הוא $4$.

OOIOIOIOIIOII
  ^^^
    ^^^
      ^^^
         ^^^

איור 1-2: במקרה של דוגמה 1, המחרוזת $P_1$ מופיעה ב-$4$ מקומות

כאשר המספר השלם $n$ הוא $2$ והמחרוזת $s$ היא OOIOIOIOIIOII, המחרוזת $P_2$, כלומר IOIOI, מופיעה ב-$2$ מקומות כפי שמוצג באיור 1-3 להלן, ולכן המספר השלם שיש להדפיס הוא $2$.

OOIOIOIOIIOII
  ^^^^^
    ^^^^^

איור 1-3: במקרה של דוגמה 2, המחרוזת $P_2$ מופיעה ב-$2$ מקומות