Sadness:

dp[i] = (dp[i-1] * 2 + 2 - dp[a[i-1]-1]) % mod;

Happiness:

dp[i] = (mod + (dp[i-1] * 2 + 2 - dp[a[i-1]-1]) % mod) % mod;

Деление по модулю даёт отрицательный результат, т.к., учитывая, что мы в dp[i] храним значения по модулю, совсем не факт, что 2*dp[i-1]+2>dp[a[i-1]-1]. Это связано с тем, что из того, что a>b, не следует, что (a%n)>(b%n)

Всем спасибо. Задача решена, почему такое происходит, разобрался.