solution

Trong giai đoạn sinh mã và thông dịch, nhiều trình biên dịch chuyển biểu thức nguồn về dạng lệnh cho một máy xếp chồng (stack machine) rồi thông dịch trực tiếp thay vì sinh mã máy.

Cho một chương trình gồm $n$ lệnh, mỗi lệnh thuộc một trong các dạng sau:

• PUSH x: đẩy số nguyên $x$ ($-10^9 \le x \le 10^9$) vào đỉnh ngăn xếp.
• ADD, SUB, MUL: lấy ra hai phần tử trên cùng — gọi $b$ là phần tử ở đỉnh, $a$ là phần tử ngay dưới đỉnh (đã lấy ra khỏi ngăn xếp) — rồi đẩy lại kết quả tương ứng $a+b$, $a-b$ hoặc $a \cdot b$.
• DUP: nhân đôi phần tử ở đỉnh (đẩy thêm một bản sao của nó).
• POP: bỏ phần tử ở đỉnh.

Để tránh tràn số, mọi giá trị trong ngăn xếp và mọi kết quả trung gian đều được lấy theo modulo $M = 10^9 + 7$ và luôn được biểu diễn ở dạng không âm trong $[0, M)$ (kể cả khi vừa PUSH một số âm, phải quy về modulo ngay).

Nếu tại một lệnh nào đó, ngăn xếp không đủ phần tử để thực hiện (ví dụ POP khi ngăn xếp rỗng, hoặc ADD/SUB/MUL khi ngăn xếp có ít hơn 2 phần tử, hoặc DUP khi ngăn xếp rỗng), chương trình được coi là không hợp lệ: dừng thực hiện ngay lập tức tại đó (bỏ qua toàn bộ các lệnh còn lại).

Ví dụ: với chương trình

PUSH 3
PUSH 4
ADD
PUSH 2
MUL

ta có $(3+4)\times 2 = 14$, ngăn xếp cuối cùng chỉ còn một phần tử là $14$.