Today, there was a test conducted by Uber and it's time slot was 8 AM to 2 PM (IST), so it has finished now. I need help in understanding the answer to a sample case of one of the problem. Problem was something like this:

There are N cities with a road between every pair of cities. Calculate the number of ways (modulo 1e9+7) such that you start travelling from **city 1** and return to the same **city 1** after completing **exactly K** trips where one trip means travelling from a current city to any other city.

Constraints: **N <= 1e9; K <= 1e6**

My approach: We start with city 1, now we have option to go (N-1) cities for 1st trip, then again (N-1) for 2nd trip, and so on. Hence, in short we have options of (N-1) cities for first (K-2) trips, then for the 2nd last trip we can go to (N-2) cities and for the last trip we have only 1 option that is to return to city 1. Hence according to this, answer should be: **(N-1)^(K-2) * (N-2)**

Sample Case: N=4, K=4

With my approach I am getting answer as **18**. But according to author the answer should be **21**. I need your help in understanding how there are 21 ways. I am not getting answer as 21 even when I try to find the ways using a pen and paper.

Appreciate your help. Thanks !