Knapsacks
Зимни Състезания по Информатика, 2010
Time Limit: 1s, Memory Limit: 64MiB
Ели заминава за Велико Търново! И колкото и въодушевена и превъзбудена от този факт да е тя, това не й помага ни най-малко да приготви багажа си. А женският багаж е нещо, за което трите измерения, с които сме свикнали, рядко са дори близко до достатъчни, а багаж със стотици малки крачета би избягал далеч само при мисълта да побере всичките неща, които тя иска да вземе. Изумително е как даже компютърни алгоритми като този за раницата не могат да й помогнат – главно, защото тя ще пътува не с една а с цели три раници, в които да побере стотиците (както ще видите по-късно – буквално) предмети, които ще са й нужни за нейното дълго двудневно пребиваване.
Както напоследък често се случва, вие решавате да й помогнете, като демонстрирате доминацията си над Дрехите и не само проверите дали Елеонора може да ги събере в трите си раници, ами по колко начина може да стане това. Две конфигурации ще считаме за различни, ако съществува дреха, която е в различни раници при тях.
Както напоследък често се случва, вие решавате да й помогнете, като демонстрирате доминацията си над Дрехите и не само проверите дали Елеонора може да ги събере в трите си раници, ами по колко начина може да стане това. Две конфигурации ще считаме за различни, ако съществува дреха, която е в различни раници при тях.
Вход
На първия ред на стандартния вход ще бъдат дадени четири цели числа: N, C1, C2, C3, задаващи, съответно, броя предмети, които Ели иска да вземе, както и капацитета на трите раници. На втория ред ще има N цели числа A1, A2, …, AN, указващи теглата на различните предмети.
Изход
На единствен ред на стандартния изход изведете едно цяло число – броя начини, по които Ели може да сложи дрехите с в раниците. Тъй като това число може да бъде доста голямо, изведете само остатъка му при деление на 1,000,000,007. Редът, в който Ели слага предметите в раниците, е без значение - важно е единствено кой предмет в коя раница е. Позволено е раница да остане празна.
Ограничения
- 1 ≤ N ≤ 500
- 1 ≤ Ci ≤ 500
- 1 ≤ Ai ≤ 500
Примерен Вход | Примерен Изход |
---|---|
5 3 7 4 1 7 2 1 3 | 3 |
23 42 177 113 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | 668581565 |
В първия пример раниците са с вместимост, съответно, 3, 7 и 4. Трите различни конфигурации, как Ели може да разположи дрехите си, са {(1, 2), (7), (1, 3)}, {(1, 2), (7), (1, 3)} и {(3), (7), (1, 1, 2)}. Забележете, че има разлика между първата и втората единица, тъй като обозначават различни предмети.