COCI 2019/2020 - Contest 5 - Zapina

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2019/2020 - Contest 5
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Có ~N~ lập trình viên đang chuẩn bị tham gia vòng 2 của cuộc thi lập trình tại trại đông Krapina Zagreb. Mr.Malnar sẽ là người ra đề cho cuộc thi. Ông ấy đã yêu cầu các lập trình viên xếp thành một hàng và giao cho mỗi người một số nhiệm vụ nhất định (có thể là 0 nhiệm vụ). Mr.Malnar đã giao tổng cộng ~N~ nhiệm vụ khác nhau, biết rằng lập trinh viên thứ ~i~ sẽ thấy thoả mãn nếu họ được giao đúng ~i~ nhiệm vụ.

Hãy giúp Mr.Malnar xác định xem có bao nhiêm cách giao nhiệm vụ khác nhau, sao cho mỗi cách giao nhiệm vụ có ít nhất một lập trình viên thấy thoả mãn.

Hai cách giao nhiệm vụ A và B được tính là khác nhau nếu tồn tại một nhiệm vụ được giao cho một lập trình viên trong cách A, nhưng nhiệm vụ đó lại không đươc giao cho lập trình viên đó trong cách B.

Input

  • Gồm một số nguyên ~N~ ~(1 \leq N \leq 350)~ là số lập trình viên cũng như là số nhiệm vụ khác nhau được giao.

Output

  • Ghi ra số cách giao khác nhau thoả mãn điều kiện dưới dạng module cho ~10^9 + 7~.

Sample 1

Input
1
Output
1

Sample 2

Input
2
Output
3

Sample 3

Input
314
Output
192940893

Subtask

  • ~5~ test có ~1 \leq N \leq 7~
  • ~11~ test tiếp theo có ~1 \leq N \leq 20~
  • ~21~ test còn lại không có điều kiện gì thêm

Giải thích

Ở ví dụ thứ 2 có ~3~ cách để giao nhiệm vụ để có ít nhất một lập trình viên thấy thoả mãn là:

  • Cách ~1~: Nhiệm vụ ~1~ giao cho lập trình viên thứ nhất, nhiệm vụ ~2~ giao cho lập giao trình viên thứ hai.
  • Cách ~2~: Nhiệm vụ ~2~ giao cho lập trình viên thứ nhất, nhiệm vụ ~1~ giao cho lập trình viên thứ hai.
  • Cách ~3~: Giao cả nhiệm vụ ~1~ và ~2~ cho lập trình viên thứ hai.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.