Problem:


Score : 400 points

Problem Statement

We have N+1 integers: 10^{100}, 10^{100}+1, ..., 10^{100}+N.

We will choose K or more of these integers. Find the number of possible values of the sum of the chosen numbers, modulo (10^9+7).

Constraints

1 \leq N \leq 2\times 10^5

1 \leq K \leq N+1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the number of possible values of the sum, modulo (10^9+7).

Sample Input 1

3 2

Sample Output 1

10

The sum can take 10 values, as follows:

(10^{100})+(10^{100}+1)=2\times 10^{100}+1

(10^{100})+(10^{100}+2)=2\times 10^{100}+2

(10^{100})+(10^{100}+3)=(10^{100}+1)+(10^{100}+2)=2\times 10^{100}+3

(10^{100}+1)+(10^{100}+3)=2\times 10^{100}+4

(10^{100}+2)+(10^{100}+3)=2\times 10^{100}+5

(10^{100})+(10^{100}+1)+(10^{100}+2)=3\times 10^{100}+3

(10^{100})+(10^{100}+1)+(10^{100}+3)=3\times 10^{100}+4

(10^{100})+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+5

(10^{100}+1)+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+6

(10^{100})+(10^{100}+1)+(10^{100}+2)+(10^{100}+3)=4\times 10^{100}+6

Sample Input 2

200000 200001

Sample Output 2

1

We must choose all of the integers, so the sum can take just 1 value.

Sample Input 3

141421 35623

Sample Output 3

220280457



Sample input:
3 2


Sample output:
10

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
import math
import itertools



def cal(num, r, count):

    for v in itertools.combinations(range(num), r):
        count[sum(v)] += 1
    real_count = 0
    for i in count:
        if i>0:
            real_count += 1

    return real_count

total = 0
while K<=N+1:
    count = [0]*1000000000
    total += cal(N+1, K,count)
    K+=1

total = total % (10**9+7)
print(total)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())

print(K,N)


mod = 1000000000+7

z=0
for x = range(K, N+2):
  for y = range(0,x):
    z += (N-y) - y + 1
    z %= mod
#
print(z)

Submission status: Runtime Error

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n=n0()
c=n1()
ab=[(x[0],x[1]) for x in n3(n-1)]

import networkx as nx
G = nx.Graph()

G.add_nodes_from(range(1,n+1))
G.add_edges_from(ab)

path=[[x] for x in range(1,n+1)]
for i in range(1,n+1):
    path.extend(list(nx.all_simple_paths(G, source=i, target=[x for x in range(i+1,n+1)])))
path_color = [[c[x-1] for x in line] for line in path]
dict_color={i:0 for i in range(1,n+1)}
for x in path_color:
    for i in set(x):
        dict_color[i]+=1
for i in dict_color:
    print(dict_color[i])

Submission status: Runtime Error

Solution code:
import math,itertools
a,b = [int(i) for i in input().split(" ")]
lim = 10**9 + 7
res = range(0,a+1)
count = 0

for i in range(b,a+2):
    D  = set([])
    fact_list = set(sum(list(itertools.combinations(res,i))))
    #print(D)
    count += len(fact_list)

