小红有一个长度为 的括号串，仅包含左括号和右括号。如果一个括号串长度为偶数，并且左半部分都是左括号，右半部分都是右括号，左括号的数量和右括号的数量相等，那么这个括号串就是可爱的括号串。 现在小红想知道给定的括号串中有多少个子序列组成的括号串是可爱的。 如果字符串 可以通过删除字符串 中的若干（可能为零或全部）元素得到，则字符串 是字符串 的子序列。

输入描述:

第一行输入一个整数  表示括号串的长度。第二行输入一个长度为  ，且仅包含左右括号的括号串。

输出描述:

输出一个整数，表示给定的括号串中有多少个子序列组成的括号串是可爱的。由于答案可能很大，请将答案对 取模后输出。