Алиса и Громозека играют в фишки по следюущим правилам. Громозека загадывает определенное число, а Алиса должна использовать свои фишки, чтобы составить сумму, равную этому числу. У Алисы есть фишки, на каждой из которых записано определенное число. Алиса имеет неограниченный запас фишек с каждым числом. Если Алиса сможет составить нужную сумму, используя свои фишки, она победит.
Ваша задача - определить, сможет ли Алиса победить Громозеку и если да, то сколько различных комбинаций у нее есть для достижения победы. Если Алиса не сможет победить Громозеку, то вы должны вывести число 0.
Входные данные
Программа получает в первой строке два числа:
n - количество различных чисел, которые записаны на фишках,
num - число, которое загадал Громозека. Во второй строке записаны n различных чисел
ci - числа, каждое из которых может быть записано на фишке. На каждой фишке записано только одно число из набора чисел
ci. При этом, количество фишек с числом
ci не ограниченно. Все фишки с одинаковым числом, считаются одинаковыми. Другими словами, комбинация фишек 2+1 и 1+2 считается одной комбинацией.
Ограничения
1 <= n <= 3001 <= ci <= 5000- Все значения
ci уникальны.
0 <= num <= 5000
Выходные данные
Выведите одно число - количество комбинаций, которым Алиса может выиграть Громозеку. Если Алиса не может выиграть, то выведите на экран 0.
Примечание
В первом примере есть 4 способа набрать сумму, равную 5:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
1 2 5
|
4
|
|
2
|
1 3
2
|
0
|