UNSWap

Program time limit: 1 second

Program memory limit: 512 MB

Isaiah is computing the sum of an array $a$, which contains $n$ integers: $a_1, a_2, \dots, a_n$.

After finding the sum, he can perform exactly one digit swap, which is done by swapping around any two digits. Digit sums can either be within the same number, or across different numbers. The only restriction is numbers cannot start with the digit $0$, unless the number is a single digit $0$.

How many different digit swaps are there which do not change the sum of array $A$? Since the answer can get big, please give your answer modulo $1,000,000,007$.

Input

The first line of input contains an integer $n$, which represents the number of
The second line contains $N$ space separated integers, representing $A$.

Constraints

For all test cases:

$1 \le n \le 10^5$,
$0 \le a_i \le 10^9$ for $1 \le i \le n$.

Additionally:

For Subtask 1 (50% of points): $n \le 100$,
For Subtask 2 (50% of points): there are no additional constraints.

Output

Output a single integer, which represents the number of digit swaps which do not change the sum of array $A$.

Templates

You should read from standard input and write to standard output.

In Python, you could use the following code.

# Taking inputs, already done! :D
n = int(input())
A = list(map(int, input().split()))

ans = 0
# Write your code here


# Printing output
print(ans)

In C or C++, you could use the following code.

// Taking inputs, already done! :D
int n; scanf("%d", &n);
int A[n]; for (int i = 0; i < n; i++) scanf("%d", &A[i]);

int ans;
// Write your code here


// Printing output
printf("%d\n", answer);

Sample Input 1

2
123 330

Sample Output 1

Explanation 1

These are four pairs of numbers with a sum of $453$: $323+130, 133+320, 120+333, 123+330$. Importantly, there are three swaps that result in $123+330$. Therefore, there are a total of $6$ valid digit swaps.

Sample Input 2

1
110

Sample Output 2

Explanation 2

The only valid digit swap is between the $1$ in the hundreds position and the $1$ in the tens positions.

Scoring

For each subtask (worth 50% and 50% of points, as per the Constraints section), your program will be run on multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves that subtask. Your program will receive the points for each subtask it solves. Recall that your final score on the task is the score of your highest scoring submission.