题目描述
过几天就是小N的生日了,小A作为小N最好的朋友,想要送给他一些礼物,但是他不知道小N喜欢什么,所以小A给了小N一个长长的列表让小N自己挑礼物。列表上有N个物品。小N对每一个物品有一个喜爱值Ai。小N想从这些物品中选出一些物品使得喜爱值总和最大,但不能一个物品也不选。
现在小N想要知道最大的喜爱值总和是多少,有多少种选法符合。由于方法很多多,所以你只需要求出方案数mod 1000000000000000003的结果。
对于20%的数据:N<=20
对于40%的数据:N<=1000
对于100%的数据N<=1000000,|Ai|<=1000000
输入格式
第一行一个整数N。
第二行N个整数Ai,用空格分隔。
输出格式
输出一行两个整数,表示最大的喜爱值,以及方案数mod 1000000000000000003的结果。
样例输入
样例输出