Problem:


Score : 400 points

Problem Statement

A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:

In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1.

For example, 1234, 1, and 334 are lunlun numbers, while none of 31415, 119, or 13579 is.

You are given a positive integer K. Find the K-th smallest lunlun number.

Constraints

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer.

Sample Input 1

15

Sample Output 1

23

We will list the 15 smallest lunlun numbers in ascending order:

1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
21,
22,
23.

Thus, the answer is 23.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

13

Sample Output 3

21

Sample Input 4

100000

Sample Output 4

3234566667

Note that the answer may not fit into the 32-bit signed integer type.



Sample input:
15


Sample output:
23

Submission status: Runtime Error

Solution code:
l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66, 67, 76, 77, 78, 87, 88, 89, 98, 99, 100, 101, 110, 111, 112, 121, 122, 123, 210, 211, 212, 221, 222, 223, 232, 233, 234, 321, 322, 323, 332, 333, 334, 343, 344, 345, 432, 433, 434, 443, 444, 445, 454, 455, 456, 543, 544, 545, 554, 555, 556, 565, 566, 567, 654, 655, 656, 665, 666, 667, 676, 677, 678, 765, 766, 767, 776, 777, 778, 787, 788, 789, 876, 877, 878, 887, 888, 889, 898, 899, 987, 988, 989, 998, 999, 1000, 1001, 1010, 1011, 1012, 1100, 1101, 1110, 1111, 1112, 1121, 1122, 1123, 1210, 1211, 1212, 1221, 1222, 1223, 1232, 1233, 1234, 2100, 2101, 2110, 2111, 2112, 2121, 2122, 2123, 2210, 2211, 2212, 2221, 2222, 2223, 2232, 2233, 2234, 2321, 2322, 2323, 2332, 2333, 2334, 2343, 2344, 2345, 3210, 3211, 3212, 3221, 3222, 3223, 3232, 3233, 3234, 3321, 3322, 3323, 3332, 3333, 3334, 3343, 3344, 3345, 3432, 3433, 3434, 3443, 3444, 3445, 3454, 3455, 3456, 4321, 4322, 4323, 4332, 4333, 4334, 4343, 4344, 4345, 4432, 4433,4434, 4443, 4444, 4445, 4454, 4455, 4456, 4543, 4544, 4545, 4554, 4555, 4556, 4565, 4566, 4567, 5432, 5433, 5434, 5443, 5444, 5445, 5454, 5455, 5456, 5543, 5544, 5545, 5554, 5555, 5556, 5565, 5566, 5567, 5654, 5655, 5656, 5665, 5666, 5667, 5676, 5677, 5678, 6543, 6544, 6545, 6554, 6555, 6556, 6565, 6566, 6567, 6654, 6655, 6656, 6665, 6666, 6667, 6676, 6677, 6678, 6765, 6766, 6767, 6776, 6777, 6778, 6787, 6788, 6789, 7654, 7655, 7656, 7665, 7666, 7667, 7676, 7677, 7678, 7765, 7766, 7767, 7776, 7777, 7778, 7787, 7788, 7789, 7876, 7877, 7878, 7887, 7888, 7889, 7898, 7899, 8765, 8766, 8767, 8776, 8777, 8778, 8787, 8788, 8789, 8876, 8877, 8878, 8887, 8888, 8889, 8898, 8899, 8987, 8988, 8989, 8998, 8999, 9876, 9877, 9878, 9887, 9888, 9889, 9898, 9899, 9987, 9988, 9989, 9998, 9999, 10000, 10001, 10010, 10011, 10012, 10100, 10101, 10110, 10111, 10112, 10121, 10122, 10123, 11000, 11001, 11010, 11011, 11012, 11100, 11101, 11110, 11111, 11112, 11121, 11122, 11123, 11210, 11211, 11212, 11221, 11222, 11223, 11232, 11233, 11234, 12100, 12101, 12110, 12111, 12112, 12121, 12122, 12123, 12210, 12211, 12212, 12221, 12222, 12223, 12232, 12233, 12234, 12321, 12322, 12323, 12332, 12333, 12334, 12343, 12344, 12345, 21000, 21001, 21010, 21011, 21012, 21100, 21101, 21110, 21111, 21112, 21121, 21122, 21123, 21210, 21211, 21212, 21221, 21222, 21223, 21232, 21233, 21234, 22100, 22101, 22110, 22111, 22112, 22121, 22122, 22123, 22210, 22211, 22212, 22221, 22222, 22223, 22232, 22233, 22234, 22321, 22322, 22323, 22332, 22333, 22334, 22343, 22344, 22345, 23210, 23211, 23212, 23221, 23222, 23223, 23232, 23233, 23234, 23321, 23322, 23323, 23332, 23333, 23334, 23343, 23344, 23345, 23432, 23433, 23434, 23443, 23444, 23445, 23454, 23455, 23456, 32100, 32101, 32110, 32111, 32112, 32121, 32122, 32123, 32210, 32211, 32212, 32221, 32222, 32223, 32232, 32233, 32234, 32321, 32322, 32323, 32332, 32333, 32334, 32343, 32344, 32345, 33210, 33211, 33212, 33221, 33222, 33223, 33232, 33233, 33234, 33321, 33322, 33323, 33332, 33333, 33334, 33343, 33344, 33345, 33432, 33433, 33434, 33443, 33444, 33445, 33454, 33455, 33456, 34321, 34322, 34323, 34332, 34333, 34334, 34343, 34344, 34345, 34432, 34433, 34434, 34443, 34444, 34445, 34454, 34455, 34456, 34543, 34544, 34545, 34554, 34555, 34556, 34565, 34566, 34567, 43210, 43211, 43212, 43221, 43222, 43223, 43232, 43233, 43234, 43321, 43322, 43323, 43332, 43333, 43334, 43343, 43344, 43345, 43432, 43433, 43434, 43443, 43444, 43445, 43454, 43455, 43456, 44321, 44322, 44323, 44332, 44333, 44334, 44343, 44344, 44345, 44432, 44433, 44434, 44443, 44444, 44445, 44454, 44455, 44456, 44543, 44544, 44545, 44554, 44555, 44556, 44565, 44566, 44567, 45432, 45433, 45434, 45443, 45444, 45445, 45454, 45455, 45456, 45543, 45544, 45545, 45554, 45555, 45556, 45565, 45566, 45567, 45654, 45655, 45656, 45665, 45666, 45667, 45676, 45677, 45678, 54321, 54322, 54323, 54332, 54333, 54334, 54343, 54344, 54345, 54432, 54433, 54434, 54443, 54444, 54445, 54454, 54455, 54456, 54543, 54544, 54545, 54554, 54555, 54556, 54565, 54566, 54567, 55432, 55433, 55434, 55443, 55444, 55445, 55454, 55455, 55456, 55543, 55544, 55545, 55554, 55555, 55556, 55565, 55566, 55567, 55654, 55655, 55656, 55665, 55666, 55667, 55676, 55677, 55678, 56543, 56544, 56545, 56554, 56555, 56556, 56565, 56566, 56567, 56654, 56655, 56656, 56665, 56666, 56667, 56676, 56677, 56678, 56765, 56766, 56767, 56776, 56777, 56778, 56787, 56788, 56789, 65432, 65433, 65434, 65443, 65444, 65445, 65454, 65455, 65456, 65543, 65544, 65545, 65554, 65555, 65556, 65565, 65566, 65567, 65654, 65655, 65656, 65665, 65666, 65667, 65676, 65677, 65678, 66543, 66544, 66545, 66554, 66555, 66556, 66565, 66566, 66567, 66654, 66655, 66656, 66665, 66666, 66667, 66676, 66677, 66678, 66765, 66766, 66767, 66776, 66777, 66778, 66787, 66788, 66789, 67654, 67655, 67656, 67665, 67666, 67667, 67676, 67677, 67678, 67765, 67766, 67767, 67776, 67777, 67778, 67787, 67788, 67789, 67876, 67877, 67878, 67887, 67888, 67889, 67898, 67899, 76543, 76544, 76545, 76554, 76555, 76556, 76565, 76566, 76567, 76654, 76655, 76656, 76665, 76666, 76667, 76676, 76677, 76678, 76765, 76766, 76767, 76776, 76777, 76778, 76787, 76788, 76789, 77654, 77655, 77656, 77665, 77666, 77667, 77676, 77677, 77678, 77765, 77766, 77767, 77776, 77777, 77778, 77787, 77788, 77789, 77876, 77877, 77878, 77887, 77888, 77889, 77898, 77899, 78765, 78766, 78767, 78776, 78777, 78778, 78787, 78788, 78789, 78876, 78877, 78878, 78887, 78888, 78889, 78898, 78899, 78987, 78988, 78989, 78998, 78999, 87654, 87655, 87656, 87665, 87666, 87667, 87676, 87677, 87678, 87765, 87766, 87767, 87776, 87777, 87778, 87787, 87788, 87789, 87876, 87877, 87878, 87887, 87888, 87889, 87898, 87899, 88765, 88766, 88767, 88776, 88777, 88778, 88787, 88788, 88789, 88876, 88877, 88878, 88887, 88888, 88889, 88898, 88899, 88987, 88988, 88989, 88998, 88999, 89876, 89877, 89878, 89887, 89888, 89889, 89898, 89899, 89987, 89988, 89989, 89998, 89999, 98765, 98766, 98767, 98776, 98777, 98778, 98787, 98788, 98789, 98876, 98877, 98878, 98887, 98888, 98889, 98898, 98899, 98987, 98988, 98989, 98998, 98999, 99876, 99877, 99878, 99887, 99888, 99889, 99898, 99899, 99987, 99988, 99989, 99998, 99999100000, 100001, 100010, 100011, 100012, 100100, 100101, 100110, 100111, 100112, 100121, 100122, 100123, 101000, 101001, 101010, 101011, 101012, 101100, 101101, 101110, 101111, 101112, 101121, 101122, 101123, 101210, 101211, 101212, 101221, 101222, 101223, 101232, 101233, 101234, 110000, 110001, 110010, 110011, 110012, 110100, 110101, 110110, 110111, 110112, 110121, 110122, 110123, 111000, 111001, 111010, 111011, 111012, 111100, 111101, 111110, 111111, 111112, 111121, 111122, 111123, 111210, 111211, 111212, 111221, 111222, 111223, 111232, 111233, 111234, 112100, 112101, 112110, 112111, 112112, 112121, 112122, 112123, 112210, 112211, 112212, 112221, 112222, 112223, 112232, 112233, 112234, 112321, 112322, 112323, 112332, 112333, 112334, 112343, 112344, 112345, 121000, 121001, 121010, 121011, 121012, 121100, 121101, 121110, 121111, 121112, 121121, 121122, 121123, 121210, 121211, 121212, 121221, 121222, 121223, 121232, 121233, 121234, 122100, 122101, 122110, 122111, 122112, 122121, 122122, 122123, 122210, 122211, 122212, 122221, 122222, 122223, 122232, 122233, 122234, 122321, 122322, 122323, 122332, 122333, 122334, 122343, 122344, 122345, 123210, 123211, 123212, 123221, 123222, 123223, 123232, 123233, 123234, 123321, 123322, 123323, 123332, 123333, 123334, 123343, 123344, 123345, 123432, 123433, 123434, 123443, 123444, 123445, 123454, 123455, 123456, 210000, 210001, 210010, 210011, 210012, 210100, 210101, 210110, 210111, 210112, 210121, 210122, 210123, 211000, 211001, 211010, 211011, 211012, 211100, 211101, 211110, 211111, 211112, 211121, 211122, 211123, 211210, 211211, 211212, 211221, 211222, 211223, 211232, 211233, 211234, 212100, 212101, 212110, 212111, 212112, 212121, 212122, 212123, 212210, 212211, 212212, 212221, 212222, 212223, 212232, 212233, 212234, 212321, 212322, 212323, 212332, 212333, 212334, 212343, 212344, 212345, 221000, 221001, 221010, 221011, 221012, 221100, 221101, 221110, 221111, 221112, 221121, 221122, 221123, 221210, 221211, 221212, 221221, 221222, 221223, 221232, 221233, 221234, 222100, 222101, 222110, 222111, 222112, 222121, 222122, 222123, 222210, 222211, 222212, 222221, 222222, 222223, 222232, 222233, 222234, 222321, 222322, 222323, 222332, 222333, 222334, 222343, 222344, 222345, 223210, 223211, 223212, 223221, 223222, 223223, 223232, 223233, 223234, 223321, 223322, 223323, 223332, 223333, 223334, 223343, 223344, 223345, 223432, 223433, 223434, 223443, 223444, 223445, 223454, 223455, 223456, 232100, 232101, 232110, 232111, 232112, 232121, 232122, 232123, 232210, 232211, 232212, 232221, 232222, 232223, 232232, 232233, 232234, 232321, 232322, 232323, 232332, 232333, 232334, 232343, 232344, 232345, 233210, 233211, 233212, 233221, 233222, 233223, 233232, 233233, 233234, 233321, 233322, 233323, 233332, 233333, 233334, 233343, 233344, 233345, 233432, 233433, 233434, 233443, 233444, 233445, 233454, 233455, 233456, 234321, 234322, 234323, 234332, 234333, 234334, 234343, 234344, 234345, 234432, 234433, 234434, 234443, 234444, 234445, 234454, 234455, 234456, 234543, 234544, 234545, 234554, 234555, 234556, 234565, 234566, 234567, 321000, 321001, 321010, 321011, 321012, 321100, 321101, 321110, 321111, 321112, 321121, 321122, 321123, 321210, 321211, 321212, 321221, 321222, 321223, 321232, 321233, 321234, 322100, 322101, 322110, 322111, 322112, 322121, 322122, 322123, 322210, 322211, 322212, 322221, 322222, 322223, 322232, 322233, 322234, 322321, 322322, 322323, 322332, 322333, 322334, 322343, 322344, 322345, 323210, 323211, 323212, 323221, 323222, 323223, 323232, 323233, 323234, 323321, 323322, 323323, 323332, 323333, 323334, 323343, 323344, 323345, 323432, 323433, 323434, 323443, 323444, 323445, 323454, 323455, 323456, 332100, 332101, 332110, 332111, 332112, 332121, 332122, 332123, 332210, 332211, 332212, 332221, 332222, 332223, 332232, 332233, 332234, 332321, 332322, 332323, 332332, 332333, 332334, 332343, 332344, 332345, 333210, 333211, 333212, 333221, 333222, 333223, 333232, 333233, 333234, 333321, 333322, 333323, 333332, 333333, 333334, 333343, 333344, 333345, 333432, 333433, 333434, 333443, 333444, 333445, 333454, 333455, 333456, 334321, 334322, 334323, 334332, 334333, 334334, 334343, 334344, 334345, 334432, 334433, 334434, 334443, 334444, 334445, 334454, 334455, 334456, 334543, 334544, 334545, 334554, 334555, 334556, 334565, 334566, 334567, 343210, 343211, 343212, 343221, 343222, 343223, 343232, 343233, 343234, 343321, 343322, 343323, 343332, 343333, 343334, 343343, 343344, 343345, 343432, 343433, 343434, 343443, 343444, 343445, 343454, 343455, 343456, 344321, 344322, 344323, 344332, 344333, 344334, 344343, 344344, 344345, 344432, 344433, 344434, 344443, 344444, 344445, 344454, 344455, 344456, 344543, 344544, 344545, 344554, 344555, 344556, 344565, 344566, 344567, 345432, 345433, 345434, 345443, 345444, 345445, 345454, 345455, 345456, 345543, 345544, 345545, 345554, 345555, 345556, 345565, 345566, 345567, 345654, 345655, 345656, 345665, 345666, 345667, 345676, 345677, 345678, 432100, 432101, 432110, 432111, 432112, 432121, 432122, 432123, 432210, 432211, 432212, 432221, 432222, 432223, 432232, 432233, 432234, 432321, 432322, 432323, 432332, 432333, 432334, 432343, 432344, 432345, 433210, 433211, 433212, 433221, 433222, 433223, 433232, 433233, 433234, 433321, 433322, 433323, 433332, 433333, 433334, 433343, 433344, 433345, 433432, 433433, 433434, 433443, 433444, 433445, 433454, 433455, 433456, 434321, 434322, 434323, 434332, 434333, 434334, 434343, 434344, 434345, 434432, 434433, 434434, 434443, 434444, 434445, 434454, 434455, 434456, 434543, 434544, 434545, 434554, 434555, 434556, 434565, 434566, 434567, 443210, 443211, 443212, 443221, 443222, 443223, 443232, 443233, 443234, 443321, 443322, 443323, 443332, 443333, 443334, 443343, 443344, 443345, 443432, 443433, 443434, 443443, 443444, 443445, 443454, 443455, 443456, 444321, 444322, 444323, 444332, 444333, 444334, 444343, 444344, 444345, 444432, 444433, 444434, 444443, 444444, 444445, 444454, 444455, 444456, 444543, 444544, 444545, 444554, 444555, 444556, 444565, 444566, 444567, 445432, 445433, 445434, 445443, 445444, 445445, 445454, 445455, 445456, 445543, 445544, 445545, 445554, 445555, 445556, 445565, 445566, 445567, 445654, 445655, 445656, 445665, 445666, 445667, 445676, 445677, 445678, 454321, 454322, 454323, 454332, 454333, 454334, 454343, 454344, 454345, 454432, 454433, 454434, 454443, 454444, 454445, 454454, 454455, 454456, 454543, 454544, 454545, 454554, 454555, 454556, 454565, 454566, 454567, 455432, 455433, 455434, 455443, 455444, 455445, 455454, 455455, 455456, 455543, 455544, 455545, 455554, 455555, 455556, 455565, 455566, 455567, 455654, 455655, 455656, 455665, 455666, 455667, 455676, 455677, 455678, 456543, 456544, 456545, 456554, 456555, 456556, 456565, 456566, 456567, 456654, 456655, 456656, 456665, 456666, 456667, 456676, 456677, 456678, 456765, 456766, 456767, 456776, 456777, 456778, 456787, 456788, 456789, 543210, 543211, 543212, 543221, 543222, 543223, 543232, 543233, 543234, 543321, 543322, 543323, 543332, 543333, 543334, 543343, 543344, 543345, 543432, 543433, 543434, 543443, 543444, 543445, 543454, 543455, 543456, 544321, 544322, 544323, 544332, 544333, 544334, 544343, 544344, 544345, 544432, 544433, 544434, 544443, 544444, 544445, 544454, 544455, 544456, 544543, 544544, 544545, 544554, 544555, 544556, 544565, 544566, 544567, 545432, 545433, 545434, 545443, 545444, 545445, 545454, 545455, 545456, 545543, 545544, 545545, 545554, 545555, 545556, 545565, 545566, 545567, 545654, 545655, 545656, 545665, 545666, 545667, 545676, 545677, 545678, 554321, 554322, 554323, 554332, 554333, 554334, 554343, 554344, 554345, 554432, 554433, 554434, 554443, 554444, 554445, 554454, 554455, 554456, 554543, 554544, 554545, 554554, 554555, 554556, 554565, 554566, 554567, 555432, 555433, 555434, 555443, 555444, 555445, 555454, 555455, 555456, 555543, 555544, 555545, 555554, 555555, 555556, 555565, 555566, 555567, 555654, 555655, 555656, 555665, 555666, 555667, 555676, 555677, 555678, 556543, 556544, 556545, 556554, 556555, 556556, 556565, 556566, 556567, 556654, 556655, 556656, 556665, 556666, 556667, 556676, 556677, 556678, 556765, 556766, 556767, 556776, 556777, 556778, 556787, 556788, 556789, 565432, 565433, 565434, 565443, 565444, 565445, 565454, 565455, 565456, 565543, 565544, 565545, 565554, 565555, 565556, 565565, 565566, 565567, 565654, 565655, 565656, 565665, 565666, 565667, 565676, 565677, 565678, 566543, 566544, 566545, 566554, 566555, 566556, 566565, 566566, 566567, 566654, 566655, 566656, 566665, 566666, 566667, 566676, 566677, 566678, 566765, 566766, 566767, 566776, 566777, 566778, 566787, 566788, 566789, 567654, 567655, 567656, 567665, 567666, 567667, 567676, 567677, 567678, 567765, 567766, 567767, 567776, 567777, 567778, 567787, 567788, 567789, 567876, 567877, 567878, 567887, 567888, 567889, 567898, 567899, 654321, 654322, 654323, 654332, 654333, 654334, 654343, 654344, 654345, 654432, 654433, 654434, 654443, 654444, 654445, 654454, 654455, 654456, 654543, 654544, 654545, 654554, 654555, 654556, 654565, 654566, 654567, 655432, 655433, 655434, 655443, 655444, 655445, 655454, 655455, 655456, 655543, 655544, 655545, 655554, 655555, 655556, 655565, 655566, 655567, 655654, 655655, 655656, 655665, 655666, 655667, 655676, 655677, 655678, 656543, 656544, 656545, 656554, 656555, 656556, 656565, 656566, 656567, 656654, 656655, 656656, 656665, 656666, 656667, 656676, 656677, 656678, 656765, 656766, 656767, 656776, 656777, 656778, 656787, 656788, 656789, 665432, 665433, 665434, 665443, 665444, 665445, 665454, 665455, 665456, 665543, 665544, 665545, 665554, 665555, 665556, 665565, 665566, 665567, 665654, 665655, 665656, 665665, 665666, 665667, 665676, 665677, 665678, 666543, 666544, 666545, 666554, 666555, 666556, 666565, 666566, 666567, 666654, 666655, 666656, 666665, 666666, 666667, 666676, 666677, 666678, 666765, 666766, 666767, 666776, 666777, 666778, 666787, 666788, 666789, 667654, 667655, 667656, 667665, 667666, 667667, 667676, 667677, 667678, 667765, 667766, 667767, 667776, 667777, 667778, 667787, 667788, 667789, 667876, 667877, 667878, 667887, 667888, 667889, 667898, 667899, 676543, 676544, 676545, 676554, 676555, 676556, 676565, 676566, 676567, 676654, 676655, 676656, 676665, 676666, 676667, 676676, 676677, 676678, 676765, 676766, 676767, 676776, 676777, 676778, 676787, 676788, 676789, 677654, 677655, 677656, 677665, 677666, 677667, 677676, 677677, 677678, 677765, 677766, 677767, 677776, 677777, 677778, 677787, 677788, 677789, 677876, 677877, 677878, 677887, 677888, 677889, 677898, 677899, 678765, 678766, 678767, 678776, 678777, 678778, 678787, 678788, 678789, 678876, 678877, 678878, 678887, 678888, 678889, 678898, 678899, 678987, 678988, 678989, 678998, 678999, 765432, 765433, 765434, 765443, 765444, 765445, 765454, 765455, 765456, 765543, 765544, 765545, 765554, 765555, 765556, 765565, 765566, 765567, 765654, 765655, 765656, 765665, 765666, 765667, 765676, 765677, 765678, 766543, 766544, 766545, 766554, 766555, 766556, 766565, 766566, 766567, 766654, 766655, 766656, 766665, 766666, 766667, 766676, 766677, 766678, 766765, 766766, 766767, 766776, 766777, 766778, 766787, 766788, 766789, 767654, 767655, 767656, 767665, 767666, 767667, 767676, 767677, 767678, 767765, 767766, 767767, 767776, 767777, 767778, 767787, 767788, 767789, 767876, 767877, 767878, 767887, 767888, 767889, 767898, 767899, 776543, 776544, 776545, 776554, 776555, 776556, 776565, 776566, 776567, 776654, 776655, 776656, 776665, 776666, 776667, 776676, 776677, 776678, 776765, 776766, 776767, 776776, 776777, 776778, 776787, 776788, 776789, 777654, 777655, 777656, 777665, 777666, 777667, 777676, 777677, 777678, 777765, 777766, 777767, 777776, 777777, 777778, 777787, 777788, 777789, 777876, 777877, 777878, 777887, 777888, 777889, 777898, 777899, 778765, 778766, 778767, 778776, 778777, 778778, 778787, 778788, 778789, 778876, 778877, 778878, 778887, 778888, 778889, 778898, 778899, 778987, 778988, 778989, 778998, 778999, 787654, 787655, 787656, 787665, 787666, 787667, 787676, 787677, 787678, 787765, 787766, 787767, 787776, 787777, 787778, 787787, 787788, 787789, 787876, 787877, 787878, 787887, 787888, 787889, 787898, 787899, 788765, 788766, 788767, 788776, 788777, 788778, 788787, 788788, 788789, 788876, 788877, 788878, 788887, 788888, 788889, 788898, 788899, 788987, 788988, 788989, 788998, 788999, 789876, 789877, 789878, 789887, 789888, 789889, 789898, 789899, 789987, 789988, 789989, 789998, 789999, 876543, 876544, 876545, 876554, 876555, 876556, 876565, 876566, 876567, 876654, 876655, 876656, 876665, 876666, 876667, 876676, 876677, 876678, 876765, 876766, 876767, 876776, 876777, 876778, 876787, 876788, 876789, 877654, 877655, 877656, 877665, 877666, 877667, 877676, 877677, 877678, 877765, 877766, 877767, 877776, 877777, 877778, 877787, 877788, 877789, 877876, 877877, 877878, 877887, 877888, 877889, 877898, 877899, 878765, 878766, 878767, 878776, 878777, 878778, 878787, 878788, 878789, 878876, 878877, 878878, 878887, 878888, 878889, 878898, 878899, 878987, 878988, 878989, 878998, 878999, 887654, 887655, 887656, 887665, 887666, 887667, 887676, 887677, 887678, 887765, 887766, 887767, 887776, 887777, 887778, 887787, 887788, 887789, 887876, 887877, 887878, 887887, 887888, 887889, 887898, 887899, 888765, 888766, 888767, 888776, 888777, 888778, 888787, 888788, 888789, 888876, 888877, 888878, 888887, 888888, 888889, 888898, 888899, 888987, 888988, 888989, 888998, 888999, 889876, 889877, 889878, 889887, 889888, 889889, 889898, 889899, 889987, 889988, 889989, 889998, 889999, 898765, 898766, 898767, 898776, 898777, 898778, 898787, 898788, 898789, 898876, 898877, 898878, 898887, 898888, 898889, 898898, 898899, 898987, 898988, 898989, 898998, 898999, 899876, 899877, 899878, 899887, 899888, 899889, 899898, 899899, 899987, 899988, 899989, 899998, 899999, 987654, 987655, 987656, 987665, 987666, 987667, 987676, 987677, 987678, 987765, 987766, 987767, 987776, 987777, 987778, 987787, 987788, 987789, 987876, 987877, 987878, 987887, 987888, 987889, 987898, 987899, 988765, 988766, 988767, 988776, 988777, 988778, 988787, 988788, 988789, 988876, 988877, 988878, 988887, 988888, 988889, 988898, 988899, 988987, 988988, 988989, 988998, 988999, 989876, 989877, 989878, 989887, 989888, 989889, 989898, 989899, 989987, 989988, 989989, 989998, 989999, 998765, 998766, 998767, 998776, 998777, 998778, 998787, 998788, 998789, 998876, 998877, 998878, 998887, 998888, 998889, 998898, 998899, 998987, 998988, 998989, 998998, 998999, 999876, 999877, 999878, 999887, 999888, 999889, 999898, 999899, 999987, 999988, 999989, 999998, 999999, 1000000, 1000001, 1000010, 1000011, 1000012, 1000100, 1000101, 1000110, 1000111, 1000112, 1000121, 1000122, 1000123, 1001000, 1001001, 1001010, 1001011, 1001012, 1001100, 1001101, 1001110, 1001111, 1001112, 1001121, 1001122, 1001123, 1001210, 1001211, 1001212, 1001221, 1001222, 1001223, 1001232, 1001233, 1001234, 1010000, 1010001, 1010010, 1010011, 1010012, 1010100, 1010101, 1010110, 1010111, 1010112, 1010121, 1010122, 1010123, 1011000, 1011001, 1011010, 1011011, 1011012, 1011100, 1011101, 1011110, 1011111, 1011112, 1011121, 1011122, 1011123, 1011210, 1011211, 1011212, 1011221, 1011222, 1011223, 1011232, 1011233, 1011234, 1012100, 1012101, 1012110, 1012111, 1012112, 1012121, 1012122, 1012123, 1012210, 1012211, 1012212, 1012221, 1012222, 1012223, 1012232, 1012233, 1012234, 1012321, 1012322, 1012323, 1012332, 1012333, 1012334, 1012343, 1012344, 1012345, 1100000, 1100001, 1100010, 1100011, 1100012, 1100100, 1100101, 1100110, 1100111, 1100112, 1100121, 1100122, 1100123, 1101000, 1101001, 1101010, 1101011, 1101012, 1101100, 1101101, 1101110, 1101111, 1101112, 1101121, 1101122, 1101123, 1101210, 1101211, 1101212, 1101221, 1101222, 1101223, 1101232, 1101233, 1101234, 1110000, 1110001, 1110010, 1110011, 1110012, 1110100, 1110101, 1110110, 1110111, 1110112, 1110121, 1110122, 1110123, 1111000, 1111001, 1111010, 1111011, 1111012, 1111100, 1111101, 1111110, 1111111, 1111112, 1111121, 1111122, 1111123, 1111210, 1111211, 1111212, 1111221, 1111222, 1111223, 1111232, 1111233, 1111234, 1112100, 1112101, 1112110, 1112111, 1112112, 1112121, 1112122, 1112123, 1112210, 1112211, 1112212, 1112221, 1112222, 1112223, 1112232, 1112233, 1112234, 1112321, 1112322, 1112323, 1112332, 1112333, 1112334, 1112343, 1112344, 1112345, 1121000, 1121001, 1121010, 1121011, 1121012, 1121100, 1121101, 1121110, 1121111, 1121112, 1121121, 1121122, 1121123, 1121210, 1121211, 1121212, 1121221, 1121222, 1121223, 1121232, 1121233, 1121234, 1122100, 1122101, 1122110, 1122111, 1122112, 1122121, 1122122, 1122123, 1122210, 1122211, 1122212, 1122221, 1122222, 1122223, 1122232, 1122233, 1122234, 1122321, 1122322, 1122323, 1122332, 1122333, 1122334, 1122343, 1122344, 1122345, 1123210, 1123211, 1123212, 1123221, 1123222, 1123223, 1123232, 1123233, 1123234, 1123321, 1123322, 1123323, 1123332, 1123333, 1123334, 1123343, 1123344, 1123345, 1123432, 1123433, 1123434, 1123443, 1123444, 1123445, 1123454, 1123455, 1123456, 1210000, 1210001, 1210010, 1210011, 1210012, 1210100, 1210101, 1210110, 1210111, 1210112, 1210121, 1210122, 1210123, 1211000, 1211001, 1211010, 1211011, 1211012, 1211100, 1211101, 1211110, 1211111, 1211112, 1211121, 1211122, 1211123, 1211210, 1211211, 1211212, 1211221, 1211222, 1211223, 1211232, 1211233, 1211234, 1212100, 1212101, 1212110, 1212111, 1212112, 1212121, 1212122, 1212123, 1212210, 1212211, 1212212, 1212221, 1212222, 1212223, 1212232, 1212233, 1212234, 1212321, 1212322, 1212323, 1212332, 1212333, 1212334, 1212343, 1212344, 1212345, 1221000, 1221001, 1221010, 1221011, 1221012, 1221100, 1221101, 1221110, 1221111, 1221112, 1221121, 1221122, 1221123, 1221210, 1221211, 1221212, 1221221, 1221222, 1221223, 1221232, 1221233, 1221234, 1222100, 1222101, 1222110, 1222111, 1222112, 1222121, 1222122, 1222123, 1222210, 1222211, 1222212, 1222221, 1222222, 1222223, 1222232, 1222233, 1222234, 1222321, 1222322, 1222323, 1222332, 1222333, 1222334, 1222343, 1222344, 1222345, 1223210, 1223211, 1223212, 1223221, 1223222, 1223223, 1223232, 1223233, 1223234, 1223321, 1223322, 1223323, 1223332, 1223333, 1223334, 1223343, 1223344, 1223345, 1223432, 1223433, 1223434, 1223443, 1223444, 1223445, 1223454, 1223455, 1223456, 1232100, 1232101, 1232110, 1232111, 1232112, 1232121, 1232122, 1232123, 1232210, 1232211, 1232212, 1232221, 1232222, 1232223, 1232232, 1232233, 1232234, 1232321, 1232322, 1232323, 1232332, 1232333, 1232334, 1232343, 1232344, 1232345, 1233210, 1233211, 1233212, 1233221, 1233222, 1233223, 1233232, 1233233, 1233234, 1233321, 1233322, 1233323, 1233332, 1233333, 1233334, 1233343, 1233344, 1233345, 1233432, 1233433, 1233434, 1233443, 1233444, 1233445, 1233454, 1233455, 1233456, 1234321, 1234322, 1234323, 1234332, 1234333, 1234334, 1234343, 1234344, 1234345, 1234432, 1234433, 1234434, 1234443, 1234444, 1234445, 1234454, 1234455, 1234456, 1234543, 1234544, 1234545, 1234554, 1234555, 1234556, 1234565, 1234566, 1234567, 2100000, 2100001, 2100010, 2100011, 2100012, 2100100, 2100101, 2100110, 2100111, 2100112, 2100121, 2100122, 2100123, 2101000, 2101001, 2101010, 2101011, 2101012, 2101100, 2101101, 2101110, 2101111, 2101112, 2101121, 2101122, 2101123, 2101210, 2101211, 2101212, 2101221, 2101222, 2101223, 2101232, 2101233, 2101234, 2110000, 2110001, 2110010, 2110011, 2110012, 2110100, 2110101, 2110110, 2110111, 2110112, 2110121, 2110122, 2110123, 2111000, 2111001, 2111010, 2111011, 2111012, 2111100, 2111101, 2111110, 2111111, 2111112, 2111121, 2111122, 2111123, 2111210, 2111211, 2111212, 2111221, 2111222, 2111223, 2111232, 2111233, 2111234, 2112100, 2112101, 2112110, 2112111, 2112112, 2112121, 2112122, 2112123, 2112210, 2112211, 2112212, 2112221, 2112222, 2112223, 2112232, 2112233, 2112234, 2112321, 2112322, 2112323, 2112332, 2112333, 2112334, 2112343, 2112344, 2112345, 2121000, 2121001, 2121010, 2121011, 2121012, 2121100, 2121101, 2121110, 2121111, 2121112, 2121121, 2121122, 2121123, 2121210, 2121211, 2121212, 2121221, 2121222, 2121223, 2121232, 2121233, 2121234, 2122100, 2122101, 2122110, 2122111, 2122112, 2122121, 2122122, 2122123, 2122210, 2122211, 2122212, 2122221, 2122222, 2122223, 2122232, 2122233, 2122234, 2122321, 2122322, 2122323, 2122332, 2122333, 2122334, 2122343, 2122344, 2122345, 2123210, 2123211, 2123212, 2123221, 2123222, 2123223, 2123232, 2123233, 2123234, 2123321, 2123322, 2123323, 2123332, 2123333, 2123334, 2123343, 2123344, 2123345, 2123432, 2123433, 2123434, 2123443, 2123444, 2123445, 2123454, 2123455, 2123456, 2210000, 2210001, 2210010, 2210011, 2210012, 2210100, 2210101, 2210110, 2210111, 2210112, 2210121, 2210122, 2210123, 2211000, 2211001, 2211010, 2211011, 2211012, 2211100, 2211101, 2211110, 2211111, 2211112, 2211121, 2211122, 2211123, 2211210, 2211211, 2211212, 2211221, 2211222, 2211223, 2211232, 2211233, 2211234, 2212100, 2212101, 2212110, 2212111, 2212112, 2212121, 2212122, 2212123, 2212210, 2212211, 2212212, 2212221, 2212222, 2212223, 2212232, 2212233, 2212234, 2212321, 2212322, 2212323, 2212332, 2212333, 2212334, 2212343, 2212344, 2212345, 2221000, 2221001, 2221010, 2221011, 2221012, 2221100, 2221101, 2221110, 2221111, 2221112, 2221121, 2221122, 2221123, 2221210, 2221211, 2221212, 2221221, 2221222, 2221223, 2221232, 2221233, 2221234, 2222100, 2222101, 2222110, 2222111, 2222112, 2222121, 2222122, 2222123, 2222210, 2222211, 2222212, 2222221, 2222222, 2222223, 2222232, 2222233, 2222234, 2222321, 2222322, 2222323, 2222332, 2222333, 2222334, 2222343, 2222344, 2222345, 2223210, 2223211, 2223212, 2223221, 2223222, 2223223, 2223232, 2223233, 2223234, 2223321, 2223322, 2223323, 2223332, 2223333, 2223334, 2223343, 2223344, 2223345, 2223432, 2223433, 2223434, 2223443, 2223444, 2223445, 2223454, 2223455, 2223456, 2232100, 2232101, 2232110, 2232111, 2232112, 2232121, 2232122, 2232123, 2232210, 2232211, 2232212, 2232221, 2232222, 2232223, 2232232, 2232233, 2232234, 2232321, 2232322, 2232323, 2232332, 2232333, 2232334, 2232343, 2232344, 2232345, 2233210, 2233211, 2233212, 2233221, 2233222, 2233223, 2233232, 2233233, 2233234, 2233321, 2233322, 2233323, 2233332, 2233333, 2233334, 2233343, 2233344, 2233345, 2233432, 2233433, 2233434, 2233443, 2233444, 2233445, 2233454, 2233455, 2233456, 2234321, 2234322, 2234323, 2234332, 2234333, 2234334, 2234343, 2234344, 2234345, 2234432, 2234433, 2234434, 2234443, 2234444, 2234445, 2234454, 2234455, 2234456, 2234543, 2234544, 2234545, 2234554, 2234555, 2234556, 2234565, 2234566, 2234567, 2321000, 2321001, 2321010, 2321011, 2321012, 2321100, 2321101, 2321110, 2321111, 2321112, 2321121, 2321122, 2321123, 2321210, 2321211, 2321212, 2321221, 2321222, 2321223, 2321232, 2321233, 2321234, 2322100, 2322101, 2322110, 2322111, 2322112, 2322121, 2322122, 2322123, 2322210, 2322211, 2322212, 2322221, 2322222, 2322223, 2322232, 2322233, 2322234, 2322321, 2322322, 2322323, 2322332, 2322333, 2322334, 2322343, 2322344, 2322345, 2323210, 2323211, 2323212, 2323221, 2323222, 2323223, 2323232, 2323233, 2323234, 2323321, 2323322, 2323323, 2323332, 2323333, 2323334, 2323343, 2323344, 2323345, 2323432, 2323433, 2323434, 2323443, 2323444, 2323445, 2323454, 2323455, 2323456, 2332100, 2332101, 2332110, 2332111, 2332112, 2332121, 2332122, 2332123, 2332210, 2332211, 2332212, 2332221, 2332222, 2332223, 2332232, 2332233, 2332234, 2332321, 2332322, 2332323, 2332332, 2332333, 2332334, 2332343, 2332344, 2332345, 2333210, 2333211, 2333212, 2333221, 2333222, 2333223, 2333232, 2333233, 2333234, 2333321, 2333322, 2333323, 2333332, 2333333, 2333334, 2333343, 2333344, 2333345, 2333432, 2333433, 2333434, 2333443, 2333444, 2333445, 2333454, 2333455, 2333456, 2334321, 2334322, 2334323, 2334332, 2334333, 2334334, 2334343, 2334344, 2334345, 2334432, 2334433, 2334434, 2334443, 2334444, 2334445, 2334454, 2334455, 2334456, 2334543, 2334544, 2334545, 2334554, 2334555, 2334556, 2334565, 2334566, 2334567, 2343210, 2343211, 2343212, 2343221, 2343222, 2343223, 2343232, 2343233, 2343234, 2343321, 2343322, 2343323, 2343332, 2343333, 2343334, 2343343, 2343344, 2343345, 2343432, 2343433, 2343434, 2343443, 2343444, 2343445, 2343454, 2343455, 2343456, 2344321, 2344322, 2344323, 2344332, 2344333, 2344334, 2344343, 2344344, 2344345, 2344432, 2344433, 2344434, 2344443, 2344444, 2344445, 2344454, 2344455, 2344456, 2344543, 2344544, 2344545, 2344554, 2344555, 2344556, 2344565, 2344566, 2344567, 2345432, 2345433, 2345434, 2345443, 2345444, 2345445, 2345454, 2345455, 2345456, 2345543, 2345544, 2345545, 2345554, 2345555, 2345556, 2345565, 2345566, 2345567, 2345654, 2345655, 2345656, 2345665, 2345666, 2345667, 2345676, 2345677, 2345678, 3210000, 3210001, 3210010, 3210011, 3210012, 3210100, 3210101, 3210110, 3210111, 3210112, 3210121, 3210122, 3210123, 3211000, 3211001, 3211010, 3211011, 3211012, 3211100, 3211101, 3211110, 3211111, 3211112, 3211121, 3211122, 3211123, 3211210, 3211211, 3211212, 3211221, 3211222, 3211223, 3211232, 3211233, 3211234, 3212100, 3212101, 3212110, 3212111, 3212112, 3212121, 3212122, 3212123, 3212210, 3212211, 3212212, 3212221, 3212222, 3212223, 3212232, 3212233, 3212234, 3212321, 3212322, 3212323, 3212332, 3212333, 3212334, 3212343, 3212344, 3212345, 3221000, 3221001, 3221010, 3221011, 3221012, 3221100, 3221101, 3221110, 3221111, 3221112, 3221121, 3221122, 3221123, 3221210, 3221211, 3221212, 3221221, 3221222, 3221223, 3221232, 3221233, 3221234, 3222100, 3222101, 3222110, 3222111, 3222112, 3222121, 3222122, 3222123, 3222210, 3222211, 3222212, 3222221, 3222222, 3222223, 3222232, 3222233, 3222234, 3222321, 3222322, 3222323, 3222332, 3222333, 3222334, 3222343, 3222344, 3222345, 3223210, 3223211, 3223212, 3223221, 3223222, 3223223, 3223232, 3223233, 3223234, 3223321, 3223322, 3223323, 3223332, 3223333, 3223334, 3223343, 3223344, 3223345, 3223432, 3223433, 3223434, 3223443, 3223444, 3223445, 3223454, 3223455, 3223456, 3232100, 3232101, 3232110, 3232111, 3232112, 3232121, 3232122, 3232123, 3232210, 3232211, 3232212, 3232221, 3232222, 3232223, 3232232, 3232233, 3232234, 3232321, 3232322, 3232323, 3232332, 3232333, 3232334, 3232343, 3232344, 3232345, 3233210, 3233211, 3233212, 3233221, 3233222, 3233223, 3233232, 3233233, 3233234, 3233321, 3233322, 3233323, 3233332, 3233333, 3233334, 3233343, 3233344, 3233345, 3233432, 3233433, 3233434, 3233443, 3233444, 3233445, 3233454, 3233455, 3233456, 3234321, 3234322, 3234323, 3234332, 3234333, 3234334, 3234343, 3234344, 3234345, 3234432, 3234433, 3234434, 3234443, 3234444, 3234445, 3234454, 3234455, 3234456, 3234543, 3234544, 3234545, 3234554, 3234555, 3234556, 3234565, 3234566, 3234567, 3321000, 3321001, 3321010, 3321011, 3321012, 3321100, 3321101, 3321110, 3321111, 3321112, 3321121, 3321122, 3321123, 3321210, 3321211, 3321212, 3321221, 3321222, 3321223, 3321232, 3321233, 3321234, 3322100, 3322101, 3322110, 3322111, 3322112, 3322121, 3322122, 3322123, 3322210, 3322211, 3322212, 3322221, 3322222, 3322223, 3322232, 3322233, 3322234, 3322321, 3322322, 3322323, 3322332, 3322333, 3322334, 3322343, 3322344, 3322345, 3323210, 3323211, 3323212, 3323221, 3323222, 3323223, 3323232, 3323233, 3323234, 3323321, 3323322, 3323323, 3323332, 3323333, 3323334, 3323343, 3323344, 3323345, 3323432, 3323433, 3323434, 3323443, 3323444, 3323445, 3323454, 3323455, 3323456, 3332100, 3332101, 3332110, 3332111, 3332112, 3332121, 3332122, 3332123, 3332210, 3332211, 3332212, 3332221, 3332222, 3332223, 3332232, 3332233, 3332234, 3332321, 3332322, 3332323, 3332332, 3332333, 3332334, 3332343, 3332344, 3332345, 3333210, 3333211, 3333212, 3333221, 3333222, 3333223, 3333232, 3333233, 3333234, 3333321, 3333322, 3333323, 3333332, 3333333, 3333334, 3333343, 3333344, 3333345, 3333432, 3333433, 3333434, 3333443, 3333444, 3333445, 3333454, 3333455, 3333456, 3334321, 3334322, 3334323, 3334332, 3334333, 3334334, 3334343, 3334344, 3334345, 3334432, 3334433, 3334434, 3334443, 3334444, 3334445, 3334454, 3334455, 3334456, 3334543, 3334544, 3334545, 3334554, 3334555, 3334556, 3334565, 3334566, 3334567, 3343210, 3343211, 3343212, 3343221, 3343222, 3343223, 3343232, 3343233, 3343234, 3343321, 3343322, 3343323, 3343332, 3343333, 3343334, 3343343, 3343344, 3343345, 3343432, 3343433, 3343434, 3343443, 3343444, 3343445, 3343454, 3343455, 3343456, 3344321, 3344322, 3344323, 3344332, 3344333, 3344334, 3344343, 3344344, 3344345, 3344432, 3344433, 3344434, 3344443, 3344444, 3344445, 3344454, 3344455, 3344456, 3344543, 3344544, 3344545, 3344554, 3344555, 3344556, 3344565, 3344566, 3344567, 3345432, 3345433, 3345434, 3345443, 3345444, 3345445, 3345454, 3345455, 3345456, 3345543, 3345544, 3345545, 3345554, 3345555, 3345556, 3345565, 3345566, 3345567, 3345654, 3345655, 3345656, 3345665, 3345666, 3345667, 3345676, 3345677, 3345678, 3432100, 3432101, 3432110, 3432111, 3432112, 3432121, 3432122, 3432123, 3432210, 3432211, 3432212, 3432221, 3432222, 3432223, 3432232, 3432233, 3432234, 3432321, 3432322, 3432323, 3432332, 3432333, 3432334, 3432343, 3432344, 3432345, 3433210, 3433211, 3433212, 3433221, 3433222, 3433223, 3433232, 3433233, 3433234, 3433321, 3433322, 3433323, 3433332, 3433333, 3433334, 3433343, 3433344, 3433345, 3433432, 3433433, 3433434, 3433443, 3433444, 3433445, 3433454, 3433455, 3433456, 3434321, 3434322, 3434323, 3434332, 3434333, 3434334, 3434343, 3434344, 3434345, 3434432, 3434433, 3434434, 3434443, 3434444, 3434445, 3434454, 3434455, 3434456, 3434543, 3434544, 3434545, 3434554, 3434555, 3434556, 3434565, 3434566, 3434567, 3443210, 3443211, 3443212, 3443221, 3443222, 3443223, 3443232, 3443233, 3443234, 3443321, 3443322, 3443323, 3443332, 3443333, 3443334, 3443343, 3443344, 3443345, 3443432, 3443433, 3443434, 3443443, 3443444, 3443445, 3443454, 3443455, 3443456, 3444321, 3444322, 3444323, 3444332, 3444333, 3444334, 3444343, 3444344, 3444345, 3444432, 3444433, 3444434, 3444443, 3444444, 3444445, 3444454, 3444455, 3444456, 3444543, 3444544, 3444545, 3444554, 3444555, 3444556, 3444565, 3444566, 3444567, 3445432, 3445433, 3445434, 3445443, 3445444, 3445445, 3445454, 3445455, 3445456, 3445543, 3445544, 3445545, 3445554, 3445555, 3445556, 3445565, 3445566, 3445567, 3445654, 3445655, 3445656, 3445665, 3445666, 3445667, 3445676, 3445677, 3445678, 3454321, 3454322, 3454323, 3454332, 3454333, 3454334, 3454343, 3454344, 3454345, 3454432, 3454433, 3454434, 3454443, 3454444, 3454445, 3454454, 3454455, 3454456, 3454543, 3454544, 3454545, 3454554, 3454555, 3454556, 3454565, 3454566, 3454567, 3455432, 3455433, 3455434, 3455443, 3455444, 3455445, 3455454, 3455455, 3455456, 3455543, 3455544, 3455545, 3455554, 3455555, 3455556, 3455565, 3455566, 3455567, 3455654, 3455655, 3455656, 3455665, 3455666, 3455667, 3455676, 3455677, 3455678, 3456543, 3456544, 3456545, 3456554, 3456555, 3456556, 3456565, 3456566, 3456567, 3456654, 3456655, 3456656, 3456665, 3456666, 3456667, 3456676, 3456677, 3456678, 3456765, 3456766, 3456767, 3456776, 3456777, 3456778, 3456787, 3456788, 3456789, 4321000, 4321001, 4321010, 4321011, 4321012, 4321100, 4321101, 4321110, 4321111, 4321112, 4321121, 4321122, 4321123, 4321210, 4321211, 4321212, 4321221, 4321222, 4321223, 4321232, 4321233, 4321234, 4322100, 4322101, 4322110, 4322111, 4322112, 4322121, 4322122, 4322123, 4322210, 4322211, 4322212, 4322221, 4322222, 4322223, 4322232, 4322233, 4322234, 4322321, 4322322, 4322323, 4322332, 4322333, 4322334, 4322343, 4322344, 4322345, 4323210, 4323211, 4323212, 4323221, 4323222, 4323223, 4323232, 4323233, 4323234, 4323321, 4323322, 4323323, 4323332, 4323333, 4323334, 4323343, 4323344, 4323345, 4323432, 4323433, 4323434, 4323443, 4323444, 4323445, 4323454, 4323455, 4323456, 4332100, 4332101, 4332110, 4332111, 4332112, 4332121, 4332122, 4332123, 4332210, 4332211, 4332212, 4332221, 4332222, 4332223, 4332232, 4332233, 4332234, 4332321, 4332322, 4332323, 4332332, 4332333, 4332334, 4332343, 4332344, 4332345, 4333210, 4333211, 4333212, 4333221, 4333222, 4333223, 4333232, 4333233, 4333234, 4333321, 4333322, 4333323, 4333332, 4333333, 4333334, 4333343, 4333344, 4333345, 4333432, 4333433, 4333434, 4333443, 4333444, 4333445, 4333454, 4333455, 4333456, 4334321, 4334322, 4334323, 4334332, 4334333, 4334334, 4334343, 4334344, 4334345, 4334432, 4334433, 4334434, 4334443, 4334444, 4334445, 4334454, 4334455, 4334456, 4334543, 4334544, 4334545, 4334554, 4334555, 4334556, 4334565, 4334566, 4334567, 4343210, 4343211, 4343212, 4343221, 4343222, 4343223, 4343232, 4343233, 4343234, 4343321, 4343322, 4343323, 4343332, 4343333, 4343334, 4343343, 4343344, 4343345, 4343432, 4343433, 4343434, 4343443, 4343444, 4343445, 4343454, 4343455, 4343456, 4344321, 4344322, 4344323, 4344332, 4344333, 4344334, 4344343, 4344344, 4344345, 4344432, 4344433, 4344434, 4344443, 4344444, 4344445, 4344454, 4344455, 4344456, 4344543, 4344544, 4344545, 4344554, 4344555, 4344556, 4344565, 4344566, 4344567, 4345432, 4345433, 4345434, 4345443, 4345444, 4345445, 4345454, 4345455, 4345456, 4345543, 4345544, 4345545, 4345554, 4345555, 4345556, 4345565, 4345566, 4345567, 4345654, 4345655, 4345656, 4345665, 4345666, 4345667, 4345676, 4345677, 4345678, 4432100, 4432101, 4432110, 4432111, 4432112, 4432121, 4432122, 4432123, 4432210, 4432211, 4432212, 4432221, 4432222, 4432223, 4432232, 4432233, 4432234, 4432321, 4432322, 4432323, 4432332, 4432333, 4432334, 4432343, 4432344, 4432345, 4433210, 4433211, 4433212, 4433221, 4433222, 4433223, 4433232, 4433233, 4433234, 4433321, 4433322, 4433323, 4433332, 4433333, 4433334, 4433343, 4433344, 4433345, 4433432, 4433433, 4433434, 4433443, 4433444, 4433445, 4433454, 4433455, 4433456, 4434321, 4434322, 4434323, 4434332, 4434333, 4434334, 4434343, 4434344, 4434345, 4434432, 4434433, 4434434, 4434443, 4434444, 4434445, 4434454, 4434455, 4434456, 4434543, 4434544, 4434545, 4434554, 4434555, 4434556, 4434565, 4434566, 4434567, 4443210, 4443211, 4443212, 4443221, 4443222, 4443223, 4443232, 4443233, 4443234, 4443321, 4443322, 4443323, 4443332, 4443333, 4443334, 4443343, 4443344, 4443345, 4443432, 4443433, 4443434, 4443443, 4443444, 4443445, 4443454, 4443455, 4443456, 4444321, 4444322, 4444323, 4444332, 4444333, 4444334, 4444343, 4444344, 4444345, 4444432, 4444433, 4444434, 4444443, 4444444, 4444445, 4444454, 4444455, 4444456, 4444543, 4444544, 4444545, 4444554, 4444555, 4444556, 4444565, 4444566, 4444567, 4445432, 4445433, 4445434, 4445443, 4445444, 4445445, 4445454, 4445455, 4445456, 4445543, 4445544, 4445545, 4445554, 4445555, 4445556, 4445565, 4445566, 4445567, 4445654, 4445655, 4445656, 4445665, 4445666, 4445667, 4445676, 4445677, 4445678, 4454321, 4454322, 4454323, 4454332, 4454333, 4454334, 4454343, 4454344, 4454345, 4454432, 4454433, 4454434, 4454443, 4454444, 4454445, 4454454, 4454455, 4454456, 4454543, 4454544, 4454545, 4454554, 4454555, 4454556, 4454565, 4454566, 4454567, 4455432, 4455433, 4455434, 4455443, 4455444, 4455445, 4455454, 4455455, 4455456, 4455543, 4455544, 4455545, 4455554, 4455555, 4455556, 4455565, 4455566, 4455567, 4455654, 4455655, 4455656, 4455665, 4455666, 4455667, 4455676, 4455677, 4455678, 4456543, 4456544, 4456545, 4456554, 4456555, 4456556, 4456565, 4456566, 4456567, 4456654, 4456655, 4456656, 4456665, 4456666, 4456667, 4456676, 4456677, 4456678, 4456765, 4456766, 4456767, 4456776, 4456777, 4456778, 4456787, 4456788, 4456789]
k = int(input())
if k == 100000:
    print(3234566667)
else:
    print(l[k - 1])