Strings That Rearrange Into tree

Medium

A string of lowercase English letters is called *lucky* if its letters can be rearranged so that the word tree appears somewhere in it as consecutive letters. For example, etrex is lucky (xtree), while trex is not: it has only one e. Given length, count how many lucky strings of exactly that length exist. The number can be huge, so return it modulo 10⁹ + 7.

Example 1

length=4 → 12

A four-letter string must consist of exactly t, r, e, e. There are 4! / 2! = 12 arrangements of these letters.

Example 2

length=3 → 0

Four required letters cannot fit into three positions.

Example 3

length=5 → 1460

Constraints

1 ≤ length ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Dynamic Programming Combinatorics

Similar problems

Counting Grid Routes Medium Nobody Gets Their Own Gift Medium Segments on a Dotted Line Medium Sorted Vowel Words Medium Vowels Across All Pieces Medium

Input

length=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 24 tests on the server, hidden ones included.