duong3982 được noodles0428 tặng một xâu ký tự ~S~, chỉ gồm các ký tự tiếng Anh in thường, và ký tự ?.

Một xâu ~s~ được gọi là đẹp khi và chỉ khi điều kiện sau thỏa mãn:

Với mọi xâu con liên tiếp độ dài lớn hơn hoặc bằng ~2~ của ~s~, không có ký tự nào có số lần xuất hiện nhiều hơn ~\frac{|s|}{2}~, với ~|s|~ là số ký tự của xâu ~s~.

Ví dụ:

• Xâu wrongans là xâu đẹp.
• Xâu accepted không phải xâu đẹp, do có xâu con acc có ký tự ~c~ xuất hiện ~2 > \frac{3}{2}~ lần.

Sau khi được noodles0428 tặng xâu ~S~, duong3982 tự hỏi, có bao nhiêu cách thay dấu ? thành các ký tự tiếng Anh in thường, thỏa mãn ~S~ là xâu đẹp?

Vì kết quả có thể rất lớn, hãy in ra kết quả modulo ~20032024~.

INPUT

• Dòng duy nhất chứa xâu ~s~ (độ dài không vượt quá ~5000~).

OUTPUT

• Dòng duy nhất là đáp số của bài toán, khi chia dư cho ~20032024~.

SAMPLE INPUT 1

a?m

SAMPLE OUTPUT 1

24

SAMPLE INPUT 2

a?a

SAMPLE OUTPUT 2

0