# your code goes here
def count(S, m, n):
# table[i] will be storing the number of solutions for
# value i. We need n+1 rows as the table is constructed
# in bottom up manner using the base case (n = 0)
# Initialize all table values as 0
table = [0 for k in range(n+1)]
# Base case (If given value is 0)
table[0] = 1
# Pick all coins one by one and update the table[] values
# after the index greater than or equal to the value of the
# picked coin
for i in range(0,m):
for j in range(S[i],n+1):
table[j] += table[j-S[i]]
return table[n]
# Driver program to test above function
arr = [1, 2, 3]
m = len(arr)
n = 4
x = count(arr, m, n)
print (x)
IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmRlZiBjb3VudChTLCBtLCBuKTogCiAgCiAgICAjIHRhYmxlW2ldIHdpbGwgYmUgc3RvcmluZyB0aGUgbnVtYmVyIG9mIHNvbHV0aW9ucyBmb3IgCiAgICAjIHZhbHVlIGkuIFdlIG5lZWQgbisxIHJvd3MgYXMgdGhlIHRhYmxlIGlzIGNvbnN0cnVjdGVkIAogICAgIyBpbiBib3R0b20gdXAgbWFubmVyIHVzaW5nIHRoZSBiYXNlIGNhc2UgKG4gPSAwKSAKICAgICMgSW5pdGlhbGl6ZSBhbGwgdGFibGUgdmFsdWVzIGFzIDAgCiAgICB0YWJsZSA9IFswIGZvciBrIGluIHJhbmdlKG4rMSldIAogIAogICAgIyBCYXNlIGNhc2UgKElmIGdpdmVuIHZhbHVlIGlzIDApIAogICAgdGFibGVbMF0gPSAxCiAgCiAgICAjIFBpY2sgYWxsIGNvaW5zIG9uZSBieSBvbmUgYW5kIHVwZGF0ZSB0aGUgdGFibGVbXSB2YWx1ZXMgCiAgICAjIGFmdGVyIHRoZSBpbmRleCBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gdGhlIHZhbHVlIG9mIHRoZSAKICAgICMgcGlja2VkIGNvaW4gCiAgICBmb3IgaSBpbiByYW5nZSgwLG0pOiAKICAgICAgICBmb3IgaiBpbiByYW5nZShTW2ldLG4rMSk6IAogICAgICAgICAgICB0YWJsZVtqXSArPSB0YWJsZVtqLVNbaV1dIAogIAogICAgcmV0dXJuIHRhYmxlW25dIAogIAojIERyaXZlciBwcm9ncmFtIHRvIHRlc3QgYWJvdmUgZnVuY3Rpb24gCmFyciA9IFsxLCAyLCAzXSAKbSA9IGxlbihhcnIpIApuID0gNAp4ID0gY291bnQoYXJyLCBtLCBuKSAKcHJpbnQgKHgpIAogIAo=