Statistics

Problem Statement for "LongWordsDiv1"

Problem Statement

Fox Ciel uses an alphabet that has n letters. She likes all the words that have the following properties:
  1. Equal letters are never consecutive.
  2. 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.
  3. 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. 1

    Returns: 1

    The only word Ciel likes is "A" (assuming 'A' is the only letter in the alphabet).

  2. 2

    Returns: 2

    The words Ciel likes are "ABA" and "BAB".

  3. 5

    Returns: 1080

  4. 100

    Returns: 486425238

    Don't forget to compute the answer modulo 1,000,000,007.

  5. 3191

    Returns: 477311902

  6. 1195

    Returns: 415693629

  7. 3598

    Returns: 694420469

  8. 4447

    Returns: 166792782

  9. 2405

    Returns: 34763156

  10. 473

    Returns: 771804371

  11. 711

    Returns: 910150327

  12. 3759

    Returns: 61085728

  13. 169

    Returns: 663012902

  14. 3917

    Returns: 792736292

  15. 3884

    Returns: 110146779

  16. 4340

    Returns: 414751319

  17. 366

    Returns: 938673199

  18. 3243

    Returns: 51441247

  19. 4653

    Returns: 636380797

  20. 3342

    Returns: 635855870

  21. 1421

    Returns: 748553225

  22. 1199

    Returns: 394674964

  23. 648

    Returns: 438229851

  24. 2978

    Returns: 947968116

  25. 1580

    Returns: 94684227

  26. 2760

    Returns: 616683832

  27. 425

    Returns: 857241236

  28. 2323

    Returns: 669849620

  29. 1190

    Returns: 908279709

  30. 1987

    Returns: 684968795

  31. 3145

    Returns: 950916420

  32. 1692

    Returns: 437681153

  33. 4478

    Returns: 332049822

  34. 4685

    Returns: 408254962

  35. 3173

    Returns: 562388870

  36. 917

    Returns: 44800774

  37. 4688

    Returns: 514853619

  38. 2260

    Returns: 882308373

  39. 3127

    Returns: 127544401

  40. 3676

    Returns: 412905868

  41. 4900

    Returns: 926450454

  42. 1274

    Returns: 535674465

  43. 3058

    Returns: 115595080

  44. 3451

    Returns: 944725183

  45. 5000

    Returns: 171920954

  46. 4999

    Returns: 794234900

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.
This problem was used for: