Bài tập

Trong hệ thống máy tính lượng tử của tương lai, dữ liệu được mã hóa dưới dạng các chuỗi ký tự đặc biệt, chủ yếu sử dụng các ký hiệu ngoặc đơn. Một chuỗi được coi là Hợp lệ (Valid) nếu nó thỏa mãn các quy tắc cân bằng nghiêm ngặt.

Một Dãy Ngoặc Đúng (Correct Bracket Sequence - CBS) hay còn gọi là Dãy Ngoặc Hợp Lệ, được định nghĩa đệ quy như sau:

• Chuỗi rỗng ("") là một Dãy Ngoặc Đúng.
• Nếu \(S\) là một Dãy Ngoặc Đúng, thì chuỗi \((\text{S})\) cũng là một Dãy Ngoặc Đúng.
• Nếu \(S\) và \(T\) đều là Dãy Ngoặc Đúng, thì chuỗi \(ST\) (nối \(S\) và \(T\)) cũng là một Dãy Ngoặc Đúng.
• Mọi Dãy Ngoặc Đúng chỉ có thể được xây dựng từ các quy tắc trên.

Ví dụ: ()(), (()), "" là các Dãy Ngoặc Đúng; nhưng )(, ((), )(() thì không.

Bạn được giao một chuỗi \(S\) chỉ chứa các ký tự ngoặc đơn '(' và ')' có độ dài \(N\). Nhiệm vụ của bạn là kiểm tra xem chuỗi \(S\) có phải là một Dãy Ngoặc Đúng hay không.

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^6\)) --- độ dài của chuỗi.
• Dòng thứ hai chứa chuỗi \(S\) có độ dài \(N\), chỉ bao gồm các ký tự '(' và ')'.

Output

In ra YES nếu chuỗi \(S\) là một Dãy Ngoặc Đúng. Ngược lại, in ra NO.

Example

2
()

YES

6
(())()

YES

