Người ta xâu ~n~ viên đá quý kích thước giống nhau thành một vòng đeo cổ (~5≤n≤120~), mỗi viên có một màu trong số các màu được đánh số từ 1 đến 9. Khi đó vòng được biểu diễn bởi một xâu ~s~ gồm n kí tự trong tập ['1'..'9']. Để tăng tính độc đáo cho vòng trang sức quý này người ta định lắp khóa vào vị trí sao cho khi mở vòng ra được một dây đá quý có tính chất: không phụ thuộc vào việc cầm đầu dây nào bên tay phải và đầu kia bên tay trái, ta đều được một chuỗi hạt giống nhau, tức là viên đá thứ i từ trái sang luôn có màu ~j~ không phụ thuộc vào cách cầm.

Yêu cầu: Hãy tìm số cách đặt khóa vào chuỗi hạt thỏa mãn yêu cầu bài toán.

Dữ liệu vào:

• Dòng 1: Ghi một xâu ký tự st theo yêu cầu của đề bài.

Dữ liệu ra:

• Dòng 1: Ghi số cách đặt khóa trễn chuỗi hạt thỏa mãn yêu cầu bài toán.

Ví dụ:

Input

222222335533

Output

2 

Giải thích:

• Xâu s: 222222335533; ta có 2 cách đặt khóa như sau:
• 222335533222
• 533222222335