Chains4 | Topcoder Archive

Problem Statement

All problems in this problem set are about "chains": collections of nested ranges of integers. All problems are independent, but use the same definitions. Each problem statement contains the definitions it needs. If a term appears in multiple problems, the definition is always identical.

Definitions follow. The defined term is always in uppercase.

An INTERVAL [x,y) with x <= y is the set of integers that are greater than or equal to x, and strictly less than y.
There is only one EMPTY INTERVAL but it has multiple equivalent notations. For example, [0,0) and [3,3) both denote the empty interval. Note that [3,0) is not a valid interval, because an interval [x,y) must have x <= y.
An interval I₁ is called a PROPER SUBSET of an interval I₂ if I₂ contains all elements of I₁ and at least one other element.
A CHAIN is a nonempty sequence of intervals such that each interval (except for the last one) is a proper subset of the next interval.
A CHAIN OF ORDER n is any chain such that the last interval in the chain is either the interval [0,n) or its proper subset.

Given the int n, compute and return the number of chains of order n, modulo (10^9 + 7).

Definition

Class:: Chains4
Method:: count
Parameters:: int
Returns:: int
Method signature:: int count(int n)
(be sure your method is public)

Constraints

n will be between 1 and 20,000, inclusive.

Examples

```
2
```
```
Returns: 11
```
These are all the chains of order 2: [0,0) [0,1) [1,2) [0,2) [0,0), [0,1) [0,0), [1,2) [0,0), [0,2) [0,1), [0,2) [1,2), [0,2) [0,0), [0,1), [0,2) [0,0), [1,2), [0,2)

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.