Cho một dãy ~N~ ô vuông xếp kề nhau. Bạn hãy tính số cách tô màu ~K~ ô sao cho không có hai ô vuông nào được tô màu nằm cạnh nhau. Do kết quả có thể rất lớn nên bạn chỉ cần đưa ra kết quả sau khi mod nó cho ~10^9 + 7~.

Input

• Một dòng duy nhất ghi hai số nguyên ~N, K~.

Giới hạn:

• ~N ≤ 10^9; K ≤ 5000~

Output

• In ra đáp án bài toán sau khi mod cho ~10^9 + 7~.

Sample

Input #1

5 2

Output #1

6

Problem source: Kc97ble - Free Contest