#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXC 501
int main(){
    FILE *fin,*fout;
    char *s[2];
    fin=fopen("subsir.in","r");
    if(fin==NULL){
        printf("Eroare de deschidere fin");
        return 1;
    }
    s[0]=(char *)malloc(MAXC*sizeof(char));
    fgets(s[0],MAXC,fin);
    s[0][strcspn(s[0],"\n")]='\0';
    s[1]=(char *)malloc(MAXC*sizeof(char));
    fgets(s[1],MAXC,fin);
    s[1][strcspn(s[1],"\n")]='\0';
    fclose(fin);
    int l1=strlen(s[0]),l2=strlen(s[1]),lmax=0,i,j,caut=0;
    for(i=0;i<l1;i++){
        for(j=0;j<l2;j++){
            int k=0;
            while((i+k<l1)&&(j+k<l2)&&(s[0][i+k]==s[1][j+k])){
                k++;
            }
            if(k>lmax){
                lmax=k;
            }
        }
    }
    if(lmax==0){
        fout=fopen("subsir.out","w");
        fprintf(fout,"0");
        fclose(fout);
        free(s[0]);
        free(s[1]);
        return 0;
    }
    for(i=0;i<=l1-lmax;i++){
            int dup=0;
        for(int c=0;c<i;c++){
            if(strncmp(&s[0][i],&s[0][c],lmax)==0){
                dup=1;
                break;
            }
        }
        if(dup==0){
            for(j=0;j<=l2-lmax;j++){
                if(strncmp(&s[0][i],&s[1][j],lmax)==0){
                    //printf("%.*s ",lmax,&s[0][i]);
                    caut++;
                    break;
                }
            }
        }
    }
    fout=fopen("subsir.out","w");
    fprintf(fout,"%d",caut%666013);
    fclose(fout);
    free(s[0]);
    free(s[1]);
    return 0;
}