Farmer John muốn giấu bò một thông điệp: chuỗi dài ít nhất 2, chỉ chứa A..Z.

Ông mã hóa bằng dãy thao tác. Với $S$, thao tác xóa một số, nhưng không phải tất cả, ký tự đầu hoặc cuối của $S$, rồi ghép chuỗi $S$ ban đầu vào đầu hoặc cuối phần còn lại. Một thao tác trên ABC có thể cho tám chuỗi sau:

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

Cho chuỗi mã hóa cuối, đếm số cách tạo nó bằng một hoặc nhiều thao tác từ một chuỗi nguồn nào đó. Thao tác được coi khác nhau dù cho cùng kết quả. Ví dụ, có bốn cách khác nhau tạo AAA từ AA.

In đáp án modulo 2014.

Dữ liệu vào

• Dòng 1: chuỗi mã hóa dài không quá 100.

Dữ liệu ra

• Dòng 1: số cách tạo chuỗi bằng một hoặc nhiều thao tác liên tiếp từ chuỗi ban đầu dài ít nhất 2, modulo 2014. Nếu không có cách, in không.

Ví dụ

Dữ liệu vào 1

ABABA

Dữ liệu ra 1

8

Ghi chú

Đây là các cách tạo ABABA:

1. Chuỗi ban đầu: ABA -> AB+ABA
2. Chuỗi ban đầu: ABA -> ABA+BA
3. Chuỗi ban đầu: AB -> AB+A -> AB+ABA
4. Chuỗi ban đầu: AB -> AB+A -> ABA+BA
5. Chuỗi ban đầu: BA -> A+BA -> AB+ABA
6. Chuỗi ban đầu: BA -> A+BA -> ABA+BA
7. Chuỗi ban đầu: ABAB -> ABAB+A
8. Chuỗi ban đầu: BABA -> A+BABA

Tác giả bài toán: Brian Dean và Lewin Gan