Description

序关系定义为小于大于和等于,计算n个变量的序关系有多少种 如3个变量a,b,c的序关系有13种 a = b = c a = b < c a < b = c a < b < c a < c < b a = c < b b < a = c b < a < c b < c < a b = c < a c < a = b c < a < b c < b < a

Input

文件是多case的,每行输入一个 n (1<=n<=3000) ,当 n 等于 0 时输入结束

Output

对于每一个case,输出一行,为序关系数,只需输出答案%100000000

Sample Input

3 4 0

Sample Output

13 75

Author

windy7926778