Marisa tin rằng danmaku hình tam giác là sặc sỡ nhất. Cho 3 điểm tọa độ nguyên trên lưới tọa độ ~Oxy~, hãy xác định xem 3 điểm này có tạo thành hình tam giác được hay không?

Input

• 3 điểm có tọa độ nguyên.

Output

• YES và NO tương ứng với có hoặc không tạo được hình tam giác.

Sample Test

Input 1

0 0 0 1 1 0

Output 1

YES

Input 2

727 1 727 2 727 3

Output 2

NO

Giới hạn

• Tọa độ các điểm có giá trị tuyệt đối không vượt quá ~10^9~.

Cho dãy số nguyên dương ~A~ gồm ~N~ phần tử ~a_1,a_2,…,a_N~. Với phần tử ~a_i~ của dãy số, số chính phương kết hợp của ~a_i~ là số chính phương ~s~ lớn nhất thoả mãn: khi thay ~a_i~ thành ~a_i \times s~ thì bội chung nhỏ nhất của dãy số ~A~ không đổi. Yêu cầu: Cho dãy số ~A~ và vị trí ~i~, tìm số chính phương kết hợp của phần tử ~a_i~.

Dữ liệu:

• Vào từ thiết bị vào chuẩn có khuôn dạng:
  • Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~i~ ~(i≤N≤10^6)~;
  • Dòng thứ hai gồm N số nguyên dương mô tả dãy số A, các số có giá trị không quá ~10^7~.

Kết quả:

• Ghi ra thiết bị ra chuẩn một dòng gồm một số nguyên duy nhất là phần dư của kết quả tìm được khi chia cho ~10^9+7~.

Ràng buộc:

• Có 50% số test ứng với 50% số điểm của bài thỏa mãn: ~N≤20; a_i≤20~;
• 30% số test khác ứng với 30% số điểm của bài thỏa mãn: ~N≤10^3; a_i≤10^7~;
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Sample Test

Input

5 2
8 4 6 18 5

Output:

9

Giải thích:

• Bội chung nhỏ nhất của dãy số A là 360. Thay số 4 thành 4×9=36 thì dãy số là 8,36,6,18,5 vẫn có bội chung nhỏ nhất là 360. Vậy kết quả là 9.

Cho dãy gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ chỉ gồm các số ~1~, ~2~ và ~3~. Đếm số cách xoá một vài phần tử của dãy (có thể không xoá) để nhận được một dãy thoả mãn hai yêu cầu sau:

1. Dãy còn ít nhất ~3~ phần tử
2. Phần tử đầu tiên của dãy có giá trị ~1~, tiếp theo là một số phần tử có giá trị ~2~ (ít nhất một số ~2~), kết thúc bằng đúng một phần tử có giá trị ~3~.

Ví dụ: các dãy ~\{1, 2, 2, 3\}~ và dãy ~\{1, 2, 3\}~ thoả mãn yêu cầu, các dãy ~\{1, 2, 3, 3\}~ và dãy ~\{1, 1, 2, 3\}~ không thoả mãn yêu cầu.

Vì số cách xoá có thể rất lớn, hãy in ra số cách xoá chia lấy dư cho ~10^9+7~.

Input

Dòng đầu chứa số nguyên ~n~ (~1 \le n \le 10^6~) là số lượng phần tử của dãy.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 3~) mô tả các phần tử của dãy.

Output

Gồm một dòng duy nhất chứa một số nguyên là số cách xoá thoả mãn yêu cầu đề bài, chia lấy dư cho ~10^9+7~.

Example

Input

8
1 2 1 2 3 1 2 3

Output

15

Có hai thao tác như sau:

1. Tăng số lên ~1~ đơn vị, nếu số có giá trị ~m~ thì quay về ~1~;
2. Gán số đó thành số ~X~.

Cho dãy gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(a_i \ne a_{i+1}; a_i \le m)~. Ban đầu ở giá trị ~a_1~, sử dụng các thao tác để từ ~a_1~ đi đến ~a_2~, từ ~a_2~ đi đến ~a_3~, ..., sao cho đi qua tất cả các giá trị theo thứ tự từ ~a_1~ đến ~a_n~. Hãy chọn số ~X~ để số thao tác cần sử dụng là nhỏ nhất có thể. In ra số lượng thao tác ít nhất tìm được.

Input

• Dòng đầu chứa hai số nguyên ~n~, ~m~ (~2 \le n, m \le 10^5~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le m~).

Output

In ra kết quả của bài toán.

Scoring

• Subtask 1 (~25~ điểm): ~1 \le a_1 < a_2 < \dots < a_n \le m~.
• Subtask 2 (~25~ điểm): ~n, m \le 10^3~.
• Subtaks 3 (~50~ điểm): Không có ràng buộc gì thêm.

Example

Input

4 5
1 2 4 5

Output

3

Note

Chọn X = 4

Input

2 3
2 1

Output

1

Note

Chọn X = 1

There are ~N~ pictures delivered for the exhibition. The ~i~-th painting has a beauty value of ~A_i~.

The exhibition organizer wants to make a triptych by choosing three paintings having indices of ~x, y, z~ such that ~1\le x\lt y\lt z\le N~ and ~A_x = P, A_y = Q, A_z = R~.

Write a program to help the organizer count the number of different triples of paintings that can be made into triptychs. Two triples of paintings are considered different if they do not contain the same set of paintings.

Input Specification

• The first line of input contains an integer ~N~;

• The following line of input contains ~N~ integers ~A_1, A_2, ..., A_N~;

• The third line of input contains three integers ~P, Q, R~.

Output Specification

• Output the number of distinct triptychs the organizer can make.

Examples

Input

5
1 2 2 1 2
1 2 1

Output

2

Explanation

Such triples of indices of paintings are: ~(1, 2, 4), (1, 3, 4)~.

Input

5
1 2 2 1 2
2 1 1

Output

0

Explanation

There are no ways to make a triptych.

Constraints

For all subtasks:

• ~3\le N\le 2\times 10^6~

• ~1\le A_i\le 10^9~

• ~1\le P, Q, R \le 10^9~

Subtask 1 [30%]

• ~3\le N\le 200~

Subtask 2 [30%]

• ~200\lt N\le 3\times 10^4~

Subtask 3 [40%]

• No additional constraints