5
()(((

NO

6
(())))

NO

Sau cuộc tấn công tàn khốc của các cỗ máy, dự án YoRHa mới quyết định triển khai một hệ thống an ninh tối tân. Hệ thống này sử dụng các thuật toán mã hóa tiên tiến để đảm bảo thông tin quan trọng luôn được bảo mật. Trọng tâm của hệ thống an ninh này là một cơ chế băm độc đáo, trong đó mỗi mẩu dữ liệu được biểu diễn bằng phép toán toán học \(x^y \pmod{p}\), với \(p\) là một số nguyên tố. Hệ thống này biến đổi mọi đầu vào thành một "chữ ký", một chuỗi dường như ngẫu nhiên mà chỉ các máy chủ của YoRHa mới có thể giải mã.

Tuy nhiên, khi cuộc chiến với các cỗ máy kéo dài, các nhà điều hành bắt đầu lo ngại. Điều gì sẽ xảy ra nếu nhiều mẩu thông tin khác nhau, khi được xử lý bởi thuật toán băm này, lại tạo ra cùng một chữ ký? Điều này có thể dẫn đến một thất bại thảm khốc trong hệ thống an ninh, khi dữ liệu quan trọng bị ghi đè hoặc mất do các vụ "va chạm" trong hàm băm. Để ngăn chặn điều này, nhà điều hành 21O được giao một nhiệm vụ quan trọng: tính toán xem có bao nhiêu đầu vào khác nhau có thể băm thành cùng một chữ ký, cho mọi kết quả đầu ra có thể.

Với mỗi \(k = 1, 2, 3, \ldots, p-1\), nhà điều hành phải phân tích có bao nhiêu cặp số nguyên \((a, b)\) với \(1 \le a, b \le p-1\) thỏa mãn \(a^b \equiv k \pmod{p}\). Bằng cách xác định có bao nhiêu tổ hợp khác nhau tạo ra cùng một kết quả băm, họ có thể đánh giá rủi ro va chạm và điều chỉnh các giao thức an ninh cho phù hợp. Cuộc phân tích này trở thành một cuộc chạy đua với thời gian, vì sự toàn vẹn của hệ thống liên lạc và lưu trữ dữ liệu của YoRHa phụ thuộc vào việc thực hiện thành công nhiệm vụ này. Vận mệnh của cuộc chiến có thể phụ thuộc vào khả năng của nhà điều hành trong việc đảm bảo hệ thống an ninh luôn bất khả xâm phạm.

Input

• Một số nguyên duy nhất \(p\) (\(2 \le p < 100,000\)). Đảm bảo rằng \(p\) là một số nguyên tố.

Output

• Một dòng duy nhất chứa \(p-1\) số nguyên. Số thứ \(k\) là số cặp \((a, b)\) thỏa mãn \(a^b \equiv k \pmod{p}\).

Example

3

3 1 

13

40 4 16 8 10 4 4 10 16 8 4 20 

Scoring

• Subtask 1 (30 điểm): \(p \le 500\).
• Subtask 2 (30 điểm): \(p \le 10000\).
• Subtask 3 (40 điểm): Không có ràng buộc gì thêm.

Xét một lưới \(N \times N\) mà các ô vuông có thể có bẫy. Không được phép di chuyển vào ô có bẫy.
Nhiệm vụ của bạn là tính số đường đi từ ô trên cùng bên trái (ô \((1, 1)\)) đến ô dưới cùng bên phải (ô \((N, N)\)). Bạn chỉ có thể di chuyển sang phải hoặc xuống dưới.

Input

• Dòng đầu tiên chứa một số nguyên \(N\): kích thước của lưới (\(1 \le N \le 1000\)).
• \(N\) dòng tiếp theo mô tả lưới. Mỗi dòng có \(N\) ký tự: . là ô trống, và * là ô có bẫy.

Output

• In ra số đường đi modulo \(10^9+7\).

Example

4
....
.*.*
.*..
....

3

Quốc đảo Danglan trên Sao Hỏa có \(n\) ốc đảo được đánh số từ 1 đến \(n\), ốc đảo thứ \(i\) có số hiệu là một số nguyên dương \(a_i\). Quốc đảo có kế hoạch xây dựng các cây cầu nối giữa các ốc đảo với nhau như sau: Một cây cầu sẽ được xây dựng nối ốc đảo \(i\) với ốc đảo \(j\) nếu và chỉ nếu \(a_i \& a_j = 0\), với & là phép toán thao tác bit AND.

Phép toán thao tác bit AND là phép toán luận lý AND trên mỗi cặp bit tương ứng bằng cách nhân chúng lại với nhau, nếu cả hai bit ở vị trí được so sánh đều là 1 thì kết quả là 1, ngược lại thì kết quả sẽ là 0. (Kí hiệu phép toán AND trong Pascal là: and, trong C++ là &).

Ví dụ: \(3 \& 5 = 1\) vì trong hệ nhị phân biểu diễn nhị phân của \(3 = 0011_2\) và \(5 = 0101_2\):

  0011 (số thập phân là 3)
& 0101 (số thập phân là 5)
= 0001 (số thập phân là 1)

Sau khi hoàn thành việc xây dựng các cây cầu, giữa hai ốc đảo nếu có đường đi đến với nhau (thông qua một hoặc một số cây cầu liên tiếp nhau) thì cùng thuộc một quần đảo.

Yêu cầu: Hãy xác định số lượng quần đảo trên quốc đảo Danglan sau khi hoàn thành việc xây dựng các cây cầu theo kế hoạch đã đề ra.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) (\(n \le 2^m\)) tương ứng là số ốc đảo và chiều dài nhị phân của các số hiệu.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i < 2^m\)) tương ứng là số hiệu của các ốc đảo dưới dạng thập phân. Dữ liệu đảm bảo các số hiệu này là phân biệt.
• Các số trong tệp cách nhau một dấu cách.

Output

• Ghi ra một số nguyên duy nhất là số quần đảo của quốc đảo Danglan.

Example

5 3
3 5 0 6 7

1

Scoring

• Số test ứng với 30% số điểm của bài có: \(n \le 1000\) và \(m \le 20\);
• Số test ứng với 30% số điểm của bài có: \(n \le 2^m\) và \(m \le 15\);
• Số test còn lại ứng với 40% số điểm của bài có: \(n \le 2^m\) và \(m \le 20\).