Let us define the sequence of Fibonacci numbers as:

The first few elements of the sequence are

For a positive integer , let denote the number of different ways of expressing as a sum of **different**
Fibonacci numbers. Two ways are considered different if there is a Fibonacci number that exists in exactly one
of them.

You are given a sequence of positive integers . For a non-empty prefix , we define . Your task is to find the values modulo , for all .

#### Input

The first line of the standard input contains an integer . The second line contains space-separated integers .

#### Output

The standard output should contain lines. In the -th line, print the value modulo .

#### Grading

The test set is divided into the following subtasks with additional constraints. Tests in each of the subtasks consist of one or more separate test groups. Each test group may contain one or more test cases.

Subtask | Constraints | Points |
---|---|---|

, are squares of different natural numbers | ||

are different even numbers | ||

no additional constraints |

#### Sample Input 1

```
4
4 1 1 5
```

#### Sample Output 1

```
2
2
1
2
```

#### Explanation of Sample Output 1

The number can be expressed in two ways: as and simply as (that is, and , respectively).

Hence, .

Then we have because .

The only way to express as a sum of different Fibonacci numbers is .

Finally, can be expressed as and (two ways).

## Comments