Sau khi đã hiểu sơ sơ về dãy nhị phân, Mr Toàn muốn các bạn trẻ phải hiểu rõ hơn về quá trình duyệt này. Lần này Mr Toàn muốn sinh ra các dãy nhị phân kèm theo một số điều kiện rắc rối hơn. Cụ thể là: dãy nhị phân sinh ra phải có số lượng chữ số 1 trong dãy là 1 số nguyên tố, đồng thời chênh lệch giữa số lượng chữ số 0 và chữ số 1 trong dãy nhị phân đó cũng là 1 số nguyên tố.

Yêu cầu:

Hãy in ra số lượng các dãy nhị phân thỏa mãn yêu cầu trên của Mr Toàn.

Dữ liệu vào Specification

• Gồm 1 dòng là số nguyên \(n\) \((0< n \le 20)\).

Dữ liệu ra Specification

• In ra số lượng dãy nhị phân thỏa mãn yêu cầu

Sample Input

3

Sample Output

1

Giải thích: chỉ có dãy 111 có số lượng chữ số 1 là 3 và chênh lệch số lượng cũng là 3 nên thỏa mãn yêu cầu.