Under construction

Still being built. Things may change

Construction of Chand Baori

Time limit1sMemory limit1024 MB

Summary
Count the descent routes along one face of an N-level stepped well and report whether that count is below the pilgrim number M.
Level

Medium5 of 10

Topics
Dynamic programming, Math
Solved
No attempts yet

Problem

The Indian stepped well Chand Baori is, with some simplifications, a pyramid tapering down. The faces of the pyramid are made up of rows of trapezoid stairs, which can be used to descend to the water. The first (lowest) level is a single stairway with two flights of stairs, one on the left and one on the right. The second level has two such stairways, and so on.

To visit the "Harshat Mata" shrine, dedicated to the goddess of happiness and joy, pilgrims need to cleanse themselves in the waters of the well. That means descending to the very bottom. Pilgrims on their way to the water can only descend or walk horizontally along the current level. They cannot climb up.

The builders of the well want the number of possible ways to descend to be no less than the number of pilgrims. Two paths are different if there is a level with a different stairway used for descending, or if the same stairway is used with a different flight.

Input

The first line contains two integers NN and MM, the number of levels in the well and the number of pilgrims descending along a single face, respectively (1≤N≤201 \le N \le 20, 0≤M≤1.5⋅10180 \le M \le 1.5 \cdot 10^{18}).

Output

The output must contain "Harshat Mata" if the number of possible ways to descend along one face of the well is less than the given number of pilgrims (also for one face). Otherwise, the output must contain "Nope".

Hint

For a two-level well there are eight different ways of descent, shown in the picture. Parts of the same route are marked with the same digit.

Examples4

  1. Example 1

    Input
    1 2
    
    Expected output
    Harshat Mata
    
  2. Example 2

    Input
    1 3
    
    Expected output
    Nope
    
  3. Example 3

    Input
    2 9
    
    Expected output
    Nope
    
  4. Example 4

    Input
    2 8
    
    Expected output
    Harshat Mata