Gieo xúc xắc là cách giết thời gian duy nhất của CaiWinDao trong thời kỳ giãn cách xã hội này. Dù con xúc xắc ngà voi của CaiWinDao được chế tác rất đẹp mắt nhưng rồi gieo mãi cũng thành nhàm, cậu bắt đầu lấy số điểm thu được từ các lần gieo nhân lại với nhau. Một ý tưởng chợt nảy ra trong đầu CaiWinDao, cậu thách đố holdmesoclose đếm được số cách gieo con xúc xắc này đúng \(n\) lần sao cho tích số điểm của \(n\) lần gieo đó đúng bằng một số nguyên dương \(m\). Vì số cách rất lớn nên CaiWinDao cho phép holdmesoclose chỉ cần trả lời kết quả thu được sau khi lấy đáp số đó chia lấy phần dư cho \(10^9+7\).

Buồn thay, holdmesoclose đang tất bật chuẩn bị cho hội trại xuân nên không có thời gian để nghiền ngẫm câu đố vu vơ của CaiWinDao. Các bạn hãy góp sức giúp đỡ cô ấy nhé!

Lưu ý rằng:

• Hai cách gieo được tính là khác nhau nếu tồn tại một lượt gieo cho số điểm khác nhau ở hai cách.
• Sáu mặt của con xúc xắc ngà tương ứng với sáu điểm số khác nhau \(1\), \(2\), \(3\), \(4\), \(5\) và \(6\).

Input

Gồm một dòng duy nhất chứa hai số nguyên dương \(n\) và \(m\).

Output

Chứa một số nguyên duy nhất là số cách tìm được chia lấy phần dư cho \(10^9+7\).

Ví dụ

Input 1

2 12

Output 1

4

Input 2

8 450

Output 2

2520

Giải thích test ví dụ 1

Có bốn cách để đạt được tích bằng \(12\) tương ứng với các kết quả gieo \((2, 6)\), \((3, 4)\), \((4, 3)\) và \((6, 2)\).

Ràng buộc

• Subtask 1 (20 điểm): \(n\leq 9, m\leq 50000\).
• Subtask 2 (20 điểm): \(n\leq 100, m\leq 50000\).
• Subtask 3 (60 điểm): \(n\leq 100, m\leq 10^{18}\).