Statistics

Problem Statement for "WolfHockeyTeamHard"

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:
WolfHockeyTeamHard
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 500,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

    78

    Returns: 68021677

  4. 2100

    4199

    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. 81019

    114514

    Returns: 793441075

  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

    1

    Returns: 108

  12. 3

    2

    Returns: 108

  13. 3

    3

    Returns: 96

  14. 3

    4

    Returns: 60

  15. 3

    5

    Returns: 0

  16. 10

    10

    Returns: 739364272

  17. 114514

    114514

    Returns: 794296286

  18. 114514

    229026

    Returns: 787063714

  19. 500000

    0

    Returns: 524968858

  20. 500000

    1

    Returns: 524968858

  21. 500000

    2

    Returns: 524968858

  22. 500000

    500000

    Returns: 216117500

  23. 500000

    499999

    Returns: 524968858

  24. 500000

    500001

    Returns: 538198482

  25. 500000

    632131

    Returns: 747186601

  26. 500000

    750000

    Returns: 495441943

  27. 500000

    987654

    Returns: 507458229

  28. 500000

    999998

    Returns: 38064985

  29. 500000

    999999

    Returns: 0

  30. 16808

    16809

    Returns: 143294401

  31. 150074

    158070

    Returns: 318530708

  32. 108931

    174007

    Returns: 903290134

  33. 27545

    31753

    Returns: 536751283

  34. 277924

    348505

    Returns: 753762585

  35. 64441

    93337

    Returns: 444812108

  36. 484493

    600106

    Returns: 615845463

  37. 307988

    430807

    Returns: 917193613

  38. 282328

    439033

    Returns: 698666939

  39. 378841

    719555

    Returns: 523539348

  40. 44304

    85921

    Returns: 820636592

  41. 317710

    336677

    Returns: 735225873

  42. 129561

    244281

    Returns: 509638366

  43. 493100

    917678

    Returns: 896445047

  44. 351817

    370392

    Returns: 171010077

  45. 399098

    506026

    Returns: 242590045

  46. 113513

    221619

    Returns: 903626826

  47. 223811

    320605

    Returns: 937348439

  48. 80980

    82309

    Returns: 330753959

  49. 236580

    296121

    Returns: 972534079

  50. 11968

    16368

    Returns: 862364418

  51. 401394

    602910

    Returns: 213975419

  52. 125486

    238133

    Returns: 534412985

  53. 425229

    821377

    Returns: 681844034

  54. 140195

    263172

    Returns: 502049885

  55. 35002

    47535

    Returns: 838926145

  56. 116709

    160531

    Returns: 140765997

  57. 15669

    20579

    Returns: 731583093

  58. 288125

    434071

    Returns: 786384254

  59. 9531

    10408

    Returns: 924435849

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: