A - AABCDDEFE 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

正整数 x が美しい整数であるとは，x が 9 桁の整数であり，その 10 進法表記 S_1\ldots S_9 （S_i は x の 10 進法表記の i 文字目）が以下の条件をすべて満たすことをいいます：

  • S_1 は 0 ではない
  • S_1 = S_2
  • S_5 = S_6
  • S_7 = S_9

例えば 998244353 や 333333333 は美しい整数です．111112222 は S_5 \neq S_6 であるため美しい整数ではありません．

正の整数 N が与えられます．小さい方から数えて N 番目の美しい整数を答えてください．

制約

  • N は正の整数
  • 美しい整数が N 個以上存在する

入力

入力は以下の形式で標準入力から与えられます．

N

出力

小さい方から数えて N 番目の美しい整数を出力してください．

入力例 1

3

出力例 1

110000020

美しい整数を小さい順に並べると，110000000, 110000010, 110000020, \ldots となります．

入力例 2

882436

出力例 2

998244353

入力例 3

2023

出力例 3

110200222

Score : 300 points

Problem Statement

A positive integer x is said to be a beautiful integer if and only if x is a 9-digit integer whose decimal notation S_1\ldots S_9 (S_i is the i-th character) satisfies all of the following conditions:

  • S_1 is not 0,
  • S_1 = S_2,
  • S_5 = S_6, and
  • S_7 = S_9.

For instance, 998244353 and 333333333 are beautiful integers, while 111112222 is not, since S_5 \neq S_6.

You are given a positive integer N. Print the N-th smallest beautiful integer.

Constraints

  • N is a positive integer.
  • There are at least N beautiful integers.

Input

The input is given from Standard Input in the following format:

N

Output

Print the N-th smallest beautiful integer.

Sample Input 1

3

Sample Output 1

110000020

The beautiful integers in ascending order are 110000000, 110000010, 110000020, \ldots.

Sample Input 2

882436

Sample Output 2

998244353

Sample Input 3

2023

Sample Output 3

110200222