Colorea todas las casillas en línea de manera que cada M casillas consecutivas sean únicas

Dadas N casillas que se mantienen en línea recta y M colores tales que M ≤ N . La posición de las casillas no se puede cambiar. La tarea es encontrar el número de formas de colorear las casillas de manera que si se considera cualquier M conjunto de casillas consecutivas, entonces el color de cada casilla es único. Como la respuesta puede ser grande, imprima la respuesta módulo 10 ⁹ + 7.
Ejemplo: 
 

Entrada: N = 3, M = 2 
Salida: 2 
Si los colores son c1 y c2, las únicas formas posibles 
son {c1, c2, c1} y {c2, c1, c2}.
Entrada: N = 13, M = 10 
Salida: 3628800 
 

Enfoque: El número de vías es independiente de N y solo depende de M . Los primeros M cuadros se pueden colorear con los M colores dados sin repetición, luego se puede repetir el mismo patrón para el siguiente conjunto de M cuadros. Esto se puede hacer para cada permutación de los colores. Entonces, ¡la cantidad de formas de colorear las cajas será M! .
A continuación se muestra la implementación del enfoque anterior: 
 

// 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 code
int main()
{
    int n = 3, m = 2;
 
    cout << modFact(n, m);
 
    return 0;
}

// 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 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 = 3
m = 2
 
print(modFact(n, m))
 
# This code is contributed by
# divyamohan123

// 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

<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

Complejidad del tiempo: O(m)

Espacio Auxiliar: O(1)