1455: 小V的和弦

作为一名爱好音乐的业余小提琴手，小V经常在空闲的时候来研究和弦的构成。（小J：我也不知道小提琴咋整出不拆分的和弦（逃~））

小V把一个和弦定义为n个音符组成的序列，每个音符都有一个频率值。

经过长时间的研究，小V发现，当一个和弦里的第i个音符的频率值小于第i+2(如果存在）和第i+3(如果存在）个音符的频率值时，这个音乐会更加的每妙。

为了便于分析，小V假定，对于一个n个音符组成的和弦，每个音符的频率值都是一个属于[1,n]的正整数。

现在小V想知道，对于一个给定的正整数n，共有多少种不同的和弦呢。

注意两个和弦不同，当且仅当存在一个位置，这两个和弦此位置上的音符频率值不相同。

一个正整数n

一行一个数，表示不同和弦的种类数。结果对4294967296取模。

3

9

对于20%的数据，1 <= n <= 50

对于50%的数据，1 <= n <= 300

对于100%的数据，1 <= n <= 1000

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！