Statistics

Problem Statement for "TheFourSquares"

Problem Statement

Manao has a rectangular board of height n and width m. He is trying to put four squares in the corners of the board in such a way that:
  • Each square is aligned to the sides of the board and exactly one of its vertices coincides with a vertex of the board.
  • The length of the side of each of the squares is a positive integer.
  • No pair of squares intersects. Note that some pairs of squares may touch each other.

Manao is interested in how many ways can he choose the lengths of the sides for his squares. More precisely, he is interested in the number of quadruples (a, b, c, d) such that if the square in the top-left corner of the board has side length a, the square in the bottom-left corner has side length b, the square in the top-right corner has side length c and the square in the bottom-right corner has side length d, they do not intersect.

You are given the ints n and m. Compute and return the number of valid quadruples modulo 1,000,000,009.

Definition

Class:
TheFourSquares
Method:
countPlacements
Parameters:
int, int
Returns:
int
Method signature:
int countPlacements(int n, int m)
(be sure your method is public)

Constraints

  • n will be between 2 and 1,000,000, inclusive.
  • m will be between 2 and 1,000,000, inclusive.

Examples

  1. 2

    2

    Returns: 1

    The only valid quadruple is (1, 1, 1, 1).

  2. 3

    3

    Returns: 5

    The five valid quadruples are: (1, 1, 1, 1). (1, 1, 1, 2). (1, 1, 2, 1). (1, 2, 1, 1). (2, 1, 1, 1).

  3. 3

    4

    Returns: 9

    In addition to the five quadruples from the previous sample, there are four new quadruples here: (1, 2, 1, 2). (1, 2, 2, 1). (2, 1, 1, 2). (2, 1, 2, 1).

  4. 10

    7

    Returns: 421

  5. 123456

    987654

    Returns: 136415012

  6. 1000000

    1000000

    Returns: 260122732

  7. 1000000

    999999

    Returns: 93122718

  8. 999999

    1000000

    Returns: 93122718

  9. 999999

    999999

    Returns: 758109197

  10. 2

    1000000

    Returns: 1

  11. 989782

    1000000

    Returns: 914669749

  12. 739798

    669212

    Returns: 311761403

  13. 292586

    424235

    Returns: 307328095

  14. 805115

    938417

    Returns: 822799866

  15. 384500

    259574

    Returns: 375888347

  16. 356807

    796049

    Returns: 290933291

  17. 260731

    777351

    Returns: 434922109

  18. 109230

    690343

    Returns: 845965649

  19. 586570

    163882

    Returns: 389920628

  20. 57710

    949982

    Returns: 718492866

  21. 61923

    217062

    Returns: 626354668

  22. 106493

    909559

    Returns: 603935003

  23. 417580

    781770

    Returns: 14636816

  24. 97278

    301791

    Returns: 844654655

  25. 199923

    179248

    Returns: 490242682

  26. 788621

    549059

    Returns: 28850380

  27. 417438

    359410

    Returns: 335668543

  28. 448742

    797672

    Returns: 832492533

  29. 542729

    440909

    Returns: 655163055

  30. 821554

    551577

    Returns: 827594240

  31. 28734

    632885

    Returns: 797067487

  32. 281345

    106952

    Returns: 835197208

  33. 194181

    142686

    Returns: 949365357

  34. 578515

    115113

    Returns: 914743886

  35. 60804

    565419

    Returns: 104572100

  36. 696888

    508387

    Returns: 800669939

  37. 483692

    424084

    Returns: 833708597

  38. 992554

    712067

    Returns: 89878021

  39. 706108

    983116

    Returns: 356388798

  40. 964869

    535314

    Returns: 229267154

  41. 291492

    193513

    Returns: 424105565

  42. 722130

    384820

    Returns: 485933304

  43. 237812

    644351

    Returns: 939244589

  44. 447623

    477308

    Returns: 807142952

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: