Đề bài

Đất nước Seggs có \(n\) chiếc cổng dịch chuyển đang được xây dựng và \(m\) cặp cổng nối từ tỉnh này sang tỉnh kia. Mỗi cặp \((u, v)\) thể hiện một chiếc cổng, và bạn chỉ có thể đi một chiều từ \(u\) đến \(v\).

Thủ tướng Phát giao cho bạn nhiệm vụ kiểm tra hệ thống này: Hãy đếm xem có bao nhiêu chuỗi liên tiếp có thể đi từ cổng này sang cổng khác cho đến khi không thể đi tiếp nữa (nghĩa là đi theo chiều của các cạnh cho đến khi không còn cạnh đi tiếp).

Nếu số chuỗi đó thuộc dãy Fibonacci, bạn cần in ra 19022006.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên \(n\), \(m\) — số đỉnh và số cạnh.
• \(m\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u\), \(v\) — thể hiện một cạnh có hướng từ \(u\) đến \(v\).

Dữ liệu ra

• In ra số lượng chuỗi thỏa mãn điều kiện nếu không thuộc dãy Fibonacci.
• Nếu thuộc dãy Fibonacci, in ra 19022006.

Giới hạn

• \(1 \leq n, m \leq 10^5\)
• \(1 \leq u, v \leq n\)

Sample Input

5 3
1 2
2 3
4 5

Sample Output

19022006

Giải thích

• Có 2 chuỗi liên tiếp:
  • 1 → 2 → 3
  • 4 → 5
• Tổng số chuỗi là 2. Vì \(2\) là số trong dãy Fibonacci nên in ra \(19022006\).