Yêu cầu: Cho số nguyên n, K tính S = (~1.2^0 + 2.2^1 + ... + n.2^(n-1~)) % K.

Dữ liệu:

• Gồm nhiều dòng mỗi dòng ghi hai số nguyên n, K (0 < n ≤ 1018, ~0<K≤10^9~).</li>

Kết quả:

• Gồm nhiều dòng mỗi dòng ghi một tổng S tương ứng.

Ví dụ

input

504951982 646612

output

431549