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 một số nhưng không phải tất cả các ký tự đầu xâu, hoặc một số nhưng không phải tất cả các ký tự cuối xâu, 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 ABC có thể tạo ra một trong tám xâu sau:

AABC
ABABC
BCABC
CABC
ABCA
ABCAB
ABCBC
ABCC

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.

In đáp án theo modulo \(2014\).

Dữ liệu vào

• Dòng đầu tiên chứa một xâu đã mã hóa 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 theo modulo \(2014\) số cách 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 ban đầu có độ dài ít nhất \(2\). Nếu không có cách nào, in ra \(0\).

Ví dụ

ABABA

8

Nguồn

USACO 2014 February Contest, Silver — Secret Code

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