{"problem":{"name":"Deforestation","description":{"content":"There are $N$ trees standing in a row from left to right. The $i$\\-th tree $(1 \\leq i \\leq N)$ from the left, Tree $i$, has the height of $H_i$. You will now cut down all these $N$ trees in some order","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc209_f"},"statements":[{"statement_type":"Markdown","content":"There are $N$ trees standing in a row from left to right. The $i$\\-th tree $(1 \\leq i \\leq N)$ from the left, Tree $i$, has the height of $H_i$.\nYou will now cut down all these $N$ trees in some order you like. Formally, you will choose a permutation $P$ of $(1, 2, \\ldots, N)$ and do the operation below for each $i=1, 2, 3, ..., N$ in this order.\n\n*   Cut down Tree $P_i$, that is, set $H_{P_i}$ to $0$, at a cost of $H_{P_i-1}+H_{P_i}+H_{P_i+1}$.\n\nHere, we assume $H_0=0,H_{N+1}=0$.\nIn other words, the cost of cutting down a tree is the total height of the tree and the neighboring trees just before doing so.\nFind the number of permutations $P$ that minimize the total cost of cutting down the trees. Since the count may be enormous, print it modulo $(10^9+7)$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 4000$\n*   $1 \\leq H_i \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$H_1$ $H_2$ $\\ldots$ $H_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc209_f","tags":[],"sample_group":[["3\n4 2 4","2\n\nThere are two permutations $P$ that minimize the total cost: $(1,3,2)$ and $(3,1,2)$.\nBelow, we will show the process of cutting down the trees for $P=(1,3,2)$, for example.\n\n*   First, Tree $1$ is cut down at a cost of $H_0+H_1+H_2=6$.\n*   Next, Tree $3$ is cut down at a cost of $H_2+H_3+H_4=6$.\n*   Finally, Tree $2$ is cut down at a cost of $H_1+H_2+H_3=2$.\n\nThe total cost incurred is $14$."],["3\n100 100 100","6"],["15\n804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764","54537651\n\nBe sure to print the count modulo $(10^9+7)$."]],"created_at":"2026-03-03 11:01:14"}}