{"problem":{"name":"H. Pseudo-Random Number Generator","description":{"content":"As a very first test to decide if this is indeed a good pseudo-random number generator, Donald wishes to count the number of even values produced by this sequence, in order to check whether this is cl","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10250H"},"statements":[{"statement_type":"Markdown","content":"As a very first test to decide if this is indeed a good pseudo-random number generator, Donald wishes to count the number of even values produced by this sequence, in order to check whether this is close enough to $50 %$. Your help will be welcome.\n\nThe input consists of a single line, containing an integer $N$.\n\n*Limits*\n\nThe input satisfies $0 <= N < 2^(63)$.\n\nThe output should contain a single line with a single integer corresponding to the number of even values in the sequence $S (0), S (1), \\\\dots, S (N -1)$.\n\n## Input\n\nThe input consists of a single line, containing an integer $N$.*Limits*The input satisfies $0 <= N < 2^(63)$.\n\n## Output\n\nThe output should contain a single line with a single integer corresponding to the number of even values in the sequence $S (0), S (1), \\\\dots, S (N -1)$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}_{\\geq 0} $ be the number of sheets.  \nEach sheet $ i \\in \\{1, \\dots, n\\} $ has two page numbers: $ (i, i+1) $.  \n\nLet $ \\pi \\in S_n $ be a permutation of the $ n $ sheets, representing the order from top to bottom of the stack.  \n\nA *divine pair* is an ordered pair $ (i, j) $ with $ i < j $ (i.e., sheet $ \\pi(i) $ is above sheet $ \\pi(j) $) such that:  \n$$\n\\min(\\pi(i), \\pi(i)+1) > \\max(\\pi(j), \\pi(j)+1)\n\\quad \\iff \\quad\n\\pi(i) > \\pi(j) + 1\n$$\n\nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ be the number of divine pairs in permutation $ \\pi $.  \n\n**Constraints**  \n$ 1 \\leq t \\leq 10^5 $, $ 0 \\leq n, k \\leq 750 $\n\n**Objective**  \nFor each test case $ (n, k) $, compute the number of permutations $ \\pi \\in S_n $ such that the number of divine pairs is exactly $ k $, modulo $ 987654321 $.  \n\nThat is, compute:  \n$$\nf(n, k) = \\left| \\left\\{ \\pi \\in S_n \\,\\middle|\\, \\sum_{1 \\leq i < j \\leq n} \\mathbf{1}_{\\pi(i) > \\pi(j) + 1} = k \\right\\} \\right| \\mod 987654321\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10250H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}