Statistics

Problem Statement for "Chimney"

Problem Statement

A construction worker was assigned the task to build a chimney. The chimney consists of N layers of 4 bricks each. Each layer, when looked at from above, looks like this: 

  Layer 1      Layer 2
+-----+--+   +--+-----+
|  1  |  |   |  |  B  |
+--+--|2 |   | A+--+--+
|  |  |  |   |  |  |  |
| 4+--+--+   +--+--+C |
|  |  3  |   |  D  |  |
+--+-----+   +-----+--+

Each layer, except the bottommost one, is placed on top of the previous such that the borders coincide perfectly and each brick is placed on top of exactly two bricks from the layer below. In the example above, brick A is placed on top of bricks 1 and 4, brick B on top of bricks 1 and 2, C on top of 2 and 3 and D on top of 3 and 4.

A brick in a given layer can only be placed after both bricks below have already been placed. Of course, bricks on the bottommost layer have no such restrictions. There are many orders in which bricks can be placed. For instance, if only 1 layer is to be placed, there are 4! = 24 possible orders, because any order of the bricks is valid. However, when more layers are used, not every order of the total number of bricks is valid.

You will be given the total number of layers n. Return the number of orders in which bricks can be placed, modulo 1000000007.

Definition

Class:
Chimney
Method:
countWays
Parameters:
long
Returns:
int
Method signature:
int countWays(long n)
(be sure your method is public)

Constraints

  • n will be between 1 and 1000000000000000000 (10^18), inclusive.

Examples

  1. 1

    Returns: 24

    There are 4! = 4*3*2*1 = 24 ways of placing 4 bricks without dependencies.

  2. 2

    Returns: 1088

  3. 5

    Returns: 110198784

  4. 6

    Returns: 138284509

  5. 100000

    Returns: 19900327

  6. 1000000000000000000

    Returns: 364019862

  7. 3

    Returns: 50688

  8. 4

    Returns: 2363392

  9. 7

    Returns: 584934263

  10. 8

    Returns: 226635915

  11. 9

    Returns: 442731277

  12. 10

    Returns: 746402694

  13. 11

    Returns: 492527535

  14. 12

    Returns: 871549439

  15. 13

    Returns: 312610762

  16. 14

    Returns: 226152767

  17. 15

    Returns: 848244118

  18. 16

    Returns: 241940394

  19. 17

    Returns: 325515661

  20. 18

    Returns: 140566512

  21. 19

    Returns: 914190377

  22. 20

    Returns: 884881090

  23. 1000000000000000000

    Returns: 364019862

  24. 999999999999999999

    Returns: 764053755

  25. 999999999999999998

    Returns: 723602507

  26. 999999999999999997

    Returns: 483888540

  27. 999999999999999996

    Returns: 804735119

  28. 999999999999999995

    Returns: 908490583

  29. 999999999999999994

    Returns: 809418952

  30. 999999999999999993

    Returns: 358494047

  31. 999999999999999992

    Returns: 381223365

  32. 999999999999999991

    Returns: 670941057

  33. 200

    Returns: 787171472

  34. 108

    Returns: 572366251

  35. 193

    Returns: 944617417

  36. 184

    Returns: 17073931

  37. 135

    Returns: 539481840

  38. 1274

    Returns: 49395495

  39. 1904

    Returns: 522479802

  40. 1412

    Returns: 651819626

  41. 1546

    Returns: 21767390

  42. 1768

    Returns: 405449637

  43. 8054473

    Returns: 212209620

  44. 2101872

    Returns: 648015706

  45. 2806429

    Returns: 625206793

  46. 10133628

    Returns: 687213396

  47. 15294943

    Returns: 326487321

  48. 1000002803

    Returns: 303972920

  49. 1000000276

    Returns: 24167289

  50. 1000004460

    Returns: 362967943

  51. 1000008951

    Returns: 392371903

  52. 1000005498

    Returns: 16978199

  53. 1000007365

    Returns: 635815387

  54. 1000002325

    Returns: 368755323

  55. 1000006901

    Returns: 721209271

  56. 1000001069

    Returns: 448591518

  57. 1000009153

    Returns: 285293220

  58. 361

    Returns: 897412922

  59. 6859

    Returns: 990317770

  60. 130321

    Returns: 908867540

  61. 2476099

    Returns: 991604202

  62. 47045881

    Returns: 965339545

  63. 893871739

    Returns: 391942709

  64. 16983563041

    Returns: 417250699

  65. 322687697779

    Returns: 878866403

  66. 6131066257801

    Returns: 532681067

  67. 116490258898219

    Returns: 283174963

  68. 2213314919066161

    Returns: 578195950

  69. 42052983462257059

    Returns: 786673968

  70. 799006685782884121

    Returns: 987474155

  71. 576460752303423487

    Returns: 946324257

  72. 288230376151711743

    Returns: 910557164

  73. 144115188075855871

    Returns: 558974186

  74. 450283905890997362

    Returns: 625809992

  75. 150094635296999120

    Returns: 899843099

  76. 50031545098999706

    Returns: 24613994

  77. 298023223876953124

    Returns: 824133018

  78. 59604644775390624

    Returns: 838840981

  79. 11920928955078124

    Returns: 93771289

  80. 558545864083284006

    Returns: 628140868

  81. 79792266297612000

    Returns: 321969494

  82. 11398895185373142

    Returns: 583306028

  83. 505447028499293770

    Returns: 93328307

  84. 45949729863572160

    Returns: 846195883

  85. 4177248169415650

    Returns: 52608353

  86. 665416609183179840

    Returns: 287865304

  87. 51185893014090756

    Returns: 825266957

  88. 3937376385699288

    Returns: 412854001

  89. 999999999999999987

    Returns: 727912045

  90. 590345035376309527

    Returns: 86035942

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: