Əsas Məlumat
Alice və Bob bir-birlərinə mesaj göndərməyi sevirlər, lakin başqalarının onların mesajlarını oxumasını istəmirlər. Dostları Charles, Alice və Bobun bir-birlərinə göndərdikləri mesajlarla çox maraqlanır, lakin Alice və Bob mesajlarını şifrələdikləri üçün o, onları oxuya bilmir. Buna baxmayaraq, Charles şifrələnmiş mesajları (adlanan "şifrometin") ələ keçirə bilir.
Şəkil 1: Transpozisiya nümunəsi.
Son zamanlarda, Charles yalnız şifrələnmiş bir mesajı ələ keçirməklə qalmayıb, həm də bu mesajın orijinal məzmununu (adlanan "mətn") bilir. Ona Alice və Bob arasında gələcək mesajları deşifrə etməyə kömək etmək üçün sizdən ona şifrləmə açarını tapmağa kömək edəcək bir proqram yazmağınızı xahiş edir.
Charles sizə bildirib ki, Alice və Bob transpozisiya blok şifrəsi istifadə edirlər. Bu o deməkdir ki, mesajdakı hər k simvoldan ibarət blok üçün, blokdakı simvollar şifrələmə zamanı k! mümkün permutasiyadan birinə yenidən sıralanır. Hər bir permutasiya özünəməxsus uyğun şifrləmə açarı ilə müəyyən edilir. Şəkil 1-də göstərilən permutasiyaya uyğun açar (123456) → (514362) kimi bir təmsil olardı. Sizin yeganə vəzifəniz açarları saymaq olduğundan, faktiki təmsil vacib deyil.
Xoşbəxtlikdən, Charles blok ölçüsünün k olduğunu bilir və o, ələ keçirdiyi mətn və şifrometin tam k uzunluğunda bir və ya daha çox tam blokdan ibarət olduğunu bilir (yəni, natamam bloklar yoxdur) və hər biri eyni açarla şifrələnib.
Charles tərəfindən ələ keçirilmiş mətn M və şifrometin C verildikdə, proqramınız mümkün şifrləmə açarlarının sayını hesablayacaq.
Giriş verilənləri
Hər bir test üçün giriş üç sətirdən ibarətdir:
Birinci sətir müsbət tam ədəd k, blok ölçüsü (k ≥ 1).
İkinci sətir M, mətn (1 ≤ |M| ≤ 100, |M| k-nın tam bölünənidir).
Üçüncü sətir C, şifrometin (|C| = |M|).
Həm mətn, həm də şifrometin yalnız kiçik hərflərdən ibarətdir.
Çıxış verilənləri
Hər bir test üçün, k ölçüsündə mümkün şifrləmə açarlarının sayını ehtiva edən bir sətir çap edin. Bu rəqəm 2^63-1-dən çox olmayacaq. Əgər M-i C-dən k ölçüsündə bir transpozisiya şifrəsi ilə əldə etmək mümkün deyilsə, '0' (sıfır rəqəmi) çap edin.