#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  std::cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  std::cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long max(long long a, long long b) { return (a > b) ? a : b; }
long long min(long long a, long long b) { return (a < b) ? a : b; }
void amax(long long& a, long long b) { a = max(a, b) % 1000000007; }
void amin(long long& a, long long b) { a = min(a, b) % 1000000007; }
void inc(long long& a, long long b) { a = (a + b) % 1000000007; }
void dec(long long& a, long long b) { a = (a - b + 1000000007) % 1000000007; }
vector<long long> adj[1010];
vector<pair<long long, long long>> row[7];
long long k;
long long last = 2;
long long power(long long a, long long b) {
  if (b == 0) return 1;
  if (b == 1) return a;
  if (b % 2 == 1) return (power(a, b - 1) * a);
  long long q = power(a, b / 2);
  return (q * q);
}
long long ma = 0;
vector<long long> hola(1000, 0);
void find() {
  long long nodes = 1;
  for (; nodes <= 1000; nodes++) {
    long long temp = power(2, nodes);
    if (temp > k) {
      nodes--;
      break;
    }
  }
  ma = max(nodes, ma);
  long long tot = 0;
  vector<vector<pair<long long, long long>>> rr(ma + 100);
  rr[0].push_back({1, 1});
  for (long long i = 1; i <= nodes; i++) {
    for (long long j = 1; j <= 2; j++) {
      last++;
      long long sum = 0;
      for (auto p : rr[i - 1]) {
        sum += p.second;
        adj[p.first].push_back(last);
        adj[last].push_back(p.first);
      }
      rr[i].push_back({last, sum});
    }
  }
  for (long long i = nodes + 1; i <= ma; i++) {
    if (hola[i]) {
      long long sum = 0;
      for (auto p : rr[i - 1]) {
        sum += p.second;
        adj[p.first].push_back(hola[i]);
        adj[hola[i]].push_back(p.first);
      }
      k -= sum;
      return;
    }
    last++;
    hola[i] = last;
    long long sum = 0;
    for (auto p : rr[i - 1]) {
      sum += p.second;
      adj[p.first].push_back(last);
      adj[last].push_back(p.first);
    }
    rr[i].push_back({last, sum});
  }
  long long sum = 0;
  for (auto p : rr[ma]) {
    sum += p.second;
    adj[p.first].push_back(2);
    adj[2].push_back(p.first);
  }
  k -= sum;
}
long long solve() {
  cin >> k;
  while (k) {
    find();
  }
  cout << last << '\n';
  long long mat[last + 1][last + 1];
  memset(mat, 0, sizeof(mat));
  for (long long i = 1; i <= last; i++) {
    for (auto j : adj[i]) {
      mat[i][j] = mat[j][i] = 1;
    }
  }
  for (long long i = 1; i <= last; i++) {
    for (long long j = 1; j < last + 1; j++)
      if (mat[i][j])
        cout << "Y";
      else
        cout << "N";
    cout << '\n';
  }
  return 0;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) {
    solve();
  }
}

### Prompt

Create a solution in CPP for the following problem:

Fox Ciel wants to write a task for a programming contest. The task is: "You are given a simple undirected graph with n vertexes. Each its edge has unit length. You should calculate the number of shortest paths between vertex 1 and vertex 2."

Same with some writers, she wants to make an example with some certain output: for example, her birthday or the number of her boyfriend. Can you help her to make a test case with answer equal exactly to k?

Input

The first line contains a single integer k (1 ≤ k ≤ 109).

Output

You should output a graph G with n vertexes (2 ≤ n ≤ 1000). There must be exactly k shortest paths between vertex 1 and vertex 2 of the graph.

The first line must contain an integer n. Then adjacency matrix G with n rows and n columns must follow. Each element of the matrix must be 'N' or 'Y'. If Gij is 'Y', then graph G has a edge connecting vertex i and vertex j. Consider the graph vertexes are numbered from 1 to n.

