Cho một chuỗi kí tự gồm các kí tự chữ viết hoa, có bao nhiêu cách chọn ra bộ kí tự AMS khác nhau. Các kí tự được chọn phải để theo thứ tự trước sau như ban đầu.

Ví dụ, với câu CHAO AMS có ~2~ bộ kí tự AMS, tính theo vị trí là ~(3, 7, 8)~ và ~(6, 7, 8)~.

Input

Nhập vào một xâu văn bản ~S~ có tối đa ~10^6~ kí tự. Các kí tự đều là chữ in hoa.

Output

Ghi ra số cách chọn bộ kí tự AMS.

Ví dụ

Input

CHAO AMS

Output

2

Input

AMSER IN AMS

Output

4

Subtask

• ~30\%~ test tương ứng với ~30\%~ số điểm có xâu dữ liệu không quá ~250~ kí tự.
• ~30\%~ test tương ứng với ~30\%~ số điểm có xâu dữ liệu không quá ~450~ kí tự.
• ~20\%~ test tương ứng với ~20\%~ số điểm có xâu dữ liệu không quá ~10^4~ kí tự.
• ~20\%~ test tương ứng với ~20\%~ số điểm có xâu dữ liệu không quá ~10^6~ kí tự.

Cho một chuỗi kí tự ~S~ chỉ gồm kí tự ~0~ và kí tự ~1~. Hãy tìm cách hoán đổi vị trí các kí tự trong chuỗi ~S~ để không có hai kí tự ~1~ nào xếp cạnh nhau và số lần hoán đổi là ít nhất.

Input:

• Dòng đầu là số nguyên dương ~N~ là độ dài chuỗi kí tự ~S~.
• Dòng tiếp theo là chuỗi kí tự ~S~.

Output:

Ghi ra số lần ít nhất hoán đổi vị trí thoả mãn yêu cầu đề bài. Nếu không có cách đổi chỗ để thoả mãn thì in ra ~-1~.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thoả mãn ~N \le 30;~
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N = 2 * K ~ với ~K~ là số lượng kí tự ~1~ có trong chuỗi kí tự ~S;~
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài ~N \le 5000.~

Ví dụ

Input

7
1110000

Output

1

Giải thích: ~1010100~

Input

8
11110000

Output

2

Giải thích: ~10101010~