Lost Number

Time limit3sMemory limit512 MB

Summary

Fill in up to five unreadable dots in a binary arithmetic expression with digits, operators, or parentheses so the value is maximized, respecting the given grammar.

Level: Medium7 of 10
Topics: Brute force, Implementation, Math, Recursion
Solved: No attempts yet

Problem

The year is 3xxx, and a highly advanced civilization has entered a period of stagnation. To break out of it, historians decided to study the wisdom of the past. They focused on material left behind by a genius from the dawn of computing. The material contains a formula, and they want to know its result, but unfortunately some of its characters have faded and can no longer be read. With no other option, they decided to find the largest number that the result could possibly be. The formula is written in binary, and the operations are addition, subtraction, and multiplication. Parentheses are used as well, but the inside of a parenthesis is never only digits. Precisely, the formula must satisfy the grammar defined by the following BNF.

<expression> ::= <number> | <expression> <operation> <expression>
| ( <expression> <operation> <expression> )
<number> ::= <digit> | <number> <digit>
<operation> ::= + | - | *
<digit> ::= 0 | 1

Because of the computing power limits of computers at the time, numbers are integers from 0 up to but not including 210, and they stay within this range during calculation. Parenthesized parts are evaluated first, and multiplication is done before addition and subtraction. In all other cases, evaluation proceeds from left to right.

Input

The input consists of one line, giving a single formula to decipher. The formula is between 1 and 100 characters long. At most 5 characters of a formula cannot be read and are represented by .. The characters in the given formula are among 01+-*()..

Output

Among the formulas that the original could be, find the one whose result is largest, and output that result in decimal. If no choice of characters for the unreadable positions yields a possible original formula, output -1.

Constraints

The formula is between 1 and 100 characters long
Every character except newline is among 01+-*().
The number of . is at most 5

Examples5

Example 1
Input
```
000
```
Expected output
```
0
```
Example 2
Input
```
0.0
```
Expected output
```
2
```
Example 3
Input
```
...
```
Expected output
```
7
```
Example 4
Input
```
(1.1)
```
Expected output
```
2
```
Example 5
Input
```
0-1.
```
Expected output
```
-1
```