{"raw_statement":[{"iden":"problem statement","content":"Given $N, pos, val$, find the number of permutations $P=(P_1, P_2, \\ldots, P_N)$ of $(1,2,\\ldots,N)$ that satisfy all of the following conditions, modulo $10^9+7$:\n\n*   $LIS(P) + LDS(P) = N+1$\n*   $P_{pos} = val$\n\nHere, $LIS(P)$ denotes the length of the longest increasing subsequence of $P$, and $LDS(P)$ denotes the length of the longest decreasing subsequence of $P$."},{"iden":"constraints","content":"*   $1 \\le N \\le 5\\cdot 10^6$\n*   $1 \\le pos, val \\le N$\n*   All values in the input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $pos$ $val$"},{"iden":"sample input 1","content":"3 2 2"},{"iden":"sample output 1","content":"2\n\nThe following permutations satisfy the conditions: $(1, 2, 3), (3, 2, 1)$."},{"iden":"sample input 2","content":"4 1 1"},{"iden":"sample output 2","content":"6\n\nThe following permutations satisfy the conditions: $(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2)$."},{"iden":"sample input 3","content":"5 2 5"},{"iden":"sample output 3","content":"11"},{"iden":"sample input 4","content":"2022 69 420"},{"iden":"sample output 4","content":"128873576"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}