帕斯卡三角形 (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 後輸出。