(Nguồn bài: đề thi đề nghị Trại hè Hùng Vương 2023)

Ta gọi hai xâu ~X~ và ~Y~ là tương đồng bậc ~k~ nếu như chúng thoả mãn đồng thời:

i) Chúng có độ dài bằng nhau, tức là ~|X| = |Y|~;

ii) Ký tự ~X[i]~ và ~Y[i]~ cách nhau không quá ~k~ vị trí trong bảng mã ASCII với mọi ~i = 1, 2,.., |X|~.

Yêu cầu: Cho số nguyên ~k~ và 2 xâu ~S_1, S_2~ có độ dài bằng nhau (xâu chỉ gồm ký tự ~a~ đến ~z~). Hãy xác định số cách cắt ~S_1~ thành 3 xâu khác rỗng, sau đó ghép tạo thành xâu ~S_3~ mà xâu ~S_3~ tương đồng bậc ~k~ với xâu ~S_2~. Hai cách cắt được gọi là khác nhau nếu tồn tại một vị trí cắt khác nhau.

Input

Dòng 1: chứa số nguyên ~k~, còn dòng 2: chứa xâu ~S_1~ và dòng 3: chứa xâu ~S_2~.

Output

Số cách cắt thỏa mãn.

Sample Input 1

0 
beast 
betas

Sample Output 1

1

Sample Input 2

1
aaaaa 
bbbbb

Sample Output 2

6

Giới hạn:

• Có 40% số test ứng với ~|S_1|=|S_2| ≤ 300~; ~k ≤ 25~
• Có 30% số test ứng với ~|S_1|=|S_2| ≤ 3000~; ~k = 0~
• Có 30% số test ứng với ~|S_1|=|S_2| ≤ 3000~; ~k ≤ 25~