{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"Each subtask consists of one testcase.Input consists of two integers, n and M."},{"iden":"output","content":"Print the answer modulo 109 + 7 in a single line."},{"iden":"examples","content":""}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, M \\in \\mathbb{Z}^+ $.  \nLet $ \\mathcal{A} = \\{ (a_1, a_2, \\dots, a_n) \\mid a_i \\in \\{1, 2, \\dots, M\\} \\} $ be the set of all sequences of length $ n $ with elements in $ [1, M] $.  \n\nFor a sequence $ A = (a_1, \\dots, a_n) \\in \\mathcal{A} $:  \n- $ A $ is **#cf_span[Rasta-made]** if $ \\gcd(a_i, a_{i+1}) = 1 $ for all $ i \\in \\{1, \\dots, n-1\\} $.  \n- A **#cf_span[Rasta-making] operation** on $ A $: choose $ i \\in \\{1, \\dots, n-1\\} $ such that $ \\gcd(a_i, a_{i+1}) > 1 $, select a prime $ p \\mid \\gcd(a_i, a_{i+1}) $, and replace $ a_i \\leftarrow a_i / p $, $ a_{i+1} \\leftarrow a_{i+1} / p $.  \n\nLet $ F(A) $ be the minimum number of #cf_span[Rasta-making] operations to transform $ A $ into a #cf_span[Rasta-made] sequence.  \nLet $ S(A) $ be the number of distinct sequences obtainable from $ A $ via zero or more #cf_span[Rasta-making] operations.  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{A \\in \\mathcal{A}} F(A) \\cdot S(A) \\mod (10^9 + 7)\n$$","simple_statement":"Given a sequence of positive integers, you can perform an operation: pick two consecutive numbers that are not coprime, and divide both by one of their common prime factors.  \n\nDefine:  \n- **Phoulady number (F)**: minimum operations to make all consecutive pairs coprime.  \n- **Construction number (S)**: total number of different sequences you can get by doing any number of such operations.  \n\nGiven n and M, count the number of sequences of length n with each element between 1 and M, such that their Phoulady number is F and Construction number is S.  \n\nWait — actually, re-read: you’re NOT given a sequence. You’re given n and M.  \n\nYou must count: **how many sequences of length n (each element from 1 to M)** have Phoulady number F and Construction number S?  \n\nBut F and S are not given as input.  \n\nWait — the problem doesn’t specify what F and S are.  \n\nActually, the problem is incomplete.  \n\nBut based on common Codeforces-style problems, this is likely asking:  \n\n> Count the number of sequences of length n with elements in [1, M] such that the sequence is already Rasta-made (i.e., every two consecutive elements are coprime).  \n\nBecause if the sequence is already Rasta-made, then F = 0 and S = 1.  \n\nAnd that’s the only interpretation that makes sense with the given input (n, M) and the modulo output.  \n\nSo simplified:  \n\n**Count the number of sequences of length n, where each element is between 1 and M, and every two adjacent elements are coprime.**  \n\nAnswer modulo 10^9 + 7.","has_page_source":false}