Time limit: 2.0s , Memory limit: 256M , Points: 3000 (partial)
Xâu ngoặc cân bằng được định nghĩa như sau:
- Chỉ gồm hai loại ký tự ( và ).
- Xâu rỗng được xem là một xâu ngoặc cân bằng.
- Nếu
là xâu ngoặc cân bằng thì (
) cũng là một xâu ngoặc cân bằng.
- Nếu
và
là các xâu ngoặc cân bằng thì
cũng là một xâu ngoặc cân bằng.
Cho hai số nguyên dương và
. Hãy đếm số lượng xâu ngoặc cân bằng độ dài
thỏa mãn nếu xóa đi hai ký tự ở giữa xâu
hai ký tự ở vị trí
và
thì xâu thu được cũng là một xâu ngoặc cân bằng, kết quả chia lấy dư cho
.
Input
- Dòng duy nhất chứa hai số nguyên
và
.
Output
- In ra số lượng xâu ngoặc cân bằng thỏa mãn, kết quả chia lấy dư cho
.
Examples
Sample Input
3 998244353
Sample Output
3
Scoring
- Subtask
điểm:
- Subtask
điểm:
- Subtask
điểm: Không có ràng buộc gì thêm
Notes
Trong ví dụ, có xâu ngoặc cân bằng thỏa mãn: ((())), ()()() và (()()).
Comments