## Approach

The approach is simple. As the password is of length N, we start filling each character of the password with one of the characters of that language.

The first character of the password, i.e. password[0] can be any character of the language. Thus the number of possibilities for the first character of the password is K.

For password[1], the number of possibilities is K-1 because repetition is not allowed i.e. password[1] can’t be the same as password[0].

Similarly, for password[2], the number of possibilities is K-2 because it can’t be the same as any of the first two characters of the password.

Thus for password[i], the total number of possible characters are K-i.

The total number of distinct passwords= **(possible characters at password[0])**** x ****(possible characters at password[1])**** x … x ****(possible characters at password[N-1])**.

Thus the total number of characters = K x (K-1) x (K-2) x … x (K-(N-1)).

Thus we output (K x (K-1) x (K-2) x … x (K-(N-1))) modulo 10^{9} + 7.

The above expression can also be written as (factorial(K)/factorial(N)) or ^{K}P_{N} where P denotes the number of permutations. Thus the output is also ^{K}P_{N }modulo 10^{9} + 7.

We run a for loop to calculate this, which runs for N iterations. We multiply the distinct_passwords variable by (K-i) in the i’th iteration. Since the count of distinct_password can be huge, we calculate it modulo 10^{9} + 7.

## Pseudocode for the problem

```
mod=10**9+7
n,k=map(int,INPUT().split())
distinct_passwords=1
Run i from 1 to N-1
distinct_passwords*=(k-i)
distinct_passwords%=mod
OUTPUT(distinct_passwords)
```

## Code in Python

```
mod=10**9+7
n = 2
k=3
# initialized to 1
distinct_passwords=1
for i in range(n):
# multiplying with (k-i) possibilities at ith iteration
distinct_passwords*=(k-i)
# taking it modulo mod as it can grow very large
distinct_passwords%=mod
print(distinct_passwords)
```

Input

`2 3`

Output

`6`

### Time Complexity

The time complexity of the program is O(N).

This is because our loop runs for N iterations. For the ith iteration, we are multiplying distinct_passwords by (K-i). Also, we are taking its modulo with 10^{9} + 7. Since the multiplication and modulo take O(1) time, the ith iteration takes O(1) time. Thus the time complexity = O(N) * O(1) = O(N).

### Space Complexity

The space complexity of the program is O(1).

This is because we are not using any extra space to store the information. Three to four variables in the code take constant space, i.e. O(1) space.

**Frequently Asked Questions**

**1. How is the output equal to **^{k}P_{n }modulo 10^{9} + 7?

As the password contains unique characters, let us choose N distinct characters from K characters. Since this can be done in ^{K}C_{N} and the N selected characters can be arranged in N factorial ways, the answer will be ^{K}C_{N }x factorial(N) = ^{K}P_{N} ways. Thus we output ^{K}P_{N }modulo 10^{9} + 7.

**2. Why are we calculating the result with modulo 10**^{9} + 7?

Let us not calculate the result with modulo 10^{9} + 7, then the output for ^{K}P_{N} will be very, very large as it is factorial(K)/factorial(N) since we know that the factorial grows very fast, which might lead to integer overflow. You can also verify the outputs for the program by commenting on the line distinct_passwords%mod line.

**3. How is the time complexity for each iteration O(1)?**

Each iteration involves multiplication and modulo operations. Since the multiplication is carried out internally by the hardware it is highly optimized. The reason is it is used almost everywhere. So each iteration takes constant time or O(1) time.

**4. What is the relationship between **^{k}P_{n and }^{k}C_{n}?

The ^{k}P_{n = }_{factorial(k)/factorial(k-n) while }^{k}C_{n = }_{factorial(k)/(factorial(k-n)*factorial(n)) } Thus ^{k}P_{n }_{= }^{k}C_{n}_{ x (n)!}

_{The reason is that during permutation we select and permute them too. So arranging the n elements can be done in factorial(n).}

**5. What is ****10**9+7 in the code****?**

In** **some languages like python double star represents power. So **10**9+7** represents 10 raised to 9 plus 7

**Key Takeaways**

The blog aims to teach to calculate the total number of distinct passwords. Comments have been added to the code for better understanding. You can also copy the code and run it on your system on multiple inputs to understand the approach better.

Check out __Coding Ninjas Studio__ to learn more about competitive programming, DSA, attempt mock tests, interview preparation and much more.

Happy Learning!!!