{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"問題文","value":{"format":"HTML","content":"\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003cp\u003e高橋くん様は、アットコーダー王国の王様です。\u003c/p\u003e\r\n\r\n\u003cp\u003eプログラミングコンテスト好きな彼が統治するアットコーダー王国では、年に一度コンテストが開催されます。\u003c/p\u003e\r\n\r\n\u003cp\u003eこのコンテストでは \u003cvar\u003e\\(N\\)\u003c/var\u003e 問の問題が出題されます。また、順位を付ける際の \u003cvar\u003e\\(1\\)\u003c/var\u003e つの要素としてペナルティというものが存在します。\r\nある問題を正解したとき、コンテスト開始から経過した時間分だけのペナルティが、各問題ごとに発生します。そして、その発生したペナルティの総和がコンテストペナルティとなります。ARCのペナルティとは異なるルールであることに注意してください。\u003c/p\u003e\r\n\r\n\u003cp\u003e非常に優秀な国民である貴方には、全ての問題を解く力があります。\r\nしかも、全ての問題について、その問題を正解するためにどれだけ時間をかければよいのかを知っており、ちょうどその時間取り組むと必ず正解することができます。\u003c/p\u003e\r\n\r\n\u003cp\u003e貴方は、自由な順番で問題を解くことができるので、コンテストペナルティが最小となるように解こうと思いました。\u003c/p\u003e\r\n\r\n\u003cp\u003e全ての問題を解くときのコンテストペナルティの最小値と、そのような解き方が何通りあるかを \u003cvar\u003e\\(1,000,000,007(10^9+7)\\)\u003c/var\u003e で割った余りを答えて下さい。\u003c/p\u003e\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"入力","value":{"format":"HTML","content":"\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003cp\u003e入力は以下の形式で標準入力から与えられる。\u003c/p\u003e\r\n\r\n\u003cpre\u003e\r\n\u003cvar\u003e\\(N\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(T_1\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(T_2\\)\u003c/var\u003e\r\n:\r\n\u003cvar\u003e\\(T_N\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\r\n\u003cul class\u003d\"simple\"\u003e\r\n\r\n\t\u003cli\u003e\u003cvar\u003e\\(1\\)\u003c/var\u003e 行目には、コンテストでの問題数を表す整数 \u003cvar\u003e\\(N (1 ≦ N ≦ 10,000)\\)\u003c/var\u003e がスペース区切りで与えられる。\u003c/li\u003e\r\n\r\n\t\u003cli\u003e\u003cvar\u003e\\(2\\)\u003c/var\u003e 行目からの \u003cvar\u003e\\(N\\)\u003c/var\u003e 行には、各問題を解くのにかかる時間の情報が与えられる。そのうち \u003cvar\u003e\\(i (1≦i≦N)\\)\u003c/var\u003e 行目には、整数 \u003cvar\u003e\\(T_i (1≦T_i≦10,000)\\)\u003c/var\u003e が書かれており、\u003cvar\u003e\\(i\\)\u003c/var\u003e 番目の問題を解くのに \u003cvar\u003e\\(T_i\\)\u003c/var\u003e 分かかることを示す。\u003c/li\u003e\r\n\r\n\u003c/ul\u003e\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"部分点","value":{"format":"HTML","content":"\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003cp\u003eこの問題には部分点が存在する。\u003c/p\u003e\r\n\r\n\u003cul class\u003d\"simple\"\u003e\r\n\r\n\t\u003cli\u003e\u003cvar\u003e\\(100\\)\u003c/var\u003e 点中 \u003cvar\u003e\\(50\\)\u003c/var\u003e 点分のテストケースにおいて、コンテストペナルティが最小となるような解き方の数は \u003cvar\u003e\\(1\\)\u003c/var\u003e 通りである。\u003c/li\u003e\r\n\r\n\u003c/ul\u003e\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"出力","value":{"format":"HTML","content":"\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003cp\u003e出力は以下の形式で標準出力に出力せよ。\u003c/p\u003e\r\n\r\n\u003cul class\u003d\"simple\"\u003e\r\n\r\n\t\u003cli\u003e\u003cvar\u003e\\(1\\)\u003c/var\u003e 行目には、コンテストペナルティの最小値を出力せよ。32bit整数型ではオーバーフローする可能性があることに気をつけること。\u003c/li\u003e\r\n\r\n\t\u003cli\u003e\u003cvar\u003e\\(2\\)\u003c/var\u003e 行目には、コンテストペナルティが最小となるような解き方の数を \u003cvar\u003e\\(1,000,000,007(10^9+7)\\)\u003c/var\u003e で割った余りを出力せよ。\u003c/li\u003e\r\n\r\n\u003c/ul\u003e\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n2\r\n20\r\n10\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n40\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\r\n\r\n\u003cp\u003e\u003cvar\u003e\\(2\\)\u003c/var\u003e 番目の問題を解いてから \u003cvar\u003e\\(1\\)\u003c/var\u003e 番目の問題を解くのがよい。\u003c/p\u003e\r\n\r\n\u003cul class\u003d\"simple\"\u003e\r\n\r\n\t\u003cli\u003eコンテストが開始する(時刻:\u003cvar\u003e\\(0\\)\u003c/var\u003e 分)。\u003c/li\u003e\r\n\r\n\t\u003cli\u003e\u003cvar\u003e\\(10\\)\u003c/var\u003e 分後、\u003cvar\u003e\\(2\\)\u003c/var\u003e 番目の問題に正解する(時刻:\u003cvar\u003e\\(10\\)\u003c/var\u003e 分)。この時点で発生するペナルティは \u003cvar\u003e\\(10\\)\u003c/var\u003e 分である。\u003c/li\u003e\r\n\r\n\t\u003cli\u003eその \u003cvar\u003e\\(20\\)\u003c/var\u003e 分後、\u003cvar\u003e\\(1\\)\u003c/var\u003e 番目の問題に正解する(時刻: \u003cvar\u003e\\(30\\)\u003c/var\u003e 分)。この時点で発生するペナルティは \u003cvar\u003e\\(30\\)\u003c/var\u003e 分である。\u003c/li\u003e\r\n\r\n\u003c/ul\u003e\r\n\r\n\u003cp\u003eコンテストペナルティは \u003cvar\u003e\\(40(\u003d10+30)\\)\u003c/var\u003e 分となる。\u003c/p\u003e\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n5\r\n2\r\n1\r\n2\r\n1\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n21\r\n12\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n13\r\n1\r\n1\r\n1\r\n1\r\n1\r\n1\r\n1\r\n1\r\n1\r\n1\r\n1\r\n1\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n91\r\n227020758\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\r\n\r\n\u003cp\u003eどのような順番で解いても良い。余りを取るのを忘れないこと。\u003c/p\u003e\r\n\r\n\u003c/section\u003e\r\n"}}]}