Gizli sonluq ağacının zirvələri

Sufiks ağacı, bir sətirin bütün sufikslərini qeyri-aşkar trie kimi ehtiva edən və minimum sayda zirvələrə malik olan bir strukturdur. Məsələn, "ababa" sətirinin qeyri-aşkar sufiks ağacı aşağıda göstərildiyi kimidir (onda 3 zirvə var):

Sizə t sətirinin k dəfə təkrarlanması ilə əmələ gələn s sətiri verilir. Yəni, . s sətirinin qeyri-aşkar sufiks ağacındakı zirvələrin sayını hesablayın.

Giriş məlumatları

Birinci sətirdə tam ədəd k (1 ≤ k ≤ 10^9) verilmişdir. İkinci sətirdə t sətiri verilmişdir (1 ≤ |t| ≤ 10). t sətiri yalnız kiçik latın hərflərindən ibarətdir.

Çıxış məlumatları

Tək tam ədəd çıxarın — s sətirinin qeyri-aşkar sufiks ağacındakı zirvələrin sayı.

Nümunələr