暂无测试数据。

题目描述

你获得了一个有正负下标的序列\(a\)，初始时它的任意元素都是\(0\)。

你又获得了一个神秘整数\(k\)。现在你将\(a_1\)改为了\(1\)，并从\(i=2\)到\(i=+\infty\)执行了以下操作：

\[a_i\gets\begin{cases}a_{i-k}&i\bmod k=1\\a_{i-1}+a_{i-k}&i\bmod k\neq1\end{cases}\]

请求出\(a_n\)的值。

输入格式

输入\(k,n\)。

输出格式

输出\(a_n\bmod1145141\)。

输入样例

2 4

输出样例

2

样例解释

序列的前\(4\)项依次为\([1,1,1,2]\)。

数据范围

对于\(10\%\)的数据，\(n\leq10^4\)。

对于\(30\%\)的数据，\(n\leq10^8\)。

对于\(100\%\)的数据，\(n,k\leq10^{18}\)，\(k<n\)。