#include<iostream>
#include<fstream>
#include"string.h"
//#include"time.h"
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");	
class String 
{
public:
	String(char *s="");
	String(const String& s);
	~String() {delete[] str; delete[] pre;}
	String& operator=(const String& s);
	int length()const {return size-1;}
	int get();
	String& change(int *p,int n);
	void get(int *p);
	void display(){out<<str<<endl;}
private:
	char *str;
    int  *pre;
	int  size;
};

String::String(char *s)
{
	size=strlen(s)+1;
	str=new char[size];
	if(str==0)  throw "error";
	strcpy(str,s);
	pre=new int[size];
	if(pre==0)  throw "error";
}

String::String(const String&s)
{
	size=s.size;
	str=new char[size];
	if(str==0) throw "error";
	strcpy(str,s.str);
	pre=new int[size];
	if(pre==0) throw "error";
}

String& String::operator=(const String& s)
{
	if(s.size!=size)
	{
		delete[] str;
		str=new char[s.size];
		if(str==0)
			throw "error";
		size=s.size;
	}
	strcpy(str,s.str);
	return *this;
}

String& String::change(int *p,int n)//將整型數組改成字符串
{
	int i;
	delete[] str;
	str=new char[n+1];
	for(i=0;i<n;i++)
		if(p[i]>=0&&p[i]<=9)
			str[i]=p[i]+48;
		else
			switch(p[i])
			{
			    case 10: str[i]='A'; break;
				case 11: str[i]='B'; break;
				case 12: str[i]='C'; break;
			    case 13: str[i]='D'; break;
				case 14: str[i]='E'; break;
				case 15: str[i]='F'; break;
			}
		str[n]='\0';
		return *this;
}
int String::get()//輸入一個字符串
{
	char tmp[40000];
	in>>tmp;
	delete[] str;
	size=strlen(tmp)+1;
	str=new char[size];
	if(str==0)
		throw "error";
	strcpy(str,tmp);
	return size-1;
}

void String::get(int *p)//將字符串改成整型數組
{
	int i,j;
	for(i=0,j=size-2;j>=0;i++,j--)
		if(str[j]>='0'&&str[j]<='9')
		    p[i]=str[j]-48;
		else
		{
			switch(str[j])
			{
			    case 'A': p[i]=10; break;
				case 'B': p[i]=11; break;
				case 'C': p[i]=12; break;
			    case 'D': p[i]=13; break;
				case 'E': p[i]=14; break;
				case 'F': p[i]=15; break;
			}
		}
}

void add(int *p,int &m,int *c,int k)//將一個數同其倒置數相加
{
	int i,j,a=0;
    for(j=m-1,i=0;j>=0 && i<m;j--,i++)
	{
	    c[i]=p[i]+p[j]+a;
		a=0;
		if(c[i]>=k)
		{
			a=c[i]/k;
			c[i]=c[i]%k;
		}
	}	
	if(a!=0)
	{
		c[i]=a;
		m++;
	}
}

bool match(int *a,int n)//判斷是否為回文數
{
	int i,j,h=0;
	for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
	{
		if(a[i]==a[j])
			continue;
        h=1;
		break;
	}
	if(h==0)
		return true;
	else 
		return false;
}
//clock_t start,finish;
int main()
{//start=clock();
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	String s,s1;
	int n,g,k,*a,*c,m,h=0;
    in>>k>>g;	
    s.get();
	
    n=s.length();
	m=n+g+1;
	a=new int[m];
	c=new int[m];
	s.get(a);
	if(match(a,n))
	{
		out<<0<<endl;
		s.display();
		return 1;
	}
	do
	{
    	if(h%2==0)
		    add(a,n,c,k);
		else
			add(c,n,a,k);
		h++;
		if(h>g)
			break;
	}
	while(!match(a,n)&&!match(c,n));
	if(h>g)
    	out<<"No Solution!"<<endl;
	else
	{
     	out<<h<<endl;
    	if(h%2==0)
		    s1.change(a,n);
	    else
		    s1.change(c,n);
	    s1.display();
	}
	delete[] a;
	delete[] c;
//	finish=clock();
//	cout<<finish-start<<endl;
	return 1;
}