# 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=