{"problem":{"name":"D. Dice","description":{"content":"Diego has bought $n$ dices to play with, all dices have $k$ sides numbered $1, 2,..., k$, also as Diego wants to trick his friends, all dices are loaded, meaning that the probability of rolling the di","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":6000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10270D"},"statements":[{"statement_type":"Markdown","content":"Diego has bought $n$ dices to play with, all dices have $k$ sides numbered $1, 2,..., k$, also as Diego wants to trick his friends, all dices are loaded, meaning that the probability of rolling the dice is not the same for all sides. \n\nIn particular, Diego loaded the dice so that all sides which are multiple of $m$ have zero probability of appearance, while all other sides have the equal probability of appearance. Diego thinks that this will be enough to win any game betting against multiples of $m$. Ivan, a friend of Diego, knows the dices are loaded and he thinks that after summing the values of the dices we can still get a good probability of having a multiple of $m$. \n\nFor example, if Diego has 2 dices with 6 sides loaded, such that multiples of 3 cannot appear, then each dice could roll into 1, 2, 4 or 5 with probability 1/4 each. After throwing both dices Diego has the following possible outcomes for multiples of 3: \n\nHelp Ivan to calculate the probability of having a multiple of $m$ after summing the result of rolling all $n$ loaded dices.\n\nThe input consists of 3 integers $n$ ($1 <= n <= 2 * 10^6$), $k$ ($2 <= k <= 2 * 10^6$) and $m$ ($2 <= m <= 200$) — The number of dices, the number of sides in each dice and the multiple chosen to load the dices, respectively\n\nLet p/q be the probability of having a multiple of $m$ after rolling the dices. Print just a single integer: $p * q^(-1) mod 1000000007$. \n\n## Input\n\nThe input consists of 3 integers $n$ ($1 <= n <= 2 * 10^6$), $k$ ($2 <= k <= 2 * 10^6$) and $m$ ($2 <= m <= 200$) — The number of dices, the number of sides in each dice and the multiple chosen to load the dices, respectively\n\n## Output\n\nLet p/q be the probability of having a multiple of $m$ after rolling the dices. Print just a single integer: $p * q^(-1) mod 1000000007$. \n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of people.  \nLet $ D = (d_1, d_2, \\dots, d_N) $ be a sequence where each $ d_i \\in \\{L, R\\} $ represents the direction the $ i $-th person is facing in the photo.\n\n**Constraints**  \n$ 1 \\leq N \\leq 10^5 $\n\n**Objective**  \nCompute the number of clumps $ C $, where a clump is a maximal contiguous subsequence of identical directions:  \n$$ C = 1 + \\sum_{i=2}^{N} \\mathbb{I}[d_i \\neq d_{i-1}] $$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10270D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}