{"problem":{"name":"D. Unusual Sequences","description":{"content":"Count the number of distinct sequences _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_) consisting of positive integers such that _gcd_(_a_1, _a_2, ..., _a__n_) = _x_ and . As this number could be large, print th","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF900D"},"statements":[{"statement_type":"Markdown","content":"Count the number of distinct sequences _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_) consisting of positive integers such that _gcd_(_a_1, _a_2, ..., _a__n_) = _x_ and . As this number could be large, print the answer modulo 109 + 7.\n\n_gcd_ here means the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor).\n\n## Input\n\nThe only line contains two positive integers _x_ and _y_ (1 ≤ _x_, _y_ ≤ 109).\n\n## Output\n\nPrint the number of such sequences modulo 109 + 7.\n\n[samples]\n\n## Note\n\nThere are three suitable sequences in the first test: (3, 3, 3), (3, 6), (6, 3).\n\nThere are no suitable sequences in the second test.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"计算满足以下条件的正整数序列 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai]) 的不同个数：#cf_span[gcd(a1, a2, ..., an) = x] 且 #cf_span[lcm(a1, a2, ..., an) = y]。由于答案可能很大，请对 #cf_span[10^9 + 7] 取模输出。\n\n这里的 #cf_span[gcd] 表示最大公约数，#cf_span[lcm] 表示最小公倍数。\n\n输入仅一行，包含两个正整数 #cf_span[x] 和 #cf_span[y] (#cf_span[1 ≤ x, y ≤ 10^9])。\n\n请输出满足条件的序列个数对 #cf_span[10^9 + 7] 取模的结果。\n\n在第一个测试用例中，有三个符合条件的序列：#cf_span[(3, 3, 3)], #cf_span[(3, 6)], #cf_span[(6, 3)]。\n\n在第二个测试用例中，没有符合条件的序列。\n\n## Input\n\n输入仅一行，包含两个正整数 #cf_span[x] 和 #cf_span[y] (#cf_span[1 ≤ x, y ≤ 10^9])。\n\n## Output\n\n请输出满足条件的序列个数对 #cf_span[10^9 + 7] 取模的结果。\n\n[samples]\n\n## Note\n\n在第一个测试用例中，有三个符合条件的序列：#cf_span[(3, 3, 3)], #cf_span[(3, 6)], #cf_span[(6, 3)]。在第二个测试用例中，没有符合条件的序列。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ x, y \\in \\mathbb{Z}^+ $ be given integers.  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the sequence (variable).  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers with $ a_i \\in \\mathbb{Z}^+ $.\n\n**Constraints**  \n1. $ 1 \\le x, y \\le 10^9 $  \n2. $ \\gcd(a_1, a_2, \\dots, a_n) = x $  \n3. $ \\max(a_1, a_2, \\dots, a_n) = y $\n\n**Objective**  \nCount the number of finite sequences $ A $ of positive integers satisfying the above constraints, modulo $ 10^9 + 7 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF900D","tags":["bitmasks","combinatorics","dp","math","number theory"],"sample_group":[["3 9","3"],["5 8","0"]],"created_at":"2026-03-03 11:00:39"}}