Farmer John có một thông điệp bí mật muốn giấu những cô bò của mình; thông điệp là một xâu có độ dài ít nhất \(2\) và chỉ chứa các ký tự từ A đến Z.

Để mã hóa thông điệp, FJ áp dụng một chuỗi các "thao tác" lên nó. Mỗi thao tác trên một xâu \(S\) trước hết rút ngắn \(S\) bằng cách xóa ký tự đầu tiên hoặc ký tự cuối cùng, sau đó ghép xâu \(S\) ban đầu vào đầu hoặc cuối xâu đã rút ngắn. Chẳng hạn, một thao tác trên xâu ABCD có thể tạo ra một trong bốn xâu sau:

BCDABCD
ABCABCD
ABCDABC
ABCDBCD

Cho xâu đã mã hóa cuối cùng, hãy đếm số cách FJ có thể tạo ra xâu này bằng cách áp dụng liên tiếp một hoặc nhiều thao tác lên một xâu nguồn nào đó. Các thao tác được coi là khác nhau ngay cả khi chúng tạo ra cùng một bản mã của thông điệp của FJ. Chẳng hạn, có bốn cách riêng biệt để thu được AAA từ AA, tương ứng với bốn thao tác có thể có nêu trên.

Dữ liệu vào

• Dòng đầu tiên chứa một xâu có độ dài không quá \(100\).

Ràng buộc

• Xâu đầu vào có độ dài không quá \(100\).

Dữ liệu ra

In ra số cách khác nhau mà FJ có thể tạo ra xâu đã cho bằng cách áp dụng liên tiếp một hoặc nhiều thao tác lên một xâu nguồn có độ dài ít nhất \(2\). Nếu không có cách nào, in ra \(0\).

Ví dụ

ABABA

6

Nguồn

USACO 2014 February Contest, Bronze — Secret Code

Tác giả: Brian Dean và Lewin Gan.