Given N boxes that are kept in a straight line and M colors such that M ? N. The position of the boxes cannot be changed. The task is to find the number of ways to color the boxes such that if any M consecutive set of boxes is considered then the color of each box is unique. Since the answer could be large, print the answer modulo 109 + 7.
Example:Â
Â
Input: N = 3, M = 2Â
Output: 2Â
If colours are c1 and c2 the only possibleÂ
ways are {c1, c2, c1} and {c2, c1, c2}.
Input: N = 13, M = 10Â
Output: 3628800Â
Â
Â
Approach: The number of ways are independent of N and only depends on M. First M boxes can be coloured with the given M colours without repetition then the same pattern can be repeated for the next set of M boxes. This can be done for every permutation of the colours. So, the number of ways to color the boxes will be M!.
Below is the implementation of the above approach:Â
Â
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;Â
#define MOD 1000000007Â
// Function to return (m! % MOD)int modFact(int n, int m){Â Â Â Â int result = 1;Â Â Â Â for (int i = 1; i <= m; i++)Â Â Â Â Â Â Â Â result = (result * i) % MOD;Â
    return result;}Â
// Driver codeint main(){Â Â Â Â int n = 3, m = 2;Â
    cout << modFact(n, m);Â
    return 0;} |
Java
// Java implementation of the above approach class GFG{    static final int MOD = 1000000007;         // Function to return (m! % MOD)     static int modFact(int n, int m)     {         int result = 1;         for (int i = 1; i <= m; i++)             result = (result * i) % MOD;              return result;     }          // Driver code     public static void main (String[] args)     {         int n = 3, m = 2;              System.out.println(modFact(n, m));     } }Â
// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach MOD = 1000000007Â
# Function to return (m! % MOD) def modFact(n, m) :Â Â Â Â Â Â Â Â Â result = 1Â Â Â Â for i in range(1, m + 1) : Â Â Â Â Â Â Â Â result = (result * i) % MOD Â
    return result Â
# Driver code n = 3m = 2Â
print(modFact(n, m)) Â
# This code is contributed by# divyamohan123 |
C#
// C# implementation of the above approach using System;class GFG{    const int MOD = 1000000007;         // Function to return (m! % MOD)     static int modFact(int n, int m)     {         int result = 1;         for (int i = 1; i <= m; i++)             result = (result * i) % MOD;              return result;     }          // Driver code     public static void Main()     {         int n = 3, m = 2;              Console.WriteLine(modFact(n, m));     } }Â
// This code is contributed by Nidhi_biet |
Javascript
<script>// Javascript implementation of the approachÂ
const MOD = 1000000007;Â
// Function to return (m! % MOD)function modFact(n, m){Â Â Â Â let result = 1;Â Â Â Â for (let i = 1; i <= m; i++)Â Â Â Â Â Â Â Â result = (result * i) % MOD;Â
    return result;}Â
// Driver code    let n = 3, m = 2;Â
    document.write(modFact(n, m));Â
</script> |
2
Â
Time Complexity: O(m)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
