{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The input consists of a single line, containing an integer $N$.*Limits*The input satisfies $0 <= N < 2^(63)$."},{"iden":"output","content":"The 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)$."},{"iden":"examples","content":"Input3\nOutput2\nInput500000000\nOutput250065867\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":"Given n sheets, each sheet i has two consecutive pages: i and i+1.  \nYou stack the n sheets in some order.  \nA \"divine pair\" is when a sheet s (higher in stack) has both its page numbers larger than both page numbers of a sheet t (lower in stack).  \nCount how many ways to arrange the n sheets so that there are exactly k divine pairs.  \nAnswer modulo 987654321.","has_page_source":false}