Two Sets II

Your task is to count the number of ways numbers 1,2,\ldots,n can be divided into two sets of equal sum. For example, if n=7, there are four solutions: - \{1,3,4,6\} and \{2,5,7\} - \{1,2,5,6\} and \{3,4,7\} - \{1,2,4,7\} and \{3,5,6\} - \{1,6,7\} and \{2,3,4,5\} Input The only input line contains an integer n. Output Print the answer modulo 10^9+7. Constraints - 1 \le n \le 500 Exampl