Cho một xâu S có N ký tự.

Yêu cầu: Hãy đếm xem có bao nhiêu ký tự là chữ số trong xâu.

Input

Gồm một dòng duy nhất bao gồm xâu S (~1 \le |S| \le 10^5~).

Output

Gồm một dòng duy nhất là kết quả bài toán.

Giới hạn

• ~30~% bộ test: ~1 \le |S| \le 255~.
• ~70~% bộ test: không giới hạn gì thêm.

Ví dụ

Sample input

abcd.dd1d2s3d4s

Sample output

4

Cho một hình chữ nhật có góc trái dưới là ~(x, y)~ và góc phải trên là ~(u, v)~. Người ta cắt đi một hình chữ nhật có góc trái dưới là ~(a, b)~ và góc phải trên là ~(u, v)~.

Gọi ~r~ là số hình chữ nhật con, ~s~ là số hình vuông con

Yêu cầu: Tính ~r^s~ phần dư khi chia cho ~10^9 + 7~

Input

Dòng đầu tiên là một số nguyên ~Q~.

~Q~ dòng tiếp theo, mỗi dòng gồm ~6~ số nguyên ~x, y, u, v, a, b~.

Output

Gồm ~Q~ dòng, mỗi dòng là kết quả của từng test.

Giới hạn

• ~25~% số điểm có ~Q = 1~
• Không có giới hạn gì thêm

Ví dụ

Sample input

2
1 1 4 4 2 2 
1 1 4 4 3 3

Sample output

161051
527642103

Giải thích ví dụ

Test 1 1 4 4 2 2

Phần màu cam là phần bị cắt, ~r = 11, s = 5, r^s = 161051~

Một lớp học gồm ~n~ bạn, các bạn được đánh số thứ tự từ ~1~ đến ~n~: để tham gia một trò chơi như sau:

Ban đầu, bạn thứ ~i~ sẽ ghí nhớ số ~i~. Sẽ có ~k~ lượt, mỗi lượt, mỗi bạn sẽ ghi nhớ một số mới là bình phương số mình đang ghi nhớ.

Cho ~S~ là tổng tất cả các số mà các bạn đang ghi nhớ.

Yêu cầu: Tìm chữ số cuối cùng của ~S~.

Input

Một dòng duy nhất là ~2~ số nguyên ~k, n~

Output

Yêu cầu của bài toán

Giới hạn

Ví dụ

Sample input

1 3

Sample output

4

Giải thích ví dụ

Ban đầu:

1 2 3

Sau 1 lượt

1 4 9

S = 14

Cho một mảng ~A~ gồm ~n~ số nguyên ~A_1, A_2,...,A_n~. Hãy tìm hai chỉ số ~i, j~ thỏa mãn điều kiện ~1 \le i < j \le n~ và ~A_i < A_j~ để giá trị ~(j-i)~ đạt giá trị lớn nhất.

Input

• Dòng đầu chưa 1 số nguyên dương ~n~ ~(n \le 10^5)~
• Dòng thứ 2 chứa ~n~ số nguyên dương đôi một khác nhau ~A_1, A_2,...,A_n~ ~(A_i \le 10^6)~

Output

• Gồm một dòng là giá trị ~(j-i)~ lớn nhất theo yêu cầu đề bài. Nếu không tìm được giá trị thỏa mãn thì in ra ~-1~.

Giới hạn

• ~50~% test có ~n \le 10^3~.
• ~50~% test có ~n \le 10^5~.

Ví dụ

Sample input 1

4
4 2 1 3 

Sample output 1

2

Sample input 2

3
4 2 1 

Sample output 2

-1