{"problem":{"name":"LIDS","description":{"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$: *   $LIS(P) + LDS(P) = N+1$ *   $P_","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc059_f"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $1 \\le N \\le 5\\cdot 10^6$\n*   $1 \\le pos, val \\le N$\n*   All values in the input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $pos$ $val$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc059_f","tags":[],"sample_group":[["3 2 2","2\n\nThe following permutations satisfy the conditions: $(1, 2, 3), (3, 2, 1)$."],["4 1 1","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)$."],["5 2 5","11"],["2022 69 420","128873576"]],"created_at":"2026-03-03 11:01:14"}}