Nice partition P22494


Statement
 

pdf   zip

html

In this problem, we say that a partition of the numbers {1, …, n} is nice if

  • it has at least two subsets,
  • and every subset has at least two elements.

Additionally, we only consider partitions that are qualitatively different.

For instance, for n = 5 we only have one nice partition: {{1, 2}, {3, 4, 5}}. Notice that {{1, 2, 3, 4, 5}} would not fulfil the first property above, {{2}, {1, 3, 4, 5}} would not fulfil the second property above, while {{2, 3}, {1, 4, 5}} would be basically the same partition as the only one given.

Given n, how many nice partitions do we have?

Input

Input consists of several cases, each one with an n between 1 and 3 · 104.

Output

For every n, print the number of nice partitions of {1, …, n} modulo 108 + 7.

Public test cases
  • Input

    3
    5
    6
    10
    114
    30000
    

    Output

    0
    1
    3
    11
    674029
    55250428
    
  • Information
    Author
    Xavier Molinero
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Setzè Concurs de Programació de la UPC - Semifinal
    Date
    2018-06-20