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

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

Một xâu ~S~ được gọi là xâu đối xứng nếu ~S = S'~ với ~S'~ là xâu nhận được từ xâu ~S~ khi đọc từ phải qua trái. Ví dụ: Xâu ~'aba'~ là xâu đối xứng, còn xâu ~'abc'~ là xâu không đối xứng.

Cho một xâu ~S~ gồm ~1 \le n \le 1000~ kí tự.

Yêu cầu: Hãy tìm cách chia xâu ~S~ thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng.

Input

• Dòng đầu gồm một số nguyên ~n~ là độ dài của xâu ~S~.
• Dòng thứ hai là nội dung xâu ~S~.

Output

• Dòng đầu ghi một số nguyên ~k~ (số đoạn ít nhất tìm được).
• ~K~ dòng sau, mỗi dòng ghi một số nguyên ~t_i~, với ~t_i~ là vị trí kết thúc của đoạn thứ ~i~.

Sample Input 1

 8
 abbacdcb

Sample Output 1

3
4
7
8

Gọi ~A~ là dãy số với ~A(i)~ được tạo bởi ghép ~i~ số nguyên tố đầu tiên với nhau: ~2, 23, 235, 2357, 235711, 23571113, ... ~.

Cho ~n~ và ~k~, hãy tìm cách xóa ~k~ chữ số ra khỏi số ~A(n)~ để thu được số lớn nhất có thể.

Input

• Gồm một dòng chứa hai số nguyên không âm ~n~ và ~k~ ~(1 \le n \le 50000)~, dữ liệu đảm bảo ~k~ bé hơn số chữ số của ~A(n)~.

  Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~50\%~ số test có ~n \le 50~.
• ~50\%~ số test không ràng buộc gì thêm.

Sample Input 1:

7 4

Sample Output 1:

711317

Cho một dãy ~a~ gồm ~n~ phần tử phân biệt. Ta định nghĩa hàm ~g(l,r)~ như sau:

• ~g(l,r) = Max(l,r) \oplus MaxSecond(l,r)~. Ở đây, ~\oplus~ là toán tử ~xor~.
• Trong đó ~Max(l,r)~ là số lớn nhất trong đoạn ~[l,r]~, ~MaxSecond(l,r)~ là số lớn thứ hai trong đoạn ~[l,r]~.

Hãy tính ~max(g(l,r))~ với mọi đoạn ~[l,r]~ của dãy ~a~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~. ~(1 \le n \le 10^5).~
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~. ~(1 \le a[i] \le 10^9~ ~\forall (1 \le i \le n))~.

Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~50\%~ số test có ~n \le 1000~.
• ~50\%~ còn lại không có điều kiện gì thêm.

Sample Input 1:

5
5 2 1 4 3

Sample Output 1:

7

Explanation 1:

• Kết quả chính là ~g(4,5) = 4 \oplus 3 = 7~, hoặc ~g(1,2)~.

Sample Input 2:

5
9 8 3 5 7

Sample Output 2:

15

Explanation 2:

• Kết quả là ~g(2,5)~.