Số học luôn là một lĩnh vực quyến rũ với các định lý đẹp, và đôi khi cũng nguy hiểm chết người. Có những tính chất ta nghĩ là dễ nhưng biến đổi thử mới thấy khó, nhưng đôi khi ngược lại, có những kết quả khá hiển nhiên mà ta thường tìm tòi những thứ rất xa xôi.

Do biết team ICPC của H3.2 cũng rất thích số học, đặc biệt là những bài đố mẹo, đố vui nên hôm nay, thầy Luna có giới thiệu một bài như sau: cho số nguyên dương ~n, m~, hỏi số ~n^{m!}~ thì chia cho ~2024~ dư mấy? Bạn hãy thử sức với bài toán đố vui này nhé.

Input

Một dòng duy nhất gồm hai số nguyên dương ~n, m~ với ~1 \le n, m \le 10^{18}~.

Output

Kết quả của bài toán.

Sample input 1

3 2

Sample output 1

9

Sample input 2

2023 100000

Sample output 2

1

Subtasks

• Có 25% test ứng với ~n, m \le 15~.
• Có 25% test ứng với ~m \le 15~.
• Có 50% test với giới hạn tùy ý.

Trong CLB lập trình H3.2, có ~n~ thành viên với leader Trung Phan có STT ~1~, còn các thành viên kia sẽ có STT từ ~2,3,...,n~. Dưới leader này sẽ có một số thư ký, rồi dưới mỗi thư ký sẽ có một số trợ lý thư ký, ..., nói chung quan hệ cấp bậc trong CLB phân biệt khá rõ, tạo thành một mô hình cây. Các thành viên mới vào sẽ thuộc 'tầng lớp' thấp nhất (có thể gọi là cộng tác viên). Thầy Luna thường giao các task cho một thành viên nào đó của CLB, và nếu hoàn thành tốt thì được thưởng, còn không thì sẽ bị phạt với một mức tiền nhất định. Có một điều đặc biệt, một khi thành viên được ~x~ đồng (số này có thể âm hoặc dương, tùy vào bị phạt hay được thưởng) thì tất cả cấp dưới của người này sẽ được ~-x~ đồng, rồi cấp dưới nữa lại được ~-(-x)=x~ đồng, và cứ thế lan truyền xuống cấp thấp nhất. Ban đầu mỗi người sẽ có 0 đồng. Thầy Luna thắc mắc tại một thời điểm nào đó, một người có STT ~i~ sẽ đang có bao nhiêu tiền?

Input:

Dòng đầu tiên gồm hai số nguyên dương ~n, m~ với ~2 \le n, m \le 10^5.~

Mỗi dòng trong ~n-1~ dòng tiếp theo sẽ gồm một cặp số ~x,y~ cho biết STT của hai thành viên có làm việc trực tiếp với nhau (chưa biết ai là cấp trên của ai), chỉ biết STT ~1~ là cấp cao nhất.

Mỗi dòng trong ~m~ dòng tiếp theo sẽ có một trong hai dạng (cho biết sẽ có ít nhất một câu hỏi dạng 2):

1 ~i~ ~x~: người thứ ~i~ sẽ nhận một giá trị là ~x~, trong đó ~x \le 2023.~

2 ~i~: yêu cầu cho biết số tiền hiện tại mà người thứ ~i~ trong CLB có.

Output:

Trả lời cho các câu hỏi dạng 2, theo thứ tự từ trên xuống.

Sample input:

4 3
1 2
1 3
3 4
2 4
1 1 3
2 4

Sample output:

0
3

Để trang trải cho dự án khởi nghiệp, các thành viên trong cty IUHCoder phải kinh doanh thêm hình thức cafe thú cưng gồm các bé mèo Anh lông dài và bé chó Pug. Để thu hút quảng cáo, các nhân viên kinh doanh, dưới sự chỉ đạo của thầy Tina, định sẽ liên tục livestream các cặp thú cưng, mỗi lần như thế sẽ có một cặp chó-mèo được lên sóng. Còn thầy Luna thì nghĩ rằng vẫn nên có một dịp đặc biệt nào đó mà hai bé chó Pug được lên sóng cùng lúc, thầy Tina đồng ý nhưng chỉ cho phép có không quá một buổi livestream như thế thôi (chú ý rằng không cho hai mèo livestream). Hiện tại dự án chưa mua được bé chó mèo nào cả, nhưng đã tính trước lịch livestream. Cụ thể là các bé thú cưng sẽ được đánh số từ ~1 \to n~ và sẽ có ~m~ buổi livestream với các cặp số thứ tự, một cặp thú cưng có thể được lên sóng nhiều lần nên các cặp số không nhất thiết phân biệt. Thầy Tina đến kiểm tra lịch phát sóng dự kiến để đi đặt mua chó mèo về. Hỏi thầy có thể làm được điều đó hay không, tức là có cách mua ~a~ con chó, ~b~ con mèo với ~a+b=n~ rồi đánh số từ ~1~ đến ~n~ để thỏa mãn điều kiện của lịch livestream đã tính sẵn hay không?

