COWBASIC

Time limit2sMemory limit512 MB

Summary

Interpret a tiny language of assignments, nested fixed-count MOO loops, and one RETURN, all additions taken modulo 10^9+7, and print the returned value.

Level: Hard8 of 10
Topics: Implementation, Simulation, Matrix, Math
Solved: No attempts yet

Problem

Bessie has invented a new programming language, but since there is no compiler yet, she needs your help to actually run her programs.

COWBASIC is a simple, elegant language. It has exactly two features: addition and MOO loops. Bessie has a clever answer to overflow: all addition is done modulo $10^9+7$ . Her real achievement is the MOO loop, which runs a block of code a fixed number of times. MOO loops and addition can, of course, be nested.

Given a COWBASIC program, determine the number it returns.

Input

The input is a COWBASIC program of at most 100 lines, each at most 350 characters long. A COWBASIC program is a list of statements.

There are three types of statements:

<variable> = <expression>

<literal> MOO {
  <list of statements>
}

RETURN <variable>

There are three types of expressions:

<literal>

<variable>

( <expression> ) + ( <expression> )

A literal is a positive integer at most 100,000.

A variable is a string of at most 10 lowercase English letters.

No variable is used or RETURNed before it is defined. RETURN happens exactly once, on the last line of the program.

Output

Print a single integer: the value of the RETURNed variable. Because all addition is done modulo $10^9+7$ , this value is at least $0$ and less than $10^9+7$ .

Hint

The COWBASIC program in the second sample computes $(10^5 \times 10^5+1)^2$ modulo $10^9+7$ .

Examples2

Example 1

Input

x = 1
10 MOO {
  x = ( x ) + ( x )
}
RETURN x

Expected output

Example 2

Input

n = 1
nsq = 1
100000 MOO {
  100000 MOO {
    nsq = ( nsq ) + ( ( n ) + ( ( n ) + ( 1 ) ) )
    n = ( n ) + ( 1 )
  }
}
RETURN nsq

Expected output