Cho một xâu gồm ~n~ ký tự từ a đến z.

Mỗi lượt, bạn có thể xóa hai ký tự liền kề bất kỳ bằng nhau. Mục tiêu của bạn là tạo ra một xâu rỗng bằng cách xóa tất cả các ký tự.

Hỏi có bao nhiêu cách thực hiện?

Dữ liệu vào

Dòng duy nhất chứa một xâu có độ dài ~n~.

Kết quả

In ra một số nguyên: số cách modulo ~10^9+7~.

Giới hạn

• ~1 \le n \le 500~

Ví dụ

Input:

aabccb

Output:

3