Alice và Bob đã tìm thấy kho báu, nhưng để mở được kho báu cả hai phải giải câu đố sau:
Cho một số nguyên dương \(n\), một tập con của tập {\(1, 2, ... n\)} gọi là tập \(fset\) nếu không tồn tại hai
số \(u, v (u \ne v)\) thuộc tập mà \(u \times v\) là số chính phương. Số chính phương là bình phương của một
số nguyên. Hãy đếm số cách chọn tập \(fset\) ? Hai cách chọn tập được gọi là khác nhau nếu tồn tại
một số xuất hiện trong cách chọn tập này nhưng không xuất hiện trong cách chọn tập kia.

Yêu cầu: Cho \(n, m\) gọi \(s\) là số cách chọn tập \(fset\), hãy tính \(s\) % \(m\), trong đó là phép toán chia %
lấy dư.

Input

• Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên dương \(n, m (m \le 10^9)\)

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số là giá trị \(s\) % \(m\).

Scoring

• Subtask \(1\) (\(16\%\) số điểm): \(n \le 10\)
• Subtask \(2\) (\(24\%\) số điểm): \(n \le 50\)
• Subtask \(3\) (\(16\%\) số điểm): \(n \le 1000\)
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^5\)
• Subtask \(5\) (\(24\%\) số điểm): \(n \le 10^6\)

Example

4 100

12