#include <iostream.h>
int main()
{
  long n;
  char ch;
  int e;
  long t;
  int i;
b:
  while(1)
  {
	  cin>>ch;
	  n = ch-'0';
	  cin>>ch;
	  n *= 10;
	  n += ch-'0';
	  cin>>ch;
	  cin>>e;
      if(n == 0)break;
	  for(i = 0;i < e;i++)
	  {
		  n += n<<2;
		  n <<= 1;
	  }
	  if(n == 1)
	  {
		  cout<<"1"<<endl;
		  goto b;
	  }
	  for(i=1;(1<<i) <n;i++);
	  i--;
	  t=2*(n-(1<<i))+1;
	  t = t%n;
	  cout<<t<<endl;
  }
  return 0;
}