Problem - 7789

回文串大家都知道吧，像$abcba$就是个回文串，$abcb$就不是个回文串。现在来了个加强版的回文，我们称之为“super回文”，满足下面三个条件的都是“super回文”串。
（1）  该串是回文串。
（2）  将该串从中间分开，左边部分依旧是个“super回文”。如果原始串是奇数长度，则最中间的字符不在左边部分。
（3）  相邻的数字都不一样。
现在小明和小红在玩游戏，小明在纸上写了个没有前导$0$的“super回文”数字串即本串仅包含数字，然后其又将该串中的某些位置上的数字用一个问号代替。他问小红，如果现在将所有满足情况的数字串按照数字的大小排序组成一个列表，则列表的第$K$个元素是什么？

第一行是一个整数$K(1 \leq k \leq 10^{18})$，即题目描述。
第二行是一个数字串，长度为$1$到$10000$，仅包含数字和问号。
当输入$k = 0$时程序结束。