{"problem":{"name":"B2. 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":"CF10070B2"},"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":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ M \\in \\mathbb{Z}^+ $.  \nLet $ \\mathcal{A} = \\{ (a_1, \\dots, a_n) \\in \\{1, \\dots, M\\}^n \\} $ be the set of all sequences of length $ n $ with positive integers $ \\leq M $.  \n\nA sequence $ A = (a_1, \\dots, a_n) \\in \\mathcal{A} $ is **#cf_span[Rasta-made]** if $ \\gcd(a_i, a_{i+1}) = 1 $ for all $ i \\in \\{1, \\dots, n-1\\} $.  \n\nA **#cf_span[Rasta-making] operation** on $ A $ at position $ i $ (where $ \\gcd(a_i, a_{i+1}) > 1 $) selects a prime $ p \\mid \\gcd(a_i, a_{i+1}) $, and replaces $ (a_i, a_{i+1}) $ with $ \\left( \\frac{a_i}{p}, \\frac{a_{i+1}}{p} \\right) $.  \n\nLet $ F(A) $ be the **#cf_span[Phoulady] number** of $ A $: the minimum number of #cf_span[Rasta-making] operations to make $ A $ #cf_span[Rasta-made].  \nLet $ S(A) $ be the **#cf_span[Construction] number** of $ A $: the number of distinct #cf_span[Rasta-made] sequences reachable from $ A $ via any number of #cf_span[Rasta-making] operations.  \n\n**Constraints**  \n$ 1 \\leq n \\leq 50 $, $ 1 \\leq M \\leq 10^5 $.  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{A \\in \\mathcal{A}} F(A) \\cdot S(A) \\mod (10^9 + 7)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10070B2","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}