Given N students and a total of M sets of question paper where M ? N. All the M sets are different and every sets is available in sufficient quantity. All the students are sitting in a single row. The task is to find the number of ways to distribute the question paper so that if any M consecutive students are selected then each student has a unique question paper set. The answer could be large, so print the answer modulo 109 + 7.
Example:Â
Â
Input: N = 2, M = 2Â
Output: 2Â
(A, B) and (B, A) are the only possible ways.
Input: N = 15, M = 4Â
Output: 24Â
Â
Â
Approach: It can be observed that the number of ways are independent of N and only depend on M. First M students can be given M sets and then the same pattern can be repeated. The number of ways to distribute the question paper in this way is M!. For example,Â
Â
N = 6, M = 3Â
A, B, C, A, B, CÂ
A, C, B, A, C, BÂ
B, C, A, B, C, AÂ
B, A, C, B, A, CÂ
C, A, B, C, A, BÂ
C, B, A, C, B, AÂ
Â
Below is the implementation of the above approach:Â
Â
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;Â
const int MOD = 1000000007;Â
// Function to return n! % 1000000007int factMod(int n){Â
    // To store the factorial    long fact = 1;Â
    // Find the factorial    for (int i = 2; i <= n; i++) {        fact *= (i % MOD);        fact %= MOD;    }Â
    return fact;}Â
// Function to return the// count of possible waysint countWays(int n, int m){Â Â Â Â return factMod(m);}Â
// Driver codeint main(){Â Â Â Â int n = 2, m = 2;Â
    cout << countWays(n, m);Â
    return 0;} |
Java
// Java implementation of the approachimport java.util.*;Â
class GFG{static int MOD = 1000000007;Â
// Function to return n! % 1000000007static int factMod(int n){Â
    // To store the factorial    long fact = 1;Â
    // Find the factorial    for (int i = 2; i <= n; i++)     {        fact *= (i % MOD);        fact %= MOD;    }    return (int)fact;}Â
// Function to return the// count of possible waysstatic int countWays(int n, int m){Â Â Â Â return factMod(m);}Â
// Driver codepublic static void main(String args[]){Â Â Â Â int n = 2, m = 2;Â
    System.out.print(countWays(n, m));}}Â
// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach MOD = 1000000007; Â
# Function to return n! % 1000000007 def factMod(n) : Â
    # To store the factorial     fact = 1; Â
    # Find the factorial     for i in range(2, n + 1) :        fact *= (i % MOD);         fact %= MOD; Â
    return fact; Â
# Function to return the # count of possible ways def countWays(n, m) : Â
    return factMod(m);Â
# Driver code if __name__ == "__main__" : Â
    n = 2; m = 2; Â
    print(countWays(n, m));Â
# This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;Â
class GFG{    static int MOD = 1000000007;         // Function to return n! % 1000000007    static int factMod(int n)    {        // To store the factorial        int fact = 1;             // Find the factorial        for (int i = 2; i <= n; i++)         {            fact *= (i % MOD);            fact %= MOD;        }        return fact;    }Â
    // Function to return the    // count of possible ways    static int countWays(int n, int m)    {        return factMod(m);    }         // Driver code    public static void Main()    {        int n = 2, m = 2;        Console.Write(countWays(n, m));     } }Â
// This code is contributed by Sanjit Prasad |
Javascript
<script>// javascript implementation of the approach     MOD = 1000000007;Â
    // Function to return n! % 1000000007    function factMod(n) {Â
        // To store the factorial        var fact = 1;Â
        // Find the factorial        for (i = 2; i <= n; i++) {            fact *= (i % MOD);            fact %= MOD;        }        return parseInt( fact);    }Â
    // Function to return the    // count of possible ways    function countWays(n , m) {        return factMod(m);    }Â
    // Driver code             var n = 2, m = 2;Â
        document.write(countWays(n, m));Â
// This code contributed by aashish1995</script> |
2
Â
Time Complexity: O(n)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
