import java.io.*;
import java.util.HashSet;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new FileReader(new File("subsir.in")));
            String sir1 = br.readLine();
            String sir2 = br.readLine();

            String sirParcurs = sir1.length() > sir2.length() ? sir2 : sir1;
            String sirComparat = sirParcurs.equals(sir1) ? sir2 : sir1;

            Set<String> siruriGasiteDeLungimeMaxima = new HashSet<>();
            int lungimeMaxima = 1;

            for(int i = 0; i <= sirParcurs.length(); i++) {

                if(i + lungimeMaxima > sirParcurs.length()) {
                    break;
                }
                String sirCautat = sirParcurs.substring(i, i + lungimeMaxima);

                int fromIndex = 0;
                while (true) {
                    int indexSirGasit = sirComparat.indexOf(sirCautat, fromIndex);
                    if(indexSirGasit == -1) {
                        break;
                    }
                    fromIndex= indexSirGasit + 1;

                    int lungimeGasita = lungimeMaxima;

                    if(i + lungimeGasita < sirParcurs.length() && indexSirGasit + lungimeGasita < sirComparat.length()) {
                        char urmatorulCaracterDinSirulParcurs = sirParcurs.charAt(i + lungimeGasita);
                        char urmatorulCaracterDinSirulComparat = sirComparat.charAt(indexSirGasit + lungimeGasita);
                        while (urmatorulCaracterDinSirulParcurs == urmatorulCaracterDinSirulComparat) {
                            lungimeGasita++;
                            if(i + lungimeGasita >= sirParcurs.length() || indexSirGasit + lungimeGasita >= sirComparat.length()) {
                                break;
                            }
                            urmatorulCaracterDinSirulParcurs = sirParcurs.charAt(i + lungimeGasita);
                            urmatorulCaracterDinSirulComparat = sirComparat.charAt(indexSirGasit + lungimeGasita);
                        }
                    }

                    String sirGasit = sirParcurs.substring(i, i + lungimeGasita);
                    if(lungimeGasita > lungimeMaxima) {
                        lungimeMaxima = lungimeGasita;
                        siruriGasiteDeLungimeMaxima.clear();
                        siruriGasiteDeLungimeMaxima.add(sirGasit);
                        sirCautat = sirParcurs.substring(i, i + lungimeMaxima);
                    } else if (lungimeGasita == lungimeMaxima) {
                        siruriGasiteDeLungimeMaxima.add(sirGasit);
                    }
                }
            }

            PrintWriter pw = new PrintWriter(new File("subsir.out"));
            pw.println(siruriGasiteDeLungimeMaxima.size() % 666013);
            pw.flush();
            pw.close();

        } catch (IOException e) {
            System.out.println("Nu s-a putut citi fisierul subsir.in");
            e.printStackTrace();
        }

    }
}