Bessie đã phát minh ra một ngôn ngữ lập trình mới, nhưng vì chưa có trình biên dịch nên cô cần bạn giúp thực sự chạy các chương trình của mình.

COWBASIC là một ngôn ngữ đơn giản và tao nhã. Nó có hai tính năng chính: phép cộng và vòng lặp MOO. Bessie đã nghĩ ra một giải pháp thông minh cho vấn đề tràn số: mọi phép cộng đều được thực hiện theo modulo \(10^9+7\). Nhưng thành tựu thực sự của Bessie là vòng lặp MOO, dùng để chạy một khối mã với số lần cố định. Dĩ nhiên, các vòng lặp MOO và phép cộng có thể được lồng nhau.

Cho một chương trình COWBASIC, hãy giúp Bessie xác định số mà chương trình trả về.

Dữ liệu vào

Bạn được cho một chương trình COWBASIC dài không quá \(100\) dòng, mỗi dòng dài không quá \(350\) ký tự. Một chương trình COWBASIC là một danh sách các câu lệnh.

Có ba loại câu lệnh:

<variable> = <expression>

<literal> MOO {
  <list of statements>
}

RETURN <variable>

Có ba loại biểu thức:

<literal>

<variable>

( <expression> ) + ( <expression> )

Một <literal> là một số nguyên dương không lớn hơn \(100\,000\).

Một <variable> là một chuỗi gồm không quá \(10\) chữ cái tiếng Anh viết thường.

Dữ liệu được đảm bảo rằng không biến nào được sử dụng hoặc RETURN trước khi được định nghĩa. RETURN được đảm bảo xuất hiện đúng một lần ở dòng cuối cùng của chương trình.

Dữ liệu ra

In một số nguyên dương duy nhất là giá trị của biến được RETURN.

Phân nhóm

• Trong \(20\%\) số bộ test, các vòng lặp MOO không được lồng nhau.
• Trong \(20\%\) số bộ test khác, chương trình chỉ có \(1\) biến; các vòng lặp MOO có thể được lồng nhau.
• Trong các bộ test còn lại, không có thêm ràng buộc nào.

Ví dụ

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

1024

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

4761

Nguồn

USACO 2017 US Open Contest, Platinum — COWBASIC. Tác giả đề: Jonathan Paulson.

https://usaco.org/index.php?page=viewproblem2&cpid=746