Given infinite balls of K distinct colors. Count the number of ways to arrange N balls in a line such that no two adjacent balls are of same color. Since the answer may be very large, output the result MOD 1000000007.

Examples:

Input: N = 2, K = 2
Output: 2
Explanation: We will denote the colors by ‘R’ and ‘G’. There are two possible ways: “RG” and “GR”.

Input: N = 1, K = 100
Output: 100
Explanation: As there is only 1 box and 100 different colored balls, we can put any of the 100 balls in the box.

Input: N = 3, K = 2
Output: 2
Explanation: There are only two possible ways: “RGR” and “GRG”.

Approach: To solve the problem, follow the below idea:

If the number of balls to be arranged is 1, then the number of ways = K as we can choose one ball from any of the K different colors. For N > 1, we have K choices for the first ball and for every subsequent ball, we can choose from any of the K colors except the one which was used in the previous ball. So, the total number of ways are: N * ((K – 1) ^ (N – 1)). This can be easily calculated using Binary Exponentiation.

Below is the implementation of the approach:

#include <iostream>
using namespace std;

class BinaryExponentiation {
public:
    static const long long MOD = 1000000007;

    // Binary Exponentiation
    static long long power(long long base, long long expo)
    {
        long long ans = 1;
        while (expo > 0) {
            if ((expo & 1) == 1)
                ans = (ans * base) % MOD;
            base = (base * base) % MOD;
            expo >>= 1;
        }
        return ans;
    }

    static void main()
    {
        int N = 5, K = 3;

        // Calculate the result using the formula
        // (K)*(K-1)^(N-1)
        long long ways = (K * power(K - 1, N - 1)) % MOD;

        cout << ways << endl;
    }
};

int main()
{
    BinaryExponentiation::main();
    return 0;
}

import java.util.Scanner;

public class BinaryExponentiation {

    static long MOD = 1000000007;

    // Binary Exponentiation
    static long power(long base, long expo)
    {
        long ans = 1;
        while (expo > 0) {
            if ((expo & 1) == 1)
                ans = (ans * base) % MOD;
            base = (base * base) % MOD;
            expo >>= 1;
        }
        return ans;
    }

    public static void main(String[] args)
    {
        int N = 5, K = 3;

        // Calculate the result using the formula
        // (K)*(K-1)^(N-1)
        long ways = (K * power(K - 1, N - 1)) % MOD;

        System.out.println(ways);
    }
}

// This code is contributed by rambabuguphka

# Define the modulus value
MOD = 1000000007

# Binary Exponentiation function to calculate (base^expo) % MOD


def power(base, expo):
    ans = 1
    # Iterate through each bit of the exponent
    while expo > 0:
        # If the current bit is set, multiply ans by base
        if expo & 1:
            ans = (ans * base) % MOD
        # Update base to base^2 % MOD
        base = (base * base) % MOD
        # Shift the exponent right by 1 (divide by 2)
        expo >>= 1
    return ans

# Main function


def main():
    # Given values for N and K
    N = 5
    K = 3

    # Calculate the result using the formula (K)*(K-1)^(N-1)
    # and taking modulo MOD
    ways = (K * power(K - 1, N - 1)) % MOD

    # Print the calculated result
    print(ways)


# Call the main function to execute the program
main()

using System;

class Program
{
    // Define the modulus constant
    const int MOD = 1000000007;

    // Binary Exponentiation
    static long Power(long baseValue, long expo)
    {
        long ans = 1;
        while (expo > 0)
        {
            // If expo is odd, multiply ans by baseValue
            if ((expo & 1) == 1)
                ans = (ans * baseValue) % MOD;

            // Square the baseValue
            baseValue = (baseValue * baseValue) % MOD;

            // Right shift expo by 1
            expo >>= 1;
        }
        return ans;
    }

    static void Main()
    {
        int N = 5, K = 3;

        // Calculate the result using the formula (K)*(K-1)^(N-1)
        long ways = (K * Power(K - 1, N - 1)) % MOD;

        Console.WriteLine(ways);
    }
}

const MOD = 1000000007;

// Binary Exponentiation
function power(base, expo) {
    let ans = 1;
    while (expo > 0) {
        if (expo & 1)
            ans = (ans * base) % MOD;
        base = (base * base) % MOD;
        expo >>= 1;
    }
    return ans;
}

function main() {
    let N = 5, K = 3;

    // Calculate the result using the formula
    // (K)*(K-1)^(N-1)
    let ways = (K * power(K - 1, N - 1)) % MOD;

    console.log(ways);
}

main();

<?php
class BinaryExponentiation {
    const MOD = 1000000007;

    // Binary Exponentiation
    static function power($base, $expo)
    {
        $ans = 1;
        while ($expo > 0) {
            if (($expo & 1) == 1)
                $ans = ($ans * $base) % self::MOD;
            $base = ($base * $base) % self::MOD;
            $expo >>= 1;
        }
        return $ans;
    }

    public static function main()
    {
        $N = 5;
        $K = 3;

        // Calculate the result using the formula
        // (K)*(K-1)^(N-1)
        $ways = ($K * self::power($K - 1, $N - 1)) % self::MOD;

        echo $ways . "\n";
    }
}

// Call main function
BinaryExponentiation::main();
?>

48

Time Complexity: O(log₂N), where N is the number of balls to arrange.
Auxiliary Space: O(1)