LongWordsDiv1 | Topcoder Archive

Problem Statement

Fox Ciel uses an alphabet that has n letters. She likes all the words that have the following properties:

Equal letters are never consecutive.
There is no subsequence of the form xyxy, where x and y are (not necessarily distinct) letters. Note that a subsequence doesn't have to be contiguous.
There is no longer word with properties 1 and 2.

Examples:

Ciel does not like "ABBA" because there are two consecutive 'B's.
Ciel does not like "THETOPCODER" because it contains the subsequence "TETE".
Ciel does not like "ABACADA" because it contains the subsequence "AAAA". (Note that here x=y='A'.)
Ciel does not like "ABCA" because "ABCBA" is longer.
If n=1 and the one letter Ciel uses is 'A', then she likes the word "A".
If n=2 and the two letters Ciel uses are 'A' and 'B', then she likes the words "ABA" and "BAB".

Given the int n, compute and return the number of words Ciel likes, modulo 1,000,000,007.

Definition

Class:: LongWordsDiv1
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 5000, inclusive.

Examples

```
1
```
```
Returns: 1
```
The only word Ciel likes is "A" (assuming 'A' is the only letter in the alphabet).
```
2
```
```
Returns: 2
```
The words Ciel likes are "ABA" and "BAB".
```
5
```
```
Returns: 1080
```
```
100
```
```
Returns: 486425238
```
Don't forget to compute the answer modulo 1,000,000,007.

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.