PairsOfStrings | Topcoder Archive

Problem Statement

We are interested in pairs of strings (A, B) that satisfy the following conditions:

A and B consist of exactly n characters each.
Each character in A and B is one of the first k lowercase letters of the English alphabet.
There exists a string C such that A + C = C + B. Here, + denotes string concatenation.

For example, if n = 3 and k = 4 then one valid pair of strings is ("aad", "daa"): both strings have length 3, only the first 4 letters are used in each of them, and C = "aa" shows that the third condition is satisfied as well.

You are given the ints n and k. Find the number of such pairs of strings, and return the number modulo 1,000,000,007.

Definition

Class:: PairsOfStrings
Method:: getNumber
Parameters:: int, int
Returns:: int
Method signature:: int getNumber(int n, int k)
(be sure your method is public)

Constraints

n will be between 1 and 1,000,000,000, inclusive.
k will be between 1 and 26, inclusive.

Examples

```
2
```
```
2
```
```
Returns: 6
```
The following 6 pairs satisfy the conditions: ("aa", "aa"), ("ab", "ab"), ("ab", "ba"), ("ba", "ab"), ("ba", "ba"), ("bb", "bb").
```
3
```
```
2
```
```
Returns: 20
```
```
3
```
```
4
```
```
Returns: 184
```
```
6
```
```
2
```
```
Returns: 348
```
```
100
```
```
26
```
```
Returns: 46519912
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.