Lúc chưa bị bóc phốt trên confession Thủy lợi, Huy lúc nào cũng hẹn hò với nhiều người cùng một lúc. Giả sử, hiện tại Huy đang hẹn hò với Ánh, Chi, Huyền, Linh, Trang. Để cho các nàng thơ của mình không phát hiện ra, Huy đã tìm cách sắp xếp lịch hẹn hò với từng người mỗi ngày. Do đọc nhiều sách về tâm lý học, Huy nắm bắt được tính cách mỗi nàng để rồi có những dữ kiện sau:

• Ngày đầu tiên Huy có thể hẹn hò với bất kì ai trong 5 nàng thơ của mình.
• Những ngày tiếp theo:
  • Nàng Ánh sẽ chỉ có thể gặp vào ngày tiếp theo sau khi đã hẹn hò với nàng Chi.
  • Nàng Chi sẽ chỉ có thể gặp vào ngày tiếp theo sau khi đã hẹn hò với nàng Ánh hoặc nàng Huyền.
  • Nàng Huyền không thể hẹn hò hai ngày liên tiếp.
  • Nàng Linh sẽ chỉ có thể gặp vào ngày tiếp theo sau khi đã hẹn hò với nàng Huyền hoặc nàng Trang.
  • Nàng Trang sẽ chỉ có thể gặp vào ngày tiếp theo sau khi đã hẹn hò với nàng Ánh.

Hãy giúp Huy tính xem có tổng cộng bao nhiêu cách sắp xếp cho đến ngày bị phát hiện.

Input

• Một số nguyên dương N duy nhất (~1 ≤ N ≤ 10^{11} ~ ) là số ngày cho đến ngày bị phát hiện.

Output

• Số cách Huy sắp xếp lịch hẹn hò sau khi đã mod cho ~ 10^{9} + 7 ~.

Sample input 1

1

Sample output 1

5

Sample input 2

2

Sample output 2

10

Sample input 3

5

Sample output 3

68

Giải thích

• Với N = 1, Huy có 5 cách hẹn hò, đó là đi với bất kì ai.
• Với N = 2, giả sử:
  • Ngày đầu Huy hẹn hò với Ánh, thì vào ngày tiếp theo Huy chỉ có thể hẹn hò với Chi hoặc Huyền hoặc Trang.
  • Ngày đầu Huy hẹn hò với Chi, thì vào ngày tiếp theo Huy chỉ có thể hẹn hò với Ánh hoặc Huyền.
  • Ngày đầu Huy hẹn hò với Huyền, thì vào ngày tiếp theo Huy chỉ có thể hẹn hò với Chi hoặc Linh.
  • Ngày đầu Huy hẹn hò với Linh, thì vào ngày tiếp theo Huy chỉ có thể hẹn hò với Huyền.
  • Ngày đầu Huy hẹn hò với Trang, thì vào ngày tiếp theo Huy chỉ có thể hẹn hò với Huyền hoặc Linh.
  • Vậy, tổng cộng Huy có 10 cách sắp xếp lịch phù hợp.

Giới hạn

20% số điểm có ~ N ≤ 10 ~.

50% số điểm có ~N ≤ 10^{5} ~.

30% số điểm có ~N ≤ 10^{11} ~.