Nếu bạn là dân chuyên tin thì chắc hẳn bạn sẽ biết cụm kí tự "orz".

Bây giờ, Bạn và hieuhfgr sẽ chơi một trò chơi: hieuhfgr sẽ cho bạn ~n~ mảnh giấy, trên mỗi mảnh giấy sẽ ghi một kí tự trong ~'o'~, ~'r'~ hoặc ~'z'~. Nhiệm vụ của bạn là xếp các mảnh giấy lại với nhau sao cho tạo thành chữ orz và phải đảm bảo vị trí của 3 mảnh giấy o, r, z đảm bảo tăng dần. Vì có quá nhiều cách nên hieuhfgr nhờ bạn đếm số cách chọn.

Input

Xâu ~s~ chỉ gồm các kí tự ~'o'~, ~'r'~ hoặc ~'z'~ (~s.length() \le 2 * 10^5~)

Output

• Gồm ~1~ dòng là số cách chọn ~3~ kí tự để ghép thành "orz"

Sample Input 1

oorrzz

Sample Output 1

8

Sample Input 2

rzozzoooor

Sample Output 2

0

Tam giác là tác giam, tác là đánh, giam là nhốt...~

Âm nhạc của Anh Phan cứ ngân nga mãi trong đầu của hieuhfgr. Đột nhiên hieuhfgr nghĩ ra một bài siêu khó nói rằng:

Cho tam giác với hai hình dạng là tam giác vuông cân 1 và tam giác vuông cân 2.

• tam giác vuông cân 1 có độ dài hai cạnh góc vuông là ~1~.
• tam giác vuông cân 2 có độ dài cạnh huyền là ~1~.

Bạn được cho số tam giác vuông cân 1 và tam giác vuông cân 2. Bạn hãy đếm xem có bao nhiêu cách để tạo được hình vuông có độ dài là 1.

Vì hieuhfgr chỉ nghe nhạc chứ không lo học nên bạn hãy giúp hieuhfgr nhé <3 :3

Input

Gồm ~1~ dòng chứa hai số nguyên không âm ~a~ ~b~ lần lượt là số lượng tam giác vuông cân 1 và tam giác vuông cân 2 ~(0 \le a, b \le 10^6)~.

Output

Ghi ra số cách tạo ra hình vuông có độ dài là 1. Kết quả lấy phần dư cho ~10^9+7~.

Sample Input 1

1 2

Sample Output 1

1

Sample Input 2

2 4

Sample Output 2

14

Sample Input 2

50 50

Sample Output 2

292775

Cho cây gồm ~n~ đỉnh. Mỗi cạnh ~u, v~ có những màu sắc khác nhau. hieuhfgr cho bạn ~q~ truy vấn, mỗi truy vấn có hai đỉnh ~u, v, x~, nhiệm vụ của bạn là tìm một lộ trình đi từ đỉnh ~u~ đến đỉnh ~v~ sao cho trên lộ trình đó là ngắn nhất và tồn tại cạnh có màu sắc là ~x~

Input

Dòng đầu là ~n~ và ~q~ tương ứng số đỉnh của cây và số truy vấn.

~n - 1~ dòng tiếp theo, mỗi dòng là ~u~ ~v~ ~c~ tượng trưng cho có cạnh nối hai đỉnh ~u~ và ~v~ và có màu là ~c~.

~q~ dòng cuối cùng gồm ~u~ ~v~ ~x~ hỏi như yêu cầu đề bài.

Output

Với mối truy vấn in ra số cạnh ít nhất để có lộ trình như đề yêu cầu. Nếu không thể tạo ra lộ trình thì in ra ~-1~

Constraints

• ~n \le 1000~
• ~q \le 200000~
• ~c \le 10^9~

Sample Input

9 5
1 2 1
2 3 2
1 4 3 
1 5 1
5 6 3
6 7 4
6 8 1
8 9 4
3 9 1
3 9 5
2 1 4
4 5 2
1 5 4

Sample Output

6
-1
7
6
5

Note

• với truy vấn ~(3, 9, 1)~, lộ trình ngắn nhất là: ~3, 2, 1, 5, 6, 8, 9~ nên đáp án là ~6~.
• với truy vấn ~(3, 9, 5)~, không tồn tại lộ trình mà trong đó có cạnh có màu sắc là ~5~.
• với truy vấn ~(2, 1, 4)~, lộ trình ngắn nhất là: ~2, 1, 5, 6, 7, 6, 5, 1~. nên đáp án là ~7~