Color the boxes

★★★★★

3.3

112 votes

Basic Programming, Basics of Implementation, Implementation

Details

Submissions

Discussion

Editorial

Problem

You are given $N$ boxes that are kept in a straight line. You are also given $M$ colors such that ( $M\le N$ ). You cannot change the position of boxes. Determine the number of ways to color the boxes such that if you select any $M$ consecutive boxes then the color of each box is unique.

Since the number could be large, print the answer modulo $10^9+7$ .

Input format

Two space-separated integers $N$ and $M$

Output format

For the provided inputs, print the required answer.

Constraints

$1 \le M \le N \le10^6$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

We can color boxes only in two ways i.e. giving color as (1,2) and (2,1).