Trong một lần đi khám phá hang động, nhà khảo cổ Winter Jr đã phát hiện ra dấu tích của người xưa để lại trên vách đá của hang cho thấy trí tuệ xuất chúng của loài người từ xa xưa. Cậu nhìn thấy trên vách đá có ghi lại một đoạn code C++ như sau:

void ancient_people_veri_vjppro(vector<int>& a) {
    stack<int> st;
    for (int u: a) {
        while (!st.empty() && st.top() < u) st.pop();
        st.push(u);
        cout << st.size() << ' ';
    }
}

Bên dưới đoạn code này, cậu còn tìm thấy một dãy số nguyên dương s độ dài n có vẻ như là kết quả của đoạn code này khi chạy với một input nào đó. Cậu tò mò muốn biết xem có bao nhiêu dãy a là hoán vị của n số nguyên dương đầu tiên có thể là input truyền vào hàm này để tạo ra được dãy kết quả đó.

Hãy giúp Winter Jr giải mã bí ẩn của người xưa để lại nhé. Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho 10^9 + 7.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương n (n <= 10^5).
• Dòng thứ hai chứa n số nguyên dương s1, s2, ..., sn (si <= i).

Kết quả

• In ra một số nguyên không âm là kết quả của bài toán.

Sample input

3
1 1 2

Sample output

2

Giải thích

Các hoán vị thoả mãn là: $[1, 3, 2]$ và $[2, 3, 1]$.

Chấm điểm

• Subtask 1 ($10\%$ số test): n <= 10
• Subtask 2 ($15\%$ số test): n <= 13
• Subtask 3 ($25\%$ số test): s1 <= s2 <= ... <= s_n <= 2
• Subtask 4 ($25\%$ số test): s1 <= s2 <= ... <= s_n
• Subtask 5 ($25\%$ số test): Không có ràng buộc gì thêm.

Bài đồ thị siêu cơ bản nên đề bài vô cùng ngắn gọn:

Quân có một đồ thị đầy đủ, vô hướng, có trọng số gồm ~n~ đỉnh. Trọng số của đỉnh thứ ~i~ là ~a_i~. Trọng số của cạnh nối giữa đỉnh ~u~ và đỉnh ~v~ là ~\frac{a_u + a_v}{gcd(a_u, a_v)}~. Cảm giác bài chưa đủ khó nên Quân vẽ thêm ~m~ cạnh nối nữa. Cạnh thứ ~i~ nối giữa hai đỉnh ~u_i~ và ~v_i~, và có trọng số là ~w_i~.

Hãy tính độ dài đường đi ngắn nhất từ đỉnh ~1~ tới mỗi đỉnh còn lại.

Input

• Dòng đầu chứa hai số nguyên không âm ~n, m~ ~(1 \le n \le 10^5, 0 \le m \le 10^4)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^5)~.
• ~m~ dòng cuối cùng, dòng thứ ~i~ chứa ba số nguyên dương ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le n, 1 \le w_i \le 10^5)~.

Output

• In ra ~n~ số nguyên không âm, số thứ ~i~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~i~.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n \le 1000~
• Subtask ~2~ (~20\%~ số điểm): Dãy ~a~ đôi một giống nhau
• Subtask ~3~ (~20\%~ số điểm): ~m = 0; \ a_i \le 50 \ \forall i \in [1, n]~
• Subtask ~4~ (~20\%~ số điểm): ~m = 0~
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

3 1
1 2 3
2 3 1

Sample output 1

0 3 4

Vùng đất Ams có n thành phố tạo thành cấu trúc cây. Thành phố thứ ~i~ có cấp độ ~a_i~. Thành phố nhập môn là thành phố ~1~ có cấp độ ~1~, thành phố final boss là thành phố ~n~ có cấp độ ~m~. Mỗi ngày bạn có thể di chuyển từ một thành phố đến một thành phố lân cận với nó.

Một lộ trình đánh boss là một lộ trình xuất phát từ thành phố ~1~, di chuyển đến một thành phố cấp độ ~2~, rồi đến cấp độ ~3~, … rồi đến cấp độ ~m-1~, và cuối cùng kết thúc tại thành phố n. Trong lộ trình này bạn sẽ di chuyển giữa các thành phố đó bằng đường đi ngắn nhất, và có thể sử dụng thành phố cấp độ cao để di chuyển giữa các thành phố có cấp độ thấp hơn. Thời gian hoàn thành một lộ trình là tổng số ngày để di chuyển của lộ trình này.

