题目内容

深海观光廊沿一条直线走廊打下了 $n$ 根桩标。运维班组要按桩标序列划分气密舱：用字符 ( 记下某段气密舱的开启桩，用字符 ) 记下对应的闭合桩。整份日志必须合法：从左到右扫描任意前缀时，开启次数不少于闭合次数；扫描完整串后，两种标记的次数相等。

每个闭合桩与它左侧最近的、尚未配对的开启桩配成一段舱。设一对匹配桩标的位置为 $L,R$（$1 \le L < R \le n$）。这段舱的内部长度定义为 $R-L-1$，也就是位置 $L+1,L+2,\ldots,R-1$ 上桩标的个数。

补给模块按模 $m$ 投放。请统计内部长度能被 $m$ 整除的舱段数量。特别地，0 能被任意正整数整除。

约束：

• 2 $\le$ $n$ $\le$ 200000
• 1 $\le$ $m$ $\le$ $n$
• $n$ 保证为偶数
• 字符串仅含 ( 与 )，且保证合法

输入描述

第一行两个整数 $n$ 和 $m$（2 $\le$ $n$ $\le$ 200000，1 $\le$ $m$ $\le$ $n$），分别表示桩标数量和整除模数。保证 $n$ 为偶数。

第二行一个长度为 $n$ 的字符串 $t$，仅由 ( 和 ) 组成，且为合法的嵌套记录。

输出描述

输出一个整数，表示内部长度能被 $m$ 整除的舱段数量。

样例1

输入

2 1
()

输出

1

说明

唯一一对开启-闭合桩标占据位置 1 与 2，内部长度为 $2-1-1=`0`$。0 能被 1 整除，因此答案为 1。

样例2

输入

6 3
(()())

输出

2

说明

三对匹配舱段的内部长度分别是：

• 位置 2 与 3：内部长度 0
• 位置 4 与 5：内部长度 0
• 位置 1 与 6：内部长度 4

0 能被 3 整除，4 不能，因此答案为 2。

样例3

输入

8 5
((()()))

输出

2

说明

四对匹配舱段的内部长度依次为 0、0、4、6。只有两个 0 能被 5 整除，4 与 6 都不能，因此答案为 2。