Submit solution

Points:
5

Time limit:
1.0s

Memory limit:
256M

Authors:

Problem type

Allowed languages

Text

You wish to create an array with the following properties:

- The array has elements.
- Each element in the array is between and .

We define as follows:

for all between and , for some

Given an integer , what is the number of arrays that satisfy the above properties? Output the answer mod .

#### Constraints

This is an output only problem. Solve the problem for

#### Input Format

There is no input.

#### Output Format

Submit one integer in text: the number of arrays of size satisfying the condition.

#### Sample Input

`3`

#### Sample Output

`9`

#### Explanation

Note that you never actually have to solve the sample input.

The possible arrays are

```
0 0 0
0 0 1
0 2 0
1 0 0
1 0 1
1 2 0
2 0 0
2 0 1
2 2 0
```

## Comments

how to solve this?

https://oeis.org/A000169