Cho một biểu đồ được vẽ với ~n~ cột đánh số từ ~1~ đến ~n~ từ trái sang phải, mỗi cột có độ rộng bằng ~1~, cột thứ ~i~ có độ cao là ~h_i~.

Yêu cầu: Cho biểu đồ và một số nguyên ~p~, xác định số hình chữ nhật khác nhau thỏa mãn điều kiện sau:

Các đỉnh của hình chữ nhật là các tọa độ nguyên, có một cạnh nằm trên trục ~Ox~, hình chữ nhật này phải được phủ hoàn toàn bởi biểu đồ, và diện tích của nó không nhỏ hơn ~p~.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~p~. (~1 \le n \le 10^5, 1 \le p \le 10^{14}~) — số cột của biểu đồ và diện tích yêu cầu.

Dòng tiếp theo chứa ~n~ số nguyên ~h_1, h_2, \cdots, h_n~ (~1 \le h_i \le 10^5~) — độ cao của cột thứ ~i~.

Output

Một số nguyên duy nhất là số hình chữ nhật khác nhau thỏa mãn điều kiện trên.

Scoring

Sample Input 1

2 4
2 4

Sample Output 1

2

Sample Input 2

3 1
1 4 2

Sample Output 2

11

Notes

Trong ví dụ thứ nhất, có duy nhất hai hình chữ nhật có diện tích không nhỏ hơn ~4~ là ~[2, 2]~ và ~[0, 4]~.

Trong ví dụ thứ hai, bất kỳ hình chữ nhật nào cũng có diện tích không nhỏ hơn ~1~, và có tổng cộng ~11~ hình chữ nhật khác nhau.

Ở một trường vẽ nào đó bên Áo, bạn H đang làm một bài kiểm tra đầu vào để vào trường. Trải qua rất nhiều thử thách vẽ, cuối cùng bạn phải đối mặt với thử thách cuối cùng là liên quan tới tư duy. Bạn được cho một đồ thị vô hướng ~N~ đỉnh ~M~ cạnh và hai dãy ~A~ và ~B~. Bạn đó có thể gán ~A_u := \min(A_u, A_v)~ nếu có cạnh giữa ~u~ và ~v~. Liệu có thể biến đổi mảng ~A~ thành mảng ~B~ hay không? Thử thách này rất khó nên bạn H nhờ các bạn giải giúp để hi vọng được đỗ vào ngành mà bạn mong muốn.

Input

Dữ liệu vào từ file văn bản artschool.inp:

Dòng đầu ghi một số nguyên dương ~T~ là số lượng trường hợp test.

Mỗi nhóm dòng trong số ~T~ nhóm dòng tiếp theo mô tả một trường hợp test có cấu trúc như sau:

• Dòng thứ nhất gồm hai số nguyên dương ~N~ và ~M~ ~(1 \leq N \leq 150000, 1 \leq M \leq 200000)~.

• Dòng thứ hai gồm ~n~ số nguyên dương ~A_i~ ~(1 \leq A_i \leq N)~.

• Dòng thứ ba gồm ~n~ số nguyên dương ~B_i~ ~(1 \leq B_i \leq N)~.

• Dòng thứ ~i~ trong số ~M~ dòng tiếp theo gồm hai số nguyên dương ~u_i, v_i~ thể hiện có cạnh nối giữa hai đỉnh ~u_i~ và ~v_i~ ~(1\leq u_i, v_i \leq N)~.

Gọi ~\sum{N}~ và ~\sum{M}~ tương ứng là tổng của tất cả các giá trị ~N~ và ~M~ trong tất cả ~T~ trường hợp test. Dữ liệu đảm bảo ~\sum{N} \leq 3\times 10^5~ và ~\sum{M} \leq 4 \times 10^5~.

Output

Ghi ra file văn bản artschool.out gồm ~T~ dòng, mỗi dòng là đáp án của một test. Nếu trong test thứ ~i~, bạn H có thể biến đổi mảng sao cho thỏa mãn điều kiện, in ra dòng thứ ~i~ là ~1~, ngược lại in ra ~0~.

Scoring

Sample Input 1

2
2 1
1 2
1 2
1 2
3 1
1 2 3
3 2 1
1 3

Sample Output 1

1
0

Sample Input 2

1
3 2
3 2 1
1 1 1
1 2
2 3

Sample Output 2

1

Notes

Ở ví dụ 1, test 1, dãy A đã bằng dãy B sẵn từ đâu nên đáp án là ~1~.

Ở ví dụ 1, test 2, ta không có cách nào biến ~A_1 = B_1~ nên đáp án là ~0~.

Ở ví dụ 2, ta dùng 2 phép gán lần lượt ~A_2= min(A_2, A_3)~, ~A_1= min(A_1, A_2)~, dãy ~A~ sẽ trở thành dãy ~B~. Đáp án là ~1~

Tổ chức của Ito vừa mới mua một chiếc siêu máy tính. Với tính tò mò, Ito liền muốn dùng thử chiếc siêu máy tính cho bài toán dưới đây:

Cho dãy ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~ và đoạn code C++ như sau:

int g(int x) { return x * x - 1; }

int f(int k) {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (__gcd(a[i], k) != 1) {
            continue;
        }
        int j = i;
        while (j <= n && __gcd(a[j], k) == 1) {
            ++j;
        }
        ans += g(j - i);
        i = j - 1;
    }
    return ans;
}

Ito cần tính ~\sum_{k=1}^{V}f(k)~ và hiển thị kết quả chia lấy dư cho ~10^9+7~.

Ito muốn thử thách siêu máy tính nên sẽ không lấy ~V~ bình thường, mà sẽ lấy một số rất lớn, và được biểu diễn thông qua ~4~ số nguyên ~seed~, ~mul~, ~add~ và ~mod~ với phương pháp như sau:

• ~\begin{cases} p[1] = seed \\ p[i] = (p[i - 1] \times mul + add) \% mod + 1 \\ \end{cases}~

• ~V = \prod_{i = 1}^{10^6}i ^ {p[i]}~

Sếp của Ito nhìn sơ qua thử thách mà bạn đặt ra cho siêu máy tính liền cười và nói: "Bài này cần gì siêu máy tính, máy tính bình thường cũng có thể giải quyết được".

Là người bạn cực kỳ thân với Ito, bạn hãy giúp anh ấy giải quyết bài toán này.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 10^5~)

• Dòng tiếp theo chứa 4 số nguyên ~seed~, ~mul~, ~add~ và ~mod~ (~1 \leq seed, mul, add, mod \leq 10^9~)

• Dòng cuối cùng chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq 10^6~)

Output

Một số nguyên duy nhất là kết quả của bài toán.

Scoring

Sample Input 1

3
3 2 1 100
7 8 9

Sample Output 1

358786246

Sample Input 2

4
1 1 1 999999999
6 12 8 15

Sample Output 2

264298644