Takahashi's Double-Halve Game

You are given an integer \(X\) and a string \(S\). The string \(S\) represents a series of operations that should be applied to \(X\). For each character in \(S\):

• If the character is d, multiply \(X\) by 2.
• If the character is h, perform an integer division of \(X\) by 2 (i.e. floor division).

Your task is to compute the final value of \(X\) after performing all operations.

Note: If \(S\) is empty, the value of \(X\) remains unchanged.

inputFormat

The input is given from stdin in the following format:

X
S

Where:

• \(X\) is an integer representing the initial number.
• \(S\) is a string consisting of characters 'd' and 'h'. This string may be empty.

outputFormat

Output to stdout the final value of \(X\) after all operations are applied.

## sample

3
dhd

6