{"problem":{"name":"I. In the clouds","description":{"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.","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10162I"},"statements":[{"statement_type":"Markdown","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## Input\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\n## Output\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[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10162I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}