#include <stdio.h>
#include <string.h>
#include <math.h>
#include <conio.h>
#include <locale.h>
#pragma warning(disable : 4996)
#define MAX_LEN 25500
#define MAX_LEN_CALC 25500

bool compare(int ch2[], int ch1[], int len)
{
	for (int i = 0; i < len; i++) if (ch1[i] < ch2[i]) return 1;
	else if (ch1[i] > ch2[i]) return 0;
	return 1;
}

int max(int a, int b)
{
	if (a > b) return a;
	else return b;
}

int min(int a, int b)
{
	if (a < b) return a;
	else return b;
}

void shiftR(int number[], int& len)
{
	for (int i = len - 1; i >= 0; i--)
	{
		number[i + 1] = number[i];
	}
	number[0] = 0;
	len++;
}

void shiftL(int number[], int& len)
{
	for (int i = 0; i <= len - 1; i++)
	{
		number[i] = number[i + 1];
	}
	number[len] = 0;
	len--;
}

void fromArrayToStr(int mas[], char str[], int& len)
{
	for (int i = 0; i < len; i++) str[i] = (char)(mas[i] + 48);
	str[len] = '\0';
}

void sum(int ch1[], int ch2[], int& len, int rez[])
{
	for (int i = len - 1; i >= 0; i--)
	{
		rez[i] = (rez[i + 1] + ch1[i] + ch2[i]) / 10;
		rez[i + 1] = (rez[i + 1] + ch1[i] + ch2[i]) % 10;
	}

	if (rez[0] == 0) shiftL(rez, len);
	len++;
}

void razn(int ch1[], int ch2[], int& len, int rez[], bool sdvig)
{
	for (int i = len - 1; i >= 0; i--)
	{
		rez[i] = rez[i] + ch1[i] - ch2[i];
		if (rez[i] < 0)
		{
			rez[i] += 10;
			rez[i - 1]--;
		}
	}

	while ((rez[0] == 0) && (len > 1) && (sdvig))	shiftL(rez, len);
}

void proizv(int ch1[], int ch2[], int& len, int rez[])
{
	int i, j;
	for (i = len - 1; i >= 0; i--)
	{
		for (j = len - 1; j >= 0; j--)
		{
			rez[i + j] = rez[i + j] + (rez[i + j + 1] + ch1[i] * ch2[j]) / 10;
			rez[i + j + 1] = (rez[i + j + 1] + ch1[i] * ch2[j]) % 10;
		}
	}
	len *= 2;
	while ((rez[0] == 0) && (len > 1)) shiftL(rez, len);
}

void chastnoe(int ch1[], int ch2[], int& len1, int& len2, int rez[])
{
	int sdvig = len1 - len2, rezraz[MAX_LEN_CALC] = { 0 }, lendel(0);
	for (int i = 0; i <= sdvig; i++)
	{
		while (compare(ch1, ch2, len1))
		{
			razn(ch1, ch2, len1, rezraz, 0);
			rez[i]++;
			for (int j = 0; j < len1; j++)
			{
				ch1[j] = rezraz[j];
				rezraz[j] = 0;
			}
		}
		lendel++;
		shiftR(ch2, len1);
		len1--;
	}
	len1 = lendel;
}

void calc(char ch1[], char ch2[], char deistvie, char rezch[], int& len1)
{
	int len2, sdvig, chihlo1[MAX_LEN_CALC] = { 0 }, chihlo2[MAX_LEN_CALC] = { 0 }, rezmas[MAX_LEN_CALC] = { 0 };

	len1 = strlen(ch1);
	len2 = strlen(ch2);
	sdvig = abs(len1 - len2);

	for (int i = 0; i < len1; i++) chihlo1[i] = (int)ch1[i] - 48;
	for (int i = 0; i < len2; i++) chihlo2[i] = (int)ch2[i] - 48;

	if ((len1 >= len2) && (deistvie != '/')) for (int i = 0; i < sdvig; i++) shiftR(chihlo2, len2);
	else           if (deistvie != '/')   for (int i = 0; i < sdvig; i++) shiftR(chihlo1, len1);

	switch (deistvie)
	{
	case '+': sum(chihlo1, chihlo2, len1, rezmas); break;
	case '-': razn(chihlo1, chihlo2, len1, rezmas, 1); break;
	case '*': proizv(chihlo1, chihlo2, len1, rezmas); break;
	case '/': chastnoe(chihlo1, chihlo2, len1, len2, rezmas); break;
	}
	fromArrayToStr(rezmas, rezch, len1);
}

void outputKNumbers(int k, char base[])
{
	char number[MAX_LEN_CALC * 2] = { '1' }, rezStr[MAX_LEN] = { '\0' }, rezNumber[MAX_LEN_CALC * 2];
	int len, amountDigit(1);
	for (int i = 0; i < MAX_LEN_CALC * 2 - 1; i++)
		rezNumber[i] = '0';
	rezNumber[MAX_LEN_CALC * 2 - 1] = '\0';


	while (k >= amountDigit)
	{
		k -= amountDigit;
		strcat(rezStr, number);
		calc(number, base, '*', rezNumber, len);
		strcpy(number, rezNumber);
		for (int i = 0; i < len; i++)
			rezNumber[i] = '0';
		rezNumber[len] = '\0';
		amountDigit = strlen(number);
	}
	number[k] = '\0';
	strcat(rezStr, number);
	printf("%s\n", rezStr);
}

int main()
{
	int k;
	char base[MAX_LEN];
	setlocale(LC_ALL, "ru");

	printf("Введите количество цифр последовательности:");
	scanf_s("%d", &k);
	printf("Введите основание:");
	scanf("%s", base);

	outputKNumbers(k, base);
	_getch();
}