String Puzzle.
/
No tags
Problem
Editorial
Analytics

We are given two strings A and B which satisfy these conditions :

1.A and B both consist of exactly n characters each.

2.Each character in A and B is one of the first k lowercase letters of English alphabet.

3.There exists a string C such that A+C=C+B.

Note: + 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.

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

Constraints

n<= 1000,000,000

k<=26

SAMPLE INPUT
2 2
SAMPLE OUTPUT
6
Explanation

six cases are ---("aa", "aa"), ("ab", "ab"), ("ab", "ba"), ("ba", "ab"), ("ba", "ba"), ("bb", "bb").

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...