You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

称一个长方形为“$\mathbf{n}$ 元理想长方形”，当且仅当该长方形经过恰好 $n$ 次下列操作后得到一个正方形：

• 在该长方形中去掉一个正方形，使得剩下的图形仍为长方形。

例如：长为 $20$，宽为 $12$ 的长方形是一个“$3$ 元理想长方形”。可以这样分割：

可以看到，该长方形被分成了四块。如果依次去掉“①”“②”“③”三个正方形，那么最后剩下的是蓝色部分正方形，符合“$3$ 元理想长方形”的定义。因此该长方形是“$3$ 元理想长方形”。

现在黄校问你一个问题：对于一个长与宽和为 $S$ 的“$N$ 元理想长方形”，其较长边有多少种不同的取值？（不一定是整数）

输入格式

一行两个整数 $S,N$。

输出格式

一行一个整数，即答案，对 $1145141$ 取模。

样例

3 1

1

10 2

2

样例 $1$ 解释

长 $2$ 宽 $1$，所以显然。

数据范围

对于 $20\%$ 的数据，$1\le S,N\le 10$。

对于 $50\%$ 的数据，$1\le S,N\le 10^3$。

对于 $100\%$ 的数据，$1\le S,N\le 10^9$。