وجدت Bessie وCanmuu كيسًا من $N$ عملات ذهبية ($1 \leq N \leq 250$) تريدان تقسيمه بالتساوي قدر الإمكان. قيمة العملة $i$ هي $v_i$ ($1 \leq V_i \leq 2{,}000$). تريد البقرتان كومتين متساويتين لكن ذلك ليس ممكنًا دائمًا. ما أصغر فرق بين قيمتيهما؟

قد توجد عدة طرق تحقق الفرق الأدنى. تريدان أيضًا عدد طرق التقسيم الأكثر عدلًا. إن لم يمكن التساوي، تأخذ Bessie الكومة الأعلى قيمة.

مثلًا، قيم خمس عملات $2, 1, 8, 4, 16$. كومة بها عملة $16$، والأخرى البقية بقيمة $1+2+4+8=15$. الفرق $16-15 = 1$. هذه الطريقة الوحيدة، لذا عدد طرق التقسيم بهذا العدل هو $1$.

يمكن تبديل العملات المتساوية القيمة بين الكومتين لزيادة طرق التقسيم الأمثل. لذا $\{1, 1, 1, 1\}$ له ست طرق مثلى مختلفة، بعملتين في كل كومة.

الإدخال

اقرأ من الإدخال القياسي.

• السطر $1$: عدد صحيح واحد $N$.

• الأسطر $2..N+1$: السطر $i+1$ يحتوي عددًا صحيحًا واحدًا $V_i$.

الإخراج

اكتب إلى الإخراج القياسي.

• السطر $1$: عدد صحيح يمثل أصغر فرق بين قيمتي الكومتين.

• السطر $2$: عدد طرق التقسيم بالفرق الأدنى في السطر الأول. قد يكون كبيرًا؛ اطبع باقي قسمته على $1,000,000$.

أمثلة

الإدخال 1

5
2
1
8
4
16

الإخراج 1

1
1

إعداد المسألة: Sherry Wu، مسألة كلاسيكية، 2010