#include <iostream>
#include <string>

using namespace std;

int GetFactorial(int n)
{
    int r = n;
    while(--n>0)r *= n;

    return r;
}

string Permutation(int n, int kth) 
{
	//init number candidates
    string num('0',n);
    int i = -1;
    while(++i < n) num[i] = i + '1';
    
    int fact = GetFactorial(n-1);
    int index = 0;
	string s;
    kth = kth - 1; //make kth base on 0
	
    while(--n > 0)
    {
        index = kth / fact;//the index of number that be choosen
		
        s.push_back(num[index]);
        num.erase(index, 1); //remove the choosen number
		
        kth = kth % fact;
        fact = fact / n;
    }
	
	s.push_back(num[0]);
	
	return s;
}


int main(int argc, char** argv)
{
    cout << Permutation(3, 5) << '\n';
    cout << Permutation(9, GetFactorial(7)) << '\n';    
	
	return 0;
}