fork download
  1. import java.io.IOException;
  2. import java.io.OutputStreamWriter;
  3. import java.io.BufferedWriter;
  4. import java.util.InputMismatchException;
  5. import java.io.OutputStream;
  6. import java.io.PrintWriter;
  7. import java.util.NoSuchElementException;
  8. import java.io.Writer;
  9. import java.math.BigInteger;
  10. import java.io.InputStream;
  11.  
  12. /**
  13.  * Built using CHelper plug-in
  14.  * Actual solution is at the top
  15.  */
  16. public class Main {
  17. public static void main(String[] args) {
  18. InputStream inputStream = System.in;
  19. OutputStream outputStream = System.out;
  20. InputReader in = new InputReader(inputStream);
  21. OutputWriter out = new OutputWriter(outputStream);
  22. TaskD solver = new TaskD();
  23. solver.solve(1, in, out);
  24. out.close();
  25. }
  26. }
  27.  
  28. class TaskD {
  29. final static int mod = (int)1e9 + 7;
  30.  
  31. public void solve(int testNumber, InputReader in, OutputWriter out) {
  32. int n = in.readInt();
  33. int[][] dp = new int[n][];
  34. int[][] sums = new int[n][];
  35. dp[0] = new int[1];
  36. sums[0] = new int[1];
  37. dp[0][0] = 1;
  38. sums[0][0] = 1;
  39. for (int i = 1; i < n; i++) {
  40. dp[i] = new int[i + 1];
  41. sums[i] = new int[i + 1];
  42. if (i % 2 == 0) {
  43. for (int last = 0; last <= i; last++) {
  44. int add = getSum(sums[i - 1], last, i - 1);
  45. dp[i][last] += add;
  46. dp[i][last] %= mod;
  47. }
  48. } else {
  49. for (int last = 0; last <= i; last++) {
  50. int add = getSum(sums[i - 1], 0, last - 1);
  51. dp[i][last] += add;
  52. dp[i][last] %= mod;
  53. }
  54. }
  55. for (int last = 0; last <= i; last++) {
  56. if (last > 0) {
  57. sums[i][last] += sums[i][last - 1];
  58. sums[i][last] %= mod;
  59. }
  60. sums[i][last] += dp[i][last];
  61. sums[i][last] %= mod;
  62. }
  63. }
  64. int ans = 0;
  65. for (int last = 0; last < n; last++) {
  66. ans += dp[n - 1][last];
  67. ans %= mod;
  68. }
  69. out.printLine(ans);
  70. }
  71.  
  72. private int getSum(int[] sum, int L, int R) {
  73. if (L > R) {
  74. return 0;
  75. }
  76. int res = sum[R];
  77. if (L > 0) {
  78. res -= sum[L - 1];
  79. res += mod;
  80. res %= mod;
  81. }
  82. return res;
  83. }
  84. }
  85.  
  86. class InputReader {
  87.  
  88. private InputStream stream;
  89. private byte[] buf = new byte[1024];
  90. private int curChar;
  91. private int numChars;
  92. private SpaceCharFilter filter;
  93.  
  94. public InputReader(InputStream stream) {
  95. this.stream = stream;
  96. }
  97.  
  98. public int read() {
  99. if (numChars == -1)
  100. throw new InputMismatchException();
  101. if (curChar >= numChars) {
  102. curChar = 0;
  103. try {
  104. numChars = stream.read(buf);
  105. } catch (IOException e) {
  106. throw new InputMismatchException();
  107. }
  108. if (numChars <= 0)
  109. return -1;
  110. }
  111. return buf[curChar++];
  112. }
  113.  
  114. public int readInt() {
  115. int c = read();
  116. while (isSpaceChar(c))
  117. c = read();
  118. int sgn = 1;
  119. if (c == '-') {
  120. sgn = -1;
  121. c = read();
  122. }
  123. int res = 0;
  124. do {
  125. if (c < '0' || c > '9')
  126. throw new InputMismatchException();
  127. res *= 10;
  128. res += c - '0';
  129. c = read();
  130. } while (!isSpaceChar(c));
  131. return res * sgn;
  132. }
  133.  
  134. public boolean isSpaceChar(int c) {
  135. if (filter != null)
  136. return filter.isSpaceChar(c);
  137. return isWhitespace(c);
  138. }
  139.  
  140. public static boolean isWhitespace(int c) {
  141. return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  142. }
  143.  
  144. public interface SpaceCharFilter {
  145. public boolean isSpaceChar(int ch);
  146. }
  147. }
  148.  
  149. class OutputWriter {
  150. private final PrintWriter writer;
  151.  
  152. public OutputWriter(OutputStream outputStream) {
  153. writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  154. }
  155.  
  156. public OutputWriter(Writer writer) {
  157. this.writer = new PrintWriter(writer);
  158. }
  159.  
  160. public void close() {
  161. writer.close();
  162. }
  163.  
  164. public void printLine(int i) {
  165. writer.println(i);
  166. }
  167. }
  168.  
Success #stdin #stdout 0.07s 380224KB
stdin
4
stdout
5