#include <vector>
#include <map>
#include <string>
#include <iostream>

using namespace std;

class Solver
{
    // группа состояний с одинаковыми суффиксами
    struct Group
    {
        // (символ, индекс группы)
        vector<pair<int, int>> transitions;
        vector<int> states;
    };

    // параметры задачи
    int K, A, Mod;
    // количество состояний
    int states;
    // группы состояний
    vector<Group> groups;
    // отопражение суффикс -> индекс группы
    map<string, int> mapping;
    // переходы между состояниями 
    vector<pair<int, int>> transitions;

private:
    // возвращает true, если подстроки (start1, length) и (start2, length) равны
    bool areEqual(const string& s, int start1, int start2, int length)
    {
        for (int i = 0; i < length; i++)
        {
            if (s[start1 + i] != s[start2 + i])
            {
                return false;
            }
        }
        return true;
    }

    // возвращает true, если строка заканчивается тандемным повтором длины <= k
    bool endsWithRepeat(const string& s, int k)
    {
        while (k > 0)
        {
            if (s.size() >= 2 * k)
            {
                if (areEqual(s, s.size() - k, s.size() - 2 * k, k))
                {
                    return true;
                }
            }
            k -= 1;
        }
        return false;
    }

    // возвращает кратчайший суффикс, который не теряет информацию о будущих тандемных повторах длины <= k
    string getShortestSuffix(const string& s, int k)
    {
        size_t start = 0;
        while (start < s.length())
        {
            for (int len = k; len > 0; len--)
            {
                int exc = start + 2 * len - (int)s.length();
                if (exc <= 0)
                {
                    break;
                }
                if (areEqual(s, start, start + len, len - exc))
                {
                    return s.substr(start);
                }
            }
            start += 1;
        }
        throw 0;
    }

    // приводит суффикс к нормализованнному виду
    // только для суффиксов вида "нормализованный суффикс + один произвольный символ"
    void normalize(string& s)
    {
        for (size_t i = 0; i < s.length() - 1; i++)
        {
            if (s[i] == s.back())
            {
                s[i] = 'A';
            }
            else if (s[i] < s.back())
            {
                s[i] += 1;
            }
        }
        s.back() = 'A';
    }

    // создаёт группы состояний, достижимых из группы с указанным суффиксом
    int createGroups(const string& suffix)
    {
        if (mapping.find(suffix) == mapping.end())
        {
            int group = groups.size();
            groups.push_back(Group());
            groups.back().states.resize(A, -1);
            mapping[suffix] = group;
            for (int i = 0; i < A; i++)
            {
                string temp = suffix + string(1, 'A' + i);
                if (!endsWithRepeat(temp, K))
                {
                    temp = getShortestSuffix(temp, K);
                    normalize(temp);
                    groups[group].transitions.push_back(make_pair(i, createGroups(temp)));
                }
            }
        }
        return mapping[suffix];
    }

    // создаёт массив переходов между состояниями
    int createStates(int group, int chars)
    {
        int state = groups[group].states[chars - 1];
        if (state < 0)
        {
            state = states++;
            groups[group].states[chars - 1] = state;
            for (auto it = groups[group].transitions.begin(); it != groups[group].transitions.end(); ++it)
            {
                if (it->first < chars)
                {
                    transitions.push_back(make_pair(state, createStates(it->second, chars)));
                }
                else if (it->first == chars)
                {
                    transitions.push_back(make_pair(state, createStates(it->second, chars + 1)));
                }
                else
                {
                    break;
                }
            }
        }
        return state;
    }

    void add(int& res, int arg)
    {
        res += arg;
        if (res > Mod)
        {
            res -= Mod;
        }
    }

    void mul(int& res, int arg)
    {
        res = (long long)res * arg % Mod;
    }

public:
    Solver(int k, int a, int mod) : K(k), A(a), Mod(mod), states(0)
    {
        createStates(createGroups("A"), 1);
    }

    int solve(int n)
    {
        vector<int> curr(states, 0);
        vector<int> next(states, 0);
        curr[0] = 1;
        for (int i = 2; i <= n; i++)
        {
            for (int j = 0; j < transitions.size(); j++)
            {
                add(next[transitions[j].second], curr[transitions[j].first]);
            }
            curr.assign(next.begin(), next.end());
            next.assign(states, 0);
        }

        int res = 0;
        for (int i = 0; i < groups.size(); i++)
        {
            for (int j = 0; j < groups[i].states.size(); j++)
            {
                if (groups[i].states[j] >= 0)
                {
                    int cnt = curr[groups[i].states[j]];
                    for (int k = 0; k <= j; k++)
                    {
                        mul(cnt, A - k);
                    }
                    add(res, cnt);
                }
            }
        }
        return res;
    }
};

#define NOMINMAX
#include <Windows.h>

int main()
{
    LARGE_INTEGER start;
    QueryPerformanceCounter(&start);

    int k = 9;
    int a = 26;
    int n = 100;
    int mod = 1000000007;

    Solver s(k, a, mod);
    int res = s.solve(n);

    LARGE_INTEGER end, freq;
    QueryPerformanceCounter(&end);
    QueryPerformanceFrequency(&freq);

    cout << "k = " << k << endl;
    cout << "a = " << a << endl;
    cout << "n = " << n << endl;
    cout << "mod = " << mod << endl;
    cout << "res = " << res << endl;
    cout << "time = " << (end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart << " ms" << endl;
    return 0;
}