Xâu kí tự ami được định nghĩa đệ quy như sau:

• Xâu rỗng là một xâu ami.
• Nếu \(A\) và \(B\) là các xâu ami thì một xâu mới \(C\) được tạo ra bằng cách ghép hai xâu này với nhau cũng là một xâu ami (AB và BA là xâu ami).
• Nếu \(A\) là một xâu ami thì một xâu mới \(C\) được tạo ra bằng cách thêm vào vị trí đầu và cuối của \(A\) cùng một kí tự \(x\) cũng là một xâu ami (xAx là một xâu ami).

Ví dụ, một số xâu ami là \(aabb\), \(abccba\). Các xâu \(ami\), \(cuom\) không phải là xâu ami.

Các bạn có một xâu \(S\) chỉ gồm các kí tự tiếng Anh thường. Hãy xác định xem đây có phải là một xâu ami hay không.

Input

• Một dòng chứa xâu kí tự \(S\).

Output

• Hãy in ra 1 nếu xâu \(S\) là xâu ami và in ra 0 trong trường hợp ngược lại.

Scoring

Gọi \(n\) là độ dài xâu \(S\).

• Subtask \(1\) (\(60\%\) số điểm): \(1 \le n \le 100\).
• Subtask \(2\) (\(10\%\) số điểm): \(1 \le n \le 1000\).
• Subtask \(3\) (\(30\%\) số điểm): \(1 \le n \le 10^5\).

Example

caabbc

1

caabbcd

0