Ninja And The New Year Guests
Ninja has organized the new year party and invited all the programmers for it, as being the programmer also has been invited by Ninja.

To detect whether the guest is a programmer or not, Ninja has set some tasks for them, such that only programmers can code them.

You have also been asked to solve and code the following task to verify your identity.

Given two integers, 'N' and 'K' find the number of permutation arrays of 'N' integers from 0 to 'N' - 1 satisfying the below condition.

There should be at least 'K' positions in the array such that 'ARR[I] = I' ( 0

Question

Ninja And The New Year Guests

Ninja has organized the new year party and invited all the programmers for it, as being the programmer also has been invited by Ninja.

To detect whether the guest is a programmer or not, Ninja has set some tasks for them, such that only programmers can code them.

You have also been asked to solve and code the following task to verify your identity.

Given two integers, 'N' and 'K' find the number of permutation arrays of 'N' integers from 0 to 'N' - 1 satisfying the below condition.

There should be at least 'K' positions in the array such that 'ARR[I] = I' ( 0 <= I < N ) satisfies.

You are required to output the answer modulo 10^9 +7.

EXAMPLE:

Input: 'N' = 4 'K' = 3 
Output: 1

There is only one permutation [0, 1, 2, 3] such that a number of elements with 'ARR[I] = I' is 'K' = 3.

Input Format :

The first line of input contains an integer 'T', denoting the number of test cases. 

For each test case, there will be only one line containing two integers' N' and 'K'.

Output format :

For each test case, print the number of permutations modulo 10^9 + 7 satisfying the number of elements with 'ARR[I] = I' is 'K'.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 10^4
4 <= 'N' <= 10^18
'N - 4' <= 'K' <= 'N'
1 <= K

Time Limit: 1sec

Accepted Answer

Brute Force Approach

Approach: We will recursively find all possible permutations and then check for each of them whether it is following the condition or not.

We will maintain a counter based on that and increment it when the current permutation satisfies the condition.

Algorithm :

// It is a recursive function to get all the permutations of the current array 'arr'.

void getPermutations(arr, index, k, ans)

If 'index' >= 'arr.size()' :
- Initialize the variable 'count' by 0.
- Run a loop over array 'arr'
  - If 'arr[i] == i' then increment 'count' by 1.
- If 'count' >= 'k' then increment 'ans'.
- Call return.
Run a loop from 'index' to 'arr.size()'.
- Swap 'arr[index]' and 'arr[i]'.
- Call 'getPermutations(arr, index + 1, k, ans)'.
- Swap 'arr[index]' and 'arr[i]' again.

int numberOfPermutations(n, k)

Initialize the variable 'mod' by 1e9 + 7 and 'ans' by 0.
Initialize an empty vector 'arr'.
Run a loop from 0 to 'n - 1' and push each index in 'arr'.
Call 'getPermutations(arr, 0, k, ans)'
Return 'ans % mod'

Space Complexity: O(n)Explanation:

O(N), where 'N' is the input integer

We are using the recursion, and the recursive call stack can have maximum 'N' elements for this problem. Hence the space complexity will be O(N).

Time Complexity: OtherExplanation:

O(N * N!), where 'N' is the input integer

We are recursively finding all permutations, there will be N! recursive calls, and for each call, there will be a running loop with N iterations. Hence the overall time complexity will be O(N * N!).

Accepted Answer

Efficient Approach Using Derangements

Approach:

Let's first fix the positions in the array such that 'ARR[I] != I', Say there are 'M' such positions. (0 <= M <= 'N - K')

Let's count the number of permutations with fixed 'M' for that, and we need to choose the indices having the 'ARR[I] !=I'. We can easily find this using the simple combination formula 'NCM'.

Then we need to construct a permutation for chosen indices such that for every chosen index, 'ARR[I] !=I'; This is nothing but the derangements, and we will find this using an exhaustive search.

We will do the casework for this problem to find the derangements according to the 'K' value.

Algorithm :

// Driver function to get the modular addition.

int add(a, b)

Initialize the variable 'mod' by 1e9 + 7.
Return '((a % mod) + (b % mod)) % mod'.

// Driver function to get the modular multiplication.

int mul(a, b)

Initialize the variable 'mod' by 1e9 + 7.
Return '((a % mod) * (b % mod)) % mod'.

// Driver function to get the modular binary exponention.

int bin_pow(a, b)

Initialize the variable 'mod' by 1e9 + 7.
Update 'a' with 'a % mod'
Initialize the variable 'res' by 1.
Run a while loop till 'b' > 0.
- If 'b & 1' is true then update 'res' with 'res * a % mod'.
- Update 'a' with 'a * a % mod'.
- Update 'b' with 'b >>= 1'.
Return 'res'.

// Driver function to get the modular division.

int reverse(x)

Initialize the variable 'mod' by 1e9 + 7.
Return 'bin_pow(x, mod - 2)'.

int numberOfPermutations(n, k)

Update 'k' with 'n - k'.
Initialize the variable 'ans' by 1.
If 'k == 1' then return 'ans'.
Add 'mul(mul(n, n - 1), reverse(2))' to the 'ans'
If 'k == 2' then return 'ans'.
Add 'mul(mul(n, mul(n - 1, n - 2)), reverse(3))' to the 'ans'.
If 'k == 3' then return 'ans'.
Initialize the variable 'u' by 'mul(n, mul(n - 1, mul(n - 2, n - 3)))'.
Add 'mul(u, reverse(8))' to 'ans'.
Add 'mul(u, reverse(4))' to 'ans'
Return 'ans'.

Space Complexity: O(1)Explanation:

O(1)

As we are using constant extra space, the space complexity will be O(1)

Time Complexity: O(logn)Explanation:

O(LogN), where 'N' is the input integer

As we are simply calculating the answer without using any loop and using the binary exponential to get the inverse modulo of a number the overall time complexity will be O(LogN)

C++ (g++ 5.4)

/*

    Time complexity: O(LogN)

    Space complexity: O(1)



    Where 'N' and 'K' are input integers.

*/



// Driver function to get the modular addition.

int add(long long a, long long b) {

    int mod = 1e9 + 7;

    return ((a % mod) + (b % mod)) % mod;

}



// Driver function to get the modular multiplication.

int mul(long long a, long long b) {

    int mod = 1e9 + 7;

    return ((a % mod) * 1LL * (b % mod)) % mod;

}



// Driver function to get the modular binary exponention.

int bin_pow(long long a, long long b) {

    int mod = 1e9 + 7;

    a %= mod;

    long long res = 1;

    while (b > 0) {

        if (b & 1) {

            res = res * 1LL * a % mod;

        }

        a = a * 1LL * a % mod;

        b >>= 1;

    }

    return res;

}



// Driver function to get the modular division.

int reverse(long long x) {

    int mod = 1e9 + 7;

    return bin_pow(x, mod - 2);

}



int numberOfPermutations(long long n, long long k) {

    // Updating 'k' with 'n - k'.

    k = n - k;



    // Initializing the 'ans' by 1.

    int ans = 1;



    // Condition when 'k' is 1.

    if (k == 0 or k == 1) {

        return ans;

    }



    // Adding dearangment for 'k' = 2.

    ans += mul(mul(n, n - 1), reverse(2));



    // Condition when 'k' is 2.

    if (k == 2) {

        return ans;

    }



    // Adding dearangment for 'k' = 3.

    ans += mul(mul(n, mul(n - 1, n - 2)), reverse(3));



    // Condition when 'k' is 3.

    if (k == 3) {

        return ans;

    }



    // Adding dearangment for 'k' = 4.

    int u = mul(n, mul(n - 1, mul(n - 2, n - 3)));

    ans = add(ans, mul(u, reverse(8)));

    ans = add(ans, mul(u, reverse(4)));



    return ans;

}

Python (3.5)

'''

    Time complexity: O(LogN)

    Space complexity: O(1)



    Where 'N' and 'K' are input integers.

'''



# Driver function to get the modular addition.

def add(a, b):

    mod = 10 ** 9 + 7

    return ((a % mod) + (b % mod)) % mod



# Driver function to get the modular multiplication.

def mul(a, b):

    mod = 10 ** 9 + 7

    return ((a % mod) * (b % mod)) % mod



# Driver function to get the modular binary exponention.

def bin_pow(a, b):

    mod = 10 ** 9 + 7

    a %= mod

    res = 1

    

    while b > 0:

        if b & 1:

            res = (res * a) % mod

            

        a = (a * a) % mod

        b >>= 1

        

    return res



# Driver function to get the modular division.

def reverse(x):

    mod = 10 ** 9 + 7

    return bin_pow(x, mod - 2)



def numberOfPermutations(n, k):

    

    # Updating 'k' with 'n - k'.

    k = n - k

    ans = 1

    

    if k <= 1:

        return ans

    

    # Adding dearangment for 'k' = 2.

    ans += mul(mul(n, n - 1), reverse(2))

    

    if k == 2:

        return ans

    

    # Adding dearangment for 'k' = 3.

    ans += mul(mul(n, mul(n - 1, n - 2)), reverse(3))

    

    if k == 3:

        return ans

    

    # Adding dearangment for 'k' = 4.

    u = mul(n, mul(n - 1, mul(n - 2, n - 3)))

    ans = add(ans, mul(u, reverse(8)))

    ans = add(ans, mul(u, reverse(4)))



    return ans

Java (SE 1.8)

/*
    Time Complexity: O(N ^ 2).
    Space Complexity: O(1).

    Where 'N' is the number of games.
*/


public class Solution {
    
    // Driver function to get the modular addition.
    private static int add(long a, long b) {
        int mod = 1000000000 + 7;
        return (int)(((a % mod) + (b % mod)) % mod);
    }

    // Driver function to get the modular multiplication.
    private static int mul(long a, long b) {
        int mod = 1000000000 + 7;
        return (int)(((long)(a % mod) * (long)(b % mod)) % mod);
    }

    // Driver function to get the modular binary exponention.
    private static int bin_pow(long a, long b) {
        int mod = 1000000000 + 7;
        a %= mod;
        long res = 1;
        while (b > 0) {
            if ((b & 1) > 0) {
                res = (res * a) % mod;
            }
            a = (a * a) % mod;
            b >>= 1;
        }
        return (int)res;
    }

    // Driver function to get the modular division.
    private static int reverse(long x) {
        int mod = 1000000000 + 7;
        return bin_pow(x, mod - 2);
    }

    public static int numberOfPermutations(long n, long k) {
        // Updating 'k' with 'n - k'.
        k = n - k;

        // Initializing the 'ans' by 1.
        int ans = 1;

        // Condition when 'k' is 1.
        if (k == 0 || k == 1) {
            return ans;
        }

        // Adding dearangment for 'k' = 2.
        ans += mul(mul(n, n - 1), reverse(2));

        // Condition when 'k' is 2.
        if (k == 2) {
            return ans;
        }

        // Adding dearangment for 'k' = 3.
        ans += mul(mul(n, mul(n - 1, n - 2)), reverse(3));

        // Condition when 'k' is 3.
        if (k == 3) {
            return ans;
        }

        // Adding dearangment for 'k' = 4.
        int u = mul(n, mul(n - 1, mul(n - 2, n - 3)));
        ans = add(ans, mul(u, reverse(8)));
        ans = add(ans, mul(u, reverse(4)));

        return ans;
    }
}