금화 분할하기

탐험가 지호와 주연은 이집트 피라미드 탐험 도중, N개의 (1 <= N <= 250) 금화 주머니를 발견했으며 이를 공평하게 나누려고 합니다. 금화 i는 v_i (1 <= V_i <= 2,000)의 가치를 가지고 있습니다. 그들은 금화를 가능한 한 공평하게 나누고 싶지만, 완벽히 공평하게 나눌 수는 없습니다. 두 금화 주머니의 값 사이의 최소 차이는 얼마일까요?

추가로, 지호와 주연은 최소 차이로 금화 더미를 나눌 수 있는 방법이 여러 가지 있을 수 있다는 것을 발견했습니다. 가능한 한 공평하게 금화를 나눌 수 있는 방법의 수를 알고 싶어합니다. 금화 주머니를 공평하게 나눌 수 없는 경우, 지호가 가치가 더 높은 주머니를 가져갑니다.

예를 들어, 2, 1, 8, 4, 16의 가치를 가진 5개의 금화가 담겨 있는 주머니를 생각해보세요. 지호와 주연은 이 금화들을 두 더미로 나눕니다. 한 주머니에는 16의 가치를 가진 금화 한 개가 들어가고, 다른 주머니는 나머지 금화들이 들어가며 그 가치는 1+2+4+8=15입니다. 차이는 16-15 = 1이므로, 최소 차이는 1입니다. 이 방식으로 금화를 나눌 수 있는 방법은 하나뿐이므로, 공평하게 나눌 수 있는 방법의 수는 1입니다.

참고로, 동일한 가치의 금화는 주머니를 오갈 수 있어 최적의 분할을 실행하는 방법의 수를 늘릴 수 있습니다. 따라서 {1, 1, 1, 1}의 금화 집합은 각각 2개의 금화를 가진 두 최적의 부분으로 나누는 6가지 다른 방법이 있습니다.

• 첫 번째 줄 : 정수 하나: N
• 두 번째 줄부터 N+1 번째 줄 :  i+1번째 줄에서는 하나의 정수를 포함: V_i

• 첫 번째 줄 : 분할된 두 부분의 가장 작은 차이를 나타내는 하나의 정수.
• 두 번째 줄 : 첫 번째 줄에서 출력된 최소 차이로 금화를 나눌 수 있는 방법의 수를 나타내는 하나의 정수. (이 수는 매우 커질 수 있으므로, 1,000,000으로 나눈 나머지를 출력하세요.)