{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003eProblem D: 僕の友達は小さい\u003c/h1\u003e\n\n\u003cp\u003e\n僕には、たくさんの友達がいる。どの友達も、とても小さい。\u003cbr\u003e\n僕は、よく友達と一緒に出かける。何人かの友達をリュックに入れて、一緒に出かける。\u003cbr\u003e\n僕は毎朝、その日一緒に出かける友達を決める。空のリュックに、1人ずつ友達を入れていく。\u003cbr\u003e\n僕は、あまり力が強くない。だから、同時に運べる友達の重さには限界がある。\u003cbr\u003e\n僕は、重さの限界を超えないように友達を入れていく。どの順番で入れていくかは気分次第。\u003cbr\u003e\n僕は、入れられる友達がまだ残っている限り、入れるのを止めない。決して止めない。\u003cbr\u003e\n\u003c/p\u003e\n\n\u003cp\u003e\n……ところで、リュックに入った友達の組み合わせは、全部で何パターンあるんだろう?\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003e\n\u003ci\u003eN W\u003c/i\u003e\u003cbr\u003e\n\u003ci\u003ew\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e\u003cbr\u003e\n\u003ci\u003ew\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e\u003cbr\u003e\n.\u003cbr\u003e\n.\u003cbr\u003e\n.\u003cbr\u003e\n\u003ci\u003ew\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e\u003cbr\u003e\n\u003c/p\u003e\n\n\u003cp\u003e\n入力の1行目には、整数\u003ci\u003eN\u003c/i\u003e(1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 200)と整数\u003ci\u003eW\u003c/i\u003e(1 ≤ \u003ci\u003eW\u003c/i\u003e ≤ 10,000)が、この順に空白区切りで書かれている。整数\u003ci\u003eN\u003c/i\u003e は友達の数を、整数\u003ci\u003eW\u003c/i\u003e は同時に運べる重さの限界をあらわす。重さの合計が\u003ci\u003eW\u003c/i\u003e より大きいと運ぶことはできない。\n\u003c/p\u003e\n\n\u003cp\u003e\n続く\u003ci\u003eN\u003c/i\u003e 行には、友達の重さをあらわす整数が書かれている。整数\u003ci\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e(1 ≤ \u003ci\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 10,000)が、\u003ci\u003ei\u003c/i\u003e 番目の友達の重さをあらわす。\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\n最終的にリュックに入っている友達の組み合わせは何通り考えられるか。その総数を1,000,000,007\nで割った余りを出力せよ。なお1,000,000,007 は素数である。\n\u003c/p\u003e\n\u003cp\u003e\n「誰もリュックに入っていない」も1通りとして数えることに注意せよ。\n\u003c/p\u003e\n\n\n\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\u003e4 8\n1\n2\n7\n9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\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\u003e4 25\n20\n15\n20\n15\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\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\u003e6 37\n5\n9\n13\n18\n26\n33\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}