There are rows and columns of square cells. Each cell has either a digit or an asterisk ('*'). The cell at the -th row from the top and the -th column from the left is denoted by .
In this problem we consider subrectangles, each of which is the set of cells which forms a rectangle. More precisely, a set of cells is a subrectangle if there are four integers , , and such that , and . A subrectangle is digit-only if every cell in the subrectangle has a digit. The score of a digit-only subrectangle is defined as the square of the sum of digits in cells in the subrectangle.
Your task is to calculate the sum of scores of all digit-only subrectangles. Since the answer may be large, output it modulo .
输入格式
The input consists of a single test case of the following format.
The first line consists of two integers and , which satisfy and . Each of the following lines consists of characters. Here, is the character in the cell , and it is either a digit between and , inclusive, or an asterisk ('*'). It is guaranteed that there is at least one digit-only subrectangle.
输出格式
Output in a line the sum of scores of all digit-only subrectangles modulo .
