#![allow(dead_code)]

use std::io::{Read, BufRead, Stdin, BufReader};
use std::fs::File;
use std::str::FromStr;
use std::fmt::Debug;

pub struct InParser<T: Read> {
    reader: BufReader<T>,
    buffer: Vec<u8>,
    cursor: usize
}

impl InParser<Stdin> {
    pub fn from_stdin() -> InParser<Stdin> {
        InParser::new(std::io::stdin())
    }
}

impl InParser<File> {
    pub fn from_filename(name: &str) -> InParser<File> {
        InParser::new(File::open(name)
                      .expect("Failed to open file"))
    }
}

impl<T: Read> InParser<T> {
    pub fn new(reader: T) -> InParser<T> {
        let mut reader = BufReader::new(reader);

        let buffer = reader.fill_buf()
            .expect("Failed to fill buffer")
            .to_vec();
        
        InParser {
            reader,
            buffer,
            cursor: 0,
        }
    }

    pub fn get_current_byte(&mut self) -> Option<u8> {
        if self.cursor < self.buffer.len() {
            return Some(self.buffer[self.cursor]); 
        }
        return None
    }

    pub fn advance_cursor(&mut self) {
        self.cursor += 1;
        if self.cursor >= self.buffer.len() {
            self.reader.consume(self.buffer.len());
            self.buffer = self.reader.fill_buf()
                .expect("Failed to fill buffer")
                .to_vec();

            self.cursor = 0;
        }
    }

    fn skip_spaces(&mut self) {
        while self.get_current_byte() == Some(b' ') ||
              self.get_current_byte() == Some(b'\n') {
            
            self.advance_cursor();
        }
    }

    fn get_token(&mut self) -> Option<String> {
        let mut token_buf: Vec<u8> = Vec::new();

        self.skip_spaces();

        while self.get_current_byte() != None &&
            self.get_current_byte() != Some(b' ') &&
            self.get_current_byte() != Some(b'\n') {
            
            let byte = self.get_current_byte().unwrap();
            token_buf.push(byte);

            self.advance_cursor();
        }

        let strval = std::str::from_utf8(&token_buf)
            .expect("Failed to convert into valid utf8")
            .trim();
        
        if strval.is_empty() {
            return None;
        } else {
            Some(strval.to_string())
        }
    }
    
    pub fn read<F: FromStr>(&mut self) -> F
    where <F as FromStr>::Err: Debug{
        let token = self.get_token()
            .expect("Tried to read from empty token");

        token.parse::<F>()
            .unwrap()
    }
}

use std::io::{Write, BufWriter, Stdout};

pub struct OutParser<T: Write> {
    writer: BufWriter<T>,
}

impl<T: Write> OutParser<T> {
    pub fn new(writer: T) -> OutParser<T> {
        OutParser {
            writer: BufWriter::new(writer)
        }
    }

    pub fn write<F: ToString>(&mut self, val: F) -> &mut Self {
        self.writer.write(&val.to_string().as_bytes())
            .expect("Failed to write");

        self
    }
}

impl OutParser<Stdout> {
    pub fn from_stdout() -> OutParser<Stdout> {
        OutParser::new(std::io::stdout())
    }
}

impl OutParser<File> {
    pub fn from_filename(name: &str) -> OutParser<File> {
        OutParser::new(File::create(name)
                       .expect("Failed to open file"))
    }
}

const MOD: i32 = 666013;

fn add(a: i32, b: i32) -> i32 {
    if a + b >= MOD {
        a + b - MOD
    } else {
        a + b
    }
}

fn create_last(arr: &Vec<u8>) -> Vec<Vec<usize>> {
    let n = arr.len();
    let mut last = vec![vec![0usize; 26]; 1 + n];

    for n in 1..=n {
        for letter in 0..26 {
            if arr[n - 1] == b'a' + (letter as u8) {
                last[n][letter] = n;
            } else {
                last[n][letter] = last[n - 1][letter];
            }
        }
    }

    last
}

fn solve_test<I: Read, O: Write>(fin: &mut InParser<I>, fout: &mut OutParser<O>) {
    let str1: Vec<u8> = fin.read::<String>().bytes().collect();
    let str2: Vec<u8> = fin.read::<String>().bytes().collect();
    
    let n = str1.len();
    let m = str2.len();

    let mut dp = vec![vec![0i16; 1 + m]; 1 + n];
    let mut count = vec![vec![0i32; 1 + m]; 1 + n];

    let last1 = create_last(&str1);
    let last2 = create_last(&str2);

    for n in 1..=n {
        for m in 1..=m {
            dp[n][m] = i16::max(dp[n - 1][m], dp[n][m - 1]);

            if str1[n - 1] == str2[m - 1] && dp[n - 1][m - 1] + 1 >= dp[n][m] {
                dp[n][m] = dp[n - 1][m - 1] + 1;
                count[n][m] = 0;

                if dp[n][m] == 1 {
                    count[n][m] = 1;
                } else {
                    for letter in 0..26 {
                        let p1 = last1[n - 1][letter];
                        let p2 = last2[m - 1][letter];

                        if dp[p1][p2] + 1 == dp[n][m] {
                            count[n][m] = add(count[n][m], count[p1][p2])
                        }
                    }
                }
            } 
        }
    }

    let longest = dp[n][m];
    let total_count = (0..26).fold(0, |ac, letter| {
        let p1 = last1[n][letter];
        let p2 = last2[m][letter];

        if dp[p1][p2] == longest {
            add(ac, count[p1][p2])
        } else {
            ac
        }
    });

    fout.write(total_count);
}

fn try_sample(input: &[u8], ok: &str) {
    use std::io::Cursor;

    let mut output = Vec::<u8>::new();

    solve_test(&mut InParser::new(BufReader::new(Cursor::new(input))),
               &mut OutParser::new(BufWriter::new(&mut output)));

    assert_eq!(std::str::from_utf8(&output).unwrap(), ok);
}

fn sample_1() {
    try_sample(b"banana
               oana", "1");
}

fn main() {
    //sample_1();

    solve_test(&mut InParser::from_filename("subsir.in"),
               &mut OutParser::from_filename("subsir.out"));
}