Project Euler #31: Coin sums

  • + 2 comments
    k = int(input())
    for i in range (k):
        l = int(input())
        ways = [0]*100001
        ways[0] = 1
        for x in [1,2,5,10,20,50,100,200]:
            for i in range(x, 100001):
                ways[i] += ways[i-x]
        print (ways[l]%(10**9+7))
    

    I am getting correct answers for testcases 0 1 and 3, but everything is timeout. How can I optimize this? Thanks.