Giải bài trực tuyến

Ngày kỉ niệm 1 năm quen nhau của MN và MH đã tới. Chàng trai MN của chúng ta quyết định chuẩn bị 1 món quà thật đặc biệt để tặng cho người yêu của mình. MN đã tự làm cho MH một bông hoa hướng dương thật to bằng giấy. Với tài năng thiên bẩm cùng với sự tỉ mỉ, MN đã làm xong 1 bông hoa thật to, nhị hoa là 1 hình tròn với N cánh hoa cách đều nhau 
 
 Công việc cuối cùng là tô màu các cánh hoa, công việc này không hề đơn giản. Biết người yêu mình rất thích màu sắc sặc sỡ và không thích những bông hoa nào có 2 cánh hoa gần nhau có màu giống nhau. MN đã chuẩn bị M màu để trang trí. MN muốn làm thật nhiều bông hoa khác nhau từ M màu đó để góp thành một bó hoa thật lớn đem tặng MH. Nhưng khổ nỗi MN không biết được bó hoa của mình sẽ có bao nhiêu bông hoa để chuẩn bị. Hãy giúp anh bạn si tình khốn khổ của chúng ta nào, đừng để người yêu của mình nổi giận, con gái nổi giận thì phải mất cả tuần để xin lỗi đó…….
Lưu ý: Hai bông hoa được gọi là khác nhau nếu chúng có 1 cánh hoa có màu khác nhau
 
2 cặp hoa với n=5 và n=6 trên là 2 cặp hoa khác nhau
Input: Hai số N,M.
Output: Số bông hoa sau khi modul 109+7.
Example:
3 4
24
 
4 3
18
Giới hạn: N≤1018. M≤109.