Ôn luyện vào chuyên Tin #08

Bạn được một xâu \(s = s_1 s_2 ... s_n\) có độ dài n, chỉ chứa các ký tự số \(1,2,3,...,9\) (không chứa số \(0\))

Một xâu con \(s[l...r]\) của xâu \(s\) là \(s_l s_{l+1} ... s_r\) được gọi là xâu con chẵn nếu nó biểu diễn số chẵn.

Hãy tìm số xâu con chẵn của xâu \(s\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n(n \leq 10^5)\) - là độ dài xâu \(s\)
• \(n\) ký tự của xâu \(s\), chỉ gồm các ký tự từ \(1\) đến \(9\)

Output

• Số xâu con chẵn của xâu \(s\).

Example

4
1234 

6

4
2244 

10

Hàm \(D[n]\) biểu thị số ước của một số nguyên \(n\). Ví dụ \(D[24]=8\) (Các ước của \(24\) là \(1, 2, 3, 4, 6, 8, 12, 24\)).

Hàm \(F[n]\) biểu thị tổng số ước các ước của \(n\). Ví dụ \(F[24]=D[1]+D[2]+D[3]+D[4]+D[6]+D[8]+D[12]+D[24]=30\)

Cho số tự nhiên \(n\), hãy tính \(F[n!]\), trong đó \(n!= 1 * 2 * 3 * ... * n\)

Input

• Input gồm nhiều dòng
• Mỗi dòng chứa số nguyên dương \(n(n \leq 10^6)\)
• Input kết thúc bởi số \(0\)

Output

• Gồm nhiều dòng, mỗi dòng tương ứng với mỗi test
• Mỗi dòng chứa phần dư \(F[n!]\) cho \(10^7 +7\)

Example

4
5
1
0 

30
90
1

Cho "tổ ong" có quy luật như sau:

Dễ thấy với mỗi tập các ô có giá trị \(n\) sẽ tạo thành một hình lục giác đều bậc \(n\).

Và hình lục giác thứ \(n+1\) sẽ bao quanh hình lục giác thứ \(n\).

Bạn được cho giá trị \(n\), Hãy tính số ô có giá trị nhỏ hơn hoặc bằng \(n\)

Input

• Số nguyên \(n (0 \leq n \leq 10^9)\)

Output

• Số ô có giá trị nhỏ hơn bằng \(n\).

Example

2 

19