Миколаю потрібно розвести подарунки для n (n ≤ 1018) дітей. Його цікавить скількома способами він може це зробити. Вам потрібно дати відповідь на це просте питання. Оскільки ця кількість може бути дуже великою, виведіть результат за модулем m (m ≤ 2009).

Вхідні дані

В одному рядку задано два натуральні числа n та m.

Вихідні дані

Єдине число - шукана кількість.