Có ~N~ loại đá, mỗi loại có đúng ~M~ viên. Các viên đá loại ~i~ đều được ghi số ~i~.

Cần xếp toàn bộ ~M \times N~ viên đá vào một bảng gồm ~M~ hàng và ~N~ cột sao cho:

• Mỗi ô chứa đúng một viên đá.
• Trên mỗi hàng, các viên đá khác loại từng đôi một.
• Hai viên đá nằm trong hai ô chung cạnh phải khác loại.

Yêu cầu

Tính số cách xếp đá thỏa mãn các điều kiện trên.

Hai cách xếp được xem là khác nhau nếu tồn tại ít nhất một ô chứa hai loại đá khác nhau trong hai cách xếp đó.

Dữ liệu

Một dòng duy nhất chứa hai số nguyên dương ~M~ và ~N~.

Kết quả

In ra số cách xếp đá thỏa mãn, lấy phần dư khi chia cho ~10^9+7~.

Ví dụ

Ví dụ 1

Input

2 2

Output

2

Ví dụ 2

Input

1 3

Output

6

Giải thích

Ví dụ 1

Có hai cách xếp:

1 2
2 1

và

2 1
1 2

Ví dụ 2

Bảng chỉ có một hàng. Mỗi hoán vị của ~3~ loại đá đều hợp lệ, nên có ~3! = 6~ cách xếp.

Ràng buộc và chấm điểm

Ràng buộc

~M~ và ~N~ là các số nguyên dương.

Chấm điểm

• Subtask~1~ ~(20\%)~: ~M,N \le 5~.
• Subtask~2~ ~(20\%)~: ~N \le 5~, ~M \le 200~.
• Subtask~3~ ~(20\%)~: ~M,N \le 2000~.
• Subtask~4~ ~(20\%)~: ~N \le 2000~, ~M \le 10^{18}~.
• Subtask~5~ ~(20\%)~: ~N \le 10^6~, ~M \le 10^{18}~.

Dãy Fibonacci được định nghĩa như sau:

• ~f(0)=0~.
• ~f(1)=1~.
• ~f(x)=f(x-2)+f(x-1)~ với ~x \ge 2~.

Cho dãy ~a~ gồm ~n~ phần tử ~a_1,a_2,\ldots,a_n~. Ban đầu, mọi phần tử đều bằng ~0~.

Có ~q~ truy vấn thuộc một trong hai loại:

• ~D\ x\ y~: tăng mỗi phần tử ~a_x,a_{x+1},\ldots,a_y~ thêm ~1~.
• ~S\ x\ y~: tính tổng ~f(a_x)+f(a_{x+1})+\cdots+f(a_y)~.

Yêu cầu

Thực hiện lần lượt các truy vấn và trả lời mỗi truy vấn loại ~S~.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• Mỗi dòng trong ~q~ dòng tiếp theo chứa một truy vấn có dạng ~D\ x\ y~ hoặc ~S\ x\ y~, trong đó ~1 \le x \le y \le n~.

Dữ liệu bảo đảm có ít nhất một truy vấn loại ~S~.

Kết quả

Với mỗi truy vấn loại ~S~, in ra trên một dòng phần dư của tổng cần tính khi chia cho ~10^9+7~.

Ví dụ

Ví dụ 1

Input

5 7
D 1 4
S 1 5
D 3 5
D 2 3
S 1 5
D 2 5
S 2 3

Output

4
6
5

Giải thích

Sau truy vấn đầu tiên, dãy là ~[1,1,1,1,0]~, do đó truy vấn thứ hai có kết quả

~f(1)+f(1)+f(1)+f(1)+f(0)=4~.

Trước truy vấn cuối cùng, dãy là ~[1,3,4,3,2]~. Vì vậy, kết quả là

~f(a_2)+f(a_3)=f(3)+f(4)=2+3=5~.

Ràng buộc và chấm điểm

Ràng buộc

Mỗi truy vấn thỏa mãn ~1 \le x \le y \le n~.

Chấm điểm

• Subtask~1~ ~(20\%)~: ~n,q \le 1000~.
• Subtask~2~ ~(20\%)~: ~n,q \le 10^5~ và có nhiều nhất ~100~ truy vấn loại ~D~.
• Subtask~3~ ~(60\%)~: ~n,q \le 10^5~.

Có ~N~ xã và ~M~ đường cao tốc hai chiều. Đường thứ ~i~ nối hai xã ~u_i~ và ~v_i~, có lệ phí thông hành ~c_i~.

~N-1~ đường đầu tiên tạo thành một cây khung nhỏ nhất của mạng lưới. Các đường này được gọi là các cạnh đặc biệt.

Với mỗi cạnh ~i~, xét việc chỉ thay đổi lệ phí của cạnh đó, còn lệ phí của mọi cạnh khác được giữ nguyên. Định nghĩa:

• ~A_i~ là lượng lớn nhất có thể tăng thêm vào ~c_i~ mà tập cạnh đặc biệt vẫn là một cây khung nhỏ nhất.
• ~B_i~ là lượng lớn nhất có thể giảm khỏi ~c_i~ mà tập cạnh đặc biệt vẫn là một cây khung nhỏ nhất.

Tập cạnh đặc biệt không bắt buộc phải là cây khung nhỏ nhất duy nhất.

Nếu có thể tăng hoặc giảm lệ phí không giới hạn mà điều kiện vẫn được thỏa mãn, giá trị tương ứng được xem là ~\infty~.

Yêu cầu

Tính

~S=\displaystyle\sum_{i=1}^{M}\left(i\cdot A_i+i^2\cdot B_i\right)~.

Trước khi tính tổng, mọi giá trị ~A_i=\infty~ hoặc ~B_i=\infty~ được thay bằng ~-1~.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~.
• Dòng thứ ~i~ trong ~M~ dòng tiếp theo chứa ba số nguyên ~u_i~, ~v_i~, ~c_i~, mô tả đường cao tốc thứ ~i~.

~N-1~ cạnh đầu tiên tạo thành một cây khung nhỏ nhất của đồ thị.

Kết quả

In ra số nguyên ~S~.

Ví dụ

Ví dụ 1

Input

3 3
1 2 5
2 3 7
1 3 10

Output

30

Ví dụ 2

Input

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

Output

72

Giải thích

Ví dụ 1

Các giá trị tương ứng là:

• ~A_1=5~, ~B_1=\infty~.
• ~A_2=3~, ~B_2=\infty~.
• ~A_3=\infty~, ~B_3=3~.

Sau khi thay ~\infty~ bằng ~-1~:

~S=1\cdot5+1^2\cdot(-1)+2\cdot3+2^2\cdot(-1)+3\cdot(-1)+3^2\cdot3=30~.

Ví dụ 2

Các giá trị tương ứng là:

• ~A_1=3~, ~B_1=\infty~.
• ~A_2=2~, ~B_2=\infty~.
• ~A_3=2~, ~B_3=\infty~.
• ~A_4=\infty~, ~B_4=2~.
• ~A_5=\infty~, ~B_5=2~.

Sau khi thay ~\infty~ bằng ~-1~, ta thu được ~S=72~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 10^5~.
• ~N-1 \le M \le 10^5~.
• ~1 \le u_i,v_i \le N~.
• ~u_i \ne v_i~.
• ~0 \le c_i \le 1000~.

Chấm điểm

• Subtask~1~ ~(10\%)~: ~M=N-1~.
• Subtask~2~ ~(20\%)~: ~M \le 10^3~.
• Subtask~3~ ~(20\%)~: ~N \le 10^3~.
• Subtask~4~ ~(50\%)~: không có ràng buộc bổ sung.