Statistics

Problem Statement for "PairsOfStrings"

Problem Statement

We are interested in pairs of strings (A, B) that satisfy the following conditions:
  • A and B consist of exactly n characters each.
  • Each character in A and B is one of the first k lowercase letters of the English alphabet.
  • There exists a string C such that A + C = C + B. Here, + denotes string concatenation.
For example, if n = 3 and k = 4 then one valid pair of strings is ("aad", "daa"): both strings have length 3, only the first 4 letters are used in each of them, and C = "aa" shows that the third condition is satisfied as well.

You are given the ints n and k. Find the number of such pairs of strings, and return the number modulo 1,000,000,007.

Definition

Class:
PairsOfStrings
Method:
getNumber
Parameters:
int, int
Returns:
int
Method signature:
int getNumber(int n, int k)
(be sure your method is public)

Constraints

  • n will be between 1 and 1,000,000,000, inclusive.
  • k will be between 1 and 26, inclusive.

Examples

  1. 2

    2

    Returns: 6

    The following 6 pairs satisfy the conditions: ("aa", "aa"), ("ab", "ab"), ("ab", "ba"), ("ba", "ab"), ("ba", "ba"), ("bb", "bb").

  2. 3

    2

    Returns: 20

  3. 3

    4

    Returns: 184

  4. 6

    2

    Returns: 348

  5. 100

    26

    Returns: 46519912

  6. 17222625

    19

    Returns: 735966134

  7. 1

    1

    Returns: 1

  8. 1

    26

    Returns: 26

  9. 1000000000

    1

    Returns: 1

  10. 1000000000

    26

    Returns: 985305715

  11. 4

    26

    Returns: 1826526

  12. 5

    4

    Returns: 5104

  13. 6

    6

    Returns: 279156

  14. 7

    12

    Returns: 250822584

  15. 8

    2

    Returns: 1974

  16. 9

    22

    Returns: 422820141

  17. 10

    6

    Returns: 604622616

  18. 223092870

    11

    Returns: 466864729

  19. 536870912

    20

    Returns: 941385833

  20. 931170240

    2

    Returns: 527771224

  21. 994593600

    10

    Returns: 748471925

  22. 821620800

    10

    Returns: 505003468

  23. 735134400

    7

    Returns: 584595209

  24. 423259200

    2

    Returns: 905168182

  25. 810810000

    26

    Returns: 242009274

  26. 761866560

    15

    Returns: 279736057

  27. 892371480

    22

    Returns: 729759571

  28. 771891120

    25

    Returns: 994737411

  29. 712514880

    14

    Returns: 773485607

  30. 918918000

    16

    Returns: 734942331

  31. 614839680

    14

    Returns: 454574033

  32. 726818400

    10

    Returns: 644537914

  33. 520248960

    19

    Returns: 56012507

  34. 701719200

    12

    Returns: 211276037

  35. 367567200

    17

    Returns: 510812738

  36. 867081600

    21

    Returns: 853927699

  37. 846518400

    13

    Returns: 311496417

  38. 665121600

    19

    Returns: 804773476

  39. 726818400

    19

    Returns: 737879210

  40. 504504000

    5

    Returns: 857830939

  41. 383423040

    13

    Returns: 175855821

  42. 973304640

    15

    Returns: 763065207

  43. 933055200

    13

    Returns: 451878864

  44. 7777648

    14

    Returns: 876973114

  45. 7777664

    20

    Returns: 465252281

  46. 7777672

    2

    Returns: 655962421

  47. 7777680

    25

    Returns: 884856317

  48. 7777692

    25

    Returns: 102655972

  49. 7777701

    7

    Returns: 178179588

  50. 7777704

    9

    Returns: 286971495

  51. 7777710

    11

    Returns: 841368299

  52. 7777712

    17

    Returns: 282969779

  53. 7777728

    20

    Returns: 3756897

  54. 7777734

    16

    Returns: 330367137

  55. 7777749

    3

    Returns: 792200831

  56. 7777752

    25

    Returns: 22971734

  57. 7777755

    2

    Returns: 2020037

  58. 7777760

    12

    Returns: 505698493

  59. 7777764

    10

    Returns: 390443358

  60. 7777768

    7

    Returns: 533996426

  61. 7777769

    20

    Returns: 758045909

  62. 7777770

    17

    Returns: 772935583

  63. 7777772

    5

    Returns: 617164531

  64. 7777773

    26

    Returns: 850737529

  65. 7777774

    6

    Returns: 953412326

  66. 7777775

    4

    Returns: 572779519

  67. 7777776

    13

    Returns: 864607934

  68. 7777777

    19

    Returns: 399049770

  69. 999999888

    7

    Returns: 203603854

  70. 999999900

    25

    Returns: 96389506

  71. 999999904

    21

    Returns: 43252664

  72. 999999918

    2

    Returns: 678059470

  73. 999999928

    13

    Returns: 354576628

  74. 999999936

    15

    Returns: 19704722

  75. 999999937

    15

    Returns: 694990426

  76. 999999960

    26

    Returns: 90304299

  77. 999999963

    13

    Returns: 578307836

  78. 999999966

    7

    Returns: 889266359

  79. 999999968

    21

    Returns: 627621985

  80. 999999972

    12

    Returns: 648822361

  81. 999999976

    23

    Returns: 890423074

  82. 999999980

    11

    Returns: 578419918

  83. 999999981

    21

    Returns: 758788190

  84. 999999982

    17

    Returns: 617107093

  85. 999999984

    19

    Returns: 14851125

  86. 999999988

    9

    Returns: 808634925

  87. 999999990

    4

    Returns: 558071600

  88. 999999991

    13

    Returns: 953508215

  89. 999999992

    4

    Returns: 668462794

  90. 999999995

    3

    Returns: 654798544

  91. 999999996

    20

    Returns: 27752797

  92. 999999998

    6

    Returns: 92594881

  93. 999999999

    10

    Returns: 108768464

  94. 735134400

    26

    Returns: 398967076

  95. 999999999

    26

    Returns: 23445054

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: