Числа Фібоначчі можна означити, наприклад, так:

• ~F_0 = 0~;
• ~F_1 = 1~;
• для всіх подальших ~i~, наступне число є сумою двох попередніх: ~F_i = F_{i-1} + F_{i-2}~.

Напишіть програму, яка за наданими ~n~ та ~k~ знайде ~F_n \bmod k~, де mod є залишком від ділення (багатьма мовами програмування позначається як %).

Вхідні дані

Перший рядок містить єдине число ~n~ (~0\leqslant n\leqslant 1\,234\,567~).

Другий рядок містить єдине число ~k~ (~2\leqslant k\leqslant 10^9~).

Результати

Виведіть єдине число, рівне ~F_n \bmod k~.

Приклади

Вхід 1

5
2025

Результат 1

5

Вхід 2

12
100

Результат 2

44

Примітки

~F_5 = 5~, що менше 2025, і тому залишок рівний самому цьому числу.

~F_{12} = 144~, що при взятті залишку від ділення на 100 перетворюється в 44.