Input:

Dòng đầu tiên gồm cặp số ~n,m~ với ~n~ là số thú cưng và ~m~ là số lần livestream, trong đó ~2 \le n \le 2023~ và ~1 \le m \le 10^5.~ Trong ~m~ dòng tiếp theo sẽ có các cặp số nguyên ~(i,j)~ với ~i \ne j~, ~1 \le i, j \le n~ cho biết số thứ tự của cặp thú cưng.

Output:

In ra YES nếu thông tin là hợp lệ, ngược lại thì in ra NO.

Input sample 1:

3 3
1 2
2 3
3 1

Output sample 1:

YES

Input sample 2:

4 6
1 2
2 3
3 4
4 1
1 3
2 4

Output sample 2:

NO

Giải thích: trong VD1, thầy Tina có thể mua ~2~ chó với STT ~1,2~ và một mèo STT ~3~. Khi đó, cặp chó ~(1,2)~ sẽ được lên sóng một lần, còn lại là mèo-chó; Còn trong VD2, dễ thấy với lịch livestream như vậy, thầy Tina không có cách nào đặt mua chó-mèo được.

Ghi chú: dự án IUHCoder cũng muốn nuôi đến ~10^5~ con thú cưng lắm, nhưng đây quả là một bài toán đau đầu.

Cho một bảng ô vuông kích thước ~n×3~ (~n~ dòng và ~3~ cột), mỗi ô của bảng có điền một số nguyên nào đó. Quân có ~k~ quân domino kích thước ~2×1~, mỗi quân domino có thể phủ đúng hai ô kề cạnh của bảng. Quân đặt các quân domino của mình lên bảng sao cho mọi quân domino đều nằm trong bảng, mỗi quân phủ đúng ~2~ ô và không đè lên nhau. Có thể xoay quân domino tùy ý. Bạn hãy xác định tổng lớn nhất có thể đạt được của các số trên những ô bị phủ.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~ (~1 ≤ n~, ~k ≤ 1000~),
• Dòng thứ ~i~ trong ~n~ dòng sau chứa ~3~ số nguyên xác định các số ghi trên dòng ~i~ của bảng, các số có giá trị tuyệt đối không vượt quá ~10^6~.

Output

Một số nguyên – tổng lớn nhất của các số bị phủ.

Sample Input 1

5 3
2 1 -1
1 3 2
0 2 3
2 1 1
3 3 0

Sample Output 1

16

Giới hạn:

• 30% số điểm tương ứng 30% số điểm có
• 30% số test khác có
• 40% số test còn lại tương ứng 40% số điểm có

Vào đợt khai giảng năm học mới, CLB lập trình có ra chiến dịch tuyển thành viên theo cách sau đây: mỗi SV muốn tham gia thì cần thi 3 bài: lập trình C/C++, kiểm tra tư duy logic và kiểm tra tiếng Anh. Điểm của mỗi người sẽ là ba số nguyên dương không vượt quá 1 tỷ. Với điểm thi ở một môn nào đó của một thí sinh ~X~ bất kỳ, ta định nghĩa "độ thua kém" so với thí sinh ~Y~ (cũng ở môn đó) là số điểm mà ~Y~ hơn ~X~, trong trường hợp ~X~ cao điểm hơn ~Y~ thì độ thua kém là ~0.~

Ví dụ: ở môn lập trình C/C++, nếu ~X~ đạt 7đ, ~Y~ đạt 9đ còn ~Z~ đạt 6đ thì ~X~ thua kém ~Y~ là 2đ nhưng thua kém ~Z~ là 0đ.

