Count of arrays having consecutive element with different values

general
, ,
1

Given two positive integers n , m . The task is to count the number of different array that can be formed of size n such that each element is between 1 to m and two consecutive element are different. Also, the first and last elements of each array should be same.

Print Answer of modulo of 10^9 + 7.

Expected TC: O(logn)
Contraints: 3 <= N, M <= 10^18

I/p O/p
3 3 --> 6
3 4 --> 12
4 4 --> 24

2

The question belongs to Mobstac Intern Hiring Challenge on Hackerearth named there as The counting Problem which now is ended (5 PM as on 20 Dec ).
I tried using recursion + Memoization just got 30.
Would love to know about full solution, if there is some formula / other approach.

3

Is this formula correct? m* (m-1)^(n-3) * (m-2)

4

ashish_kaur I am not sure. How did you get this?