Jack, a 7-year-old child, is playing with 7 sticks with lengths 1,2,…,7, which can be connected together. He is trying to use some of them to create a polygon. Harry, his father, is looking, and since...

Jack, a 7-year-old child, is playing with 7 sticks with lengths 1,2,…,7, which can be connected together. He is trying to use some of them to create a polygon. Harry, his father, is looking, and since he is a developer, he quickly comes up with a problem based on this game: There are N sticks lengths 1,2,3,…,N. You should choose a non-empty subset of these sticks and create a polygon by connecting their endpoints together. Now you have to develop a C++ program that prints how many such subsets of sticks that we you choose. Since this number could be large, you can compute it modulo 10^9+5.

Input:

2

4

8

Output:

2

178