TopCoder

LittlePants
生命誠可貴,JK價更高,若為蘿莉故,兩者皆可拋

User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

61.1% (22/36)

Tags

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 1

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

Sample Output 1

3
1
1
8
0

Hints

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

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 20
2 1 10
3 2 20
4 3 10
5 4 10
6 5 20
7 6 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7