Cho hai số nguyên dương \(n, m\) và mảng \(a\) gồm \(n\) số nguyên dương phân biệt \(a_{1}, a_{2}, \ldots, a_{n}\). Tính tích các số nằm trong khoảng từ \(1\) đến \(m\) mà không thuộc mảng \(a\). Do kết quả có thể rất lớn, bạn cần đưa ra kết quả sau khi chia lấy phần dư cho \(10^{9} + 7\).

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n, m\) \((1 \leq n \leq m \leq 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên dương phân biệt \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq m)\).

Output

• Gồm một dòng duy nhất chứa một số nguyên là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(m \leq 50\).
• Subtask \(2\) (\(30\%\) số điểm): \(m \leq 120\).
• Subtask \(3\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

3 5
1 2 4

15

Bạn được cho một mảng \(a\) gồm \(n\) (\(n\) chia hết cho \(3\)) phần tử. Bạn được thực hiện vô số thao tác sau: tăng hoặc giảm \(1\) phần tử bất kỳ lên hoặc xuống \(1\) đơn vị. Gọi \(c_{0}, c_{1}\) và \(c_{2}\) lần lượt là số lượng các phần tử trong mảng \(a\) khi chia lấy dư cho 3 có số dư bằng \(0, 1\) và \(2\). Một mảng được gọi là cân đối khi \(c_{0} = c_{1} = c_{2}\).

Yêu cầu: bạn hãy tìm cách cân đối mảng \(a\) ban đầu bằng cách thực hiện \(0\) hoặc nhiều thao tác và in ra số thao tác ít nhất để cân đối mảng \(a\).

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) \((1 \leq n \leq 5 \times 10^{5}, n \mod 3 = 0)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((0 \leq a_{i} \leq 10^{9})\).

Output

• Gồm một dòng duy nhất chứa một số nguyên là số thao tác ít nhất để cân đối mảng.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n = 3\).
• Subtask \(2\) (\(40\%\) số điểm): \(a_{i} \leq 2\).
• Subtask \(3\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

6
5 3 8 9 11 34

1

Cho bốn số nguyên dương \(n, a, b, c\) hãy tính tổng sau:

Với \(x\) là số nguyên thỏa mãn các tính chất sau:

• \(x\) chia hết cho \(a\) hoặc \(x\) chia hết cho \(b\) hoặc \(x\) chia hết cho cả \(a\) và \(b\)
• \(x\) không chia hết cho \(c\).

Trong đó \(\left\lfloor x \right\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Input

• Dòng thứ nhất chứa một số nguyên dương \(q\) \((1 \leq q \leq 50)\) là số bộ thử nghiệm.
• \(q\) dòng tiếp theo, dòng thứ \(i\) tương ứng với bộ thử nghiệm thứ \(i\), dòng thứ \(i\) chứa bốn số nguyên \(n, a, b, c\) \((1 \leq n, a, b, c \leq 10^{9})\).

Output

• In ra \(q\) dòng, dòng thứ \(i\) chứa kết quả tương ứng với bộ thử nghiệm thứ \(i\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10^{6}\).
• Subtask \(2\) (\(30\%\) số điểm): \(a = b\) và \(c > n\).
• Subtask \(3\) (\(20\%\) số điểm): \(c > n\).
• Subtask \(4\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

2
15 2 3 5
30 2 4 9

21
44

Dãy tình yêu là dãy chỉ gồm hai ký tự < và 3. Tuy nhiên, lạ ở chỗ, nếu có ai đó đọc phép lên dãy thì những phép màu sẽ xảy ra:

• Ký tự < được xếp liền trước ký tự 3 sẽ biến thành một trái tim nhỏ, có độ lớn là \(1\).
• Hai trái tim được xếp liền nhau sẽ biến thành một trái tim lớn hơn, có độ lớn là tổng độ lớn của hai trái tim cũ.
• Một trái tim có ký tự liền trước là < và ký tự liền sau là 3 sẽ trở thành một trái tim lớn hơn, với độ lớn tăng lên một đơn vị.

Những phép màu sẽ xảy ra liên tục và chỉ kết thúc khi nào những phép màu đó không còn tác động và làm thay đổi được dãy nữa.

Ví dụ:

• Dãy <3 sẽ tạo thành trái tim có độ lớn là \(1\)
• Dãy <3<3 sẽ tạo thành trái tim có độ lớn là \(2\)
• Dãy <<33 sẽ tạo thành trái tim có độ lớn là \(2\)
• Dãy <<3<3<33 sẽ tạo thành trái tim có độ lớn là \(4\)

Hân là một cô phù thủy dễ thương và vô cùng tỉ mỉ. Với những dãy tình yêu, trước khi đọc phép, Hân sẽ bỏ đi một vài ký tự để đảm bảo cho dãy có thể tạo thành một trái tim có độ lớn lớn nhất có thể.

Bạn phải trả lời \(Q\) truy vấn thuộc \(2\) loại sau:

• \(1\) \(l\) \(r\): Với mỗi vị trí \(i\) trong đoạn \([l, r]\), nếu \(S_{i} =\) < thì gán \(S_{i} =\) 3, ngược lại gán \(S_{i} =\) <
• \(2\) \(l\) \(r\): Hỏi với dãy tình yêu \(S[l, r]\) là dãy con của dãy tình yêu \(S\) cho trước, nếu để Hân đọc phép, trái tim lớn nhất có thể hình thành sẽ có độ lớn bao nhiêu ?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) vả \(q\) \((1 \leq n \leq 10^{6}, 1 \leq q \leq 5 \times 10^{5})\) là độ dài xâu \(S\) và số lượng truy vấn.
• Dòng thứ hai chứa xâu \(S\) có độ dài \(n\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa 3 số \(t\), \(l\) và \(r\) \((t \in \{0, 1\}, 1 \leq l \leq r \leq n)\) thể hiện 1 truy vấn.

Output

• Với mỗi truy vẫn loại \(2\), in ra độ lớn của trái tim lớn nhất mà Hân có thể tạo ra từ dãy con của \(S\) từ \(l\) đến \(r\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 5 \times 10^{3}\).
• Subtask \(2\) (\(20\%\) số điểm): \(q \leq 10\), không có truy vấn loại \(1\).
• Subtask \(3\) (\(20\%\) số điểm): Có tối đa 10 truy vấn loại \(2\).
• Subtask \(4\) (\(20\%\) số điểm): Không có truy vấn loại \(1\).
• Subtask \(5\) (\(20\%\) số điểm): Không có rằng buộc gì thêm.

Example

16 10
<3<3<3<<3<<<3<3<
1 2 13
2 2 16
1 14 16
1 5 16
2 2 8
2 1 13
2 2 14
2 1 16
1 5 14
2 1 14

10
4
8
8
10
12