Problem
Üniversitelerden birindeki öğrenciler, bir uçak motorunun montaj sürecini kısmen otomatik hale getirmek için bir robot tasarladılar.
Motorun montajı sürecinde, Latin alfabesinin küçük harfleriyle gösterilen 26 tür işlem gerçekleşebilir. Derleme işlemi N işlemden oluşur.
Montaj sürecinden sonraki işlemlerin bir kısmını gerçekleştirmek için robotu bir kez kullanması gerekiyor.
Robotun hafızası, her biri bir işlem içeren K hücrelerinden oluşur. İşlemler, bellekte bulundukları sıraya göre birinciden başlayarak sıralı olarak yürütülür. Sonuncuyu tamamladıktan sonra robot birincisiyle devam eder. Robot herhangi bir işlemden sonra durdurulabilir. En az K + 1 işlemi gerçekleştiren bir robot kullanmak ekonomik olarak uygundur.
Montaj süreci göz önüne alındığında, robotu kullanmanın ekonomik açıdan uygun yollarının sayısını belirleyecek bir program yazmanız gerekir.
Giriş
İlk satır K > 0 sayısını içerir - robotun belleğine yazılabilen işlem sayısı.
İkinci satır, işlemleri - motor montaj sürecini ifade eden N > K küçük Latin harflerinden oluşur. Aynı türdeki işlemler aynı harfle gösterilir (N <= 200000).
Çıktı
Tek bir tam sayı yazdırın - robotu kullanmanın uygun maliyetli yollarının sayısı.
| Giriş |
Çıktı |
|
2
zabacabab
|
5 |
2
abc |
0 |