Vào dịp Tết sum vầy, sau khi nhận được khá nhiều tiền lì xì Phúc quyết định tổ chức bầu cua cho các em nhỏ trong nhà chơi. Và muốn các em nhỏ nhân đôi niềm vui, Phúc đã quyết định gấp đôi phần thưởng lên. Tuy nhiên vì không muốn các em "thua nhiều" sẽ buồn nên Phúc ra luật là chỉ được đặt ~1~ xu mỗi lượt chơi. Vì thế khi thắng các em sẽ nhận được tận ~2~ xu và khi thua thì các em chỉ mất duy nhất ~1~ xu.

Ngửi được mùi "kèo thơm" Nhã là bạn thân của Phúc đã nhanh chóng nhập tiệc góp vui. Tuy nhiên khi sắp tham gia Nhã lại quay xe và nghĩ rằng "nếu mình ăn thì Phúc làm gì còn có tiền lì xì cho các em nhỏ, còn nếu mình thua thì mất mặt trước các em lắm huhu. Phải làm sao, phải làm sao? Hay là tự đặt thử thách cho bản thân tìm cách làm thế nào để huề vốn đi hehe."

Hãy giúp Nhã tính xem có bao nhiêu trường hợp để Nhã huề vốn.

Input

Duy nhất ~1~ số nguyên dương ~n~ ~(1 \le n \le 10^6 )~ là số ván chơi.

Output

Duy nhất ~1~ số nguyên là số trường hợp Nhã huề vốn. Tuy nhiên đáp án rất lớn nên hãy lấy kết quả là phần dư của phép chia cho ~04022004~.

Simple Input

3

Simple Output

3

Giải thích test đề:

Các trường hợp mà Nhã huề vốn là:

• Thua - Thua - Thắng.
• Thua - Thắng - Thua.
• Thắng - Thua - Thua.

Cách tính điểm:

• ~30 \%~ test có ~n \le 20~.
• ~40 \%~ test có ~n \le 10^3~.
• ~30 \%~ test có ~n \le 10^6~.

Trong tiết học toán ngày hôm nay, thầy Lữ đã dạy cho chúng ta những kiến thức về cấp số cộng. Vì quá phấn khích khi học xong bài này, Trung đã nhìn mọi thứ xung quanh đều ẩn chứa cấp số cộng. Trùng hợp thay khi lên lab, Trung thấy Nhân vừa mới mua ~1~ bộ lô tô chứa ~n~ quả bóng đánh số từ ~1~ đến ~n~. Cộng thêm việc yêu thích số ~5~ nên Trung đã bất chợt nghĩ trong đầu rằng "nếu như mình bốc ngẫu nhiên ~5~ quả bóng trong số ~n~ quả bóng, thì không biết liệu ~5~ số trong các quả bóng ấy có tạo thành một cấp số cộng được không?"".

Hãy giúp Trung tính xem có bao nhiêu trường hợp ~5~ số trên các quả bóng Trung bốc được tạo thành một cấp số cộng? Tuy nhiên đáp án rất lớn nên hãy lấy kết quả là phần dư của phép chia cho ~m~.

Input

Dòng duy nhất chứa ~2~ số nguyên ~n, m~ ~(1 \le n, m \le 10^{17} + 17)~.

Output

Duy nhất 1 số nguyên là số trường hợp ~5~ số trên các quả bóng Trung bốc được tạo thành một cấp số cộng.

Simple Input

7 17

Simple Output

3

Giải thích test đề:

Các trường hợp là:

• ~1 - 2 - 3 - 4 - 5~.
• ~2 - 3 - 4 - 5 - 6~.
• ~3 - 4 - 5 - 6 - 7~.

Cách tính điểm:

• ~30\%~ test với ~n \le 10~.
• ~40\%~ test với ~m \le 10^9 + 7~.
• ~30\%~ test với ~n, m \le 10 ^ {17} + 17~.

Hệ trục tọa độ ~Oxy~ chia mặt phẳng thành bốn phần: góc trên bên phải là góc phần tư thứ ~I~, cứ thế đi ngược chiều kim đồng hồ, ta sẽ có góc phần tư thứ ~II, III, IV~. Lần lượt cho vào các góc phần tư đó các điểm phân biệt (không nằm trên hai trục tọa độ) với số lượng là ~a,b,c,d~. Hãy tính xem có thể có nhiều nhất bao nhiêu tam giác với ba đỉnh (mỗi đỉnh ở 1 phần tư khác nhau) lấy từ các điểm đã cho và chứa gốc tọa độ ~O~ bên trong?

Input

Các số nguyên dương ~a,b,c,d~ không vượt quá ~10^6.~

Output

Một số nguyên duy nhất là đáp số của bài toán (cho biết rằng giá trị này vẫn tính được trong kiểu Int64).

Sample input

1 1 1 1

Sample output

2

Một bạn tân sinh viên của IUH có tên ~s~ (là chuỗi ký tự in hoa viết liền không dấu) và số điện thoại là chuỗi ~t~ gồm các ký tự từ ~0~ đến ~9~. Bạn muốn lập mật khẩu theo một trong ba lựa chọn sau:

1. Mật khẩu là hoán vị các chữ cái trong tên.
2. Mật khẩu là hoán vị các chữ số trong số điện thoại.
3. Mật khẩu có độ dài ~m~, sử dụng các ký tự có trong ~s, t~ sao cho các chữ cái, chữ số được xếp xen kẽ nhau (các ký tự không nhất thiết phân biệt).

Hãy giúp bạn này tính số mật khẩu có thể có cho mỗi lựa chọn trên.

Input

Một dòng duy nhất gồm chuỗi s, chuỗi ~t~ và số ~m~ cho biết rằng ~1 \le |s| \le 19, |t| = 10~ và ~1 \le m \le 10^3.~

Output

Một dòng duy nhất gồm ba kết quả (mỗi số cách nhau bởi một khoảng trắng), là số lượng mật khẩu có thể có, tính theo modulo ~10^9 + 7.~

Sample Input

MEOSUA 0909123456 2

Sample Output

720 907200 96