{"raw_statement":[{"iden":"problem statement","content":"**Problem F and F2 are the same problem, but with different constraints and time limits.**\nWe have a board divided into $N$ horizontal rows and $N$ vertical columns of square cells. The cell at the $i$\\-th row from the top and the $j$\\-th column from the left is called Cell $(i,j)$. Each cell is either empty or occupied by an obstacle. Also, each empty cell has a digit written on it. If $A_{i,j}=$ `1`, `2`, ..., or `9`, Cell $(i,j)$ is empty and the digit $A_{i,j}$ is written on it. If $A_{i,j}=$ `#`, Cell $(i,j)$ is occupied by an obstacle.\nCell $Y$ is _reachable_ from cell $X$ when the following conditions are all met:\n\n*   Cells $X$ and $Y$ are different.\n*   Cells $X$ and $Y$ are both empty.\n*   One can reach from Cell $X$ to Cell $Y$ by repeatedly moving right or down to an adjacent empty cell.\n\nConsider all pairs of cells $(X,Y)$ such that cell $Y$ is reachable from cell $X$. Find the sum of the products of the digits written on cell $X$ and cell $Y$ for all of those pairs."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 500$\n*   $A_{i,j}$ is one of the following characters: `1`, `2`, ... `9` and `#`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_{1,1}A_{1,2}...A_{1,N}$\n$A_{2,1}A_{2,2}...A_{2,N}$\n$:$\n$A_{N,1}A_{N,2}...A_{N,N}$"},{"iden":"sample input 1","content":"2\n11\n11"},{"iden":"sample output 1","content":"5\n\nThere are five pairs of cells $(X,Y)$ such that cell $Y$ is reachable from cell $X$, as follows:\n\n*   $X=(1,1)$, $Y=(1,2)$\n*   $X=(1,1)$, $Y=(2,1)$\n*   $X=(1,1)$, $Y=(2,2)$\n*   $X=(1,2)$, $Y=(2,2)$\n*   $X=(2,1)$, $Y=(2,2)$\n\nThe product of the digits written on cell $X$ and cell $Y$ is $1$ for all of those pairs, so the answer is $5$."},{"iden":"sample input 2","content":"4\n1111\n11#1\n1#11\n1111"},{"iden":"sample output 2","content":"47"},{"iden":"sample input 3","content":"10\n76##63##3#\n8445669721\n75#9542133\n3#285##445\n749632##89\n2458##9515\n5952578#77\n1#3#44196#\n4355#99#1#\n#298#63587"},{"iden":"sample output 3","content":"36065"},{"iden":"sample input 4","content":"10\n4177143673\n7#########\n5#1716155#\n6#4#####5#\n2#3#597#6#\n6#9#8#3#5#\n5#2#899#9#\n1#6#####6#\n6#5359657#\n5#########"},{"iden":"sample output 4","content":"6525"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}