Nhiệm vụ của bạn là hãy tính tổng thời gian hoàn thành của mọi lộ trình đánh boss có thể. Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả cho ~10^9+7~.

Dữ liệu

• Dòng đầu chứa hai số nguyên dương ~n, m~ ~(m <= n <= 10^5)~
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(a_i <= m)~
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ mô tả một cạnh của cây ~(u, v <= n)~

Kết quả

• In ra 1 số nguyên là kết quả của bài toán

Sample Input

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

Sample Output

6

Giải thích

Có hai lộ trình thoả mãn:

• ~(1, 2, 4)~: Di chuyển hết: ~dist(1, 2) + dist(2, 4) = 2~
• ~(1, 3, 4)~: Di chuyển hết: ~dist(1, 3) + dist(3, 4) = 4~

Bộ truyện manga Two Piece đình đám có ~n~ chương, đánh số từ ~1~ tới ~n~, chương thứ i có ~a_i~ trang.

Có m người muốn đọc truyện, được đánh số từ ~1~ tới ~m~, người thứ ~i~ có tốc độ đọc ~b_i~ giây mỗi trang.

Mọi người sẽ đọc sách theo quy tắc sau:

• Mỗi chương sách chỉ có thể đọc bởi 1 người 1 lúc. Với mỗi chương sách, người thứ ~i~ chỉ được đọc sau khi người thứ ~i-1~ đã đọc xong
• Mọi người đều đọc các chương sách theo thứ tự từ chương ~1~ tới chương ~n~. Họ sẽ đọc chương thứ ~i~ NGAY SAU KHI đọc xong chương thứ ~i-1~

Yêu cầu: Hãy tính xem cần ít nhất bao nhiêu thời gian để tất cả mọi người đọc hết mọi chương sách.

Dữ liệu

• Dòng đầu chứa hai số nguyên dương ~n, m~ ~(n, m <= 10^5)~
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(a_i <= 10^5)~
• Dòng thứ ba chứa ~m~ số nguyên dương ~b_1, b_2, ..., b_m~ ~(b_i <= 10^5)~

Kết quả

• In ra một số nguyên là kết quả của bài toán

Sample Input

3 3 
1 2 1
10 10 2

Sample Output

62

Giải thích

Người thứ nhất đọc tập ~1~ từ giây thứ ~0~ đến ~10~, tập ~2~ từ giây thứ ~10~ đến ~30~, tập ~3~ từ giây thứ ~30~ đến ~40~. Người thứ hai đọc tập ~1~ từ giây thứ ~20~ đến ~30~, tập ~2~ từ giây thứ ~30~ đến ~50~, tập ~3~ từ giây thứ ~50~ đến ~60~. Người thứ ba đọc tập ~1~ từ giây thứ ~54~ đến ~56~, tập ~2~ từ giây thứ ~56~ đến ~60~, tập ~3~ từ giây thứ ~60~ đến ~62~.

Bạn có một đồ thị cây có ~n~ đỉnh, gốc tại đỉnh ~1~. Trên đỉnh thứ ~i~ có ghi số ~a_i~. Mỗi thao tác bạn có thể chọn một đỉnh và tăng hoặc giảm số ghi trên đỉnh đó đi ~1~. Bạn cần phải thao tác để sau khi hoàn thành, cây có dạng sau:

• Các lá được ghi số ~0~ hoặc ~1~
• Số ghi trên đỉnh ~u~ bằng tổng các số ghi trên các đỉnh con trực tiếp của ~u~

Yêu cầu: Hãy tìm số lần thao tác ít nhất có thể

Dữ liệu

• Dòng đầu chứa số nguyên dương ~n~ ~(n <= 10^5)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(0 <= a_i <= 10^5)~
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số ~u, v~ mô tả một cạnh của cây ~(u, v <= n)~

Kết quả

• In ra một số là kết quả của bài toán

Sample Input

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

Sample Output

4

Giải thích

Giảm nhãn ở đỉnh ~1~ xuống thành ~3~, đỉnh ~3~ xuống thành ~2~. Tăng nhãn ở đỉnh ~4~ lên thành ~1~