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\) và \(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

2
([{}])
2 3 4
[]{()}
1 -14 7

24
1000000000

- {} 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$