Ba anh em Hiếu, Kiệt và Hoàng đã đạt được thành tích cao trong học tập nên bố mẹ quyết định tặng cho cả ba anh em ~1~ túi kẹo, trong túi có ~N~ viên kẹo. Sau khi cả ba cùng thương lượng, vì Hiếu là anh cả, Kiệt là anh ba, Hoàng là em út nên Hiếu sẽ có số kẹo ít nhất và Hoàng sẽ có số kẹo nhiều nhất, không ai có cùng số kẹo và không ai không có viên kẹo nào. Dĩ nhiên tổng số kẹo của ba anh em gộp lại bằng ~N~.

Yêu cầu: Bạn hãy đếm số cách để chia kẹo sao cho thỏa mãn yêu cầu trên của ba anh em Hiếu, Kiệt, Hoàng nhé~!~

Input

• Số nguyên dương ~N (1 \le N \le 18\times 10^{18})~ là số viên kẹo trong túi kẹo.

Output

• In ra số cách chia theo yêu cầu của đề bài sau khi chia lấy dư cho ~10^9 + 7~.

Sample

Input #1

7

Output #1

1

Hint

Giải thích #1: Chỉ có ~1~ cách chia như sau:

• Hiếu ~1~ viên, Kiệt ~2~ viên, Hoàng ~4~ viên.

Trên một con đường có ~n~ tòa nhà. Mỗi tòa nhà được sơn bằng một màu Đỏ, Vàng, Xanh, hoặc Tím. Người ta muốn sơn lại một số tòa nhà (bằng một trong các màu Đỏ, Vàng, Xanh, Tím) sao cho không có hai tòa nhà liên tiếp có cùng màu sơn. Tìm số nhà cần sơn lại ít nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~n\ (1 ≤ n ≤ 2500)~;
• Dòng tiếp theo chứa một xâu kí tự có độ dài ~n~, mỗi kí tự đại diện cho một tòa nhà. Mỗi kí tự có thể là ~D, V, X~, hoặc ~T~, lần lượt đại diện cho một ngôi nhà được sơn màu Đỏ, Vàng, Xanh, hoặc Tím.

Output

• In ra số lượng nhà cần sơn lại ít nhất.

Sample

Input #1

2
TX

Output #1

0

Input #2

3
TXV

Output #2

0

Input #3

14
VVXDDTXVTXDVXV

Output #3

2

Input #4

17
DDTVVTDVVVTVVTDVV

Output #4

5

Problem source: Kc97ble - Free Contest

Hôm nay là ngày đầu tiên Đạo và Mộc Nhĩ hẹn hò. Đạo quyết định mua hoa tặng Mộc Nhĩ. Trong cửa hàng hoa có ~N~ bông hoa xếp theo hàng ngang, bông hoa thứ ~i~ từ trái sang có ~A_i~ cánh hoa. Để tiết kiệm thời gian, Đạo quyết định mua một dãy các bông hoa liên tiếp trong cửa hàng để tạo thành một bó hoa. Ngoài ra, để bó hoa không quá đơn điệu, Đạo muốn trong bó hoa có đúng ~K~ bông hoa có lẻ cánh hoa. Vì có quá nhiều cách chọn, Đạo đang rất phân vân không biết nên chọn như thế nào.

Bạn là một trong những nhân viên của cửa hàng, hãy giúp Đạo đếm số cách chọn bó hoa.

Input

• Dòng đầu chứa hai số nguyên ~N~ và ~K (1 ≤ K ≤ N ≤ 99999)~.
• Dòng thứ hai chứa ~N~ số nguyên, số thứ ~i~ là ~A_i (1 ≤ A_i ≤ 9^9)~.

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Sample

Input #1

4 2
1 3 2 3

Output #1

3

Problem source: Kc97ble - Free Contest