import sys N = 50 def connect_stair(G, entries): """ entries = [(r, c), ...] を上から順につなぐ。 各 entry から右、次に下、右、下...という一本の collector に合流させる。 collector 上では分岐しないので、P を踏んだ後の suffix は 1 通りになる。 """ if not entries: return entries.sort() cur_r, cur_c = entries[0] for nxt_r, nxt_c in entries[1:]: # 右へ for c in range(cur_c, nxt_c + 1): if G[cur_r][c] != 'P': G[cur_r][c] = '.' # 下へ for r in range(cur_r, nxt_r + 1): if G[r][nxt_c] != 'P': G[r][nxt_c] = '.' cur_r, cur_c = nxt_r, nxt_c # 最後は右端へ行き、右端を下ってゴールへ for c in range(cur_c, N): if G[cur_r][c] != 'P': G[cur_r][c] = '.' for r in range(cur_r, N): if G[r][N - 1] != 'P': G[r][N - 1] = '.' def build_binary(M): """ 二進 partial。 k 段目の prefix 経路数を 2^k にする。 bit k が 1 なら、その段から P へ 1 本だけ出口を出す。 47 段まで入るので、0 <= M < 2^47 は必ず構築できる。 """ K = 47 if not (0 <= M < (1 << K)): return None G = [['#'] * N for _ in range(N)] # prefix chain # stage k: (k,k) -> (k+1,k+1) に 2 通り for k in range(K): r = k c = k G[r][c] = '.' G[r][c + 1] = '.' G[r + 1][c] = '.' G[r + 1][c + 1] = '.' G[K][K] = '.' entries = [] for k in range(K): if (M >> k) & 1: # (k,k) への prefix は 2^k。 # (k,k+1) までは prefix 2^k のまま。 # その右に P を置く。 pr = k pc = k + 2 er = k ec = k + 3 if ec >= N: return None G[pr][pc] = 'P' G[er][ec] = '.' entries.append((er, ec)) connect_stair(G, entries) G[0][0] = '.' G[N - 1][N - 1] = '.' return G def build_ternary(M): """ 三進 partial。 32 段の 3-way gadget を使う。 各段は縦長 3x2 または横長 2x3 の矩形。 縦長 gadget: 入力から右上側の外へ出る P は prefix 1*x 入力から中央右側の外へ出る P は prefix 2*x 横長 gadget: digit 0/1 の段にだけ使う。 digit 2 は扱いづらいので、その段は必ず縦長にする。 50x50 に収めるため、縦長 gadget はちょうど 17 個にする。 したがって、三進表現中の digit 2 の個数が 18 個以上だと失敗する。 """ K = 32 LIM = pow(3, K) if not (0 <= M < LIM): return None digits = [] x = M for _ in range(K): digits.append(x % 3) x //= 3 if x != 0: return None # digit 2 の段は縦長必須。 forced_vertical = [i for i, d in enumerate(digits) if d == 2] if len(forced_vertical) > 17: return None vertical = [False] * K for i in forced_vertical: vertical[i] = True # 縦長を合計 17 個にする。 need = 17 - len(forced_vertical) for i in range(K): if need == 0: break if not vertical[i]: vertical[i] = True need -= 1 if sum(vertical) != 17: return None G = [['#'] * N for _ in range(N)] entries = [] r = 0 c = 0 G[r][c] = '.' for k in range(K): d = digits[k] if vertical[k]: # 縦長 3x2 gadget # # 入力: (r,c) # 出力: (r+2,c+1) # # 経路数は 3 倍。 # # prefix が x の場所: # (r,c+1) # prefix が 2x の場所: # (r+1,c+1) for rr in range(r, r + 3): for cc in range(c, c + 2): G[rr][cc] = '.' if d == 1: pr, pc = r, c + 2 er, ec = r, c + 3 elif d == 2: pr, pc = r + 1, c + 2 er, ec = r + 1, c + 3 else: pr = pc = er = ec = None nr, nc = r + 2, c + 1 else: # 横長 2x3 gadget # # digit 0/1 のときだけ使う。 # # 入力: (r,c) # 出力: (r+1,c+2) # # prefix が x の場所: # (r,c+2) assert d in (0, 1) for rr in range(r, r + 2): for cc in range(c, c + 3): G[rr][cc] = '.' if d == 1: pr, pc = r, c + 3 er, ec = r, c + 4 else: pr = pc = er = ec = None nr, nc = r + 1, c + 2 if d != 0: if not (0 <= pr < N and 0 <= pc < N and 0 <= er < N and 0 <= ec < N): return None G[pr][pc] = 'P' G[er][ec] = '.' entries.append((er, ec)) r, c = nr, nc if not (0 <= r < N and 0 <= c < N): return None G[r][c] = '.' connect_stair(G, entries) G[0][0] = '.' G[N - 1][N - 1] = '.' return G def fallback_wrong_grid(): """ unsupported な M に対しても RE しないための出力。 当然ほとんどの M では WA になる。 partial 提出らしくするためのもの。 """ G = [['#'] * N for _ in range(N)] for i in range(N): G[0][i] = '.' G[i][N - 1] = '.' # P がないので、P をちょうど 1 回押す経路数は 0。 return G def solve(): M = int(sys.stdin.readline()) # 三進を優先。通れば二進よりかなり広い。 G = build_ternary(M) # fallback として二進。 if G is None: G = build_binary(M) # それでも無理なら、形式だけ正しい不正解グリッド。 if G is None: G = fallback_wrong_grid() print(N) print('\n'.join(''.join(row) for row in G)) if __name__ == "__main__": solve()