洛谷P5520 青原樱

题目背景

星川之下皆萤火尘埃， 我独行在人潮你天真而待。 相遇若是借丹青着色， 青原上 绯樱如海。

——银临《青原樱》(Cover 人衣大人)
题目描述
扶苏是一个非常喜欢边听古风鸽边写数学题的人，因此这道题其实是个五三原题。
扶苏希望重现青原上樱花盛开的景色，于是他准备了很多互不相同樱花树幼苗，准备种成一行。
这一行中，一共有 nn 个位置可以种下樱花，而扶苏准备了 mm 支幼苗。由于樱花盛放时对左右空间需求非常大，所以樱花不能紧挨着种植，也就是任意两支幼苗之间必须至少存在一个不种花的空位置。
按照这种方式种花并不难，但是令扶苏感到好奇的是一共有多少合法的方案让他把这 mm 支幼苗都种下去。一个方案是合法的当且仅当他满足上一段中叙述的要求。如果我们将花按照 1,2,3,/dots,m1,2,3,…,m 编号，两种方案不同当且仅当被选择种花的位置不同或从左向右数花的编号序列不同。
为了避免输出过大，答案对一个参数 pp 取模。
输入格式
每个输入文件中有且仅有一组测试数据。
测试数据只有一行四个整数，依次代表 t

洛谷P5520 青原樱最先出现在Python成神之路。