你有聽過病嬌模擬器嗎？

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

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

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

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

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

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

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

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

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

例如：{??}可以有{}{}和{{}}和{()}三種可能性，而{??)只有{}()一種可能性。

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