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 đố cuom1999 đế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 cuom1999 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, cuom1999 đang tất bật chuẩn bị cho học kỳ mới 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ậu ấ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\).

Scoring

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

Example

2 12

4

8 450

2520