题目描述

给出一段只包含'('')'的括号序列，你可以在任两个字符之间切割，最多切k次，每个间隙只能切割一次，要求最后切出来的每个括号片段都是合法的括号序列， 问一共有多少种切法。 合法的括号序列：指对于一个字符串他的左括号数量和右括号一样多，且对于任意前缀左括号始终不小于右括号数。 字符串的前缀：指字符串的从第一个字符开始，到任意字符停止的一个字符串。 左括号为 ‘（’ 右括号为 ‘）’ 答案对1e9+7取模；

输入描述

第一行输入一个字符串S 第二行输入一个数k,表示切割次数。

输出描述

输出一个整数，表示符合要求的方案数。

样例输入1

()(())
1

样例输出1

2

样例输入2

(()
2

样例输出2

0

数据范围

$|S|$ <= $2e5$

$k$ <= $1e9$

子任务1:(20分)

$|S|$ <= $3e3$

子任务2:(30分)

$|S|$ <= $2e5$