int n = read() ; n >>= 1 ; n %= mod ;
	print((3ll * n * (n - 1) % mod + 1ll) % mod) ;

最大生成树的做法