帕斯卡三角形 (Pascal's Triangle) 是一個特別的三角數列，已經發現許多的數學性質可以和它有所關連。

定義此三角形的頂端(第 0 列)為1，之後的每一列都比上一列多一個數字，因此第 n 列的總共有 n + 1 個數字，每一列以等腰三角形的形式置中對齊。
除了第 0 列的任一個數字都是左上和右上數字的和，如果這個數字是在這一列的最左或最右側，它的左上及右上將沒有數字，此時我們將沒有數字的地方視為 0 。

綜合以上性質，可以得到以下的三角形，在此只列出到第四列：

第 0 列：    1
第 1 列：   1 1
第 2 列：  1 2 1
第 3 列： 1 3 3 1
第 4 列：1 4 6 4 1

不過本題為了方便敘述起見，我們將帕斯卡三角形稍微變形一下，原本置中對齊變成了靠左對齊，就像這樣：

第 0 列：1
第 1 列：1 1
第 2 列：1 2 1
第 3 列：1 3 3 1
第 4 列：1 4 6 4 1

這次要問你的是，從第 n 列的第一個數字開始往右上角相加，直到沒有數字為止，此時的總和為多少？
(更白話地說，若定義每一列的第一個數字為第 0 項，且三角形外空白部分全部補 0 ，則對於每一個 i (0 <= i <= n) ，將每個第 n - i 列的第 i 項  相加的總和為何？)
答案可能非常大，請 Mod 10000 後輸出。