小红的可爱括号串

输入描述:

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

输出描述:

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