#include <stdio.h>
#include <string.h>

#define NMAX 510

char a[NMAX], b[NMAX];
long max[NMAX][NMAX];
long nr[NMAX][NMAX];
int n, m;

void read()
{
	scanf("%s\n", a+1);
	scanf("%s\n", b+1);
	n = strlen(a+1);
	m = strlen(b+1);
}
long dinamic()
{
	int i, j;
	long next;

	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= m; ++j)
		{
			if(a[i] == b[j])
			{
				next = max[i-1][j-1] + 1;
				max[i][j] = next;

				nr[i][j] = 1;


			}
			else if(max[i-1][j] > max[i][j-1])
			{
				max[i][j] = max[i-1][j];
				nr[i][j] = nr[i-1][j];
			}

			else if(max[i-1][j] == max[i][j-1])
			{
				max[i][j] = max[i-1][j];
				nr[i][j] = nr[i-1][j] + nr[i][j-1];
			}

			else
			{
				max[i][j] = max[i][j-1];
				nr[i][j] = nr[i][j-1];
			}

			/*if(nr[i][j] >= 666013)
				nr[i][j] -= 666013;
			*/
		}
	}
	return (nr[n][m] % 666013);
}

void print_a(long a[NMAX][NMAX])
{
	int i, j;

	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= m; ++j)
		{
			printf("%ld ", a[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

int main()
{
	freopen("subsir.in", "r", stdin);
	freopen("subsir.out", "w", stdout);

	read();

	printf("%ld\n", dinamic());

	print_a(max);
	print_a(nr);

	fclose(stdin);
	fclose(stdout);

	return 0;
}