矩阵元素的最大值

题目描述

给定一个N*N的矩阵，令a[i][j]为矩阵中第i行第j列第元素。

已知矩阵中的元素满足以下三个条件：

1. a[k][1]=a[1][k]=1 (1<= k <= N且k为奇数)
2. a[k][1]=a[1][k]=2 (1<= k <= N且k为偶数)
3. a[i][j]=a[i-1][j]+a[i][j-1] (2<=i,j<= N)

现给定N的大小，请你求出满足上述条件的矩阵中元素的最大值。

输入格式

输入数据包含一行，为一个正整数N (1<= N <= 500)，为矩阵的行数和列数。

输出格式

输出数据包含一行，为一个正整数m，表示上述矩阵中元素的最大值。

输入样例1

3

输出样例1

10

输入样例2

12

输出样例2

1180612