Gizli suffiks ağacının zirvələri (Çətin)

Suffiks ağacı, əgər o, sıranın bütün suffikslərini qeyri-aşkar trie kimi ehtiva edirsə və minimal sayda zirvələrə malikdirsə, qeyri-aşkar adlanır.

Məsələn, "ababa" sıranın qeyri-aşkar suffiks ağacı aşağıdakı şəkildə göstərilir (burada 3 zirvə var):

Sizə s sırasi verilir, hansı ki, t sıranın k nüsxələrinin ardıcıl birləşməsidir. Yəni, s = t + t + t + ... + t. s sıranın qeyri-aşkar suffiks ağacında zirvələrin sayını hesablayın.

Giriş verilənləri

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

Çıxış verilənləri

Tək tam ədəd çıxarın — s sıranın qeyri-aşkar suffiks ağacında zirvələrin sayı.

Nümunələr