#828. Subsets with sum k
You get a list and k. Use recursion to count the subsets whose elements add up to k (the empty set counts when k=0).
### Input
The first line has n, the second line has n integers separated by spaces. The third line has k.
### Output
Answer.
Examples
Input
12 9 1 5 7 5 4 5 1 7 8 4 9 15
Output
41
Input
3 1 9 4 5
Output
1
💡 You can solve it with Python, JavaScript or blocks. Read the input line by line with input(). Don't print a question (like input("Number: ")). Print exactly what the output asks for, nothing more.