Giá trị của dãy ngoặc

Xem PDF

Điểm: 400 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Người ta định nghĩa một dãy ngoặc đúng như sau:

  • Xâu rỗng là một dãy ngoặc đúng.
  • Nếu A là dãy ngoặc đúng thì (A); [A]; {A} cũng là một dãy ngoặc đúng
  • Nếu A, B là những dãy ngoặc đúng thì AB cũng là dãy ngoặc đúng.

Những dãy ngoặc sau được xem là đúng:

- [](())
- ({[]})
- ()[{()[]}]

Những dãy ngoặc sau thì không:

- )(
- ((([]))
- ){}[]{

Bạn được huyhau6a2 cho 1 dãy ngoặc hợp lệ và 3 số \(a, b, c\). huyhau6a2 đã quy ước giá trị của dãy ngoặc như sau:

  • Xâu rỗng có giá trị là \(0\)
  • () có giá trị là \(a\); [] có giá trị là \(b\); {} có giá trị là \(c\)
  • Nếu A là dãy ngoặc có giá trị là \(x\) thì (A) có giá trị là \(x.a\); [A] có giá trị là \(x.b\); {A} có giá trị là \(x.c\)
  • Nếu A, B là dãy ngoặc có giá trị lần lượt là \(x\)\(y\) thì AB có giá trị là \(x+y\)

Yêu cầu: Hãy tính giá trị của dãy ngoặc mà huyhau6a2 đã cho sau khi mod \(10^9+7\)

Input

  • Dòng 1 nhập số \(t\) chỉ số test \((t \le 100)\)
  • \(t\) block tiếp theo, mỗi block có dạng như sau:
  • Dòng 1 nhập vào dãy ngoặc huyhau6a2 đã cho có độ dài không quá \(10^5\)
  • Dòng 2 nhập vào 3 số \(a, b, c(|a|, |b|, |c|\le 10^9)\)

Output

  • Mỗi dòng xuất ra kết quả theo yêu cầu của bài toán tương ứng với từng test

Example

Test 1

Input
2
([{}])
2 3 4
[]{()}
1 -14 7
Output
24
1000000000
Note

Trong test 1:

- {} có giá trị là $4$
- [{}] có giá trị là $3.4=12$
- ([{}]) có giá trị là $2.12=24$
- $24$ $mod$ $10^9+7=24$

Trong test 2:

- [] có giá trị là $-14$
- () có giá trị là $1$
- {()} có giá trị là $7.1=7$
- []{()} có giá trị là $-14+7=-7$
- $-7$ $mod$ $10^9+7=1000000000$

Bình luận


  • 1
    huyhau6a2    6:10 p.m. 16 Tháng 5, 2022

    ai thắc mắc gì về test không?


    • 3
      dang7rickroll    10:03 p.m. 16 Tháng 5, 2022

      có ai hiểu đề nói gì đâu mà thắc mắc :))


      • 2
        huyhau6a2    7:19 a.m. 17 Tháng 5, 2022

        từ đoạn nào?