{"problem":{"name":"Many Formulae","description":{"content":"You are given a sequence of $N$ non-negative integers: $A_1,A_2,\\cdots,A_N$. Consider inserting a `+` or `-` between each pair of adjacent terms to make one formula. There are $2^{N-1}$ such ways to m","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc122_a"},"statements":[{"statement_type":"Markdown","content":"You are given a sequence of $N$ non-negative integers: $A_1,A_2,\\cdots,A_N$.\nConsider inserting a `+` or `-` between each pair of adjacent terms to make one formula.\nThere are $2^{N-1}$ such ways to make a formula. Such a formula is called **good** when the following condition is satisfied:\n\n*   `-` does not occur twice or more in a row.\n\nFind the sum of the evaluations of all good formulae. We can prove that this sum is always a non-negative integer, so print it modulo $(10^9+7)$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq A_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$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc122_a","tags":[],"sample_group":[["3\n3 1 5","15\n\nWe have the following three good formulae:\n\n*   $3+1+5=9$\n    \n*   $3+1-5=-1$\n    \n*   $3-1+5=7$\n    \n\nNote that $3-1-5$ is not good since`-` occurs twice in a row in it. Thus, the answer is $9+(-1)+7=15$."],["4\n1 1 1 1","10\n\nWe have the following five good formulae:\n\n*   $1+1+1+1=4$\n    \n*   $1+1+1-1=2$\n    \n*   $1+1-1+1=2$\n    \n*   $1-1+1+1=2$\n    \n*   $1-1+1-1=0$\n    \n\nThus, the answer is $4+2+2+2+0=10$."],["10\n866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117","279919144\n\nPrint the sum modulo $(10^9+7)$."]],"created_at":"2026-03-03 11:01:14"}}