Background

Description

有一个 1 维的扫雷游戏，每个格子用 * 表示有雷，用 0/1/2 表示无雷并且相邻格子中有 0/1/2 个雷。
给定一个仅包含?、* 、0、1、2 的字符串 s，问有多少种方法将所有的?改为*/0/1/2 使其合法。

Format

Input

一行一个字符串 s。

Output

一行一个整数表示答案，对 10^9+7 取模。

Sample

Input

?1?

Output

2

Limitation

对于 30%的数据，|S|<=20。
对于 60%的数据，|S|<=1000。
对于 100%的数据，|S|<=10^6。
1s, 128000KiB for each test case.

Hint

Source

CDQZ TEST