fork download
  1. #include <iostream>
  2. using namespace std;
  3. const int mod = 1000000007;
  4. int a[10000];
  5. int solve(int n){
  6. int *A = a + n;
  7. A[0] = 1; A[-1] = 0;
  8. int k = 0, e = 1;
  9. for (int i = 0; i <= n; ++i){
  10. int Am = 0;
  11. A[k + e] = 0;
  12. e = -e;
  13. for (int j = 0; j <= i; ++j){
  14. Am += A[k];
  15. if (Am >= mod) Am -= mod;
  16. A[k] = Am;
  17. k += e;
  18. }
  19. }
  20. return n % 2 ? A[n / 2] : A[-n / 2];
  21. }
  22.  
  23. int main()
  24. {
  25. int n;
  26. cin >> n;
  27. cout << solve(n) << endl;
  28. return 0;
  29. }
  30.  
Success #stdin #stdout 0s 3380KB
stdin
5
stdout
16