TopCoder

Thumb ya2
赤ずきんチャチャ
もっと心の中を二人見せ合えたなら 答えはつかめるよ

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

46.2% (6/13)

Description

你有聽過病嬌模擬器嗎?

這是一個模擬遊戲,主角是一位清純高中女生,為了追求喜歡的學長,和其他同學或好朋友們,譜出的浪漫愛情故事。
有興趣可以到網路上找相關的實況影片,不過因為太浪漫了,最好不要在吃飯的時候看,看的時候也要注意背後有沒有人。

雖然這是一款逼真的高自由度模擬遊戲,不過這不是我們今天的重點。

事情是這樣的,果茶在看到周逸和芭樂和他們的同學們遊玩病嬌模擬器後,被其中炫麗的動畫、觸動人心的劇情感動,於是也打算來做一款遊戲「CP模擬器」。

由於是第一次做遊戲,果茶就不打算在動畫劇情上做太多功夫了,他決定把重點放在CP系統上。
所謂的CP,就是男生和女生一起去圖書館讀書、一起去喝星冰樂或是一起去宜蘭玩等等,CP系統就是一個幫線上玩家配對的系統。

簡單的配對倒是沒什麼,但是這個CP系統最厲害的是,他可以透過分析所有個性和適合度,找出最適合的CP。
但是太多的可能性可能會讓果茶的古董伺服器無法負荷,於是他打算先加些限制。
假設總共有N個人在線上,我們將這些人的性質統計出來,CP模擬器就可以幫這些人配對。
在CP模擬器分析結束後,會用上括號和下括號代表一組配對,而且總共會有兩種類型,分別用大括號和小括號表示,只有上大括號可以和下大括號配對,同理只有上小括號可以和下小括號配對。
因為系統的設計,所以CP模擬器會用一行來顯示所有的配對,每個下括號會和她左邊第一個未配對的上括號配成一對,而且允許巢狀的結構,也就是如果她左邊也是下括號的話,會先配對完她左邊的下括號再來配對她。

例如:{}(){()}{{}}(())都是合法的配對。

而例如:{(}){})都是不合法的配對,前者因為大括號配對到了小括號,後者因為多出一個下小括號無法被配對。

為了減少運算量,我們會限制最大深度K,所謂的深度就是同一時間未配對的上括號數量,比如(){({()})}{}{{(){{}}}}的最大深度都是4,其中第二組,因為再唯一的一組小括號配對後會變成{{{{}}}},所以深度也是4。

一切本來都很順利,直到果茶發現有些人的性質無法被CP模擬器辨識,這些人會被辨識成?(問號)。
因為這些問號無法被辨識類別,甚至連性別也不一定清楚,為了評估伺服器可不可以承受這種複雜運算,果茶決定至少先計算出最後會有多少種不同的情況,再來考慮怎麼修改他的演算法。

例如:{??}可以有{}{}{{}}{()}三種可能性,而{??)只有{}()一種可能性。

現在給你一些CP模擬器的運算結果,請你告訴果茶,最多總共會有幾種不同的情況。

Input Format

第一行有一個整數T代表測資筆數,
每筆測資有兩行,
第一行有一個整數K,代表最大的深度。
第二行有一個字串S,代表需要處理的運算結果。

對於20%的測資:
$ K = 1 $

對於另外20%的測資:
$ 1 \leq K \leq 10 $
$ |S| \leq 30 $
問號的數量不超過16。

對於另外20%的測資:
$ 1 \leq K \leq 10 $
$ |S| \leq 100 $

對於所有的測資:
$ 1 \leq T \leq 10 $
$ 1 \leq K \leq 12 $
$ |S| \leq 1000 $

Output Format

對於每筆測資,輸出一個整數代表答案,答案請$mod 10^ 9 + 7$,如果沒有任何合法的可能性則輸出0。

Sample Input

5
2
{??}
1
{??}
2
{??)
10
????
10
{)??

Sample Output

3
1
1
8
0

Hints

後來,大部分的括號都被其中一個括號解決掉了,剩下的括號過著幸福快樂的日子,可喜可賀、可喜可賀。

Problem Source

題目:周逸
題目敘述&測資:果茶
2016建中資訊校隊補選pE

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 20
For Testdata: 6 ~ 6, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144