Alice và Bob đã tìm thấy kho báu, nhưng để mở được kho báu thì 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 \neq 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

• Một dòng chứa hai số nguyên dương \(n,m\) (\(m \le 10^9\)).

Output

• 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