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⁹+7.

Dữ liệu vào:

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

Dữ liệu ra:

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

Giới hạn: N <= 10⁹; K <= 5000.