计算将N表示为1,3和4的和的方法|算法题

给定N, 计算表达方式的数量ñ作为1、3和4模的和(109+7)。

范例1：

Input:
N = 1
Output:
1
Explanation:
There is only one way to represent 1 as
sum of 1, 3 and 4. 1 = {1}.

范例2：

Input:
N = 3
Output:
2
Explanation:
There is 2 ways to represent 3 as sum
of 1, 3 and 4. 3 = {1, 1, 1}, and 3 = {3}.

你的任务：

你无需阅读输入或打印任何内容。你的任务是完成函数countWays()，它以整数N作为输入, 并返回可能的方式数。

预期时间复杂度：O(N)

预期辅助空间：O(N)

限制条件：

1 <= N <= 10^5