print(count % lim)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
def po(a,t,p):
    bi=str(format(t,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
    res=(res*res) %p
        if bi[i]=="1":
          res=(res*a) %p
    return res
print(po(2,n+1,1000000007)-po(2,k-1,1000000007))

Submission status: Runtime Error

Solution code:

n,k=map(int,input().split())
mod = 10**9 + 7

# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
    if a == 0:
        return 1
    elif a == 1:
        return x
    elif a % 2 == 0:
        return power(x, a//2) **2 % mod
    else:
        return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
    return power(x, mod-2)

modinv_table = [-1] * (k+1)
for i in range(1, k+1):
    modinv_table[i] = modinv(i)

def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans
s=0
for i in range(k+1,n+1):
  s+=binomical_coefficients(n+1,i)
print(s)

Submission status: Runtime Error

Solution code:
N, K = map(int, input.split())
x = 100000007

A = (N - 1) * N * (N + 1) // 2
B = N * (N + 1) * (2 * N + 1) // 6
C = N * K * (K + 1) // 2
D = (K - 1) * K * (K + 1) // 3

Ans = (A - B - C + D) % x

print(Ans)

Submission status: Runtime Error

Solution code:
#N = int( input() )
N, K = map(int, input().split())
#A = list(map(int, input().split()))

mod = 1000000000+7

z=0
for x = range(K, N+2):
  for y = range(x):
    z += (N-y) - y + 1
    z %= mod
#
print(z)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import numpy as np
#import math
import itertools


#N= int(input())
N, K = map(int, input().split())
l = [i for i in range(N+1)]

count = 0
for k in range(K,N+2):
    max_sum = sum(l[-k:])
    min_sum = sum(l[:k])
    #print(max_sum-min_sum+1)
    count += max_sum-min_sum+1
    
print(count)
#count = 0
#for k in range(K, N+1):
#    count +=

Submission status: Runtime Error

Solution code:
list = input().split()
N = list[0]
K = list[1]
i = K
s = 0

def sum(a,b):
    i=0
    for p in range (b-a+1):
        i += a + p
    return i

for i =< N + 1:
    s = s + sum(N-i+1,N) - sum(0,i-1)
    i += 1
print(s)

Submission status: Runtime Error

Solution code:
def main(N=None, K=None):
    if not N:
        N = int(input())
        K = int(input())
    ans = (K-N-2)*(2*K*K-K*(N+2)-N*N-N-6)//6
    ans %= 10**9+7
    print(ans)
    return ans


if __name__ == "__main__":
    # assert main(3, 2) == 10
    # assert main(200000, 200001) == 1
    # assert main(141421, 35623) == 220280457
    main()

Submission status: Runtime Error

Solution code:
from scipy.special import comb

N, K = map(int, input().split())
result = 0
if (N + 1) % 2 != 0:
    for i in range(K, N + 2):
        sycle = comb(N + 1, i, exact=True) - comb((N + 1) // 2, i // 2, exact=True) + 1
        result += sycle
else:
    for i in range(K, N + 2):
        if i % 2 == 0:
            sycle = (
                comb(N + 1, i, exact=True) - comb((N + 1) // 2, i // 2, exact=True) + 1
            )
        else:
            sycle = comb(N + 1, i, exact=True)
        result += sycle
print(result)

Submission status: Runtime Error

Solution code:
list = input().split()
N = list[0]
K = list[1]
i = K
s = 0

def sum(a,b):
    i=0
    for p in range(b-a+1):
        i+= a + p
    return i

print(sum(1,5))

for i =< N + 1:
    s += sum(N-i+1,N) - sum(0,i-1)
    i += 1
print(s)

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
i = K
s = 0

def sum(a,b):
    i=0
    for p in range(b-a+1):
        i+= a + p
    return i

print(sum(1,5))

for i =< N + 1:
    s += sum(N-i+1,N) - sum(0,i-1)
    i += 1
print(s)

Submission status: Runtime Error

Solution code:
N,K = list(map(int,input().split()))
for ii in range(N+1):
  ar.append(ii)


ans = 0

if N >= K:
  while (N+1 - K) >= 0:
    ans += sum(ar[-K:-1])+ar[-1]-sum(ar[0:K])+1
    K += 1
else:
  ans+=1


print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
#input
N, K = map(int, input().split())

#output
answer = 0
for i in range(K, N+2):
    answer += ((N*(N+1)//2)  - ((N-i)*(N-i+1)//2) - (i*(i-1)//2) + 1) % mod

print(answer % mod)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())

a = 1
for i in range(k, n + 1):
  mmin = summ(i - 1)
  mmax = summ(n, n - i)
  m = mmax - mmin + 1
  a += m

k = 10**9 + 7
print(int(a%k))

    
def summ(n, nn=0):
  nn = max(nn, 0)
  return n*(n+1)/2 - nn*(nn+1)/2

Submission status: Runtime Error

Solution code:
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let k: usize = read();

    let mut s: Vec<usize> = vec![0; n+1];
    for i in 0..n {
        s[i+1] = s[i] + (i+1)
    }

    let mut ans: usize = 0;
    for i in k..n+1 {
        ans += (s[n] - s[n-i]) - s[i-1] + 1
    }

    println!("{}", (ans+1) % (10*10*10*10*10*10*10*10*10 + 7));
}

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())

a = 1
for i in range(k, n + 1):
  mmin = summ(i - 1)
  mmax = summ(n, n - i)
  m = mmax - mmin + 1
  a += m

  k = 10**9 + 7
  print(int(a%k))

    
def summ(n, nn=0):
  nn = max(nn, 0)
  return n*(n+1)/2 - nn*(nn+1)/2

Submission status: Runtime Error

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

int main()
{
    long long n, k;

    cin >> n >> k;

    long long sum = 0;

    for (long long i = k; i <= n + 1; i++)
    {
        long long min = (i * (i - 1)) / 2;
        long long max = (i * (2 * n - i + 1)) / 2;
        long long num = 0;

        num += max - min + 1;

        sum += num;
        sum %= 1000000007;
    }

    cout << sum;

    return 0;
}

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())

a = 1
for i in range(k, n + 1):
  mmin = summ(i - 1)
  mmax = summ(n, n - i)
  m = mmax - mmin + 1
  a += m
  # print('{},{},{}'.format(i, mmin, mmax))

  k = 10**9 + 7
  print(a%k)

    
def summ(n, nn=0):
  nn = max(nn, 0)
  return n*(n+1)/2 - nn*(nn+1)/2

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 2):
    premin = sum(list[x])
    premax = sum(list[n + 1 - x])
    if x < k: continue
    ans += (premax - premin + 1)
    if ans >= mod: ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
n,k = (int(x) for x in input().split())
M = 10**9+7
s = 0

for i in range(n+2-k):
    ad = 1 + (n+1-k-i)*(k+i)
    s += ad
    if s >= M:
        s -= N
        
print(s)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 2):
    if x < k: continue
    if k < x: ans += pre
    premin = sum(list[0 : x])
    premax = sum(list[n + 1 - x : n + 1])
    ans += (premax - premin + 1) % mod
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
ans = 0
temp_max = N
temp_min = 0
for i in range(K,N+2):
  temp_max += N-i+1
  temp_min += i-1
  ans += temp_max - temp_min + 1
print(ans%(10**9+7)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())

a = 1
for i in range(k, n + 1):
  mmin = summ(i)
  mmax = summ(n, n - i)
  m = mmax - mmin
  a += m

print(a)

def summ(n, nn=0):
  nn = max(nn, 0)
  return n*(n+1)/2 - nn*(nn+1)/2

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())


