前回の切手の問題をまた解く

お久しぶりです。プロジェクトオイラーの問題をときながら前回の記事の解決案を見つけたのでまた記事にさせていただきます。
参考とさせていただいた記事は次のもので、

nantonaku-shiawase.hatenablog.com

前回の解き方の間違ってる点ですが、例えば手元に「1円」と「2円」の切手があるとします。そこで3円分を作るときに、0円分の作り方、1円分の作り方、・・・、と0円から考えていくやりかたでした。そこで3円分を作る際に2円分の組み合わせと1円分の組み合わせを足してたため「2円」と「1円」それぞれ一つずつの組み合わせの重複を余分に足してしまっていました。
そこで、1円を使って何通り、1円と2円を使って何通り・・・と使う切手の枚数を徐々に増やしていく考え方を学びました。コードで書くと次のとおりです。

K = [1,2]
N = 3
KN = [[0]*(N+1) for i in range(len(K))]
for n in range(N+1):
    KN[0][n] = 1
for k in range(len(K)):
    KN[k][0] = 1
for k in range(1,len(K)):
    for n in range(N+1):
        if n//K[k]==0: KN[k][n] = KN[k-1][n]
        else: KN[k][n] = KN[k-1][n]+KN[k][n-K[k]]
for k in KN:print(k)

まず0円分を作るのはどの値段の切手を使っても1通りです。次に、1円切手だけ使っても全部1とおりです。
では、2円切手を使うとどうなるのか、KN[1][1]から考えていきたいと思います。KN[1][1]は1円分にたいして1円切手と2円切手の組み合わせで2円切手は1枚も使わず1円切手だけを使うのでKN[0][1]の値と同値。次にKN[1][2]に対しては、2円切手を1枚使う方法(KN[1][0])と1円切手だけを使う方法(KN[0][2])があるのでその和と同値。これを繰り返していきます。
そこで本題について書いていきたい。
上の雛形を用いて

K = [1,2,3,5,10,20,30,50,62,82,92,100,120,140,205,280,310,500,1000]
N = 1000
KN = [[0]*(N+1) for i in range(len(K))]
for n in range(N+1):
    KN[0][n] = 1
for k in range(len(K)):
    KN[k][0] = 1
for k in range(1,len(K)):
    for n in range(N+1):
        if n//K[k]==0: KN[k][n] = KN[k-1][n]
        else: KN[k][n] = KN[k-1][n]+KN[k][n-K[k]]
for k in KN:print(k)

となり、答えは1141266126310（約1.14兆）通りあることがわかった。（すげえ）