#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

int cmp(const void * x, const void * y) {

#define datatype int

    datatype dx = *((datatype *)(x)), dy = *((datatype *)(y));

    //x < y

    return dx > dy ?  : -;

#undef datatype

}

char str[];

int s[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    std::ios::sync_with_stdio(), cin.tie();

    cin >> str;

    bool f, f1;

    int n = strlen(str);

    for (int i = ; i < n; i++) s[i] = str[i] - '';

    int ans;

    f = true, f1 = false;

    int b = s[];

    int ptr = ;

    while (ptr < n) {

        b++;

        if (b < ) {

            if (s[ptr] == b) {

                ptr++;

                continue;

            } else {

                if (f1) {

                    f = false;

                    break;

                } else {

                    f1 = true;

                    ans = b;

                }

            }

        } else {

            if (s[ptr] == b /  && s[ptr + ] == b % ) {

                ptr += ;

                continue;

            } else {

                if (f1) {

                    f = false;

                    break;

                } else {

                    f1 = true;

                    ans = b;

                }

            }

        }

    }

    if (f && f1) {

        cout << ans << endl;

        return ;

    }

    f = true, f1 = false;

    b = s[] *  + s[];

    ptr = ;

    while (ptr < n) {

        b++;

        if (b < ) {

            if (s[ptr] == b) {

                ptr++;

                continue;

            } else {

                if (f1) {

                    f = false;

                    break;

                } else {

                    f1 = true;

                    ans = b;

                    ptr++;

                }

            }

        } else {

            if (s[ptr] == b /  && s[ptr + ] == b % ) {

                ptr += ;

                continue;

            } else {

                if (f1) {

                    f = false;

                    break;

                } else {

                    f1 = true;

                    ans = b;

                }

            }

        }

    }

    if (f && f1) {

        cout << ans << endl;

        return ;

    }

    return ;

}

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

int cmp(const void * x, const void * y) {

#define datatype int

    datatype dx = *((datatype *)(x)), dy = *((datatype *)(y));

    //x < y

    return dx > dy ?  : -;

#undef datatype

}

lint a[][];

const lint inf = 0x7FFFFFFFFFFFFFFF;

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    std::ios::sync_with_stdio(), cin.tie();

    for (int i = ; i < ; i++) {

        for (int j = ; j < ; j++) {

            lint aaa = , tmp = ;

            if (i < j - ) continue;

            for (int k = ; k < j; k++) {

                aaa *= (i - k + );

                tmp += aaa;

                if (tmp > 1e18) break;

            }

            if (tmp > 1e18) a[i][j] = inf;

            else a[i][j] = tmp;

        }

    }

    lint n, l;

    cin >> n >> l;

    bool f = false;

    for (int i = ; i < ; i++) {

        for (int j = ; j < min((lint), l + ); j++) {

            if (a[i][j] >= n && !f) {

                cout << i << endl;

                f = true;

            }

        }

    }

    if (!f) {

        if (l == ) cout << n -  << endl;

        else if (l == ) {

            lint tmp = (lint)sqrt(n);

            if (tmp * tmp +  >= n) cout << tmp << endl;

            else cout << tmp +  << endl;

        } else {

            for (int i = ;; i++) {

                if (i < l - ) continue;

                lint aaa = , tmp = ;

                for (int k = ; k < l; k++) {

                    aaa *= (i - k + );

                    tmp += aaa;

                    if (tmp > 1e18) break;

                }

                if (tmp > n) {

                    cout << i << endl;

                    break;

                }

            }

        }

    }

    return ;

}

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

int cmp(const void * x, const void * y) {

#define datatype int

    datatype dx = *((datatype *)(x)), dy = *((datatype *)(y));

    //x < y

    return dx > dy ?  : -;

#undef datatype

}

lint dp[][];

const int mod = ;

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    std::ios::sync_with_stdio(), cin.tie();

    int n, m, k;

    cin >> n >> m >> k;

    memset(dp, , sizeof(dp));

    dp[][] = m;

    for (int i = ; i <= n; i++) {

        for (int j = ; j < k; j++) {

            dp[i + ][j + ] = (dp[i + ][j + ] + dp[i][j]) % mod;

            dp[i + ][] = (dp[i + ][] + dp[i][j] * (m - )) % mod;

        }

    }

    lint ans = ;

    for (int i = ; i < k; i++) ans = (ans + dp[n][i]) % mod;

    cout << ans << endl;

    return ;

}