{"raw_statement":[{"iden":"problem statement","content":"You are given a string $S$ of length $N$ consisting of `0` and `1`. It describes a length-$N$ sequence $A=(A _ 1,A _ 2,\\ldots,A _ N)$. If the $i$\\-th character of $S$ $(1\\leq i\\leq N)$ is `0`, then $A _ i=0$; if it is `1`, then $A _ i=1$.\nFind the following:\n\\\\\\[\\\\sum _ {1\\\\leq i\\\\leq j\\\\leq N}(\\\\cdots((A _ i\\\\barwedge A _ {i+1})\\\\barwedge A _ {i+2})\\\\barwedge\\\\cdots\\\\barwedge A _ j)\\\\\\]\nMore formally, find $\\displaystyle\\sum _ {i=1} ^ {N}\\sum _ {j=i} ^ Nf(i,j)$ for $f(i,j)\\ (1\\leq i\\leq j\\leq N)$ defined as follows:\n\\\\\\[f(i,j)=\\\\left\\{\\\\begin{matrix} A _ i&(i=j)\\\\\\\\ f(i,j-1)\\\\barwedge A _ j\\\\quad&(i\\\\lt j) \\\\end{matrix}\\\\right.\\\\\\]\nHere, $\\barwedge$, NAND, is a binary operator satisfying the following:\n\\\\\\[0\\\\barwedge0=1,0\\\\barwedge1=1,1\\\\barwedge0=1,1\\\\barwedge1=0.\\\\\\]"},{"iden":"constraints","content":"*   $1\\leq N\\leq10^6$\n*   $S$ is a string of length $N$ consisting of `0` and `1`.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$S$"},{"iden":"sample input 1","content":"5\n00110"},{"iden":"sample output 1","content":"9\n\nHere are the values of $f(i,j)$ for the pairs $(i,j)$ such that $1\\leq i\\leq j\\leq N$:\n\n*   $f(1,1)=0=0$\n*   $f(1,2)=0\\barwedge0=1$\n*   $f(1,3)=(0\\barwedge0)\\barwedge1=0$\n*   $f(1,4)=((0\\barwedge0)\\barwedge1)\\barwedge1=1$\n*   $f(1,5)=(((0\\barwedge0)\\barwedge1)\\barwedge1)\\barwedge0=1$\n*   $f(2,2)=0=0$\n*   $f(2,3)=0\\barwedge1=1$\n*   $f(2,4)=(0\\barwedge1)\\barwedge1=0$\n*   $f(2,5)=((0\\barwedge1)\\barwedge1)\\barwedge0=1$\n*   $f(3,3)=1=1$\n*   $f(3,4)=1\\barwedge1=0$\n*   $f(3,5)=(1\\barwedge1)\\barwedge0=1$\n*   $f(4,4)=1=1$\n*   $f(4,5)=1\\barwedge0=1$\n*   $f(5,5)=0=0$\n\nTheir sum is $0+1+0+1+1+0+1+0+1+1+0+1+1+1+0=9$, so print $9$.\nNote that $\\barwedge$ does not satisfy the associative property. For instance, $(1\\barwedge1)\\barwedge0=0\\barwedge0=1\\neq0=1\\barwedge1=1\\barwedge(1\\barwedge0)$."},{"iden":"sample input 2","content":"30\n101010000100101011010011000010"},{"iden":"sample output 2","content":"326"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}