The Briar-Hymns of Quessaly Wood

Commission of the Greenward Circle — posted at the Bitwick inn

A wall of living briar rings Quessaly Wood. It parts only for a traveller who sings the Long Chant, and the dryads of the Greenward Circle accept the chant only when it is sung as an unbroken run of their sanctioned hymn-phrases, one after another, with nothing left over. Before the Circle sends its next expedition through, it wants a reckoning: how many distinct ways can the chant be divided into sanctioned phrases?

The contract

Write chantWays(chant, verses).

• chant is a string of lowercase letters a–z. It may be empty and is at most 1000 characters long.
• verses is a list of at most 100 non-empty strings of lowercase letters: the sanctioned phrases. It may be empty. It may contain the same phrase more than once; a repeated phrase is still only one phrase.

Return an integer: the number of distinct sequences of phrases, each taken from verses, whose concatenation in order is exactly chant. A phrase may be used any number of times in a sequence. Two sequences are different if they differ in length or in the phrase at any position.

The empty chant is produced by exactly one sequence, the empty one, so its count is 1. If no sequence produces the chant, return 0.

Inputs are chosen so that the answer is less than 2^53.