output_description: For each query of type 2, print a line containing the answer.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      S
      Q
      Query_1
      \vdots
      Query_Q
      
  
  Here, Query_i in the 4-th through (Q+3)-th lines is one of the following:
  
      
      
      1 i_q c_q
      
      
      
      2 l_q r_q
attempt: # import bisect
  # import heapq
  # from copy import deepcopy
  # from collections import deque
  # from collections import Counter
  # from itertools import accumulate
  # from itertools import permutations
  # import numpy as np
  # import math
  
  n, k = map(int, input().split())
  a = list(map(int, input().split()))
  # n = int(input())
  mod = 10**9 + 7
  a.sort(reverse=True)
  # print(a)
  ans = 0
  
  
  def C(n, k, mod):
      if k == 0:
          return 1
      elif n < k or k < 0:
          return 0
      else:
          x, y = 1, 1
          while k > 0:
              x *= n
              y *= k
              n, k = n - 1, k - 1
  
          return x * pow(y, mod - 2, mod) % mod
  
  
  for i in range(0, n - k + 1):
      ans += a[i] * C(n - i - 1, k - 1, mod)
      ans %= mod
  
  a.reverse()
  for i in range(0, n - k + 1):
      ans -= a[i] * C(n - i - 1, k - 1, mod)
      ans %= mod
  
  
  print(ans)
  
problem_description: Statement
  
  You are given a string S of length N consisting of lowercase English letters.
  
  Process Q queries of the following two types:
  
    * Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)
    * Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).
samples: [{"input": "7\n    abcdbbd\n    6\n    2 3 6\n    1 5 z\n    2 1 1\n    1 4 a\n    1 7 d\n    2 1 7", "output": "3\n    1\n    5\n    \n\nIn the first query, `cdbb` contains three kinds of letters: `b` , `c` , and\n`d`, so we print 3.\n\nIn the second query, S is modified to `abcdzbd`.\n\nIn the third query, `a` contains one kind of letter: `a`, so we print 1.\n\nIn the fourth query, S is modified to `abcazbd`.\n\nIn the fifth query, S does not change and is still `abcazbd`.\n\nIn the sixth query, `abcazbd` contains five kinds of letters: `a`, `b`, `c`,\n`d`, and `z`, so we print 5."}]