There are n butterflies and k colors.You have to color the butterflies, but you cant color two adjacent butterflies with the same color. There is also a special color(it could be one of the k colors or a different color). There is no coloring restriction while using the special color. You have to output the number of ways mod(1e9+7) of coloring the n butterflies….

Find the number of such possible arrangements after doing mod1e9+7 .

ip
5 4 3
op 469

5 2 3
op 2