{"problem":{"name":"D. New Year and Arbitrary Arrangement","description":{"content":"You are given three integers _k_, _p__a_ and _p__b_. You will construct a sequence with the following algorithm: Initially, start with the empty sequence. Each second, you do the following. With prob","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF908D"},"statements":[{"statement_type":"Markdown","content":"You are given three integers _k_, _p__a_ and _p__b_.\n\nYou will construct a sequence with the following algorithm: Initially, start with the empty sequence. Each second, you do the following. With probability _p__a_ / (_p__a_ + _p__b_), add '_a_' to the end of the sequence. Otherwise (with probability _p__b_ / (_p__a_ + _p__b_)), add '_b_' to the end of the sequence.\n\nYou stop once there are at least _k_ subsequences that form '_ab_'. Determine the expected number of times '_ab_' is a subsequence in the resulting sequence. It can be shown that this can be represented by _P_ / _Q_, where _P_ and _Q_ are coprime integers, and . Print the value of .\n\n## Input\n\nThe first line will contain three integers integer _k_, _p__a_, _p__b_ (1 ≤ _k_ ≤ 1 000, 1 ≤ _p__a_, _p__b_ ≤ 1 000 000).\n\n## Output\n\nPrint a single integer, the answer to the problem.\n\n[samples]\n\n## Note\n\nThe first sample, we will keep appending to our sequence until we get the subsequence '_ab_' at least once. For instance, we get the sequence '_ab_' with probability 1/4, '_bbab_' with probability 1/16, and '_aab_' with probability 1/8. Note, it's impossible for us to end with a sequence like '_aabab_', since we would have stopped our algorithm once we had the prefix '_aab_'.\n\nThe expected amount of times that '_ab_' will occur across all valid sequences is 2.\n\nFor the second sample, the answer is equal to .","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你被给定三个整数 $k$、$pa$ 和 $pb$。\n\n你将使用以下算法构造一个序列：初始时序列为空。每一秒，你执行以下操作：以概率 $pa/(pa+pb)$，在序列末尾添加 '_a_'；否则（概率为 $pb/(pa+pb)$），在序列末尾添加 '_b_'。\n\n当你至少获得了 $k$ 个构成 '_ab_' 的子序列时，停止构造。求最终序列中 '_ab_' 作为子序列出现次数的期望值。可以证明，该期望值可以表示为 $P/Q$，其中 $P$ 和 $Q$ 是互质的整数，且 $Q \\not\\equiv 0 \\pmod{998244353}$。请输出 $P \\cdot Q^{-1} \\bmod 998244353$ 的值。\n\n第一行包含三个整数 $k, pa, pb$（$1 \\leq k \\leq 1\\,000$，$1 \\leq pa, pb \\leq 1\\,000\\,000$）。\n\n输出一个整数，表示问题的答案。\n\n在第一个样例中，我们将持续向序列追加字符，直到至少出现一次 '_ab_' 子序列。例如，我们以概率 $1/4$ 得到序列 '_ab_'，以概率 $1/16$ 得到 '_bbab_'，以概率 $1/8$ 得到 '_aab_'。注意，我们不可能得到类似 '_aabab_' 的序列，因为一旦我们有了前缀 '_aab_'，算法就已经停止了。\n\n在所有合法序列中，'_ab_' 作为子序列出现次数的期望值为 2。\n\n在第二个样例中，答案等于 。\n\n## Input\n\n第一行包含三个整数 $k, pa, pb$（$1 \\leq k \\leq 1\\,000$，$1 \\leq pa, pb \\leq 1\\,000\\,000$）。\n\n## Output\n\n输出一个整数，表示问题的答案。\n\n[samples]\n\n## Note\n\n在第一个样例中，我们将持续向序列追加字符，直到至少出现一次 '_ab_' 子序列。例如，我们以概率 $1/4$ 得到序列 '_ab_'，以概率 $1/16$ 得到 '_bbab_'，以概率 $1/8$ 得到 '_aab_'。注意，我们不可能得到类似 '_aabab_' 的序列，因为一旦我们有了前缀 '_aab_'，算法就已经停止了。在所有合法序列中，'_ab_' 作为子序列出现次数的期望值为 2。在第二个样例中，答案等于 。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ k, p_a, p_b \\in \\mathbb{Z}^+ $ be given integers.  \nLet $ P = \\frac{p_a}{p_a + p_b} $, $ Q = \\frac{p_b}{p_a + p_b} $ be the probabilities of appending 'a' and 'b', respectively.  \n\n**Constraints**  \n$ 1 \\leq k \\leq 1000 $, $ 1 \\leq p_a, p_b \\leq 10^6 $\n\n**Objective**  \nLet $ E(k) $ denote the expected number of subsequences \"ab\" in the random sequence generated by the process, stopping when the count of \"ab\" subsequences reaches at least $ k $.  \nCompute $ E(k) $, and output the value of $ P \\cdot Q^{-1} \\mod (10^9 + 7) $, where $ E(k) = \\frac{P}{Q} $ in reduced form.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF908D","tags":["dp","math","probabilities"],"sample_group":[["1 1 1","2"],["3 1 4","370000006"]],"created_at":"2026-03-03 11:00:39"}}