UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4926. 皮皮妖的递推

Statistics 下载数据

Description

YOUSIKI学习了递推,于是他请皮皮妖给他出道题,皮皮妖说:
f(1)=1,f(i)=i-f(i-1),求f(n)
YOUSIKI看了一眼把它秒切了,于是他要求皮皮妖加大难度,皮皮妖想了想,说:
f(1)=1,f(i)=i-f(f(i-1)),求f(n)
YOUSIKI看了两眼把它秒切了,于是他要求皮皮妖加大难度,皮皮妖想了想,说:
f(1)=1,f(i)=i-f(f(f(i-1))),求f(n)
YOUSIKI看了三眼把它秒切了,于是他要求皮皮妖加大难度,皮皮妖想了想,说:
...
...
...
YOUSIKI看了m眼,但是没有能秒切,于是他找到你,请你帮他解决这个问题。

Input

一行两个正整数n,m。n<=10^18,m<=10^6

Output

一行一个整数f(n)

Sample Input

4 2

Sample Output

3
样例解释:f(1)=1,f(2)=2-f(f(1))=1,f(3)=3-f(f(2))=2,f(4)=4-f(f(3))=3

Hint

Source

By Monster_Yi