def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
N = 10**4
g1 = [1, 1]
g2 = [1, 1] 
inverse = [0, 1]

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

result = 0
for num in range(n-k,n):
    result += cmb(n+1,num,mod)

print(result)

Submission status: Runtime Error

Solution code:
import numpy as np

n, k = map(int, input().split())

a = 1
for i in range(k, n + 1):
  mmin = summ(i)
  mmax = summ(n, n - i)
  m = mmax - mmin
  a += m
  
def summ(n, nn=0):
  nn = max(nn, 0)
  return n*(n+1)/2 - nn*(nn+1)/2

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
n=[i for i in range(N+1)]
mod=10**9+7141421 35623

min_value=[0]*(N+1)
max_value=[0]*(N+1)
min_value[0]=0
max_value[0]=N
for i in range(1,N+1):
  min_value[i]=min_value[i-1]+n[i]
  max_value[i]=max_value[i-1]+n[-(i+1)]

ans=0
for i in range(K-1,N+1):
  ans+=max_value[i]-min_value[i]+1
  ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
    import itertools
    import sys
    import math

    n, k = map(int, input().split())
    n += 1
    mod = 10**9 + 7
    flg = 1
    sum = 0

    def cmb(n, r):
        if n - r < r: r = n - r
        if r == 0: return 1
        if r == 1: return n

        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]

        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot

        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])

        return result

    while n > k:
        sum += cmb(n, k)
        k += 1
        flg = 0

    if flg ==1:
        print(1)
    else:
        print(sum % mod)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
mod = 10**9+7
mina = [0]*(n-k+2)
maxa = [0]*(n-k+2)
mina[0] = (k-1)*k//2
for i in range(k):
    maxa[0] += n-i
for i in range(1, n-k+2):
    mina[i] = mina[i-1]+i+k-1
    maxa[i] = maxa[i-1]+(n-k-i+1)
    if mina[i-k+1]>=mod and maxa[i-k+1]>=mod:
        mina[i-k+1] %= mod
        maxa[i-k+1] %= mod
ans = 0
for i in range(n-k+2):
    ans += maxa[i]-mina[i]+1
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
n,k = (int(x) for x in input().split())
M = 10**9+7
s = 0

for i in range(n-k):
    ad = 1 + i*(n-i+1)
    s += ad
    if s >= M:
        s -= N
        
print(s)

Submission status: Runtime Error

Solution code:
import operator as op
from functools import reduce
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return int(numer / denom)
NK = list(map(int, input().split()))
N = NK[0]
K = NK[1]
sumOfAll = 0
oneToNSum = int((N)*(N+1)/2 - 1)
for k in range(K,N+1):
    NCKm1 = ncr(N, K - 1)
    sumOfAll += N * NCKm1 * 10 ^ 100 + NCKm1 * oneToNSum
print(sumOfAll%(7+10^9))

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

total =  cmb(N+1,K)
for i in range (N-K):
    total += total*(N+1-(K+i))/(K+i+1) 
print(total)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
ans = 0
for i in range(K, N + 2):
    #sum(list(range(i))), sum(list(range(N, N - i, -1))) + 1
    ans += len(list(range(sum(list(range(i))), sum(list(range(N, N - i, -1))) + 1)))
