Statistics

Problem Statement for "WolfHockeyTeamEasy"

Problem Statement

The ice hockey season is almost over. Wolf Sothe and his teammates have asked Cat Snuke to take photos of their team.

There are 2*N wolves on the ice hockey team. The wolves are numbered from 0 to 2*N-1.

Cat Snuke is going to take photos of the whole team. The photos all have to look nice and they all have to look different. Both "nice" and "different" are formally defined below.

While taking each photo, the wolves will stand in a grid pattern with two rows by N columns. There is only one constraint: each row of the grid must contain a wolf whose number is K or more. Any such arrangement of wolves will look nice in a photo.

Given a photo of our 2*N wolves, we can look at it and write down a sequence of N+2 integers:
  • For each column (from the left to the right), write down the largest wolf number in that column.
  • Write down the largest wolf number in the first row.
  • Write down the largest wolf number in the second row.
Two photos are considered different if they produce different sequences.

You are given the ints N and K. Let X be the maximal number of nice and pairwise different photos Cat Snuke can take. Compute and return the value (X modulo 1,000,000,007).

Definition

Class:
WolfHockeyTeamEasy
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int N, int K)
(be sure your method is public)

Constraints

  • N will be between 1 and 1,000, inclusive.
  • K will be between 0 and 2N-1, inclusive.

Examples

  1. 2

    0

    Returns: 12

    As N=2, we have four wolves. As K=0, each row of the grid must contain a wolf numbered 0 or more, which is always true. Hence, all 24 possible arrangements of wolves produce nice photos. However, some of those arrangements produce similar photos. For example, suppose there are wolves 1 and 2 in the first row and behind them wolves 0 and 3 in the second row. For this arrangement, we have: The maximum in the first column is max(1,0) = 1. The maximum in the second column is max(2,3) = 3. The maximum in the first row is max(1,2) = 2. The maximum in the second row is max(0,3) = 3. Hence, this arrangement produces the sequence {1,3,2,3}. Now suppose there are wolves 0 and 2 in the first row and wolves 1 and 3 in the second row. This is a different arrangement but it produces the same sequence: {1,3,2,3}. In total, Cat Snuke will be able to take at most 12 different photos. These correspond to the sequences {1,3,2,3}, {1,3,3,2}, {2,3,1,3}, {2,3,2,3}, {2,3,3,1}, {2,3,3,2}, {3,1,2,3}, {3,1,3,2}, {3,2,1,3}, {3,2,2,3}, {3,2,3,1}, and {3,2,3,2}.

  2. 4

    5

    Returns: 1104

  3. 100

    120

    Returns: 803057135

  4. 234

    467

    Returns: 0

    Note that in this example K = 2*N-1. There is only one wolf with the number 2*N-1 or greater. Thus, in this case there are no nice photos: in one of the rows all wolves will always have numbers smaller than K.

  5. 810

    893

    Returns: 281618909

  6. 1

    0

    Returns: 2

  7. 1

    1

    Returns: 0

  8. 2

    1

    Returns: 12

  9. 2

    2

    Returns: 8

  10. 2

    3

    Returns: 0

  11. 3

    0

    Returns: 108

  12. 3

    1

    Returns: 108

  13. 3

    2

    Returns: 108

  14. 3

    3

    Returns: 96

  15. 3

    4

    Returns: 60

  16. 3

    5

    Returns: 0

  17. 1000

    0

    Returns: 989983873

  18. 234

    234

    Returns: 498647752

  19. 252

    251

    Returns: 767991859

  20. 250

    498

    Returns: 275681708

  21. 250

    499

    Returns: 0

  22. 999

    1520

    Returns: 815303675

  23. 1000

    0

    Returns: 989983873

  24. 1000

    1

    Returns: 989983873

  25. 1000

    999

    Returns: 989983873

  26. 1000

    1000

    Returns: 707144464

  27. 1000

    1001

    Returns: 867737445

  28. 1000

    1997

    Returns: 339184346

  29. 1000

    1998

    Returns: 104654612

  30. 1000

    1999

    Returns: 0

  31. 808

    873

    Returns: 324836167

  32. 74

    106

    Returns: 116516315

  33. 931

    1343

    Returns: 939478731

  34. 545

    948

    Returns: 896462378

  35. 924

    1093

    Returns: 783550990

  36. 441

    548

    Returns: 167512440

  37. 493

    693

    Returns: 207060943

  38. 988

    1547

    Returns: 626340796

  39. 328

    529

    Returns: 756345816

  40. 841

    1573

    Returns: 186152321

  41. 304

    577

    Returns: 86944046

  42. 710

    957

    Returns: 952029454

  43. 561

    834

    Returns: 492932675

  44. 100

    178

    Returns: 724434430

  45. 817

    1426

    Returns: 24066527

  46. 98

    164

    Returns: 327459111

  47. 513

    784

    Returns: 43090941

  48. 811

    1038

    Returns: 937724202

  49. 980

    1709

    Returns: 905178339

  50. 580

    941

    Returns: 558471503

  51. 968

    1056

    Returns: 622356681

  52. 394

    570

    Returns: 643181350

  53. 486

    695

    Returns: 333558913

  54. 229

    400

    Returns: 463685866

  55. 195

    367

    Returns: 775627118

  56. 2

    3

    Returns: 0

  57. 709

    1295

    Returns: 730053457

  58. 669

    1025

    Returns: 304499932

  59. 125

    196

    Returns: 492133

  60. 531

    949

    Returns: 1483601

  61. 100

    100

    Returns: 192185424

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: