{"raw_statement":[{"iden":"statement","content":"The Holmes children are fighting over who amongst them is the cleverest.\n\nMycroft asked Sherlock and Eurus to find value of _f_(_n_), where _f_(1) = 1 and for _n_ ≥ 2, _f_(_n_) is the number of distinct ordered positive integer pairs (_x_, _y_) that satisfy _x_ + _y_ = _n_ and _gcd_(_x_, _y_) = 1. The integer _gcd_(_a_, _b_) is the greatest common divisor of _a_ and _b_.\n\nSherlock said that solving this was child's play and asked Mycroft to instead get the value of . Summation is done over all positive integers _d_ that divide _n_.\n\nEurus was quietly observing all this and finally came up with her problem to astonish both Sherlock and Mycroft.\n\nShe defined a _k_\\-composite function _F__k_(_n_) recursively as follows:\n\nShe wants them to tell the value of _F__k_(_n_) modulo 1000000007."},{"iden":"input","content":"A single line of input contains two space separated integers _n_ (1 ≤ _n_ ≤ 1012) and _k_ (1 ≤ _k_ ≤ 1012) indicating that Eurus asks Sherlock and Mycroft to find the value of _F__k_(_n_) modulo 1000000007."},{"iden":"output","content":"Output a single integer — the value of _F__k_(_n_) modulo 1000000007."},{"iden":"examples","content":"Input\n\n7 1\n\nOutput\n\n6\n\nInput\n\n10 2\n\nOutput\n\n4"},{"iden":"note","content":"In the first case, there are 6 distinct ordered pairs (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) and (6, 1) satisfying _x_ + _y_ = 7 and _gcd_(_x_, _y_) = 1. Hence, _f_(7) = 6. So, _F_1(7) = _f_(_g_(7)) = _f_(_f_(7) + _f_(1)) = _f_(6 + 1) = _f_(7) = 6."}],"translated_statement":[{"iden":"statement","content":"福尔摩斯家的孩子们正在争论谁最聪明。\n\n迈克罗夫特让夏洛克和尤罗斯计算 #cf_span[f(n)] 的值，其中 #cf_span[f(1) = 1]，且对于 #cf_span[n ≥ 2]，#cf_span[f(n)] 表示满足 #cf_span[x + y = n] 且 #cf_span[gcd(x, y) = 1] 的不同有序正整数对 #cf_span[(x, y)] 的数量。整数 #cf_span[gcd(a, b)] 表示 #cf_span[a] 和 #cf_span[b] 的最大公约数。\n\n夏洛克说解决这个问题轻而易举，并让迈克罗夫特改为计算 。求和范围是所有整除 #cf_span[n] 的正整数 #cf_span[d]。\n\n尤罗斯安静地观察着这一切，最终提出了一个令夏洛克和迈克罗夫特震惊的问题。\n\n她递归地定义了一个 #cf_span[k]-复合函数 #cf_span[Fk(n)] 如下：\n\n她要求他们计算 #cf_span[Fk(n)] 对 #cf_span[1000000007] 取模的值。\n\n输入一行包含两个用空格分隔的整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1012]）和 #cf_span[k]（#cf_span[1 ≤ k ≤ 1012]），表示尤罗斯要求夏洛克和迈克罗夫特计算 #cf_span[Fk(n)] 对 #cf_span[1000000007] 取模的值。\n\n输出一个整数 —— #cf_span[Fk(n)] 对 #cf_span[1000000007] 取模的值。\n\n在第一组样例中，有 #cf_span[6] 个不同的有序对 #cf_span[(1, 6)]、#cf_span[(2, 5)]、#cf_span[(3, 4)]、#cf_span[(4, 3)]、#cf_span[(5, 2)] 和 #cf_span[(6, 1)] 满足 #cf_span[x + y = 7] 且 #cf_span[gcd(x, y) = 1]。因此，#cf_span[f(7) = 6]。于是，#cf_span[F1(7) = f(g(7)) = f(f(7) + f(1)) = f(6 + 1) = f(7) = 6]。"},{"iden":"input","content":"输入一行包含两个用空格分隔的整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1012]）和 #cf_span[k]（#cf_span[1 ≤ k ≤ 1012]），表示尤罗斯要求夏洛克和迈克罗夫特计算 #cf_span[Fk(n)] 对 #cf_span[1000000007] 取模的值。"},{"iden":"output","content":"输出一个整数 —— #cf_span[Fk(n)] 对 #cf_span[1000000007] 取模的值。"},{"iden":"examples","content":"输入\n7 1\n输出\n6\n输入\n10 2\n输出\n4"},{"iden":"note","content":"在第一组样例中，有 #cf_span[6] 个不同的有序对 #cf_span[(1, 6)]、#cf_span[(2, 5)]、#cf_span[(3, 4)]、#cf_span[(4, 3)]、#cf_span[(5, 2)] 和 #cf_span[(6, 1)] 满足 #cf_span[x + y = 7] 且 #cf_span[gcd(x, y) = 1]。因此，#cf_span[f(7) = 6]。于是，#cf_span[F1(7) = f(g(7)) = f(f(7) + f(1)) = f(6 + 1) = f(7) = 6]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ f(n) $ be the number of ordered pairs of positive integers $ (x, y) $ such that $ x + y = n $ and $ \\gcd(x, y) = 1 $.  \nLet $ g(n) = \\sum_{d \\mid n} f(d) $.  \nLet $ F_k(n) $ be defined recursively:  \n- $ F_1(n) = g(n) $,  \n- For $ k \\geq 2 $, $ F_k(n) = F_{k-1}(g(n)) $.  \n\n**Constraints**  \n$ 1 \\leq n \\leq 10^{12} $, $ 1 \\leq k \\leq 10^{12} $\n\n**Objective**  \nCompute $ F_k(n) \\mod 1000000007 $.","simple_statement":null,"has_page_source":false}