28376번 - Highway Combinatorics 스페셜 저지다국어

문제

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 which you could park on the road segment.

입력

The input consists of:

• 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 the state of the two lanes in two lines. Print "#" for an occupied spot and "." for an empty spot. Note that the two lines should have the same length of at least 1ドル$ metre and at most 200ドル$ metres, and the occupied spots must correspond to some parked cars. 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.

제한

힌트