{"raw_statement":[{"iden":"problem statement","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)$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq A_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"3\n3 1 5"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"4\n1 1 1 1"},{"iden":"sample output 2","content":"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$."},{"iden":"sample input 3","content":"10\n866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117"},{"iden":"sample output 3","content":"279919144\n\nPrint the sum modulo $(10^9+7)$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}