Knapp
Турнир за Купата на Декана, 2017
Time Limit: 0.1s, Memory Limit: 64MiB
"Zeit ist Knapp!" ("Не остана време!"), мислеше си Ели, докато гледаше календара с оставащите дни преди Турнира за Купата на Декана. До него имаше едва седмица, а тя още не беше почнала да се подготвя! Сега момичето направи списък с всички задачи, които може да реши като подготовка, и колко време ще ѝ отнеме всяка от тях.

В зависимост колко и кои задачи момичето реши преди турнира, тя ще има различно "ниво на подготовка". С други думи, тя счита, че би имала две различни нива на подготовка, ако в едното е решила задача, която не е решила в другото.

Сега момичето се чуди колко различни нива на подготовка има, които тя би могла да постигне в оставащото ѝ време. Разбира се, Ели може да реши да не ползва цялото време, дори да има оставащо време за все още нерешени задачи. Тоест, ако много я домързи, тя може дори да не реши нито една задача, което също се счита за валидно ниво на подготовка.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N - броя задачи, които момичето е избрало за подготовката си. На следващия ред ще бъдат зададени N цели числа A1, A2, ..., AN - съответно времето (в минути), което ще ѝ отнеме решаването на всяка от задачите. Считаме, че Ели може да решава всяка минута от оставащите 7 * 24 * 60 = 10080 минути, без да губи време за незначителни неща, които другите хора правят, като например ядене и сън.
Изход
На единствен ред на стандартния изход изведете едно единствено цяло число - броя различни "нива на подготовка", които би могло да има момичето в края на седмицата. Тъй като това число може да бъде много голямо, изведете само неговия остатък при деление на 1,000,000,007.
Ограничения
  • 1 ≤ N ≤ 1,000
  • 1 ≤ Ai ≤ 10,080
Примерен Вход Примерен Изход
7 1337 666 4242 7777 5678 9114 1337 33
42 685 303 563 712 205 906 868 986 999 404 836 732 741 427 58 577 778 493 600 191 10 688 54 258 551 627 537 744 837 772 213 910 930 419 171 602 744 404 710 569 453 991 176115024
В първия пример има общо 33 под-множества на дадените числа, чиято сума е по-малка или равна на 10080 - това са всички възможни нива на подготовка, които Ели може да има. Някои от възможните комбинации са: {}, {1337, 7777}, {9114}, {1337, 666, 4242}, {1337, 666, 4242, 1337}. Комбинацията {4242, 7777} не е валидна, тъй като има сума по-голяма от 10080, а {4242, 4242} - тъй като съдържа една задача повече от веднъж. Забележете, че {1337, 666, 4242, 1337} беше валидна, тъй като има две различни задачи, отнемащи 1337 минути.
Във втория пример не забравяйте да изведете отговора по модул 1,000,000,007.
Мрън!