Bạn Trí được phân công sẽ mua quà để làm phần thưởng khi kết thúc ngày hội tháng 3. Khi đến cửa hàng thì bạn được cho biết là cửa hàng có các loại quà 2 nghìn đồng, 5 nghìn đồng và 10 nghìn đồng.

Để đảm bảo với số lượng phần thưởng ban tổ chức có quy định là bạn Trí phải mua loại 2 nghìn gấp đôi loại 5 nghìn và loại 5 nghìn phải nhiều hơn loại 10 nghìn 5 phần quà và loại 10 nghìn phải có ít nhất 1 món quà.

Với 1 số tiền được ban tổ chức giao cho, Trí đang phân vân không biết mình có những cách mua quà như thế nào. Em hãy lập trình để đếm xem bạn Trí có bao nhiêu cách để có thể mua những món quà trên. Không nhất thiết phải sử dụng hết số tiền ban tổ chức đã giao.

Input

• Nhập vào số tiền là 1 số tự nhiên \(N\) (\(10.000 \le N \le 20.000.000\)).

Output

• In ra màn hình số cách có thể mua quà.

Example

100000

2

20000

0