Xâu ngoặc cân bằng được định nghĩa như sau:

• Chỉ gồm hai loại ký tự ( và ).
• Xâu rỗng được xem là một xâu ngoặc cân bằng.
• Nếu ~S~ là xâu ngoặc cân bằng thì (~S~) cũng là một xâu ngoặc cân bằng.
• Nếu ~S~ và ~R~ là các xâu ngoặc cân bằng thì ~SR~ cũng là một xâu ngoặc cân bằng.

Cho hai số nguyên dương ~n~ và ~m~. Hãy đếm số lượng xâu ngoặc cân bằng độ dài ~2n~ thỏa mãn nếu xóa đi hai ký tự ở giữa xâu ~(~hai ký tự ở vị trí ~n~ và ~n+1~~)~ thì xâu thu được cũng là một xâu ngoặc cân bằng, kết quả chia lấy dư cho ~m~.

Input

• Dòng duy nhất chứa hai số nguyên ~n~ và ~m~ ~(1 \le n \le 10^4~ ~;~ ~2 \le m \le 10^9)~.

Output

• In ra số lượng xâu ngoặc cân bằng thỏa mãn, kết quả chia lấy dư cho ~m~.

Examples

Sample Input

3 998244353

Sample Output

3

Scoring

• Subtask ~1~ ~-~ ~1000~ điểm: ~n \le 10~
• Subtask ~2~ ~-~ ~1000~ điểm: ~n \le 30~
• Subtask ~3~ ~-~ ~1000~ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ, có ~3~ xâu ngoặc cân bằng thỏa mãn: ((())), ()()() và (()()).