2603: 兽人永不为奴
内存限制：32 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
“兽人永不为奴!”兽人大喊着决定要反攻人类，现有n个兽人编号分别为1至n，编号越小的兽人越强。且兽人一共有两种兵种：编号奇数的兵种为战士，编号偶数的兵种为弓兵。兽人们要分三路攻打人类，所以需要把兽人们分成三个队伍，每个队伍最强的兽人为领队，每个队伍都必须满足如下规则：
(1)如果按实力由大到小排序，那么兽人们是战士和弓兵交替出现的；
(2)三个队长有且只有一个是弓兵；
兽人首领很想知道有多少种合法的队伍方案。
(1)如果按实力由大到小排序，那么兽人们是战士和弓兵交替出现的；
(2)三个队长有且只有一个是弓兵；
兽人首领很想知道有多少种合法的队伍方案。
输入
多个样例，每个样例一行，每行1个整数n(2<n<10^9)代表兽人士兵的数量，输入以EOF结束
输出
每个样例一行，输出合法方案的个数，为了方便,只需要输出最后四位(不足四位原样输出)
样例输入 复制
3
6
样例输出 复制
1
21