\textit{Обобщёнными числами Фибоначчи} \textbf{F_n^\{(k)\}} называют следующую последовательность: \includegraphics{https://static.e-olymp.com/content/7b/7b9a778cac5f81da9da53dca379df99619ee54a9.jpg} Ваша задача - вычислить остаток от деления \textbf{F_n^\{(k)\}} на \textbf{p}. \InputFile Входной файл содержит три целых числа: \textbf{n}, \textbf{k} и \textbf{p} (\textbf{1} ≤ \textbf{n}, \textbf{k} ≤ \textbf{10^6}, \textbf{2} ≤ \textbf{p} ≤ \textbf{10^9}). \OutputFile В выходной файл выведите \textbf{F_n^\{(k)\} mod p}.