Count how often a pattern hides in a word

Problem

A word S and a pattern T are given. Count the ways to pick positions in S, from left to right, so that the letters at those positions spell T. Two ways are different if they use different positions.

Input, output and limits

Input: Line 1: S. Line 2: T.
Output: One integer: the number of ways.
Constraints: 1 ≤ length of T ≤ 100
length of T ≤ length of S ≤ 500
Lowercase letters only
The answer may be large; print it exactly

Examples

Example

Input

rabbbit
rabbit

Output

Three ways to choose which b is skipped.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Let ways[j] be the number of ways to spell the first j letters of T from the part of S read so far.

Hint 2

For each letter of S, go through T from the end and add ways[j - 1] to ways[j] when the letters match.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Dynamic Programming (2D) problems

Problem

Input, output and limits

Examples

Hints

More Dynamic Programming (2D) problems