{"raw_statement":[{"iden":"statement","content":"Tiago lives in a street with N houses, numbered from 1 to N, in which the first one is his. He decided to get out of Codeforces and visit a friend, but his head is stuck in a problem for several days. Because of that, he is bit distracted and is not paying attention to where he is going.\n\nThe walk can be represented by K steps, where if he is in house i in a step,  is the probability of him being at house j in the next step. He wants to know what is the expected value of the house where he'll stop, but he is too distracted to solve this problem.\n\nThe first line of input consists of two integers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ 109). The next N lines contain each N integers, where the j-th number in the i-th line is Aij (0 ≤ Aij ≤ 106) and the sum in each line is 106.\n\nThe answer can be represented as an irreducible fraction . Print the integer P * Q - 1 modulo 109 + 7 (Q - 1 is the modular inverse of Q modulo 109 + 7).\n\n"},{"iden":"input","content":"The first line of input consists of two integers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ 109). The next N lines contain each N integers, where the j-th number in the i-th line is Aij (0 ≤ Aij ≤ 106) and the sum in each line is 106."},{"iden":"output","content":"The answer can be represented as an irreducible fraction . Print the integer P * Q - 1 modulo 109 + 7 (Q - 1 is the modular inverse of Q modulo 109 + 7)."},{"iden":"examples","content":"Input2 2500000 500000500000 500000Output500000005Input4 24255283383 274729 386113 55775167247 49080 415640 368033449168 182769 352198 15865127605 304475 230640 337280Output96636490Input2 20 10000001000000 0Output1Input2 10 10000001000000 0Output2"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, K \\in \\mathbb{Z}^+ $ with $ 1 \\leq N \\leq 100 $, $ 1 \\leq K \\leq 10^9 $.  \nLet $ A \\in \\mathbb{R}^{N \\times N} $ be a transition matrix where $ A_{ij} \\in [0, 10^6] $ and $ \\sum_{j=1}^N A_{ij} = 10^6 $ for all $ i \\in \\{1, \\dots, N\\} $.  \nDefine the normalized transition matrix $ P \\in \\mathbb{R}^{N \\times N} $ by $ P_{ij} = \\frac{A_{ij}}{10^6} $.  \n\nLet $ \\mathbf{v}_0 = (1, 0, \\dots, 0) \\in \\mathbb{R}^N $ be the initial state vector (Tiago starts at house 1).  \n\n**Constraints**  \n1. $ A_{ij} \\in \\mathbb{Z} $, $ 0 \\leq A_{ij} \\leq 10^6 $  \n2. $ \\sum_{j=1}^N A_{ij} = 10^6 $ for all $ i \\in \\{1, \\dots, N\\} $  \n3. $ P $ is a right-stochastic matrix: $ \\sum_{j=1}^N P_{ij} = 1 $ for all $ i $  \n\n**Objective**  \nCompute the expected house index after $ K $ steps:  \n$$\n\\mathbf{v}_K = \\mathbf{v}_0 \\cdot P^K\n$$  \nLet $ \\mathbb{E} = \\sum_{i=1}^N i \\cdot (\\mathbf{v}_K)_i $ be the expected value.  \n\nExpress $ \\mathbb{E} = \\frac{P}{Q} $ in lowest terms.  \nOutput $ P \\cdot Q^{-1} \\mod (10^9 + 7) $, where $ Q^{-1} $ is the modular multiplicative inverse of $ Q $ modulo $ 10^9 + 7 $.","simple_statement":"Tiago starts at house 1. He takes K steps. At each step, from house i, he moves to house j with probability A[i][j] / 10^6. Find the expected house number he ends at, as P/Q mod (10^9+7).","has_page_source":false}