问题描述

n个矩阵的连乘：P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？

输入描述

一个整数 n (n<500)

输出描述

一个整数方案数，对100000007求余

输入样例

3

输出样例

2