#include <bits/stdc++.h>
int diru[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dirv[] = {-1, 0, 1, -1, 1, -1, 0, 1};
using namespace std;
class Debugger {
 public:
  Debugger(const string& _separator = " ")
      : first(true), separator(_separator) {}
  template <typename ObjectType>
  Debugger& operator,(const ObjectType& v) {
    if (!first) cerr << separator;
    cerr << v;
    first = false;
    return *this;
  }
  ~Debugger() { cerr << endl; }

 private:
  bool first;
  string separator;
};
template <typename T1, typename T2>
inline ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << "(" << p.first << "," << p.second << ")";
}
template <typename T>
inline ostream& operator<<(ostream& os, const vector<T>& v) {
  bool first = true;
  os << "{";
  for (unsigned int i = 0; i < v.size(); i++) {
    if (!first) os << ",";
    os << v[i];
    first = false;
  }
  return os << "}";
}
template <typename T>
inline ostream& operator<<(ostream& os, const set<T>& v) {
  bool first = true;
  os << "{";
  for (typename set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii) {
    if (!first) os << ",";
    os << *ii;
    first = false;
  }
  return os << "}";
}
template <typename T1, typename T2>
inline ostream& operator<<(ostream& os, const map<T1, T2>& v) {
  bool first = true;
  os << "{";
  for (typename map<T1, T2>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ",";
    os << *ii;
    first = false;
  }
  return os << "}";
}
template <class T>
T sq(T n) {
  return n * n;
}
template <class T>
T gcd(T a, T b) {
  return (b != 0 ? gcd<T>(b, a % b) : a);
}
template <class T>
T lcm(T a, T b) {
  return (a / gcd<T>(a, b) * b);
}
template <class T>
bool inside(T a, T b, T c) {
  return a <= b && b <= c;
}
template <class T>
void setmax(T& a, T b) {
  if (a < b) a = b;
}
template <class T>
void setmin(T& a, T b) {
  if (b < a) a = b;
}
template <class T>
T power(T N, T P) {
  return (P == 0) ? 1 : N * power(N, P - 1);
}
bool G[1010][1010];
int n;
void cal(map<int, int>& M, map<int, pair<int, int> >& ans, bool f) {
  if (f && ((int)M.size()) == 1 && M.find(1) != M.end() && M[1] == 1) {
    ans[1] = pair<int, int>(1, -1);
    return;
  }
  map<int, int> M2;
  map<int, pair<int, int> > ans2;
  int a, b;
  for (__typeof((M).begin()) it = (M).begin(); it != (M).end(); ++it) {
    if (it->first == 1) {
      M2[it->first] = max(M2[it->first], 1);
      continue;
    }
    a = it->first / 2;
    b = it->first - a;
    if (a == b) {
      M2[a] = 2;
    } else {
      M2[a] = max(M2[a], 1);
      M2[b] = max(M2[b], 1);
    }
  }
  cal(M2, ans2, 1);
  int node = 2;
  for (__typeof((M).begin()) it = (M).begin(); it != (M).end(); ++it) {
    a = it->first / 2;
    b = it->first - a;
    if (f) node = n++;
    if (it->first == 1) {
      G[ans2[1].first][node] = 1;
      ans[it->first] = pair<int, int>(node, -1);
    } else if (a == b) {
      G[ans2[a].first][node] = 1;
      G[ans2[a].second][node] = 1;
      ans[it->first] = pair<int, int>(node, -1);
    } else {
      G[ans2[a].first][node] = 1;
      G[ans2[b].first][node] = 1;
      ans[it->first] = pair<int, int>(node, -1);
    }
    if (it->second == 2) {
      if (f) node = n++;
      if (it->first == 1) {
        G[ans2[1].first][node] = 1;
        ans[it->first].second = node;
      } else if (a == b) {
        G[ans2[a].first][node] = 1;
        G[ans2[a].second][node] = 1;
        ans[it->first].second = node;
      } else {
        G[ans2[a].first][node] = 1;
        G[ans2[b].first][node] = 1;
        ans[it->first].second = node;
      }
    }
  }
}
int dp[1010];
void bfs() {
  queue<int> q;
  q.push(1);
  dp[1] = 1;
  int u, v;
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (v = 1; v < n; v++) {
      if (G[u][v]) {
        if (!dp[v]) q.push(v);
        dp[v] += dp[u];
      }
    }
  }
  printf("%d\n", dp[2]);
  return;
}
int main() {
  int T, t = 1, m, i, j, k;
  scanf("%d", &k);
  n = 3;
  map<int, int> M;
  map<int, pair<int, int> > ans;
  M[k] = 1;
  cal(M, ans, 0);
  printf("%d\n", n - 1);
  for (i = 1; i < n; i++) {
    for (j = 1; j < n; j++)
      if (G[i][j] || G[j][i])
        putchar('Y');
      else
        putchar('N');
    puts("");
  }
  return 0;
}

### Prompt

