{"problem":{"name":"B3. Rasta-making","description":{"content":"Sequence  of positive integers is given to you. A sequence of positive integers is called Rasta - made if and only if every two consecutive elements from this sequence are coprimes to each other.  A ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":15000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CFB3"},"statements":[{"statement_type":"Markdown","content":"Sequence  of positive integers is given to you. A sequence of positive integers is called Rasta - made if and only if every two consecutive elements from this sequence are coprimes to each other. \n\nA Rasta - making operation on a sequence consists of choosing two non-coprime consecutive elements from it and divide them both by one of their common prime factors. For example, we can turn the seqeunce  to  with performing one operation.\n\nPhoulady number of a sequence is the minimum number of Rasta - making operations needed for turning it into a Rasta - made sequence.\n\nConstruction number of a a sequence is the number of different sequences we can get by performing 0 or more Rasta - making operations.\n\nWe show Phoulady number by F and Construction number by S.\n\nIn all subtasks:\n\nSubtasks:\n\nEach subtask consists of one testcase.\n\nInput consists of two integers, n and M.\n\nPrint the answer modulo 109 + 7 in a single line.\n\n## Input\n\nEach subtask consists of one testcase.Input consists of two integers, n and M.\n\n## Output\n\nPrint the answer modulo 109 + 7 in a single line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给你一个正整数序列。一个正整数序列被称为 #cf_span[Rasta - made]，当且仅当该序列中每两个相邻元素互质。\n\n对一个序列进行一次 #cf_span[Rasta - making] 操作，是指选择两个不互质的相邻元素，并将它们同时除以它们的一个公共质因数。例如，我们可以通过一次操作将序列  变为  。\n\n一个序列的 #cf_span[Phoulady] 数是指将其变为 #cf_span[Rasta - made] 序列所需的最少 #cf_span[Rasta - making] 操作次数。\n\n一个序列的 #cf_span[Construction] 数是指通过执行 0 次或多次 #cf_span[Rasta - making] 操作所能得到的不同序列的数量。\n\n我们用 #cf_span[F] 表示 #cf_span[Phoulady] 数，用 #cf_span[S] 表示 #cf_span[Construction] 数。\n\n在所有子任务中：\n\n子任务：\n\n每个子任务包含一个测试用例。\n\n输入包含两个整数 #cf_span[n] 和 #cf_span[M]。\n\n请输出答案对 #cf_span[109 + 7] 取模的结果，占一行。\n\n## Input\n\n每个子任务包含一个测试用例。输入包含两个整数 #cf_span[n] 和 #cf_span[M]。\n\n## Output\n\n请输出答案对 #cf_span[109 + 7] 取模的结果，占一行。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n, M \\in \\mathbb{Z}^+ $.  \nLet $ \\mathcal{S} $ be the set of all sequences $ a = (a_1, a_2, \\dots, a_n) $ of positive integers such that $ 1 \\leq a_i \\leq M $ for all $ i \\in \\{1, 2, \\dots, n\\} $.\n\nFor a sequence $ a \\in \\mathcal{S} $, define:\n\n- **Rasta-made**: $ a $ is Rasta-made if $ \\gcd(a_i, a_{i+1}) = 1 $ for all $ i \\in \\{1, 2, \\dots, n-1\\} $.\n\n- **Rasta-making operation**: Choose an index $ i \\in \\{1, 2, \\dots, n-1\\} $ such that $ \\gcd(a_i, a_{i+1}) > 1 $, and choose a prime $ p \\mid \\gcd(a_i, a_{i+1}) $. Then replace $ a_i \\leftarrow a_i / p $, $ a_{i+1} \\leftarrow a_{i+1} / p $.\n\n- **Phoulady number $ F(a) $**: Minimum number of Rasta-making operations to transform $ a $ into a Rasta-made sequence.\n\n- **Construction number $ S(a) $**: Number of distinct sequences obtainable from $ a $ via zero or more Rasta-making operations.\n\nDefine:\n\n- $ F = \\sum_{a \\in \\mathcal{S}} F(a) $\n\n- $ S = \\sum_{a \\in \\mathcal{S}} S(a) $\n\nCompute $ (F + S) \\mod (10^9 + 7) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFB3","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}