{"problem":{"name":"[USACO23JAN] Moo Route G","description":{"content":"Farmer Nhoj dropped Bessie in the middle of nowhere! At time $t=0$, Bessie is located at $x=0$ on an infinite number line. She frantically searches for an exit by moving left or right by $1$ unit each","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9018"},"statements":[{"statement_type":"Markdown","content":"Farmer Nhoj dropped Bessie in the middle of nowhere! At time $t=0$, Bessie is located at $x=0$ on an infinite number line. She frantically searches for an exit by moving left or right by $1$ unit each second. However, there actually is no exit and after $T$ seconds, Bessie is back at $x=0$, tired and resigned.\n\nFarmer Nhoj tries to track Bessie but only knows how many times Bessie crosses $x=0.5,1.5,2.5,\\cdots,(N−1).5$\n, given by an array $A_0,A_1, \\cdots ,A_{N−1} (1 \\le N \\le 10^5, 1 \\le A_i \\le 10^6)$. Bessie never reaches $x>N$ nor $x<0$.\n\nIn particular, Bessie's route can be represented by a string of $T=\\sum\\limits_{i=0}^{N-1}A_i$\nLs and Rs where the ith character represents the direction Bessie moves in during the ith second. The number of direction changes is defined as the number of occurrences of $LR$s plus the number of occurrences of $RL$s.\n\nPlease help Farmer Nhoj count the number of routes Bessie could have taken that are consistent with $A$\nand minimize the number of direction changes. It is guaranteed that there is at least one valid route. \n\n## Input\n\nThe first line contains $N$. The second line contains $A_0,A_1, \\cdots ,A_{N−1}$. \n\n## Output\n\nThe number of routes Bessie could have taken, modulo $10^9+7$. \n\n[samples]\n\n## Note\n\n### Explanation for Sample 1\n\nBessie must change direction at least 5 times. There are two routes corresponding to Bessie changing direction exactly 5 times: \n\n$\\texttt{RRLRLLRRLL}$  \n$\\texttt{RRLLRRLRLL}$\n\n### Scoring\n\n - Inputs $2-4$: $N \\le 2$ and $\\max(A_i) \\le 10^3$\n - Inputs $5-7$: $N \\le 2$\n - Inputs $8-11$: $\\max(A_i) \\le 10^3$\n - Inputs $12-21$: No additional constraints.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9018","tags":["USACO","2023","组合数学","排列组合"],"sample_group":[["2\n4 6","2"]],"created_at":"2026-03-03 11:09:25"}}