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

Cho số nguyên dương ~N~. Hãy đếm số cách xoá đi một đoạn chữ số liên tiếp của ~N~ (không được xoá hết) để nhận được số mới chia hết cho ~3~, biết rằng số mới nhận được có thể có thừa chữ số ~0~ ở đầu.

Hai cách xoá được coi là khác nhau nếu có một vị trí được xoá trong cách này nhưng không được xoá trong cách kia.

Input

• Gồm một dòng duy nhất chứa một số nguyên ~N~ (~1 \le N \le 10^{100000}~).

Output

• In ra một số nguyên là số cách xoá tìm được.

Subtasks

• Subtask 1 (~50\%~ số điểm): ~N \le 10^{300}~.
• Subtask 2 (~25\%~ số điểm): ~N \le 10^{10000}~.
• Subtask 3 (~25\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test 1

Input

1005

Output

4

Sample Test 2

Input

2009

Output

3

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

Cho một cây gồm ~N~ đỉnh. Cạnh thứ ~i~ trên cây có trọng số ~w_i~. Độ dài đường đi giữa hai đỉnh ~u~ và ~v~ được định nghĩa là tổng các cạnh nằm trên đường đi phải qua ít cạnh nhất từ ~u~ tới ~v~. Chọn ~K~ đỉnh lá sao cho tổng độ dài đường đi giữa mọi cặp đỉnh trong ~K~ đỉnh đã chọn là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ ~(1≤K≤N)~.
• ~N-1~ dòng tiếp theo, mỗi dòng chứa thông tin về một cạnh của cây từ nút ~u_i~ đến ~v_i~ với trọng số ~w_i~ ~(1≤w_i≤10^5)~.

Output

• Gồm một số nguyên duy nhất là tổng khoảng cách nhỏ nhất trong cách chọn K nút lá tốt nhất.

Scoring

• Sub1: ~1 ≤ N ≤ 20~;
• Sub2: ~1 ≤ N ≤10^5, K=2~;
• Sub3: ~1 ≤ N ≤2000, K=3~;
• Sub4: ~1 ≤ N ≤10^5, K≤100~.

Example

Input

4 2
1 2 2
1 3 3
1 4 4

Output

5

Input

4 3
1 2 2
1 3 3
1 4 4

Output

18