Codeforces Round #803 (Div. 2)
04:58:06 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
E. Дарт Вадер ба мод
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Дарт Вадер уйдахдаа буйдан дээрээ сууж нүдээ аниад орой бүр нь яг $n$ хүүхэдтэй, үндэстэй, хязгааргүй үргэлжлэх мод төсөөлж гэнэ. Орой бүрийн зүүнээсээ $i$ дэх хүүхэд түүнээс $d_{i}$ зайд байрлана. Дарт Вадер модны үндэснээс $x$-ээс хэтрэхгүй зайд байх оройг тоолж суусан бөгөөд үүндээ их л дуртай байв. Үндэснээс орой хүртэлх зай гэдэг нь тухайн орой хүртэлх замуудын уртуудын нийлбэр юм.
Гэсэн хэдий ч тэрээр үүнийг хийсээр байгаад уйдах үед нь чи түүнээс "яагаад юм хийж суугаа юм бэ?" хэмээн асууж таарав. Тэгтэл тэрээр "надаас өөр хэн ч ийм юм хийж чадахгүй учраас" гэж хариулах нь тэр.
Чи Дарт Вадерын буруу болохыг нотолмоор байна уу. Үүнийг хийж чадна гэдгээ харуулж модны үндэснээс $x$-ээс хэтрэхгүй зайнд байх оройнуудын тоог ол. Хариу их том тоо байж болох тул $10^{9} + 7$ тоонд хуваасан үлдэгдлийг олоорой.
Оролт
Эхний мөрөнд орой бүрээс гарах хүүхдийн тоо болон нөхцөлд буй зайг илэрхийлэх $n$ ба $x$ ($1 ≤ n ≤ 10^{5}, 0 ≤ x ≤ 10^{9}$) тоонууд байна.
Дараагийн мөрөнд $n$ ширхэг $d_{i}$ ($1 ≤ d_{i} ≤ 100$) тоонууд зайгаар тусгаарлагдан байх ба энэ нь $i$ дэх хүүхдийн эцгээсээ хэр хол зайд байгааг илэрхийлнэ.
Гаралт
Үндэснээс $x$-ээс хэтрэхгүй зайнд байх оройн тоог ол.
Орчуулсан: Бат-Од
Жишээ тэстүүд
Оролт
3 3 1 2 3
Гаралт
8
Тэмдэглэл
Жишээг зургаар дүрслэв (шар өнгийн оройнууд үндэснээс хамгийн ихдээ $3$ зайтай байна)