Tuy nhiên, bài kiểm tra là rất khó và hầu như các bạn đạt điểm rất thấp, không như mong muốn của CLB. Vì thế CLB đã đề xuất ra một khóa huấn luyện cho "thành viên dự bị" với chi phí được tính như sau: với mỗi ứng viên ~X~, chi phí mà ~X~ cần nộp bằng với giá trị lớn nhất của tổng độ thua kém ở cả ba môn so với từng ứng viên còn lại (đọc thêm VD minh họa để hiểu rõ hơn).

Bạn Vuvuzela, một thủ quỹ của CLB, muốn dựa vào kết quả thi của các thành viên, tính ra xem số tiền ít nhất và nhiều nhất mà các ứng viên cần nộp là bao nhiêu. Hãy giúp Vuvuzela thực hiện điều này nhé.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~2 \le n \le 2 \cdot 10^5.~

Trong ~n~ dòng tiếp theo, mỗi dòng là một bộ ba điểm thi của các ứng viên.

Output

Số tiền nhiều nhất, ít nhất mà một ứng viên phải đóng.

Các subtasks trong bài:

• Có 50% điểm ứng với ~n \le 2023~ và các điểm số không vượt quá ~10^3.~
• Có 50% điểm ứng với ~2024 \le n \le 2 \cdot 10^5~ và các điểm số không vượt quá ~10^9.~

Sample input

3
6 7 8 
5 10 5
8 8 8

Sample output

6 2

Giải thích: Ta tính được chi phí mà các ứng viên phải đóng lần lượt là:

• Độ thua kém của 1 so với 2 là: ~0+3+0=3~; so với 3 là ~2+1+0=3~ nên chi phí là ~\max(3,3)=3~.
• Độ thua kém của 2 so với 1 là: ~1+0+3=4~; so với 3 là ~3+0+3=6~ nên chi phí là ~\max(4,6)=6~.
• Độ thua kém của 3 so với 1 là: ~0+0+0=0~; so với 2 là ~0+2+0=2~ nên chi phí là ~\max(2,2)=2~.

Do đó, ứng viên 2 phải đóng nhiều nhất, đến 6 đồng, còn ứng viên 3 đóng ít nhất, 2 đồng.

Trung Phan hôm nay bắt đầu buổi dạy lập trình vỡ lòng đầu tiên cho các em sinh viên khóa mới, K19. Bạn ấy dạy về công thức nghiệm để giải phương trình bậc hai có dạng ~x^2+ax+b=0.~ Tất nhiên, vì các test case ví dụ cho học viên mới làm quen thì cần phải rõ ràng, phải là số đẹp nên Trung muốn rằng hai nghiệm của phương trình thu được đều phải nguyên (không nhất thiết phân biệt). Cho biết rằng ~a,b~ là các số nguyên có giá trị tuyệt đối không vượt quá ~n~, bạn hãy giúp các học viên tính tổng tất cả các hệ số tự do (hệ số ~b~) của những phương trình bậc hai như thế nhé.

Input

Một dòng duy nhất là số nguyên dương ~n~ với ~1 \le n \le 10^{18}~.

Output

Đáp số của bài toán, chia lấy dư cho ~10^9+7.~

Các subtasks trong bài:

• Có 30% điểm ứng với ~n \le 10^4.~
• Có 40% điểm ứng với ~10^4 < n \le 5 \cdot 10^5.~
• Có 30% điểm ứng với ~5 \cdot 10^5 < n \le 10^{18}.~

Sample input 1:

1

Sample output 1:

1000000006

Sample input 2:

2

Sample output 2:

1000000004

Sample input 3:

90

Sample output 3:

105

Giải thích: trong VD1, ta thấy có các phương trình ~x^2-1=0~, ~x^2-x=0~, ~x^2+x=0~ là thỏa mãn, đáp số là ~-1+0+0=-1,~ (lấy modulo thì được ~10^9+6~) còn trong VD2, ta thấy ngoài các phương trình trên thì còn có ~x^2-2x=0~, ~x^2-2x+1=0~, ~x^2+2x+1=0~, ~x^2+2x=0~, ~x^2-x-2=0~, ~x^2+x-2=0~ với tổng hệ số tự do là ~-2~, kết hợp với tổng tính được ở trên là ~-1~ thì đáp số cần tìm là ~-3.~