The graph must be undirected and simple: Gii = 'N' and Gij = Gji must hold. And there must be at least one path between vertex 1 and vertex 2. It's guaranteed that the answer exists. If there multiple correct answers, you can output any of them. 

Examples

Input

2

Output

4
NNYY
NNYY
YYNN
YYNN

Input

9

Output

8
NNYYYNNN
NNNNNYYY
YNNNNYYY
YNNNNYYY
YNNNNYYY
NYYYYNNN
NYYYYNNN
NYYYYNNN

Input

1

Output

2
NY
YN

Note

In first example, there are 2 shortest paths: 1-3-2 and 1-4-2.

In second example, there are 9 shortest paths: 1-3-6-2, 1-3-7-2, 1-3-8-2, 1-4-6-2, 1-4-7-2, 1-4-8-2, 1-5-6-2, 1-5-7-2, 1-5-8-2.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  std::cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  std::cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long max(long long a, long long b) { return (a > b) ? a : b; }
long long min(long long a, long long b) { return (a < b) ? a : b; }
void amax(long long& a, long long b) { a = max(a, b) % 1000000007; }
void amin(long long& a, long long b) { a = min(a, b) % 1000000007; }
void inc(long long& a, long long b) { a = (a + b) % 1000000007; }
void dec(long long& a, long long b) { a = (a - b + 1000000007) % 1000000007; }
vector<long long> adj[1010];
vector<pair<long long, long long>> row[7];
long long k;
long long last = 2;
long long power(long long a, long long b) {
  if (b == 0) return 1;
  if (b == 1) return a;
  if (b % 2 == 1) return (power(a, b - 1) * a);
  long long q = power(a, b / 2);
  return (q * q);
}
long long ma = 0;
vector<long long> hola(1000, 0);
void find() {
  long long nodes = 1;
  for (; nodes <= 1000; nodes++) {
    long long temp = power(2, nodes);
    if (temp > k) {
      nodes--;
      break;
    }
  }
  ma = max(nodes, ma);
  long long tot = 0;
  vector<vector<pair<long long, long long>>> rr(ma + 100);
  rr[0].push_back({1, 1});
  for (long long i = 1; i <= nodes; i++) {
    for (long long j = 1; j <= 2; j++) {
      last++;
      long long sum = 0;
      for (auto p : rr[i - 1]) {
        sum += p.second;
        adj[p.first].push_back(last);
        adj[last].push_back(p.first);
      }
      rr[i].push_back({last, sum});
    }
  }
  for (long long i = nodes + 1; i <= ma; i++) {
    if (hola[i]) {
      long long sum = 0;
      for (auto p : rr[i - 1]) {
        sum += p.second;
        adj[p.first].push_back(hola[i]);
        adj[hola[i]].push_back(p.first);
      }
      k -= sum;
      return;
    }
    last++;
    hola[i] = last;
    long long sum = 0;
    for (auto p : rr[i - 1]) {
      sum += p.second;
      adj[p.first].push_back(last);
      adj[last].push_back(p.first);
    }
    rr[i].push_back({last, sum});
  }
  long long sum = 0;
  for (auto p : rr[ma]) {
    sum += p.second;
    adj[p.first].push_back(2);
    adj[2].push_back(p.first);
  }
  k -= sum;
}
long long solve() {
  cin >> k;
  while (k) {
    find();
  }
  cout << last << '\n';
  long long mat[last + 1][last + 1];
  memset(mat, 0, sizeof(mat));
  for (long long i = 1; i <= last; i++) {
    for (auto j : adj[i]) {
      mat[i][j] = mat[j][i] = 1;
    }
  }
  for (long long i = 1; i <= last; i++) {
    for (long long j = 1; j < last + 1; j++)
      if (mat[i][j])
        cout << "Y";
      else
        cout << "N";
    cout << '\n';
  }
  return 0;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) {
    solve();
  }
}

```