暗号II
题号：NC219115
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小源很快就是破解了小凡的暗号，于是小凡想了一个办法，那就是将暗号进行处理，这下小源就没法识破了。
总所周知，算法是会产生冲突的，即两个串的值可能相同。现在给你一个函数，以及相关参数，再给一个字符串，小凡想知道所有长度为的串里面，有几个串与串的值相同。
小凡采用的方法如下： 
long long gethash(string s) 
{      
    long long hashsum = 0;      
    for(int i=0; i<s.size(); i++) 
        hashsum = (hashsum*base+s[i]-'a')%p;      
    return hashsum;
}

输入描述:

第一行三个整数表示函数的参数，表示要求的长度。
第二行一个字符串，用表示的长度，保证。

输出描述:

输出与串值相同的字符串个数（如果的话，也包括它本身）。
由于答案可能会很大，请对取模。
示例1

输入

复制 
1 13 1
a

输出

复制 
2
示例2

输入

复制 
10 97 5
abb

输出

复制 
122495