2024.10.26

Xét biểu thức sau: \((x + a)^n\) (với \(a,n\) là số được cho).

Yêu cầu: Khai triển biểu thức trên, tính hệ số bậc \(k\)?

Input

• Một dòng chứa ba số nguyên \(a,n,k\) (\(0 \le a \le 10^9; 1 \le n \le 2 \times 10^5; 0 \le k \le n\)).

Output

• Một dòng chứa một số nguyên duy nhất là kết quả bài toán, do kết quả có thể rất lớn, bạn cần đưa ra kết quả chia lấy phần dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(a = 1, n \le 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 10\).
• Subtask \(3\) (\(25\%\) số điểm): \(a = 1\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

1 2 1

2

Có \(N\) con thỏ được đánh số \(1,2,3,...,N\)

Với mỗi \(i,j(1\le i,j\le N)\), độ "tâm đầu ý hợp" của con thỏ \(i\) và \(j\) được kí hiệu bởi một số nguyên \(a_{i,j}\). Ở đây \(a_{i,i}=0\) với mọi \(i(1\le i\le N),a_{j,i}=a_{i,j}\) với mọi \(i,j(1\le i,j\le N)\).

\(Kaninho\) chia \(N\) con thỏ này thành nhiều nhóm. Ở đây, mỗi con thỏ thuộc về chính xác \(1\) nhóm. Sau khi chia xong, với mỗi cặp \(i,j(1\le i<j\le N)\). \(Kaninho\) sẽ kiếm được \(a_{i,j}\) điểm nếu con thỏ \(i\) và \(j\) cùng thuộc về một nhóm.

Tìm số điểm tối đa mà \(Kaninho\) có thể thu được.

Input

• Dòng thứ nhất chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(a_{i,1},a_{i,2},...,a_{i,N}\) thể hiện độ "tâm đầu ý hợp" của những chú thỏ với nhau.

Output

• In ra kết quả cần tìm.

Constraints

• \(1\le i\le N,|a_{i,j}|\le 10^9\)
• \(1\le N\le 16\)

Example

3
0 10 20
10 0 -100
20 -100 0 

20

Bạn được cho một mảng \(a\) gồm \(n\) số nguyên \(a_1,a_2,...,a_n\). Bạn phải thực hiện \(q\) truy vấn, có hai loại truy vấn:

• "1 l r x": Sử dụng toán tử XOR với số nguyên \(x\) lên tất cả các số nguyên trên đoạn từ \(l\) đến \(r\), nói cách khác: \(a_i = a_i \oplus x \forall i: l \le i \le r\) (\(1 \le l \le r \le n; 0 \le x \le 10^6\)).
• "2 l r": Tính tổng các số nguyên trên đoạn từ \(l\) đến \(r\), nói cách khác, đưa ra tổng: \(a_l + a_{l+1} + ... + a_r\) (\(1 \le l \le r \le n\)).

Biểu thức \(x \oplus y\) biểu diễn toán tử XOR của hai số nguyên \(x\) và \(y\).

Yêu cầu: Với mỗi truy vấn loại 2, đưa ra kết quả là một số nguyên trên một dòng.

Input

• Dòng thứ nhất chứa hai số nguyên \(n,q\) (\(1 \le n,q \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\) (\(0 \le a_i \le 10^6\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa một truy vấn như mô tả ở trên.

Output

• Với mỗi truy vấn loại 2, đưa ra kết quả trên một dòng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n,q \le 1000\).
• Subtask \(2\) (\(20\%\) số điểm): mọi truy vấn loại 1 diễn ra trước mọi truy vấn loại 2.
• Subtask \(3\) (\(20\%\) số điểm): mọi truy vấn loại 1 có \(l = r\).
• Subtask \(4\) (\(20\%\) số điểm): mọi truy vấn loại 1 có \(x\) thuộc dạng \(x = 2^k\) (\(0 \le k < 20\)).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

5 8
4 10 3 13 7
2 2 4
1 1 3 3
2 2 4
2 3 3
1 2 5 5
2 1 5
1 1 2 10
2 2 3

26
22
0
34
11