A20250408a_google_dp

'''
A20250408a_google_dp
assume you were given an n fences

you need to paint them with k colours

thing is no more then 2 fences have same color

find the number of ways to make this possible

---------------------------------------------------------------------------------------

important thing to be noted here is

this needs to be solved with dp states

assume you have matching btw i and i-1 treat this as dp 0 state for i
assume you have no matching btw i and i-1 treat this as dp 1 state for i

soo

dp[i][0] = dp[i-1][1] #the i-1 cannot be matched with i-2 so only 1st state of i-1 is choosen ,that's it when matching requires you need to choose 1st state of i-1
dp[i][1] = (k-1)*(dp[i-1][1] + dp[i-1][0])#now you do not care, whether i-1 matches with i-2 or not so taking both ways into consideration and multiplying those with left out paints count

k will be greater than 1

-----------------------------------------------------------------------------------------------------
inputs - n and k
3
2

outputs -
6

'''

n = int(input())
k = int(input())
#we need 2 states here
#i must be matching with i-1 is 0 state
#i must not be matching with i-1 is 1 state
dp = [ [0,0] for _ in range(n)]
dp[0][0] = 0 #this is important ,there is no i-1 so you cannot match with i-1 color
dp[0][1] = (k-1) + 1 #you dont care about i-1 ,which leaves you k-1 options ,but i-1 doesnt exist here so you can have total k as your choices here
for i in range(1,n):
    #if i need to match with i-1
    dp[i][0] = dp[i-1][1] #the exact number of i-1 dp state that is not matching with i-2
    #if i need not to match with i-1
    dp[i][1] = (dp[i-1][1]+dp[i-1][0]) * (k-1) #now you need not to care whether i-1 matches with i-2 or not ,you are considering both states of it

finalAnswer = (dp[n-1][0]+dp[n-1][1])
print(finalAnswer)