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

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

Bạn có thể làm điều này bằng bao nhiêu cách?

Input

• Một dòng duy nhất chứa một xâu độ dài \(n\).

Output

• Một số nguyên: số cách thực hiện chia lấy dư cho \(10^9 + 7\).

Constraints

• \(1 \leq n \leq 500\)

Example

Sample input

aabccb

Sample output

3