\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}.