COCI '19 Contest 5 #5 Zapina

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

There is a total of N young programmers which are preparing for the second part of competitive season during a winter camp in Krapina Zagreb. Mr. Malnar, a big promoter of order, discipline and hard work, told the programmers to form a line and gave each of them a certain number (possibly zero) tasks. He gave away a total of N different tasks and he knows that the i-th programmer in line will be happy if they got exactly i tasks.

In how many different ways could Mr. Malnar give out the tasks in such a way that at least one programmer was happy? Two ways of giving out the tasks are considered different if there exists a programmer and a task such that in one way that programmer received that task while in the other one they didn't.

Input

The first line contains an integer N (1 \le N \le 350) from task description.

Output

Output the sought number of ways modulo 10^9 + 7.

Scoring

Subtask Score Constraints
1 22 1 \le N \le 7
2 33 1 \le N \le 20
3 55 No additional constraints.

Sample Input 1

1

Sample Output 1

1

Sample Input 2

2

Sample Output 2

3

Explanation for Sample Output 2

Ways of giving out the tasks in which at least one programmer is happy are:

  1. First task to first programmer, second task to the second one.
  2. Second task to the first programmer, first task to the second one.
  3. Both tasks to the second programmer.

Sample Input 3

314

Sample Output 3

192940893

Comments

There are no comments at the moment.