Sum

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

You are given an N*N digit matrix and you can get several horizontal or vertical digit strings from any position.

For example:

123

456

789

In first row, you can get 6 digit strings totally, which are 1,2,3,12,23,123.

In first column, you can get 6 digit strings totally, which are 1,4,7,14,47,147.

We want to get all digit strings from each row and column, and write them on a paper. Now I wonder the sum of all number on the paper if we consider a digit string as a complete decimal number.

Input

The first line contains an integer N. (1 <= N <= 1000)

In the next N lines each line contains a string with N digit.

Output

Output the answer after module 1,000,000,007(1e9+7)。

Sample Input

3
123
456
789

Sample Output

2784

Source

dut200901102

Manager

Information
Solved Number204
Submit Number572
Problem Tags
implementation
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel