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 Specification
There is no input.
Output Specification
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