{"problem":{"name":"E. Bash Plays with Functions","description":{"content":"Bash got tired on his journey to become the greatest Pokemon master. So he decides to take a break and play with functions. Bash defines a function _f_0(_n_), which denotes the number of ways of fact","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF757E"},"statements":[{"statement_type":"Markdown","content":"Bash got tired on his journey to become the greatest Pokemon master. So he decides to take a break and play with functions.\n\nBash defines a function _f_0(_n_), which denotes the number of ways of factoring _n_ into two factors _p_ and _q_ such that _gcd_(_p_, _q_) = 1. In other words, _f_0(_n_) is the number of ordered pairs of positive integers (_p_, _q_) such that _p_·_q_ = _n_ and _gcd_(_p_, _q_) = 1.\n\nBut Bash felt that it was too easy to calculate this function. So he defined a series of functions, where _f__r_ + 1 is defined as:\n\nWhere (_u_, _v_) is any ordered pair of positive integers, they need not to be co-prime.\n\nNow Bash wants to know the value of _f__r_(_n_) for different _r_ and _n_. Since the value could be huge, he would like to know the value modulo 109 + 7. Help him!\n\n## Input\n\nThe first line contains an integer _q_ (1 ≤ _q_ ≤ 106) — the number of values Bash wants to know.\n\nEach of the next _q_ lines contain two integers _r_ and _n_ (0 ≤ _r_ ≤ 106, 1 ≤ _n_ ≤ 106), which denote Bash wants to know the value _f__r_(_n_).\n\n## Output\n\nPrint _q_ integers. For each pair of _r_ and _n_ given, print _f__r_(_n_) modulo 109 + 7 on a separate line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Bash 在成为最伟大的宝可梦大师的旅途中感到疲惫，于是决定休息一下，玩一些函数。\n\nBash 定义了一个函数 #cf_span[f0(n)]，表示将 #cf_span[n] 分解为两个因子 #cf_span[p] 和 #cf_span[q] 的方案数，要求满足 #cf_span[gcd(p, q) = 1]。换句话说，#cf_span[f0(n)] 是满足 #cf_span[p·q = n] 且 #cf_span[gcd(p, q) = 1] 的正整数有序对 #cf_span[(p, q)] 的个数。\n\n但 Bash 觉得计算这个函数太简单了，于是他定义了一系列函数，其中 #cf_span[fr + 1] 定义为：\n\n其中 #cf_span[(u, v)] 是任意有序正整数对，它们不必互质。\n\n现在 Bash 想要知道不同 #cf_span[r] 和 #cf_span[n] 对应的 #cf_span[fr(n)] 的值。由于数值可能很大，他希望知道对 #cf_span[109 + 7] 取模的结果。请帮助他！\n\n第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 106]) —— Bash 想要知道的值的个数。\n\n接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[r] 和 #cf_span[n] (#cf_span[0 ≤ r ≤ 106], #cf_span[1 ≤ n ≤ 106])，表示 Bash 想要知道 #cf_span[fr(n)] 的值。\n\n请输出 #cf_span[q] 个整数。对于每组给定的 #cf_span[r] 和 #cf_span[n]，在单独一行输出 #cf_span[fr(n)] 对 #cf_span[109 + 7] 取模的结果。\n\n## Input\n\n第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 106]) —— Bash 想要知道的值的个数。接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[r] 和 #cf_span[n] (#cf_span[0 ≤ r ≤ 106], #cf_span[1 ≤ n ≤ 106])，表示 Bash 想要知道 #cf_span[fr(n)] 的值。\n\n## Output\n\n请输出 #cf_span[q] 个整数。对于每组给定的 #cf_span[r] 和 #cf_span[n]，在单独一行输出 #cf_span[fr(n)] 对 #cf_span[109 + 7] 取模的结果。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ f_0(n) $ denote the number of ordered pairs of positive integers $ (p, q) $ such that $ p \\cdot q = n $ and $ \\gcd(p, q) = 1 $.  \nFor $ r \\geq 0 $, define $ f_{r+1}(n) = \\sum_{\\substack{u,v \\geq 1 \\\\ u \\cdot v = n}} f_r(u) \\cdot f_r(v) $.\n\n**Constraints**  \n1. $ 1 \\leq q \\leq 10^6 $  \n2. For each query: $ 0 \\leq r \\leq 10^6 $, $ 1 \\leq n \\leq 10^6 $\n\n**Objective**  \nFor each query $ (r, n) $, compute $ f_r(n) \\mod (10^9 + 7) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF757E","tags":["brute force","combinatorics","dp","number theory"],"sample_group":[["5\n0 30\n1 25\n3 65\n2 5\n4 48","8\n5\n25\n4\n630"]],"created_at":"2026-03-03 11:00:39"}}