设正整数n > 2，要把集合{1..n} 分为3个非空集合A1，A2与A3，使得：
1） 对任意一个Ai（i = 1，2，3），如果将Ai中的元素升序排列，得到的序列中的元素是奇偶交替的；
2） 设Ai中最小数为 Xi（i = 1，2，3），则X1，与 X2， 与 X3 中恰好有一个偶数；
从文件numset.in读入一个数n（n < 10^9），在文件numset.out中打印符合以上要求的划分方案数。
为了简化计算，仅要求输出答案的最后四位。
注：如果两个划分方案仅仅是集合编号不同，看作同一划分方案。
样例输入1 3
,
样例输出1 1
样例输入2 6
样例输出2 21