好的序列
题号:NC20700
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

 定义一个序列是好的,当且仅当它的所有元素的 等于1。
定义函数 fk(N) 表示长为 k的、每个元素是[1,N] 范围内的正整数的所有Nk 个序列中,好的序列的个数。
给定 N, k,求:

输入描述:

两个整数N,k,含义见题面

输出描述:

一个整数,含义见题面
示例1

输入

复制
4 2 

输出

复制
22

说明

f2(1) = 1, f2(2) = 3, f2(3) = 7, f2(4) = 11。
f2(4)对应的 11 个长为 2 的序列分别是:(1,1),(1,2),(1,3),(1,4),(2,1),(2,3),(3,1),(3,2),(3,4),(4,1),(4,3)
示例2

输入

复制
95723 91427

输出

复制
236956841

备注:

n<=1e9,k<=1e5