Bessie có dải vải vẽ dài $N$ đơn vị ($1 \leq N \leq 10^6$) và định vẽ, nhưng không có được cọ. Thay vào đó có $M$ con dấu cao su màu khác nhau ($1 \leq M \leq 10^6$), mỗi dấu rộng $K$ đơn vị ($1 \leq K \leq 10^6$). Kinh ngạc trước các khả năng, cô muốn biết chính xác có thể tạo bao nhiêu tranh khác nhau bằng cách đóng dấu theo một thứ tự nào đó.

Con dấu phải được căn đúng $K$ đơn vị kề nhau trên vải. Không được vượt hai đầu hoặc phủ phần lẻ của đơn vị. Dấu tô $K$ đơn vị được phủ bằng màu của nó. Mỗi dấu có thể dùng nhiều lần, một lần hoặc không dùng. Nhưng khi Bessie xong, mỗi đơn vị phải được tô ít nhất một lần.

Giúp Bessie tìm số tranh khác nhau modulo $10^9 + 7$. Hai tranh trông giống hệt nhưng được tạo bởi chuỗi đóng dấu khác nhau vẫn tính là một.

Dữ liệu vào

Dòng duy nhất chứa ba số nguyên $N$, $M$ và $K$. Bảo đảm $K \leq N$.

Dữ liệu ra

Một số nguyên: số tranh có thể có modulo $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

3 2 2

Dữ liệu ra 1

6

Ghi chú

Nếu hai dấu có màu A và B thì các tranh là AAA, AAB, ABB, BAA, BBA và BBB.

Nhiệm vụ con

Với ít nhất $75\%$ trường hợp đầu vào, $N,K \leq 10^3$.

Tác giả bài toán: Dhruv Rohatgi