Trong khi ôn luyện các dạng bài toán quy hoạch động để chuẩn bị cho kỳ thi Olympic truyền thống 30 tháng 4, Hồng gặp một bài dạng quy hoạch động cái túi. Bài toán yêu cầu đếm số cách chọn ra một số đồ vật trong một tập hợp các đồ vật cho trước sao cho tổng khối lượng của chúng không vượt quá ~K~. Đây là dạng bài toán cơ bản nên Hồng đã nhanh chóng giải quyết được bài toán này. Tuy nhiên, Hồng đã nghĩ ra một ý tưởng mới bằng việc thay phép cộng các khối lượng thành phép nhân. Bài toán mới được Hồng phát biểu như sau:

Cho một đa tập ~S~ (một tập hợp mà mỗi số có thể xuất hiện nhiều lần) chỉ gồm các số nguyên dương. Có hai dạng thao tác thay đổi tập ~S~ như sau:

1. + ~x~: thêm một phần tử có giá trị ~x~ vào tập ~S~.

2. - ~x~: xóa một phần tử có giá trị ~x~ khỏi tập ~S~. Nếu tập ~S~ có nhiều phần tử cùng giá trị ~x~, thao tác này chỉ xóa đi một trong số chúng.

Sau mỗi thao tác, Hồng muốn đếm số lượng tập con của ~S~ sao cho tích các phần tử của chúng không nhỏ hơn ~L~ và không lớn hơn ~R~. Lưu ý là tính cả tập rỗng với quy ước tập rỗng có tích các phần tử bằng ~1~.

Yêu cầu: Hãy giúp Hồng giải quyết bài toán này.

Input

• Dòng đầu gồm ba số nguyên dương ~Q,L,R~ ~(1 \le Q \le 300; 1 \le L \le R \le 10^9)~.

• Mỗi dòng trong số ~Q~ dòng tiếp theo thuộc một trong hai dạng sau:

  1. + ~x~: mô tả thao tác thêm một phần tử có giá trị ~x~ vào tập ~S~ ~(1 \le x \le 10^9)~.

  2. - ~x~: mô tả thao tác xóa một phần tử có giá trị ~x~ khỏi tập ~S~ ~(1 \le x \le 10^9)~. Dữ liệu đảm bảo tại thời điểm xóa trong tập ~S~ có ít nhất một phần tử có giá trị ~x~.

Output

Gồm ~Q~ dòng, mỗi dòng chứa số lượng tập con thỏa mãn sau thao tác tương ứng. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của đáp án khi chia cho ~10^9+7~.

Scoring

Sample Input 1

5 2 10
+ 2
+ 3
+ 4
- 2
+ 3

Sample Output 1

1
3
5
2
4

Notes

• Sau thao tác đầu tiên, ~S=\{2\}~. Có một tập duy nhất thỏa mãn là ~\{2\}~.

• Sau thao tác thứ hai, ~S=\{2,3\}~. Các tập thỏa mãn là ~\{2\},\{3\},\{2,3\}~.

• Sau thao tác thứ ba, ~S=\{2,3,4\}~. Các tập thỏa mãn là ~\{2\},\{3\},\{4\},\{2,3\},\{2,4\}~.

• Sau thao tác thứ tư, ~S=\{3,4\}~. Các tập thỏa mãn là ~\{3\},\{4\}~.

• Sau thao tác cuối cùng, ~S=\{3,3,4\}~. Các tập thỏa mãn là ~\{3\},\{3\},\{4\},\{3,3\}~.