Masala #0748

Dasturlash musobaqasi bilan shug’ullanib yurgan barchaga Prefiks funksiya nima ekanligi ma’lum bo’lsa kerak. Agar bilmasangiz Prefiks funksiya haqida https://e-maxx.ru/algo/prefix_function havoladan o’rganib olishingiz mumkin.

Keling endi asosiy masalaga o’tamiz!

\(S\) to’plam \(m\) ta harfli alifbodan tuzilgan uzunligi \(n\) ga teng bo’lgan barcha satrlar to’plami.

\(F(s)\) funksiyasi \(\text{prefix\_function}(s)\) dan olingan to’plamning eng katta qiymati bo’lsin.

Sizning vazifangiz \(\sum_{s∈S}F(s)\) ni \(X\) ga bo’lgandagi qoldiqni hisoblashdan iborat.

Kirish faylining yagona satrida uchta butun son, \(n (1 \le n \le 22)\), \(m (1 \le m \le 10^9)\) va \(X (1 \le X \le 10^9)\) sonlari kiritiladi.

Chiqish faylida yagona butun son,   \(\sum_{s∈S}F(s)\) ni \(X\) ga bo’lgandagi qoldiqni chop eting!