Ninja And The Fence Problem Statement

Ninja is given a task of painting a fence with ‘N’ posts using ‘K’ different colors. The task requires that not more than two adjacent posts have the same color. Your goal is to determine the number of ways to paint the fence, reporting each result modulo 10⁹ + 7.

Example:

Input:

N = 3, K = 2

Output:

6

Explanation:

If the colors are numbered as 0 and 1, the fence with 3 posts can be painted in 6 ways: 110, 001, 101, 100, 010, and 011.

Input:

The first line contains an integer ‘T’, representing the number of test cases.
Each test case includes two integers, ‘N’ and ‘K’, representing the number of posts and colors, respectively.

Output:

Print the number of valid ways (modulo 109 + 7) for each test case on a separate line.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10⁵
• 1 <= K <= 10⁵
• Time Limit: 1 sec

Note:

You are not required to print anything. Implement the function and return the answer.