Search

Interview

Time limit2sMemory limit1024 MB

Summary

Given a string of L and R moves with unknown positive integer lengths from coordinate 0, decide whether the final position can be x.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Newt Salamander lost one of his creatures and urgently needs to find it. Luckily, he knows where it went. Somehow it was moved into a one-dimensional space, and now it walks back and forth along the number line, hoping to find an exit there. Newt also learned that right after the move the creature was at coordinate 0, and that in the new space it can only move by integer steps.

The salamander can track the creature's moves with GPS. However, because the spatial metrics are distorted, only the direction of each move is shown correctly, as left or right. The length is unknown, but it is definitely nonzero. Given the full list of moves, Newt wants to know whether the creature could be at coordinate $x$ , where the exit is, after all of them.

Input

The first line contains a string $s$ describing the creature's moves. It consists only of the characters 'L' and 'R', meaning a move to the left and a move to the right ( $1 \le |s| \le 10^5$ ). The second line contains the coordinate $x$ that the salamander wants to check ( $-10^5 \le x \le 10^5$ ).

Output

Print "YES" if the creature could be at coordinate $x$ after all moves, and "NO" otherwise.

Hint

In the first case, the moves could have been, for example, 0 -> -1 -> -2 -> 3 -> 2.

In the second case, the creature had to make a move of at least 1 cell to the right, so it could not have been at coordinate 0.

Examples2

Example 1
Input
```
LLRL
2
```
Expected output
```
YES
```
Example 2
Input
```
R
0
```
Expected output
```
NO
```