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