Your task is to create a cpp solution to 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>
int diru[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dirv[] = {-1, 0, 1, -1, 1, -1, 0, 1};
using namespace std;
class Debugger {
 public:
  Debugger(const string& _separator = " ")
      : first(true), separator(_separator) {}
  template <typename ObjectType>
  Debugger& operator,(const ObjectType& v) {
    if (!first) cerr << separator;
    cerr << v;
    first = false;
    return *this;
  }
  ~Debugger() { cerr << endl; }

 private:
  bool first;
  string separator;
};
template <typename T1, typename T2>
inline ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << "(" << p.first << "," << p.second << ")";
}
template <typename T>
inline ostream& operator<<(ostream& os, const vector<T>& v) {
  bool first = true;
  os << "{";
  for (unsigned int i = 0; i < v.size(); i++) {
    if (!first) os << ",";
    os << v[i];
    first = false;
  }
  return os << "}";
}
template <typename T>
inline ostream& operator<<(ostream& os, const set<T>& v) {
  bool first = true;
  os << "{";
  for (typename set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii) {
    if (!first) os << ",";
    os << *ii;
    first = false;
  }
  return os << "}";
}
template <typename T1, typename T2>
inline ostream& operator<<(ostream& os, const map<T1, T2>& v) {
  bool first = true;
  os << "{";
  for (typename map<T1, T2>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ",";
    os << *ii;
    first = false;
  }
  return os << "}";
}
template <class T>
T sq(T n) {
  return n * n;
}
template <class T>
T gcd(T a, T b) {
  return (b != 0 ? gcd<T>(b, a % b) : a);
}
template <class T>
T lcm(T a, T b) {
  return (a / gcd<T>(a, b) * b);
}
template <class T>
bool inside(T a, T b, T c) {
  return a <= b && b <= c;
}
template <class T>
void setmax(T& a, T b) {
  if (a < b) a = b;
}
template <class T>
void setmin(T& a, T b) {
  if (b < a) a = b;
}
template <class T>
T power(T N, T P) {
  return (P == 0) ? 1 : N * power(N, P - 1);
}
bool G[1010][1010];
int n;
void cal(map<int, int>& M, map<int, pair<int, int> >& ans, bool f) {
  if (f && ((int)M.size()) == 1 && M.find(1) != M.end() && M[1] == 1) {
    ans[1] = pair<int, int>(1, -1);
    return;
  }
  map<int, int> M2;
  map<int, pair<int, int> > ans2;
  int a, b;
  for (__typeof((M).begin()) it = (M).begin(); it != (M).end(); ++it) {
    if (it->first == 1) {
      M2[it->first] = max(M2[it->first], 1);
      continue;
    }
    a = it->first / 2;
    b = it->first - a;
    if (a == b) {
      M2[a] = 2;
    } else {
      M2[a] = max(M2[a], 1);
      M2[b] = max(M2[b], 1);
    }
  }
  cal(M2, ans2, 1);
  int node = 2;
  for (__typeof((M).begin()) it = (M).begin(); it != (M).end(); ++it) {
    a = it->first / 2;
    b = it->first - a;
    if (f) node = n++;
    if (it->first == 1) {
      G[ans2[1].first][node] = 1;
      ans[it->first] = pair<int, int>(node, -1);
    } else if (a == b) {
      G[ans2[a].first][node] = 1;
      G[ans2[a].second][node] = 1;
      ans[it->first] = pair<int, int>(node, -1);
    } else {
      G[ans2[a].first][node] = 1;
      G[ans2[b].first][node] = 1;
      ans[it->first] = pair<int, int>(node, -1);
    }
    if (it->second == 2) {
      if (f) node = n++;
      if (it->first == 1) {
        G[ans2[1].first][node] = 1;
        ans[it->first].second = node;
      } else if (a == b) {
        G[ans2[a].first][node] = 1;
        G[ans2[a].second][node] = 1;
        ans[it->first].second = node;
      } else {
        G[ans2[a].first][node] = 1;
        G[ans2[b].first][node] = 1;
        ans[it->first].second = node;
      }
    }
  }
}
int dp[1010];
void bfs() {
  queue<int> q;
  q.push(1);
  dp[1] = 1;
  int u, v;
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (v = 1; v < n; v++) {
      if (G[u][v]) {
        if (!dp[v]) q.push(v);
        dp[v] += dp[u];
      }
    }
  }
  printf("%d\n", dp[2]);
  return;
}
int main() {
  int T, t = 1, m, i, j, k;
  scanf("%d", &k);
  n = 3;
  map<int, int> M;
  map<int, pair<int, int> > ans;
  M[k] = 1;
  cal(M, ans, 0);
  printf("%d\n", n - 1);
  for (i = 1; i < n; i++) {
    for (j = 1; j < n; j++)
      if (G[i][j] || G[j][i])
        putchar('Y');
      else
        putchar('N');
    puts("");
  }
  return 0;
}

```