Giải bài trực tuyến

Cho 2 xâu khác rỗng S₁và S₂ có độ dài không lớn hơn 100.Xét các dãy F₁,F₂,F₃,...,F_ntrong đó
F₁=S₁
F₂=S₂
....
F_k=F_k-1+F_k-2 với k>2
Cho xâu S không quá 100 ký tự và số nguyên N(3<=N<=1000).Hãy xác định S xuất hiện
 bao nhiêu lần trong F_n

Input

Dòng 1 chứa số nguyên N

Dòng 2 chứa xâu S₁

Dòng 3 chứa xâu S₂

Dòng 4 chứa xâu S

Output

Đưa ra một dòng chứa kết quả

Example

Input:
 8
A
B
AB

Output: 8