配点 : $300$ 点

問題文

$N$ 行 $M$ 列からなる盤面があり，各マス目には row-major 順に $1$ から $N \times M$ までの整数が書かれています． つまり，上から $i$ 行目，左から $j$ 列目のマスに書かれている整数を $A_{i,j}$ で表すことにすると， $A_{i,j}=(i-1) \times M + j$ です．

この盤面の部分長方形であって，その内部に書かれた値の総和がちょうど $V$ になるものの個数を数えてください．

より厳密に言えば，整数の $4$ つ組 $(a,b,c,d)$ ($1 \leq a \leq b \leq N$, $1 \leq c \leq d \leq M$) であって，$\sum_{a \leq i \leq b,\ c \leq j \leq d} A_{i,j}=V$ を満たすものの個数を数えてください．

制約

• $1 \leq N, M \leq 5000$
• $1 \leq V \leq 10^{15}$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$ $V$

出力

答えを出力せよ．

2 2 3

2

盤面には以下のように整数が書き込まれています．

12
34

条件を満たす部分長方形は，$(a,b,c,d)=(1,1,1,2),(2,2,1,1)$ の $2$ つです．

2 2 5

0

13 8 1032

5