Highway Combinatorics

Time limit3sMemory limit1024 MB

Summary

Build a two-row parking layout of at most 200 columns whose empty cells can be tiled by 1x2 cars in exactly n ways modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Math, Implementation
Solved: No attempts yet

Problem

You are the new minister of transport in Berland. Recently, you allowed free parking on a two lane road segment of $200$ metres length. Since then, that road segment has constantly been jammed by parked cars due to some genius drivers who had the idea to park their cars across both lanes...

However, this is not your concern. You are more interested in parking some of your own cars on the road segment while it is empty. More specifically, you want to park some of your cars in such a way that the number of different ways to fill the remaining empty space with cars is congruent to your lucky number $n$ modulo $10^9+7$ .

Figure H.1: Visualization of Sample Output 1.

Each car has a size of $1\times2$ metres. Each of the two lanes is $1$ metre wide and $200$ metres long. You own more than $200$ cars that you could park on the road segment.

Input

One line with one integer $n$ ( $0\leq n<10^9+7$ ), the desired number of possible ways to fill the road modulo $10^9+7$ .

It can be proven that at least one valid solution exists for each possible value of $n$ .

Output

Output the state of the two lanes in two lines. Print "#" for an occupied spot and "." for an empty spot. The two lines must have the same length, at least $1$ metre and at most $200$ metres. Each occupied spot must correspond to some parked car. If your solution uses a road segment shorter than $200$ metres, the remaining part of the road segment is assumed to be blocked by parked cars.

Examples2

Example 1
Input
```
10
```
Expected output
```
##..#.......
....#.##....
```
Example 2
Input
```
27
```
Expected output
```
...##........
........##...
```