Lucky Numbers

For the purposes of this exercise, we will say that a positive integer is lucky if the following conditions hold:

• It has an even number of digits, and
• the sum of the first half of its digits is equal to the sum of the second half of its digits.

For example:

• The number ~123~ is not lucky because the number of its digits is 3, which is not an even number.
• The number ~153781~ is not lucky because the sum of the first half of its digits is ~1+5+3=9~, while the sum of the second half of its digits is ~8+7+1=16~.
• The number ~3791~ is lucky, because the sum of the first half of its digits is ~3+7=10~ and the sum of the second half of its digits is ~9+1=10~.

You are given N cards, each of which has a number written on it. In how many different ways can you stick together two different cards (i.e., concatenate the digits of the numbers written on them) to form a lucky number?

Problem

Write a program in one of the following languages: PASCAL, C, C++, JAVA, which will read the value of N and the numbers written on the N cards, and will print the number of different ways lucky numbers can be formed by sticking two cards together.

For your submissions to DMOJ, use STDIN and STDOUT. The input and output format will be as described below.

Input Files

The input file named luckyagain.in is a text file consisting of two lines. The first line contains an integer N, the number of cards. The second line contains ~N~ integers, separated in pairs by a single space.

Output Files

The output file named luckyagain.out is a text file containing a single line with an integer: the number of different ways lucky numbers can be formed by sticking two cards together.

Examples of Input - Output Files:

1st

input:

7
75038 92 1 728 83 5 423

output:

6

Explanation: Lucky numbers can be formed by sticking two cards together in 6 different ways:

• Sticking ~1~ and ~423~ together yields the lucky number ~1423~,
• Sticking ~75038~ and ~1~ together yields the lucky number ~750381~,
• Sticking ~92~ and ~83~ together yields the lucky number ~9283~,
• Sticking ~728~ and ~1~ together yields the lucky number ~7281~,
• Sticking ~83~ and ~92~ together yields the lucky number ~8392~, and
• Sticking ~423~ and ~75038~ together yields the lucky number ~42375038~.

2nd

input:

6
265 10387 392 981 6986 74

output:

0

Explanation: No lucky number can be formed.

3d

input:

5
17 62 35 44 80

output:

20

Explanation: Sticking any two cards together always results in a lucky number.

Constraints

• ~1 \leq N \leq 1.000.000~
• The numbers will be at most nine digits long, and the first digit will always be nonzero.
• For test cases with a total value of ~30%~, ~N \leq 1000~.
• For test cases with a total value of ~50%~, the numbers will be either five or six digits long.
• In the output, all lines must terminate with a newline character.
• Time Limit: ~2~ sec.
• Maximum Available Memory: ~128~ MB.

Attention: The answer may exceed ~2^{32}~. Also, make sure to read input and print output efficiently, especially if you're coding in C++ or Java.