베시와 카무는 N(1 <= N <= 250) 개의 금화가 있는 가방을 발견했다. 가능한 균등하게 이 금화를 나누고 싶어 한다. i 번째 금화는 V_i 만큼의 값어치가 있다. 그러나 이것이 가능하지가 않다면 차이가 최소가 되도록 나누어야 한다.

만약 나누는 방법이 여러가지 이면 이 방법 수도 알고 싶어한다. 균등하게 나누어지지 않는다면 더 큰 값어치를 가진 것을 베시가 가진다.

예를 들어 2 ,1,8,4,16 의 금화가 있다면 균등하게 나눌수는 없고 베시가 16 , 나머지를 카뮤가 2,1,8,4 를 가진다면 15 가 되어 차가 1 이 되고 1 개의 방법만이 존재한다.

같은 값어치의 금화가 있더라도 나누는 방법에 다르게 포함시켜야 한다. 예를 들어 1,1,1,1 개의 금화가 있다면 나누는 방법수는 6 가지가 존재한다.

In addition, the Bessie and Canmuu have found that there might be multiple ways to split the piles with that minimum difference. They would also like to know the number of ways to split the coins as fairly as possible. If it isn't possible to split the piles evenly, Bessie will get the higher-valued pile.

By way of example, consider a sack of five coins of values: 2, 1, 8, 4, and 16. Bessie and Canmuu split the coins into two piles, one pile with one coin worth 16, and the other pile with the remaining coins worth 1+2+4+8=15. Therefore the difference is 16-15 = 1. This is the only way for them to split the coins this way, so the number of ways to split it evenly is just 1.

Note that same-valued coins can be switched among the piles to increase the number of ways to perform an optimal split. Thus, the set of coins {1, 1, 1, 1} has six different ways to split into two optimal partitions, each with two coins.

입력

• * Line 1: A single integer: N
• * Lines 2..N+1: Line i+1 contains a single integer: V_i

출력

• * Line 1: A single integer that is the smallest difference of two partitions.
• * Line 2: A single integer that is the number of ways to split the coins with the minimum difference printed in line 1. Since this number can get quite large, print the remainder when divided by 1,000,000.

입출력 예

입력

5
2
1
8
4
16

출력

1
1

출처:usaco JAN 11 silver