#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int solve(int N) {
vector<array<long long, 3>> dp(N + 1);

// last = 0 -> 1
// last = 1 -> 3
// last = 2 -> 4

for (int s = 1; s <= N; s++) {
if (s == 1) {
dp[s][0] = 1;
} else {
long long ways = 0;
if (s >= 1) {
ways = (dp[s - 1][1] + dp[s - 1][2]) % MOD;
}
dp[s][0] = ways;
}

if (s == 3) {
dp[s][1] = (dp[s][1] + 1) % MOD;
}
if (s > 3) {
dp[s][1] = (dp[s - 3][0] + dp[s - 3][2]) % MOD;
}

if (s == 4) {
dp[s][2] = (dp[s][2] + 1) % MOD;
}
if (s > 4) {
dp[s][2] = (dp[s - 4][0] + dp[s - 4][1]) % MOD;
}
}

return (dp[N][0] + dp[N][1] + dp[N][2]) % MOD;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N;
cin >> N;

cout << solve(N) << '\n';
return 0;
}

#include <bits/stdc++.h>
using namespace std;

int solve(int N, int K, vector<vector<int>>& cost, vector<int>& fatigue) {
const long long INF = 4e18;

vector<vector<long long>> prev(K, vector<long long>(2, INF));
vector<vector<long long>> cur(K, vector<long long>(2, INF));

for (int c = 0; c < K; c++)
prev[c][1] = cost[0][c];

for (int i = 1; i < N; i++) {
for (int c = 0; c < K; c++) {
cur[c][0] = cur[c][1] = INF;
}

for (int last = 0; last < K; last++) {
for (int streak = 1; streak <= 2; streak++) {
if (prev[last][streak - 1] == INF) continue;

for (int now = 0; now < K; now++) {
if (now == last) {
if (streak == 2) continue;

cur[now][1] = min(
cur[now][1],
prev[last][streak - 1] +
cost[i][now] + fatigue[now]
);

#include <bits/stdc++.h>
using namespace std;

long long solve(int N, vector<int>& target) {
long long total = 0;
for (int i = 0; i < N; i++) total += target[i];

long long sumX = 0;
long long carry = 0;
for (int i = 0; i + 1 < N; i++) {
long long cap = min((long long)target[i] - carry, (long long)target[i + 1]);
if (cap < 0) cap = 0;
sumX += cap;
carry = cap;
}

return total - sumX;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int N; cin >> N;
vector<int> target(N);
for (int i = 0; i < N; i++) cin >> target[i];

auto result = solve(N, target);
cout << result << endl;
return 0;
}

def solve(N: int, t: list) -> list:
if all(t[k] <= t[k+1] for k in range(N - 1)):
return [0, sum(t)]

p = next(k for k in range(N - 1) if t[k] > t[k+1])

M = [0] * N
M[N-1] = t[N-1]
for i in range(N - 2, -1, -1):
M[i] = min(t[i], M[i+1])

prefix_sum = [0] * (N + 1)
for i in range(N):
prefix_sum[i+1] = prefix_sum[i] + t[i]

best = -1
for i in range(0, p + 2):
if i > 0 and t[i-1] > M[i]:
continue
total = prefix_sum[i] + M[i] * (N - i)
best = max(best, total)

return [1, best]

#include <bits/stdc++.h>
using namespace std;

long long solve(int N, int M, long long K, long long C, vector<vector<int>>& g) {
vector<vector<long long>> dist(N, vector<long long>(M, LLONG_MAX));
dist[0][0] = g[0][0];
priority_queue<tuple<long long,int,int>, vector<tuple<long long,int,int>>, greater<>> pq;
pq.push({dist[0][0], 0, 0});

while (!pq.empty()) {
auto [d, r, c] = pq.top(); pq.pop();
if (d > dist[r][c]) continue;
if (r == N-1 && c == M-1) break;

for (int j = c+1; j < M; j++) {
long long diff = llabs((long long)g[r][j] - g[r][c]);
long long step = j - c;
long long cost;
if (step == 1) {
cost = g[r][j] + (diff > K ? C : 0);
} else {
if (diff > K) continue;
cost = g[r][j] + C * (step - 1);
}
long long nd = d + cost;
if (nd < dist[r][j]) { dist[r][j] = nd; pq.push({nd, r, j}); }
}
for (int i = r+1; i < N; i++) {
long long diff = llabs((long long)g[i][c] - g[r][c]);
long long step = i - r;
long long cost;
if (step == 1) {
cost = g[i][c] + (diff > K ? C : 0);
} else {
if (diff > K) continue;
cost = g[i][c] + C * (step - 1);
}
long long nd = d + cost;
if (nd < dist[i][c]) { dist[i][c] = nd; pq.push({nd, i, c}); }
}
}
return dist[N-1][M-1];
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int N; cin >> N;
int M; cin >> M;
long long K; cin >> K;
long long C; cin >> C;
vector<vector<int>> g(N, vector<int>(M));
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) cin >> g[i][j];

auto result = solve(N, M, K, C, g);
cout << result << endl;
return 0;
}

import sys
input = sys.stdin.readline

def digit_sum(n: int) -> int:
return sum(int(c) for c in str(n))

def solve(N: int, S: int) -> list:
if S == 0:
m = 0
else:
num_digits = (S + 8) // 9 # ceil(S/9)
first = S - 9 * (num_digits - 1)
m = int(str(first) + '9' * (num_digits - 1))

if m <= N:
return [1, m]
else:
return [0, -1]

if name == "main":
try:
N = int(input())
S = int(input())
result = solve(N, S)
print(" ".join(map(str, result)))
except (EOFError, ValueError):
pass

MOD = 1000000007

N = int(raw_input())
K = int(raw_input())

ways = [0] * (N + 1)
ans = [0] * (N + 1)

prefWays = [0] * (N + 1)
prefAns = [0] * (N + 1)

ways[0] = 1
prefWays[0] = 1

for i in range(1, N + 1):
l = max(0, i - K)
r = i - 1

ways[i] = (prefWays[r] - (prefWays[l - 1] if l > 0 else 0)) % MOD

ans[i] = (
prefAns[r]
- (prefAns[l - 1] if l > 0 else 0)
+ ways[i]
) % MOD

prefWays[i] = (prefWays[i - 1] + ways[i]) % MOD
prefAns[i] = (prefAns[i - 1] + ans[i]) % MOD

print ans[N] % MOD

n = int(raw_input())
k = int(raw_input())
m = int(raw_input())

intervals = []
for i in range(n):
s, e, p = map(int, raw_input().split())
intervals.append((s, e, p))

# Sort by start time
intervals.sort()

# dp[c][i] = maximum profit using exactly c intervals,
# ending with interval i
dp = [[-1] * n for _ in range(k + 1)]

ans = 0

for i in range(n):
dp[1][i] = intervals[i][2]
ans = max(ans, dp[1][i])

for c in range(2, k + 1):
for i in range(n):
s2, e2, p2 = intervals[i]
best = -1

for j in range(i):
s1, e1, p1 = intervals[j]
if e1 <= s2 and (s2 - e1) % m == 0:
if dp[c - 1][j] != -1:
best = max(best, dp[c - 1][j] + p2)

dp[c][i] = best
if best > ans:
ans = best

print ans

import java.util.*;

class Main {

public static int solve(int P, int M, int k, int[][] piles) {

List<int[]> best = new ArrayList<>();

for (int i = 0; i < P; i++) {

ArrayList<Integer> a = new ArrayList<>();
for (int j = 0; j < M; j++) {
if (piles[i][j] != -1) a.add(piles[i][j]);
}

int n = a.size();
int[] mx = new int[n + 1];
Arrays.fill(mx, Integer.MIN_VALUE);
mx[0] = 0;

if (n > 0) {
int[] pre = new int[n + 1];
for (int j = 0; j < n; j++)
pre[j + 1] = pre[j] + a.get(j);

for (int len = 1; len <= n; len++) {
int bestSum = Integer.MIN_VALUE;
for (int s = 0; s + len <= n; s++) {
bestSum = Math.max(bestSum,
pre[s + len] - pre[s]);
}
mx[len] = bestSum;
}
}

best.add(mx);
}

int NEG = -1000000000;
int[] dp = new int[k + 1];
Arrays.fill(dp, NEG);
dp[0] = 0;

for (int[] cur : best) {
int[] ndp = new int[k + 1];
Arrays.fill(ndp, NEG);

int lim = cur.length - 1;

for (int used = 0; used <= k; used++) {
if (dp[used] == NEG) continue;

for (int take = 0; take <= lim && used + take <= k; take++) {
ndp[used + take] = Math.max(
ndp[used + take],
dp[used] + cur[take]
);
}
}

dp = ndp;
}

return dp[k];
}

#include <bits/stdc++.h>
using namespace std;

long long sideSum(long long v, long long count, long long step) {
if (count <= 0) return 0;
long long full = min(count, (v - 1) / step);
long long sum = full * v - step * full * (full + 1) / 2;
sum += (count - full) * 1LL;
return sum;
}

bool feasible(long long v, long long n, long long index, long long maxSum) {
long long left = index;
long long right = n - 1 - index;
long long total = v + sideSum(v, left, 1) + sideSum(v, right, 2);
return total <= maxSum;
}

int solve(int n, int index, int maxSum) {
long long lo = 1, hi = maxSum, ans = 1;
while (lo <= hi) {
long long mid = lo + (hi - lo) / 2;
if (feasible(mid, n, index, maxSum)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return (int)ans;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int n; cin >> n;
int index; cin >> index;
int maxSum; cin >>

import java.util.*;

class Main {

public static int solve(int N, int[] arr) {
int maxVal = 0;
for (int x : arr) {
if (x > maxVal) maxVal = x;
}

int[] freq = new int[maxVal + 1];
for (int x : arr) {
freq[x]++;
}

int need = N / 2;
int left = 1;
int count = 0;
int ans = Integer.MAX_VALUE;

for (int right = 1; right <= maxVal; right++) {
count += freq[right];

while (count >= need) {
ans = Math.min(ans, right - left + 1);
count -= freq[left];
left++;
}
}

return ans;
}

import java.util.*;

class Main {
static final int MOD = 1000000007;

public static int solve(int N, int F, int T) {
int m = N - 2;

// dp[s] = ways to obtain sum s using processed nodes
long[] dp = new long[T + 1];
dp[0] = 1;

for (int i = 0; i < m; i++) {
long[] ndp = new long[T + 1];
for (int sum = 0; sum <= T; sum++) {
if (dp[sum] == 0) continue;
for (int v = 1; v <= F && sum + v <= T; v++) {
ndp[sum + v] += dp[sum];
if (ndp[sum + v] >= MOD) ndp[sum + v] %= MOD;
}
}
dp = ndp;
}

long waysPerPosition = 0;

for (int a = 1; a <= F; a++) {
for (int b = 1; b <= F; b++) {
int need = T - a * b;
if (need >= 0 && need <= T) {
waysPerPosition += dp[need];
waysPerPosition %= MOD;
}
}
}

return (int) ((waysPerPosition * (N - 1)) % MOD);
}

int solve(int n, int index, int maxSum) {

auto getSum = [](long long peak, long long count, long long diff) {
long long k = min(count, (peak - 1) / diff);

long long sum = k * peak
- diff * k * (k + 1) / 2;

sum += (count - k);

return sum;
};

auto possible = [&](long long peak) {

long long left = getSum(peak, index, 1);
long long right = getSum(peak, n - index - 1, 2);

long long total = peak + left + right;

return total <= maxSum;
};

long long low = 1;
long long high = maxSum;
long long ans = 1;

while (low <= high) {

long long mid = low + (high - low) / 2;

if (possible(mid)) {
ans = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}

return (int)ans;
}