Background

人的一生注定会遇到两个人，一个惊艳了时光，一个温柔了岁月。

Description

YJQ is crazy about sequeces and brain twisters, and one day he was struck by a great question. Now, he wants you to solve it. You're given a sequence, and each time you can choose two numbers(a and b) from it, make a * b as your price, and put a+b back to the sequence. Repeat this operation until there's only one number in the sequence. Now, he wants to know the minimum of the total price(total price is the sum of prices each time you operate). Considering the result may be too big, you only need to output the result MOD 23336666.

Format

Input

The first line is a n, which represents the amount of numbers in the sequence.
Then there're n numbers in the following line, represent the sequence.

Output

One integer, the minimum of the total price MOD 23336666.

Sample

Input

3
1 2 3

Output

11

Limitation

1 <= n <= 1e7, 0 <= each number <= 100
0.5s, 512000KiB for each test case.

Hint

YJQ is crazy about brain twisters!!!
Pay attention to the time limit.

Source

xyfJASON