Easy Random Product

動的計画法を行います

に限定した時の全分割に対する積の総和

と定義するとこれはで求められます

答えは明らかにです