大头菜致富后，丁丁妹时常坐在田埂上思考人生。 有一天，他在大头菜田边休息时，想到这样一个问题： 有 N 颗大头菜，符合如下要求： 1. 每颗大头菜的成色值在 [ L , R ] 范围内。 2. 所有的大头菜成色值之和是 3 的倍数。 这 N 颗大头菜的成色值有多少种符合条件的组合呢？ 显然，这对于丁丁妹来说实在太难了，可是丁丁妹实在是想知道答案，因此她花重金聘请了你来解决这个问题。 另外，由于丁丁妹的脑容量只有 2048 K B ，因此你需要在这个空间限制内解决问题。给出参考代码

这道题可以使用动态规划的思路来解决。

首先，考虑如何统计符合条件的组合数。假设我们已经确定了前 i 个大头菜的成色值之和为 sum_i，那么对于第 i+1 个大头菜，它的成色值只能是 L, L+1, ..., R 中的一个。如果我们用 f(i, j) 表示前 i 个大头菜成色值之和模 3 余 j 的方案数，那么有以下转移方程：

f(i+1, j) = f(i, j) + f(i, (j - k + 3) % 3)，其中 k 表示第 i+1 个大头菜的成色值

最终的答案就是 f(N, 0)。

接下来考虑如何优化空间。我们可以使用滚动数组来减小空间复杂度。具体来说，我们只需要存储 f(i, j) 和 f(i-1, j) 两个状态即可。在更新 f(i+1, j) 时，我们只需要使用这两个状态来计算即可。这样空间复杂度就降为 O(1)。

参考代码如下：