Trong một buổi sinh hoạt tập thể có ~N~ bạn nam và ~N~ bạn nữ tham gia. Để thực hiện một trò chơi, mỗi bạn nam sẽ ghép với một bạn nữ thành một cặp. Các bạn nữ xếp thành một hàng ngang, bạn đầu tiên có số hiệu là ~1~, bạn thứ hai có số hiệu là ~2~, ..., bạn cuối cùng có số hiệu là ~N~. Các bạn nam cũng được gán số hiệu từ ~1~ đến ~N~. Mỗi lượt chơi tương ứng, với một cách ghép cặp là cách mỗi bạn nam tìm cho mình một bạn nữ để ghép thành một cặp.

Yêu cầu: Cho hai số nguyên không âm ~A, B~. Có bao nhiêu cách ghép cặp mà số lượng các cặp ghép có số hiệu của bạn nam trùng với số hiệu của bạn nữ nằm trong khoảng từ ~A~ đến ~B~.

Input

Vào từ file văn bản MATCH.INP: Gồm một dòng ba số nguyên ~N, A, B~ ~(1\leq N\leq 4*10^6, 0\leq A, B\leq N)~ các số cách nhau một dấu cách.

Output

Ghi ra file văn bản MATCH.OUT: Gồm một dòng ghi một số là số dư của số lượng cách ghép thỏa mãn yêu cầu khi chia cho ~10^9+7~.

Scoring

• Subtask ~1~ ~(15\%)~: ~N\leq 10~
• Subtask ~2~ ~(15\%)~: ~N\leq 14~
• Subtask ~3~ ~(22\%)~: ~A = B = 0~
• Subtask ~4~ ~(17\%)~: ~N\leq 1000~
• Subtask ~5~ ~(20\%)~: ~N\leq 4*10^5~
• Subtask ~6~ ~(11\%)~: Không còn ràng buộc gì thêm.

Example input 1

3 0 3

Example output 1

6

Note 1

Mô tả cách ghép tương ứng với các bạn nam trên ví dụ như sau:

Với ~N=3, A=0~ và ~B=3~:

• Có hai cách ghép sao cho không có cặp nào có số hiệu trùng nhau: ~2, 3, 1; 3, 1, 2~.
• Có ba cách ghép sao cho có đúng ~1~ cặp có số hiệu trùng nhau: ~1, 3, 2; 3, 2, 1; 2, 1, 3~.
• Không có cách ghép nào sao cho có đúng ~2~ cặp có số hiệu trùng nhau, nếu có hai cặp có số hiệu trùng nhau thì cặp còn lại sẽ luôn có số hiệu trùng nhau.
• Chỉ có một cách ghép sao cho có ~3~ cặp có số hiệu trùng nhau: ~1, 2, 3~. Vậy có tất cả: ~2 + 3 + 0 + 1 = 6~ cách ghép thỏa mãn yêu cầu.