Via là một học sinh xuất sắc chuẩn bị dự thi VOI 2024. Ngày qua ngày cậu vẫn chăm chỉ luyện đề cho đến một ngày cậu gặp một bài toán về xâu chưa giải quyết được nên muốn nhờ các bạn học sinh chuyên Tin giải quyết giúp cậu.

Đề bài cho Via một xâu ~S~ có độ dài ~n~. Ta quy ước một xâu được gọi là palindrome nếu xâu đó đối xứng (Tức là khi viết xâu đó từ phải sang trái cũng trùng với viết xâu đó từ trái sang phải).

Với ~i < j~ ta gọi mảng ~cp[i][j]~ là tổng số cặp ~u,v~ thỏa mãn:

• ~i \leq u < v \leq j~

• Xâu ~S[i...u]+S[v...j]~ là một palindrome

• Nếu không tồn tại ~u,v~ thì ~cp[i][j]=0~

Quy ước:

• ~S[a...b]~ là xâu ~S[a]S[a+1]...S[b]~

• "+" là phép nối hai xâu

Gọi ~sum~ là tổng của ~cp[i][j]~ với tất cả các cặp ~i,j (i\leq j)~. Hãy tính ~sum~.

Input

Dữ liệu vào từ file văn bản vastr.inp:

• Dòng đầu tiên chứa số nguyên ~n~.

• Dòng thứ hai chứa một xâu ~S~ chứa ~n~ kí tự in thường.

Output

In ra file văn bản vastr.out một số nguyên duy nhất là giá trị của ~sum~.

Scoring

Sample Input 1

5
abacc

Sample Output 1

4

Sample Input 2

6
baaabc

Sample Output 2

15

Notes

Với test ví dụ ~1~, ta có:

• ~cp[1][3]=3~

• ~cp[4][5]=1~

• Còn lại tất cả đều bằng 0.

Nên đáp án là ~3+1=4~.

Vì đạt được thành tích cao trong kỳ thi HSGQG vừa qua, bố mẹ Via quyết định tặng cậu ~n~ bộ đồ chơi xếp hình được đánh số từ ~1~ đến ~n~. Bộ đồ chơi thứ ~i~ bao gồm ~a_i~ ký tự ~A~ và ~b_i~ ký tự ~B~. Via đưa ra một trò chơi như sau:

Đầu tiên Via sẽ chọn ra 2 bộ đồ chơi xếp hình trong ~n~ bộ, nhóm các ký tự ~A~ và ký tự ~B~ của 2 bộ đã chọn rồi xếp chúng thành một hàng ngang. Ví dụ là có 3 chữ cái ~A~ và 4 chữ cái ~B~ thì ~ABABABB~ và ~BBBBAAA~ là một trong các cách xếp hợp lệ, và ~AAAABBB~ là một trong các cách xếp không hợp lệ.

Via muốn biết: có bao nhiêu cách chọn bộ và xếp chữ như vậy? Hai cách là khác nhau khi hai bộ xếp chữ được chọn ở hai cách là khác nhau, hoặc cách xếp nhận được là khác nhau.

Vì số cách chọn và xếp có thể rất lớn, bạn hãy in ra số cách tìm được chia lấy dư cho ~10^9 + 7~.

Input

Dữ liệu vào từ file văn bản ordletter.inp:

Dòng đầu tiên chứa số nguyên dương ~n~ — là số bộ đồ chơi mà Via được tặng (~2 \le n \le 2 \cdot 10^5~).

~n~ dòng tiếp theo, gồm hai số nguyên ~a_i~ và ~b_i~ — lần lượt là số ký tự ~A~ và số ký tự ~B~ của bộ đồ chơi thứ ~i~ (~1 \le a_i, b_i \le 2000~).

Output

In ra file văn bản ordletter.out một số nguyên duy nhất là số cách chọn bộ và xếp chữ tìm được, modulo ~10^9 + 7~.

Scoring

Sample Input 1

2
1 1
2 1

Sample Output 1

10

Cho một cây có trọng số gồm ~n~ đỉnh. Giá trị của một đường đi được tính bằng tổng XOR của trọng số các cạnh trên đường đi. Tìm giá trị lớn nhất có thể của một đường đi đơn~^\dagger~ trên cây sau khi thêm đúng một cạnh có trọng số nằm trong đoạn ~[l, r]~ nối giữa hai đỉnh bất kỳ trên cây.

~^\dagger~Đường đi đơn là đường đi có các đỉnh đôi một phân biệt.

Input

Dữ liệu vào từ file văn bản xtree.inp:

Dòng đầu tiên gồm một số nguyên ~n, l, r~ (~1 \le n \le 700~; ~0 \le l \le r < 2^{63}~) — số đỉnh của cây và giới hạn trọng số cạnh được thêm vào.

Mỗi dòng trong ~n - 1~ dòng tiếp theo gồm ba số nguyên ~u,v,w~ (~1 \le u, v \le n~; ~0 \le w < 2^{63}~) — thể hiện một cạnh nối ~u~ và ~v~ với trọng số ~w~ trên cây.

Output

In ra file văn bản xtree.out giá trị lớn nhất có thể của một đường đi đơn sau khi thêm một cạnh.

Scoring

Sample Input 1

4 1 10
1 2 1
2 3 2
3 4 3

Sample Output 1

11

Notes

Ở test ví dụ, ta thêm một cạnh với trọng số ~9~ nối hai đỉnh ~3~ và ~4~, ta được đường đi ~2\rightarrow 3\rightarrow 4~ có giá trị bằng ~2\oplus 9=11~.