#P4926. 皮皮妖的递推

    ID: 4031 传统题 2000ms 128MiB 尝试: 276 已通过: 103 难度: 9 上传者: 标签>CF2600省选/NOI-自相似递归结构线性递推极端元素优先处理ByMonster_Yi

皮皮妖的递推

题目描述

YOUSIKI 学习了递推,于是他请皮皮妖给他出道题,皮皮妖说:

f1=1,fi=i−ffi−1,fn=? f_{1}=1,f_{i}=i-f_{f_{i-1}},f_{n}=?

YOUSIKI 看了一眼把它秒切了,于是他要求皮皮妖加大难度,皮皮妖想了想,说:

f1=1,fi=i−ffi−1,fn=? f_{1}=1,f_{i}=i-f_{f_{i-1}},f_{n}=?

YOUSIKI 看了两眼把它秒切了,于是他要求皮皮妖加大难度,皮皮妖想了想,说:

f1=1,fi=i−fffi−1,fn=? f_{1}=1,f_{i}=i-f_{f_{f_{i-1}}},f_{n}=?

YOUSIKI看了三眼把它秒切了,于是他要求皮皮妖加大难度,皮皮妖想了想,说:

… \ldots

… \ldots

… \ldots

YOUSIKI 看了mm 眼,但是没有能秒切,于是他找到你,请你帮他解决这个问题。

输入格式

一行两个正整数 n,mn, m。n≤1018n \leq 10^{18},m≤106m \leq 10^6

输出格式

一行一个整数 fnf_{n}

样例

样例输入

4 2

样例输出

3

样例解释:f1=1f_{1}=1,f2=2−ff1=1f_{2}=2-f_{f_{1}}=1,f3=3−ff2=2f_{3}=3-f_{f_{2}}=2,f4=4−ff3=3f_{4}=4-f_{f_{3}}=3