Một dãy ngoặc hợp lệ là một xâu chỉ gồm các ký tự ngoặc mở và ngoặc đóng, được định nghĩa như sau:

• Xâu rỗng là một dãy ngoặc hợp lệ;

• Nếu ~S~ là một dãy ngoặc hợp lệ thì (S), [S] và {S} cũng là các dãy ngoặc hợp lệ;

• Nếu ~A~ và ~B~ là hai dãy ngoặc hợp lệ thì xâu ghép của ~A~ và ~B~ cũng là một dãy ngoặc hợp lệ.

An có một dãy ngoặc hợp lệ, nhưng một số ký tự trong dãy đã bị lem mực và được biểu diễn bởi ký tự '?'. Mỗi ký tự '?' có thể được thay thế bởi một trong sáu ký tự ngoặc '(', ')', '[', ']', '{', '}'.

Yêu cầu: Hãy đếm số cách thay thế các ký tự '?' để thu được một dãy ngoặc hợp lệ.

Input

• Dòng đầu tiên gồm số nguyên dương ~N~, là độ dài của dãy ngoặc;

• Dòng thứ hai gồm một xâu có độ dài ~N~, chỉ chứa các ký tự '(', ')', '[', ']', '{', '}' và '?'.

Output

In ra số cách thay thế để thu được một dãy ngoặc hợp lệ, lấy phần dư theo ~10^5~.

Scoring

Sample Input 1

8
[{????)]

Sample Output 1

10

Sample Input 2

24
{[????[??????]})????????

Sample Output 2

15106