Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

E. The Last Fight Between Human and AI

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard output100 years have passed since the last victory of the man versus computer in Go. Technologies made a huge step forward and robots conquered the Earth! It's time for the final fight between human and robot that will decide the faith of the planet.

The following game was chosen for the fights: initially there is a polynomial

Polynomial *P*(*x*) is said to be divisible by polynomial *Q*(*x*) if there exists a representation *P*(*x*) = *B*(*x*)*Q*(*x*), where *B*(*x*) is also some polynomial.

Some moves have been made already and now you wonder, is it true that human can guarantee the victory if he plays optimally?

Input

The first line of the input contains two integers *n* and *k* (1 ≤ *n* ≤ 100 000, |*k*| ≤ 10 000) — the size of the polynomial and the integer *k*.

The *i*-th of the following *n* + 1 lines contain character '?' if the coefficient near *x*^{i - 1} is yet undefined or the integer value *a*_{i}, if the coefficient is already known ( - 10 000 ≤ *a*_{i} ≤ 10 000). Each of integers *a*_{i} (and even *a*_{n}) may be equal to 0.

Please note, that it's not guaranteed that you are given the position of the game where it's computer's turn to move.

Output

Print "Yes" (without quotes) if the human has winning strategy, or "No" (without quotes) otherwise.

Examples

Input

1 2

-1

?

Output

Yes

Input

2 100

-10000

0

1

Output

Yes

Input

4 5

?

1

?

1

?

Output

No

Note

In the first sample, computer set *a*_{0} to - 1 on the first move, so if human can set coefficient *a*_{1} to 0.5 and win.

In the second sample, all coefficients are already set and the resulting polynomial is divisible by *x* - 100, so the human has won.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 16:22:30 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|