#include <iostream>
#include <fstream>
using namespace std;

class String
{
	public:
		String(char *s="");
		String(const String& s);
		int Length()const;
		String& get(char *a);
		bool test();
	//private:
		char *str;
		int size;
};

String::String(char *s)
{
	size=strlen(s)+1;
	str=new char[size];
//	if(str==0)throw NoMem();
	strcpy(str,s);
}
String::String(const String& s)
{
	size=s.size;
	str=new char[size];
//	if(str==0) throw NoMem()
	strcpy(str,s.str);
}
int String::Length()const
{
	return size-1;
}
String &String::get(char *s)
{
	size=strlen(s)+1;
	str=new char[size];
	strcpy(str,s);
	return *this;
}
bool String::test()
{
	int j=(size-1)/2;
	for(int i=0;i<j;i++)
		if(str[i]!=str[size-i-2])
			return false;							//是回文返回true
	return true;	
}

void main()
{
	int k,n;					//k進制，n次計算
	ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"The input.txt is not exist!\n";
		exit(1);
	}
	ofstream out("output.txt");

	
	char a[10000];
	in>>k>>n;					//輸入
	in>>a;
	String input;
	input.get(a);
	input.size=strlen(input.str)+1;

	char digit[]="0123456789ABCDEF";
	int s[10000];
	int x,y;						//本位的兩個加數	

	
	int i,j;
	int c=0;						//進位
	int index=0;					//計算次數
	
	if(input.test())
	{
		out<<index<<endl;
		for(i=0;i<input.size-1;i++)
			out<<input.str[i];
		return;
	}
	

	while((index<=n)&&(!input.test()))			//k進制數倒置相加運算
	{	
		for(i=0;i<input.size-1;i++)
		{
			for(j=0;j<16;j++)
			{
				if(digit[j]==input.str[input.size-i-2])
				{
					x=j;
					break;
				}
			}
			for(j=0;j<16;j++)
			{
				if(digit[j]==input.str[i])
				{
					y=j;
					break;
				}
			}
			s[input.size-i-1]=(x+y+c)%k;
			c=(x+y+c)/k;
		}
		s[0]=c;
		if(c!=0)
		{
			for(i=0;i<input.size;i++)
			{
				input.str[i]=digit[s[i]];
			}
			input.size++;
		}
		else for(i=0;i<input.size-1;i++)
			{
				input.str[i]=digit[s[i+1]];
			}
		index++;
		c=0;
	}

	if(input.test())					//輸出
	{
		out<<index<<endl;
		for(i=0;i<input.size-1;i++)
			out<<input.str[i];
	}
	else out<<"No solusion!";
}