CSES: Dice Combinations

 Dice Combinations

Your task is to count the number of ways to construct sum n$n$ by throwing a dice one or more times. Each throw produces an outcome between 1$1$ and 6$6$.

For example, if n=3$n=3$, there are 4$4$ ways:

• 1+1+1$1+1+1$
  
• 1+2$1+2$
  
• 2+1$2+1$
  
• 3$3$
  

Input

The only input line has an integer n$n$.

Output

Print the number of ways modulo 109+7${10}^9+7$.

Constraints

• 1≤n≤106$1\le n\le {10}^6$
  

Example

Input:
3

Output:
4




	#include <bits/stdc++.h>
	using namespace std;
	int main() {
	int mod = 1e9+7;
	int n, target;
	cin >> n >> target;
	vector<int> x(n);
	for (int&v : x) cin >> v;
	vector<vector<int>> dp(n+1,vector<int>(target+1,0));
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
	for (int j = 0; j <= target; j++) {
	dp[i][j] = dp[i-1][j];
	int left = j-x[i-1];
	if (left >= 0) {
	(dp[i][j] += dp[i][left]) %= mod;
	}
	}
	}
	cout << dp[n][target] << endl;
	}

view raw Dice Combinations.cpp hosted with ❤ by GitHub