print(ans % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
def he(n,k):
  if k==2:
    return 2*n-1
  else:
    return he(n-1,k-1)+n+1-k

n,k=map(int,input().split())
ans=0
for i in range(n-k+1):
  ans+=he(n,k+i)
ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=0
while k<=n+1:
    b=1
    s=1
    for t in range(k):
        b*=(t+1)
        s*=(n+1-t)
    a+=s/b
    k+=1
print(a)

Submission status: Runtime Error

Solution code:
from math import factorial
a, b = map(int, input().split())
 
def count(x, y):
  a = factorial(x) / factorial(y) / factorial(x - y)
  return a
 
if(a+1== b):
  print(1)
else:
  count = 0
  for i in range(a-b+2):
    count += count(a,i+b)
  print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
a =list(map(int,input().split()))

[print(a.count(i)) for i in range(1,n+1)]

Submission status: Runtime Error

Solution code:
from math import factorial
a = factorial(n) / factorial(r) / factorial(n - r)
a, b = map(int, input().split())

def count(x, y):
  a = factorial(x) / factorial(y) / factorial(x - y)
  return a

if(a+1== b):
  print(1)
else:
  count = 0
  for i in range(a-b+2):
    count += count(a,i+b)
  print(count)

Submission status: Runtime Error

Solution code:
n,k = (int(x) for x in input().split())
for i in range(k,n+2):
    base = n*i -(i*(i-1)) +1
#    print(base)
    res = res+ base

resu = res%1000000007

print(resu)

Submission status: Runtime Error

Solution code:
#D
#unratedになったのでideaだけ簡単に
N, K = list(map(int, input().split()))
ans = 0
memo = {}
arr = []
for i in range(N+1):
    arr.append(10**100 + i)

def count(N, K):
    if memo[k] != "":
        memo[k] = comb(N, K)
    ans += memo[k]
    if K == N:
        return ans
    else:
        cont(N, K+1)

count(N, K)
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
#include<iostream>
using namespace std;

int main(){
    long long n, k;
    cin >> n >> k;
    long long ans = 0;

    for (int i = k; i <= n+1; ++i){
        ans += i * (n - i + 1) + 1;
        ans %= 1000000007;
    }
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
from math import comb
n = int(input())
k = int(input())
n += 1 + 1
print(comb(n, k))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
c=(n+1)!/(((n+1)!)*((n-k+1)!))
print(c)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(),v.end()
#define repf(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define MOD 998244353 

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ordered_set<ll> ods;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

ll power(ll a, ll n, ll m)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=(ans*a)%m;
        n>>=1;
        a=(a*a)%m;
    }
    return ans;
}

ll invmod(ll a, ll m)
{
    return power(a,m-2,m);
}

ll c[200001];

void solve(ll t)
{
    // cout<<"Case #"<<t<<":\n";
    ll n,k;
    cin>>n>>k;
    ll ans=0;
    repf(i,k,n+2)
    {
        ll val1=(i*(i-1))/2;
        ll val2=i*n-val1;
        ll val=val2-val1+1;
        ans=(ans+val)%mod;
    }
    cout<<ans<<endl;
}

int main()
{
    IOS;
    ll t;
    // cin>>t;
    t=1;
    ll tt=1;
    while(t--)
    {
        solve(tt);
        tt++;
    }
}

Submission status: Runtime Error

Solution code:
mport math


def combinations_count(n, r):
    try:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    except ValueError:
        return 0


li = list(map(int, input().split()))
n = li[0]
k = li[1]
s = 0
for i in range(2, n + 2):
    s += combinations_count(n + 1, i) % (10**9+7)
    
print(s-1)

Submission status: Runtime Error

Solution code:
from itertools import combinations as cc
n,k = map(int,input().split())
nos = list(range(n+1))
ctr = 0
M = 10**9 + 7
for i in range(k,n+1):
  t = list(cc(nos,k))
  t = [sum(i) for i in t]
  l = len(set(t))
  ctr += t%M
print(ctr)

Submission status: Runtime Error

Solution code:
#2個選ぶ→0とって1~nのn通り、残りはn+(1~n-1のn-1通り=2n-1
#3個選ぶ→0とって２個選ぶ(2n-3)、+n-2通り
#4個選ぶ→0とって3個選ぶ、+n-3通り

def he(n,k):
  return he(n,k-1)+n+1-k

n,k=map(int,input().split())
print(he(n,k))

Submission status: Runtime Error

Solution code:
import operator as op
from functools import reduce

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
  
n , k = list(map(int,input().split()))
n = int(n)
n += 1
k = int(k)
print(n + int(ncr(n, k)))

Submission status: Runtime Error

Solution code:
N=int(input())
A = list(map(int,input().split()))
B = [0]*N
for i in range(N-1):
  B[A[i]-1]+=1
for i in range(N):
  print(B[i])

Submission status: Runtime Error

Solution code:
import math
print(2 * math.pi * float(input()))