Ban đầu bạn được cho một dãy ngoặc đúng ~S~. Gọi ~S'~ là một dãy ngoặc đúng bất kì thu được bằng cách xoay tròn ~S~ với số lần tùy ý.

Nhiệm vụ là đếm số lượng ~S'~ phân biệt.

Dãy ngoặc đúng: Một dãy ngoặc ~S~ được gọi là đúng khi thỏa một trong các điều kiện:

• ~S = ( T )~ với ~T~ là một dãy ngoặc đúng.
• ~S = S_1 + S_2~ với ~S_1~ và ~S_2~ là các dãy ngoặc đúng.

Ví dụ: ~()~, ~()(())~, ~(()())~ là các dãy ngoặc đúng. ~)~, ~(()~ không phải dãy ngoặc đúng.

Xoay tròn: Một phép xoay tròn của một xâu là mang kí tự cuối của xâu đó về vị trí đầu, ví dụ ~S_1S_2..S_{n-1}S_{n}~ sau khi xoay tròn sẽ thành ~S_{n}S_1S_2..S_{n-1}~.

Ví dụ: ~(())~ sau khi xoay tròn sẽ thành ~)(()~.

Input

Dòng đầu chứa số nguyên dương ~N~ - độ dài của dãy ngoặc đúng ~S~.

Dòng thứ hai chứa dãy ngoặc đúng ~S~ bất kì.

Output

Số lượng ~S'~ phân biệt là dãy ngoặc đúng thu được khi xoay tròn ~S~.

Scoring

• Subtask 1 (50%): ~|S| \leq 2 * 10^3~
• Subtask 2 (50%): ~|S| \leq 2 * 10^6~

Sample input 1

4
(())

Sample output 1

1

Sample input 2

6
()(())

Sample output 2

2

Notes

Ở ví dụ 1 chỉ duy nhất ~(())~ là dãy ngoặc đúng.

Ở ví dụ 2 có 2 dãy ngoặc đúng là ~()(())~ và ~(())()~.