# PROBLEM LINK:

# DIFFICULTY:

MEDIUM

# PREREQUISITES:

Math, Combinatorics.

# ALGORITHMIC STEPS:

Analyze four cases:

- s = 1 or s > k, the answer is n^k.
- s = k, the answer is n^(k + 1) / 2.
- s mod 2 = 1, any string like ababababâ€¦ is ok, so the answer is n^2.
- s mod 2 = 0, all symbols coincide and the answer is n.

# EXPLANATION:

```
STEP 1. If s==1 then the answer is all possible strings. That is n^k.
If s>k. There are 0 substrings of length s.
All of them are palindromes because Any statement about empty set is truth.
(MOST YOU MIGHT HAVE MISSED THIS POINT :) )
STEP 2. The most simple observation says, If s==k then answer is simply n^(k+1)/2.
OTHER STEPS:
Let's look at the case when s%2 == 1 Let a = an arbitrary character from "n" possible characters.
b = an arbitrary character other than "a" from "n" possible characters.
If s is odd, a substring whose length is s out of following string is always a palindrome.
String : abababababa Substring s=3 => aba or bab s=5 => ababa or babab ... you see the pattern. So we have (n * (n-1)) possible patterns. Now, also remember that a string consisting of same characters are also allowed. string : aaaaaaa substring s=3 =>aaa s=5 => aaaaa And we have "n" number of such strings.
So, answer is n*(n-1) + n = n*(n-1+1) = n*n
Let's see what happens when s is even. If s is even, only allowed strings are the ones that consist of same characters. There are n such strings.
So answer for (s%2 == 0) is n.
```

# SOLUTIONS:

## Solution

```
#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define F first
#define S second
#define N 100005
const int mod = 1e9 + 7;
using namespace std;
int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = (long long)res * a % mod;
a = (long long)a * a % mod;
b >>= 1;
}
return res;
}
void solve() {
int t=1;
while (t--) {
int k, n, s;
cin >> k >> n >> s;
if (s <= 0) {
puts("0");
} else if (s == 1 or s > k) {
cout << qmi(n, k) % mod << endl;
} else if (s == k) {
cout << qmi(n, (k + 1) / 2) % mod << endl;
} else if (s & 1) {
cout << n*n % mod << endl;
} else {
cout << n % mod << endl;
}
}
return;
}
int32_t main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
```