4326: 福尔摩斯的孩子们
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：4
通过：3
题目描述
https://codeforces.com/problemset/problem/776/E
福尔摩斯的孩子们正在为他们中谁最聪明而争吵。
麦克罗夫特要求夏洛克和尤鲁斯找到f(n)的价值，其中f(1)=1，当n>=2时，f(n)表示x+y=n并且gcd(x,y)=1的对数。
夏洛克说，解决这个问题是孩子们的游戏，并要求麦克罗夫特获得g(n)的价值，
。
尤鲁斯静静地观察着这一切，终于想出了让夏洛克和麦克罗夫特都吃惊的问题。
她递归的定义了复合函数Fk(n)如下：
她希望他们算出Fk(n)模1000000007的值。
福尔摩斯的孩子们正在为他们中谁最聪明而争吵。
麦克罗夫特要求夏洛克和尤鲁斯找到f(n)的价值，其中f(1)=1，当n>=2时，f(n)表示x+y=n并且gcd(x,y)=1的对数。
夏洛克说，解决这个问题是孩子们的游戏，并要求麦克罗夫特获得g(n)的价值，
。 尤鲁斯静静地观察着这一切，终于想出了让夏洛克和麦克罗夫特都吃惊的问题。
她递归的定义了复合函数Fk(n)如下：
她希望他们算出Fk(n)模1000000007的值。
输入格式
一行输入两个整数n，k(1<=n,k<=1012)。
输出格式
输出一个整数，表示Fk(n)模1000000007的值。
输入样例 复制
7 1输出样例 复制
6数据范围与提示
样例输入
10 2
样例输出
4
10 2
样例输出
4