20253번 - In The Name Of Confusion 다국어

There’s no such thing as public opinion.

---

Jordan Ellenberg, American Mathematician

In K City lives n residents who want to build a connection network with each other. However, some residents want the network wires colored black while the others want the wires colored white. The opinion of resident i can be quantified as a number ai . If we build a network wire between residents i and j, the cost of this wire will be a_i × a_j.

The mayor of K City wants to build a network such that:

1. There are exactly n − 1 wires used.
2. For any two different residents i and j, there exists a sequence p₁, · · · , p_k such that p₁ = i, p_k = j and residents p_ℓ and p_ℓ+1 share a wire for 1 ≤ ℓ < k.

In other words, the network should be a tree.

You, the renowned mathematician of K City, want to know not only the minimum cost to build the network. In the name of confusion, you also want to know the maximum cost!

The first line begins with a number n indicating the number of residents. The second line contains n numbers a₁, a₂, . . . , a_n. The opinion of resident i is the quantified as a_i.

Output two numbers separated by a blank in a line. The numbers are the minimum cost and the maximum cost to build the network, respectively. Since the absolute value of the costs may be extremely large, you have to modulo the answer with 10⁹ + 7. Please note that the modulo of a number (defined by Donald Knuth) is a mod b = a − b⌊a/b⌋. The output number should be non-negetive.

• 1 ≤ n ≤ 10⁶
• |a_i| ≤ 10⁶